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.