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
May 12, 2009 at 1:05 AM
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.
May 12, 2009 at 9:35 AM
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
October 31, 2021 at 3:32 AM
Post a Comment

Popular posts from this blog

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

Connecting Chess for Android to a Remote Server

-
Image
I have received several questions on how to connect Chess for Android running on an Android device (e.g. a phone) as client to a remote chess server (e.g. a powerful desktop), so I decided to write a small document with detailed instructions. What you will need: The server software from Bernhard Wallner's chess utilities , suited for your server's operating system (if, say, your desktop runs Windows, you will need to download the Windows version). You do not need to download the client software in this case. The network enabled version of Chess for Android . On the server, start the engine server software, and construct a new row for every engine you want to run remotely. Assign a name, port number, and select the full path to each engine binary (an executable that runs on the server). You can also supply command line options for starting the engine. Check the active checkboxes and click start when done. This yields something similar to the screenshots below. Here, I have s
Read more

Connecting with the DGT Board

-
Image
After all the fun I had connecting Chess for Android with the Millennium  over Bluetooth, I was curious if I could provide similar support for the DGT electronic chess boards. Some of these have Bluetooth capabilities, most use USB connections, and some older models, like the one I have, still use the RS-232 connector. To my pleasant surprise, by combining the original serial cable of DGT with a USB-to-serial cable and a female-USB-to-USB-C cable, I was able to get an actually working connection between my DGT board and my tablet or phone. Next was implementing support in Chess for Android. Luckily, DGT kindly shared the protocol documentation with me, and after a fun weekend of hacking, Chess for Android now proudly supports DGT electronic chess boards as well.
Read more