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.

Comments

Anonymous said…
Sorry, but not the first, check:

http://vivi.dyndns.org/d/5494
Aart Bik said…
Thanks for the link! I am happy to see the numbers confirmed. It's too bad the numbers stop at 10, since it would be interesting to see if their perft() would only count full depth leaf nodes (as done in chess), or count "higher" leaf nodes as well (which seems somewhat more logical in the context of reversi). See my presentation at Perft for Reversi.
Anonymous said…
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
13 18429641748
14 184042084512
15 1891832540064
16 20301186039128

Popular posts from this blog

Checkers Move Generation

Connecting Chess for Android to a Remote Server

Connecting with the DGT Board