Checkers, Milhouse, and Poe…

In some of my reading up on checkers, I encountered this quotation from Poe’s Murders in the Rue Morgue:

I will, therefore, take occasion to assert that the higher powers of the reflective intellect are more decidedly and more usefully tasked by the unostentatious game of draughts than by a the elaborate frivolity of chess. In this latter, where the pieces have different and bizarre motions, with various and variable values, what is only complex is mistaken (a not unusual error) for what is profound.

Very nice…

Yesterday I managed to get most of the move generator for my own checkers program, tentatively named Milhouse mostly working. I have taken a somewhat odd approach in that I am generating most of the move generator by writing a couple of Python scripts which generate the C code for the move generator. The particular board representation that I have chosen to use is a structure containing only three 32 bit integers. Coincidently, a checkerboard has 64 squares, but the game is played on only 32 of them. This makes for a fairly nice and compact representation: one integer contains a bitmask showing where the red checkers are, another, the white checkers, and a third to indicate which of the pieces are kings. This representation is compact, and fairly useful for move generation as well. Once I got the basics working, I coded up a loop to play one million games, each doing a legal move randomly chosen from the available legal moves.

[ markv@checkers .../milhouse ] % time milhouse
537359 red wins, 462641 white wins, 474661073 nodes 90572579 total moves
22.083u 0.091s 0:22.25 99.6%    0+0k 0+0io 1pf+0w

It played the million games in just 22 seconds, generating over 90 million total moves (really plies, or half moves) and 474 million total board positions. I think it’s a fairly good start.

Addendum: The assymetry in red and white wins seemed a bit extreme. It turns out I had a fairly serious bug caused by a copy paste error.

Technorati Tags: ,