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.

Movie blog

From the number of subscribers at Bloglines, it doesn't look like too many people know that Roger Ebert has a blog. His latest post is about the new Indiana Jones movie, which sounds like it's worth seeing.

kNose 1.1.1 released

This release of kNose updates the extension to work with Komodo 4.3 and nose 0.10.1.

It also fixes a problem with the interaction of certain directory paths when running nosetests. Also, I include a message and tooltip for when kNose can't find any unit tests in your project. The tooltip specifies the environment variables and arguments passed to the subprocess module, so it should be easier to debug specific problems with any user's system.




For those who don't know, kNose is a Python unit testing extension for Komodo Edit. It is a GUI frontend for the excellent nose framework written by Jason Pellerin.

Happenings at PyCon

My friend Steven is busy preparing for his Django talk at this year's PyCon. In his spare time, he's also taking shots of the conference and twittering his experiences. He shares:

The geek thing this year is the eeepc -- I've seen at least 5 or 6 already tonight.

I was unable to attend the conference, but I'm monitoring Planet Python to keep track of the goings-on. Maybe next year!

The Impatient Developer's Guide to Nose Plugins

Eric Promislow of ActiveState has been working with the nose unit-testing framework in order to hook it into the new version of Komodo IDE. Along the way he figured out how to write a nose plugin, and he's documented his work in this article. (Poor Eric misspelled my name as Brendan, but otherwise it's a great article! ;D )

I'm working hard right now on a game, but this information is cool enough that I could be persuaded to update kNose to use a nose plugin like Eric describes. However, Komodo 4.3 could very well obsolete my work. Are there enough kNose users out there that would like to see an update, or would you rather wait for the next version of Komodo and its unit testing support?

Pygame bookmark rollup

I've found a bunch of Pygame-related bookmarks lately that I thought I'd post. These don't seem to be all widely linked, so maybe they'll be useful for other Python game programmers out there.

• Chapters 5 (Making Things Move) and 7 (Take Me To Your Leader) of Will McGugan's Beginning Game Development with Python and Pygame. Personally, I find chapter 5 to be the most valuable of Will's book.
• pyMunk, a wrapper around the Chipmunk 2D gaming physics library.
• A couple versions of Pygame main loops: Simon Wittber's mainloop and Hectigo's Splush.
• Pygsear, a higher-level Pygame framework that takes care of much of the lower level setup of sprites and events and objects.
• Pygame Extended and Rabbyt, both 2D sprite library add-ons to Pygame that use OpenGL acceleration.
• Python Game Kit, plenty of .egg files that contain useful Pygame utilities and addons.
  

Something I hate about Python's re module

UPDATE: I've gotten a couple comments about this, and both seem to illustrate (with varying degrees of tact) that my complaint wasn't all that clear. My problem with the re module is this: Python's documentation for the re.match function is match(pattern, string, [flags]) where pattern can be either a regex string or a compiled regex object. If it's a compiled regex object, then supplying an optional flag to re.match (in my case, re.IGNORECASE) doesn't work and, more to the point, fails silently. I think this should throw an exception if it's not going to work. However, I really think that it should work the way I've illustrated, because, IMO, it's the most natural way to use the API.

----
I've been burned at least three separate times by the following problem: I'll start out with a simple uncompiled regex for testing and then switch over to a compiled regex. Suddenly, the whole thing stops working.

Here's an example of what I'm doing below. (Example taken from O'Reilly's Regular Expression Pocket Reference by Tony Stubblebine.)

import re
dailybugle = r'Spider-Man Menaces City!'
pattern = r'spider[- ]?man.'
if re.match(pattern, dailybugle, re.IGNORECASE):
    print dailybugle

This prints out 'Spider-Man Menaces City!' as expected. So now I want to compile the regular expression now for speed. I change the code to look like this:

import re
dailybugle = r'Spider-Man Menaces City!'
pattern = re.compile(r'spider[- ]?man.')
if re.match(pattern, dailybugle, re.IGNORECASE):
    print dailybugle

Looks simple, right? I just surrounded the pattern string with a call to re.compile(). Unfortunately, the whole thing now quietly fails. What the ... ? Take the re.compile out, it starts working again.

The solution is to move the re.IGNORECASE flag into the re.compile call, like so:

import re
dailybugle = r'Spider-Man Menaces City!'
pattern = re.compile(r'spider[- ]?man.', re.IGNORECASE)
if re.match(pattern, dailybugle):
    print dailybugle


In my opinion, this solution is very unintuitive and requires more rejiggering of the code than it should. But even worse is that in my first attempt to use a compiled regex, re.match can receive a re.IGNORECASE flag that it subsequently disregards. This type of call should throw an exception, in my opinion.

Anyone know a reason for this bad (and seemingly buggy) behavior?