Aart's Blog

I made minor improvements to the reversi move generator and evaluation function in version 1.5.5, hopefully resulting in stronger play. Unfortunately, in my excitement I forgot to add a new internal state to the save/restore functionality, which could introduce wrong play if a game was exited and later resumed. This has been fixed in version 1.6 of Reversi for Android. Many thanks to Patrick Barnes for reporting the bug (with a screen shot as illustration!).

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 ...