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.

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?

kNose 1.0 released

kNose is a free Komodo IDE/Edit extension for Python unit testing; it uses the nose unit testing framework written by Jason Pellerin.

kNose is available for download here, along with documentation I've provided on how to install and use it.

Hope you enjoy it!

A quick kNose update

Sorry, I promised to keep everyone updated, and I haven't been doing that.

I've finished working on expanding and collapsing the tree view and running tests in a background thread. I'm currently writing the code to display tooltips in the tree for any tests that had failures/errors. It's been hard to find out how to do this, because it's very hard to google for "tooltip treeview XUL" (and other combinations thereof) and get any meaningful results. However, I finally found some sample code to look at, and I'm hoping this doesn't take me very long.

I've noticed some small bugs in my parsing of nose's output results, and I also need to save some of the treeview settings inside of Komodo's preferences. Both of these "to do" items, however, are fairly insignificant.

My plan is to release it by the end of this week.

kNose extension under development

For about a month, I've been quietly developing another Komodo Edit/IDE extension called kNose. It's a GUI front-end for the nose unit testing framework for Python written by Jason Pellerin. I wanted something that would make it easy for me to jump into testing as part of my normal development. Despite the cool nature of auto-discovery and execution of unit tests with nose, I'm still too lazy to use it if it's not integrated with my IDE.

Here's a screenshot of how things look so far for the curious:


Yes, that's a red bar to indicate that some of the tests didn't pass. The auto-test feature, when checked, will run the tests each time a file is saved in the editor. When auto-test is unchecked, then the Run Tests button will kick off the unit tests manually.

Basically, my remaining to-do list is as follows:

1. make the tree nodes expandable and collapsible,
2. handle error reporting properly (whatever that means I haven't decided ... hover over a node to see a tooltip? ... double-click to get a dialog with the error message? I'll probably try both and see which style I like.)
3. run nose in a background thread so that it doesn't freeze up Komodo while the tests are running.
   
