Raven Checkers released

I published my first public version (0.3) of Raven Checkers to Google Code a few weeks ago. It has been a fun adventure to develop a cross-platform checkers game engine and GUI in Python.

Some interesting items about Raven from a development standpoint:

• One or two player mode, plus an "autoplay" feature that pits the AI engine against itself.
• Cross-platform Tkinter GUI with model-view-controller (MVC) architecture.
• Undo and redo move feature.
  
• AI opponent uses a standard alpha-beta search algorithm which runs in a background process (using the 2.6 multiprocessing library) with a customizable "think time".
• Board Setup allows you to configure the pieces on the checkerboard, set the number of players, and select which player goes next.
• Flip Board allows you to rotate the board 180 degrees to view pieces from either Black or White's perspective.
  

As I've mentioned in a previous post, my success in developing Raven owes a lot to Martin Fierz and Peter Norvig, who developed the evaluation function and search code that are used inside the game. Thanks to both of you for making your code open-source so that others could learn from and build on it.

My future plans for Raven involve taking it in a different direction than a typical game engine. Most checkers or chess programs go the route of deep search combined with perfect opening and endgame databases. These techniques are well-explored and not really all that interesting to me. I plan on making a big change in future versions of Raven by relying more on planning than brute-force search. Since Python is not a high performance language, it's encouragement to make Raven work smarter, not harder.

Here's my to-do list so far:

• Implement a hierarchical task network (HTN) planner that will devise opening themes and endgame strategies. These plans will be based on tactics and endings from Richard Pask's books Starting Out in Checkers and Play Better Checkers & Draughts, which I use in my own checkers study. The architecture of the planner will be very similar to the one used for Bridge Baron, featured in Chapter 23 of the book Automated Planning.
• Add a transposition table and some move ordering to help with alpha-beta search depth. (I will probably make use of the transposition table code in PyChess or Chesstools.) Despite my preference for using the planner, I would like to be able to fall back on good search for the early- and late-midgame when play becomes a bit more muddled.
• Add a save/load game feature, along with some way of annotating different moves in the game. (My thoughts on the "annotation" feature are a little fuzzy, but it's something I want for checkers study.)
• Make the undo and redo work correctly with the background AI processing. Right now, Raven doesn't stop its search if an undo/redo is executed, and it should.
• Create some official distributions so a user doesn't have to checkout the code themselves or require Python to be installed on their system. (Although listed last, this is really something I will likely tackle first, so more folks can enjoy Raven.)

There is plenty here, but I'm not in a hurry. This is just a fun side project. I have the vague idea that I'd like to get most of the features above (certainly the planner and its knowledge base) implemented within a year, so I could give a presentation at PyCon 2010. Seems like a good goal to keep in view.

A checkers game

I've made a couple different attempts before to write a Checkers program in Python, but for various reasons, the project stalled. This time, I've been quietly working on it behind the scenes, and last night I played my moves against an intelligent computer player. Some reasons why I had success this time around:

1. Using existing open-source code as a reference. Before I was trying to do everything myself from scratch. Sometimes this can be useful for learning purposes, but in some cases it can just be an exceptionally bad use of time. Now I'm taking a look at code that other people have written and reusing it where I can. For instance, Martin Fierz's Simple Checkers has a good, basic evaluation function that I've been able to use, and Peter Norvig's elegant Python implementation of minimax would be hard to improve upon. There's enough other interesting challenges in trying to develop my program -- there's no need to waste time doing wheel reinvention.
   
2. Testing. This is the first time I've worked on a personal project where I felt unit testing while I developed was an absolute necessity. (Although I did test-after, not test-driven development. Sorry, agile folks.) I always do testing in the Python shell, but it's somewhat informal. This time it was formal. Checkers has a number of rules about moves/jumps that are important to get right, and almost every test I wrote uncovered a bug or a subtle problem with my data structures. Thumbs up for unit tests.
   
3. Focusing on the logic, not the GUI. Before I was developing my checkers GUI in tandem with the game model. Now I'm concentrating on getting the logic right first, and my initial "GUI" is simply an ASCII representation of the checkerboard. In the past, with too many pieces of code changing at the same time I was getting overwhelmed, especially when trying to refactor. Focusing on the GUI is seductive but is ultimately the wrong use of time early in the project.

In regards to #2 above, the focus on unit testing has also continued to drive the development of my Komodo extension, kNose, which is also very positive. I'm working on updating the extension to use nose 0.10.1 and its much improved support for plugins. (And in another major milestone, kNose is now hosted on google-code and has a new project member, Christoph Zwerschke, who's been a huge help.)

Once my Checkers game is released, I'd also like to donate it back to the AIMA project as an example of what can be done with community code.