Friday, February 20, 2009

Perft for Reversi

As can be seen in previous postings, the perft method is useful to verify the correctness of a move generator. The method traverses the game tree up to various, increasing depths to count all leaf nodes. The results are compared with pre-computed values to isolate bugs. Although the method originated in the chess programming community, the same debugging principle can be used for any board game with deterministic rules. So far, I have used perft to verify the move generation of Chess for Android and, thanks to Martin Fierz, also for Checkers for Android. I was unable to find pre-computed perft numbers for reversi, however.

Therefore, here is what is probably the debut of perft for reversi from the initial position, hopefully useful data for aspirant reversi programmers (at depths 9 and up, "passing" moves start to occur; at depths 11 and up, higher leaf nodes in which neither player can move start to occur).

DEPTH #LEAF NODES
========================
1 4
2 12
3 56
4 244
5 1396
6 8200
7 55092
8 390216
9 3005288
10 24571284
11 212258800
12 1939886636

Perft is also useful to analyze and improve the performance of a move generator. Today I made some optimizations in the reversi move generator that improve performance almost two-fold, posted as version 1.3.4 of Reversi for Android at the market.

Wednesday, February 18, 2009

Checkers Move Generation

I was able to make a small improvement in the checkers move generator (written in Java for the Android SDK). The following table shows run times of several perft depths before and after optimization when run on the emulator (which should mimic actual run times on the phone quite well).

DEPTH #LEAF NODES ORIGINAL OPTIMIZED
TIME TIME
====================================
7 179740 2.9s 1.9s
8 845931 14.2s 9.7s
9 3963680 66.3s 45.6s
10 18391564 294.6s 208.7s

P.S. Runtimes for a C++ checkers move generator on a 2.2 GHz Core 2 Duo are given at my checkers page.

Friday, February 13, 2009

Perft for Checkers

Martin Fierz kindly extended his engine Cake with a perft feature. Luckily the numbers reported by Cake match the numbers reported by Checkers for Android exactly. Below the numbers from the start position are shown, hopefully useful data for aspirant checkers programmers.

DEPTH #LEAF NODES
=======================
1 7
2 49
3 302
4 1469
5 7361
6 36768
7 179740
8 845931
9 3963680
10 18391564
11 85242128
12 388623673

Wednesday, February 11, 2009

CheckerBoard

If you are looking for a checkers program for Windows, I can highly recommend Martin Fierz' CheckerBoard, consisting of a checkers GUI that features game databases, opening books, endgame databases, and various checkers engines (including the capability to plug in your own as DLL). I have used his engine Cake as "sparring partner" to test the correctness and strength of Checkers for Android. Needless to say, Cake won, but the games at least assured me that my Android version plays correct checkers. Martin also kindly responded to my request for adding a perft feature to Cake, which will enable verifying the correctness of my move generator against his.

Wednesday, February 4, 2009

Yet Another Update

I am on the roll with updates! Version 1.3.2 of Chess for Android uses a larger font for the move list and highlights the last moved played by the engine (controlled by the already existing "show valid moves" button).



I am thinking about a version 2.0 with a completely new board layout to use the limited screen space more effectively. As usual, keep an eye on this blog if you are interested.