4. test on both Linux and Windows to see that things check out. (I'll be looking for a volunteer with a Mac as I get closer to release.)
   

The last, detail stages of the project always seem to be the hardest, so I'm posting to encourage myself to "press on toward the goal". Also, I was curious if other Pythonistas in the testing community would be interested in my extension.

It will probably be another two to three weeks before I finish since this is definitely a part-time project. I'll keep everyone posted.

Komodo Hacks: Improving Python Help in Windows

This last hack for the week beefs up the context-sensitive help for Python in Komodo. By default, the Shift-F1 help in Komodo does a Google site search on docs.python.org for the current word under the cursor. I prefer instead to use the HTMLHelp manual that comes with my standard Python installation since it's often much faster and efficient than a web search.

You can download my Python Help macro here. It brings up your local Python reference with an HTMLHelp API call, with the current word under the cursor placed in the Index tab. Simple but effective.

Notes:

• This Help macro remaps the F1 key to bring up the Python manual instead of bringing up Komodo's internal help, since I use language help much more than IDE help. You can always change this in the macro Properties if you're used to Shift-F1 instead.
• You should also check the macro code to make sure that the local of my Python installation (c:\python24) matches yours, or you'll need to change it.
  

I've got more ideas percolating but they'll have to wait until another week! Hope these hacks make your work with Komodo and Python more enjoyable.

Komodo Hacks: Integrating Pylint

UPDATE: Todd left a comment on how he didn't like Pylint's verbosity. You can add a -e option to the command line to show errors only instead of stylistic warnings.

UPDATE: I see this hack has already been covered by John and Mateusz.

I'm not enjoying today's hack as much as I'd like. Pylint is great, but getting it installed and configured is much more painful than it should be. For one thing, Logilab has configured a .egg file for Pylint so that you can ostensibly use easy_install to get it on your system -- but the .egg doesn't load any of the other dependencies that are needed. Very frustrating. Consequently, we'll go about the install process manually. I'm writing the steps below from a Windows perspective, but I've tried to note where a Unix install is slightly different.

How to get PyLint installed and configured for Komodo:

1. Download Pylint and the Pylint dependency modules from Logilab's site: logilab-common and logilab-astng. The download links are in the upper-left corner of the page.
2. Extract all the packages from step 1, preserving the folder structure. WinZip is the best for this on a Windows system; if you have a Unix-based OS, you can use gunzip -c [MODULE].tar.gz | tar -xf - or similar.
3. Open up a command prompt, make sure your Python executable can be found in your PATH, and type python setup.py install inside the extracted common, astng, and pylint directories in turn.
4. Change to your Python installation's scripts directory.
5. Type pylint --generate-rcfile > standard.rc at the command prompt to create a Pylint configuration file. (If you're using a Unix system, you'll need to prefix the pylint command with a ./ )

Now you're ready to download Run Pylint macro here. Install it into Komodo by using the Import Package option under the Toolbox menu.

Additional configuration is needed to set up the macro for your system:

1. Right-click on the Pylint macro in the toolbox and click Properties.
2. Change the path to pylint in the Command text box to match the location of your python installation's scripts directory. Also, if you're using a Unix system, you'll probably need to remove the quotes around the %F in the text box as well. (Can someone verify this for me?)
   
3. Change both the directory paths in the Environment Settings list to match the location of your Python installation as well.
   

Usage notes:

• Double-clicking on the Pylint macro in the toolbox will run pylint on the currently viewed file and print a report in the Command Output tab. Each line in the report can be double-clicked, and Komodo will jump to the matching line in the file.
• The standard.rc file that was generated in step 5 above can be edited to customize the types of errors/warnings that Pylint will generate. The .rc file is commented thoroughly so you should be able to figure out what's going on with a little study and experimentation. As an alternative, pylint can also be customized with command-line parameters; type pylint (by itself) at a command prompt to see all the different possibilities.

Tomorrow's hack: beefing up context-sensitive help for Python under Windows.

Komodo Hacks: Rename Occurrences

This Komodo hack allows you to rename all occurrences of a variable or method name wherever it appears in your code. This is the last of my macros this week that uses Bicycle Repair Man; if you missed my previous post on how to get the BRM package into Komodo, it can be found here.

You can download the macro here. Install it into Komodo by using the Import Package option under the Toolbox menu.

Usage notes:

• Highlight a variable or method in your code and double-click on the Rename macro in the toolbox. The macro will prompt you for the new variable or method name and then perform the rename operation.
• Before refactoring, Komodo will prompt you to save your file if necessary. (This is a requirement of BRM.)
• After refactoring, Komodo will tell you that your file or files have changed and prompt you to reload them. Go ahead! You should see your changes in the updated file(s). If you don't like what you see, you can Undo the changes, via the Edit menu or CTRL-Z.
• Rename Occurrences may not always work like you expect. As an example, you'll want to rename method names where they are originally defined; otherwise, the renaming will only be local and not propagate throughout your code.
  

Tomorrow's hack: integrating PyLint into Komodo.

Komodo Hacks: Extract Method

Today's hack allows you to highlight a section of existing Python code in Komodo and refactor it into its own separate method.

Like yesterday's hack, Extract Method uses Bicycle Repair Man for its functionality. If you didn't catch the procedure for including the BRM package into Komodo, see my last post.

You can download the macro here. Install it into Komodo by using the Import Package option under the Toolbox menu.

Usage notes:

• Just highlight a section of code, and double-click on the Extract Method macro in the toolbox. The macro will prompt you for the name of the new method and then perform the refactoring operation.
  
• Before refactoring, Komodo will prompt you to save your file if necessary. (This is a requirement of BRM.)
• After refactoring, Komodo will tell you that your file has changed and prompt you to reload it. Go ahead! You should see your changes in the updated file. If you don't like what you see, you can Undo the changes, via the Edit menu or CTRL-Z.
  

One more BRM macro to go, coming tomorrow!

Komodo Hacks: Find References

UPDATE: Trent Mick posted a simpler method for getting the BRM package into Komodo. I've modified my original procedure below to include his suggestion.

Komodo is my favorite Python IDE. Since ActiveState has recently released their new Komodo 4.0, I've decided to publish a full week of Komodo Toolbox commands and macros that should prove useful for Python developers. (Note that I'm primarily a Windows user, but most of these commands/macros will be able to be used on other platforms as well with little or no modification.)

I'm starting off the hacks with a "Find References" macro that compliments the new "Go To Definition" feature in the latest Komodo. The idea is to be able to highlight a variable or method in your Python code and then double-click Find References in the toolbox to see all uses of that variable/method throughout your code.

I use the Bicycle Repair Man (BRM) refactoring tool, written by Phil Dawes, to implement this macro. That means the first order of business is to install BRM into Komodo's Python directory so that the module can be called from within a macro.

How to install Bicycle Repair Man into Komodo:

1. Download the BRM nightly build. I used the bicyclerepair-nightly.tar.gz.tmp file dated October 9, 2006. Rename this file to bicyclerepair-nightly.tar. (I know it looks like a gzipped file, but trust me, it's really a TAR file.)
   
2. Extract the build into a convenient directory. WinZip is one of the easiest Windows tools to do this. On a Unix platform, you can use tar xvf bicyclerepair-nightly.tar
3. Put a "bike.pth" text file in [komodo-install-dir]/lib/mozilla/python. This file should contain the path to the bicyclerepair source directory. For example, if you had extracted the bicyclerepair folder to the root of your C: drive, your "bike.pth" would contain the single line "c:\bicyclerepair". (Again, I'm sure the Unix users can figure out how this would look on their system.)
   
4. Re-start Komodo for it to pick up on the new .pth file.
   

Now you're ready to load the Find References macro into your Komodo IDE or Komodo Edit 4.0. Use the Import Package option under the Toolbox menu to load the findreferences.kpz file into Komodo.

The usage is pretty simple: highlight a variable or method in your code and then double-click the Find References entry in the Toolbox. The macro will scan your code for a second or two (or longer depending on the length of your code and the number of imports) and then output the results in the Command Output tab. You can then double-click on any line in the output to jump to the corresponding location in the code.

A few items of note:

• Find References may not work like you expect in certain cases; for example, when finding references for a class instance variable like 'self.foo', just highlight 'foo' - don't include the 'self.' prefix.
  
• Due to a limitation of Komodo's Python macros, Find References has to use a 'helper' Run Command to populate the Command Output tab. I placed this Run Command inside a separate 'Helper Commands' folder to keep it out of the way; make sure you don't change it or delete it by mistake.
  

Thanks to Shane Caraveo, Trent Mick, and Jeff Griffiths of ActiveState for helping me out with these hacks. Stay tuned for more Komodo posts through the rest of the week!

Asteroid Smash released!

Asteroid Smash is a version of the classic game Asteroids in Pygame. You can find it here. It's packaged in an installer for Windows. All the source code is included in a subdirectory.

Let me just say py2exe is incredibly underdocumented. But here are helpful links if you see "Zlib not available" or "Runtime error: default font not found" when packaging your own game.

Asteroids, part 5

Clearly I missed my Christmas deadline. I shot past my revised estimate too, which was New Year's Day. Right now I'm shooting for the end of the week, if possible.

My list of priorities has changed. The game is essentially finished, without any additional features like power-ups or additional enemies. I completed the high-score screens and fixed a bunch of little bugs that kept showing up at odd times during the game. I also added scaling, so that the game would look correct at almost any (reasonable) resolution.

Currently I'm working on the game configuration dialog. This will allow the user to select a screen resolution and customize their key controls. I'm doing it in wxPython using the fantastic VisualWx GUI builder (and once again wishing it was combined with Komodo or Wing). I was going to try it in Tkinter until I remembered that it has no combo box controls without the Pmw add-on, and wxPython is probably simpler to deploy anyway.

My final task is to write an installer for the game. I've heard lots of good things about the freeware Inno Setup program and its related utilities, so I'm going to try that. My game setup is certainly not complicated, so it will mostly involve just deploying Python, and the wxPython and pygame libraries (and perhaps psyco, I haven't decided).

There's also code cleanup and comments to do still, but I may save that for later. I'm trying not to push the release back any further, plus it's not that important until I write my accompanying "game development" article.

Abstract methods in Python

Following up one of my previous posts, I've been looking at code from Pygame Extended to get ideas for a Scene class to use with my Asteroids game. I'm requiring derived classes to override a process_events function in my Scene class, since each scene will need its own event loop.

In this case, it thought it would be good to have a way to specify that process_events was an abstract method. I guess I hadn't thought about abstract methods too much before in Python since I don't typically use inheritance, but I knew there wasn't anything like the notion of interfaces built into the language itself.

I started looking through the Python Cookbook for ideas and came across this article. Yikes! I wasn't sure I wanted to bother with metaclasses just for this feature. But in the comments I saw that someone else suggested raising an exception in the base class so that calling the method at runtime would fail unless there was an override.

I slapped my forehead after reading the Cookbook comment. Of course, in hindsight, it was obvious. But apparently it isn't obvious to other folks either. The pygext source code simply uses empty methods like the following:

class Foo(object):
   def update(self):
      pass # Override me in derived class

Of course, you can't distinguish pure virtual methods from regular virtual methods this way.

Even some very respectable folks have solved this problem differently: Peter Norvig, when writing his Python code for his Artificial Intelligence book, uses a made-up keyword called "abstract" which fails at runtime if it hasn't been overridden in a derived class. Not the most elegant solution either.

I really think handling abstract methods should be done at object creation like the previously mentioned Cookbook recipe does, but it should be built into Python itself. This may be one of the reasons people think OOP in Python is a hack ...

Nifty Python idiom?

While writing my game, I've been using Python lists to keep track of things on the screen like laser shots and asteroids. On-screen objects typically have limited lifetimes and then get deleted from their associated list. This leads to code that looks something like the following.

import random

class Foo(object):
   def __init__(self):
      self.time = random.randint(1, 100)

   def update(self):
      self.time -= 1

lst = [Foo() for x in range(5)]
while lst:
   delete_lst = []
   for i, x in enumerate(lst):
      x.update()
      if x.time == 0:
         delete_lst.append(i)
   for i in reversed(delete_lst):
      del lst[i]
print "Done!"

To summarize what's going on, a list of 5 Foo objects gets created, each with random time values, and added to a list. After that, a loop is started that calls .update() on each Foo that decrements its .time variable by 1. Once the time value reaches zero, then the object is deleted from the list.

This is clumsy. I can't delete items while I'm iterating through the list, or I'll invalidate the iterator. So I have to keep track of the index of which items need to be deleted, and then actually delete them in a second loop. Also, I have to delete the items in reverse order, or I'll throw off the indexes and delete the wrong items.

I've written code like this several times when working with vectors in C++. So it's familiar, but writing it in Python makes me almost wince.

I felt sure that I should be able to improve this code with a list comprehension, but until this morning, I couldn't see how. But sometimes the drive to work gives me some clarity.

Here's the improved list comprehension version:
import random
class Foo(object):
   def __init__(self):
      self.time = random.randint(1, 100)

   def update(self):
      self.time -= 1
      return self.time > 0

lst = [Foo() for x in range(5)]
while lst:
   lst = [x for x in lst if x.update()]
print "Done!"

Whew - that's so much nicer. The list comprehension updates all items in the list every time through the loop while automatically filtering out the ones that have a time value of zero.

There is the disadvantage of constantly generating additional lists each time through the loop, but since I don't have many objects to manage, I think the code reduction (and resulting clarity) outweighs the performance hit in this scenario.

Of course, other Python gurus probably already know about this trick, but I felt proud of myself for figuring it out.

UPDATE -- It would be nice to post this idiom to the Python Cookbook, but I'm a little baffled as to what to call it. Suggestions?

Asteroids, part 4

I've been creating increasingly complicated code to handle timed game events and multiple event loops. This has prompted me to look at Pygame Extended, which has a few nice classes (Director, Reactor, Ticker, Scene) to handle these sorts of things. Unfortunately, the author has tied them in to the OpenGL portions of the library as well, making it hard to reuse. I think I'm going to extract the portions I need (or at least the ideas) for my own game.