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

Comments

Aart Bik said…
Perft number for higher depths can be found at:
http://www.aartbik.com/MISC/checkers.html
May 8, 2009 at 9:48 AM
Marius said…
Hey, I know the article is several years old, but I was wondering if you know about any ressources to find divide tables for 8x8 american checkers.

I have a move generator which returns divide(6) = 36834, and I have trouble figuring out where I messed up. I know you have tables for depths >= 17, but I cannot find any for shallower depths like 6 or 7.

If you have anything you can point me to to solve my problem I would greatly appreciate it! :)
January 23, 2021 at 7:43 AM
Aart Bik said…
My engine BikMove has a built-in perft/divide feature (and was also the basis for the deep perft distributed experiments I published). Here is divide for 6 (but of course, for proper debugging, you will need to traverse into the mismatched position and perft-divide from there). I you posted the mismatch, I can post the divide for that position (we should find the bug in only 6 iterations!).

divide(6) =>
  0  : 12-16- : nodes=5979      
  1  : 11-16- : nodes=6805      
  2  : 11-15- : nodes=4289      
  3  : 10-15- : nodes=4659      
  4  : 10-14- : nodes=4265      
  5  :  9-14- : nodes=4133      
  6  :  9-13- : nodes=6638      
=> perft(6) = 36768
January 23, 2021 at 12:02 PM
Marius said…
Hey, thank you, I already figured out where my problem was! I had an issue where some capture sequences were calculated multiple times. Now it seems to be working, and my perft() gives me the right numbers. Only tested to depth 10, but I am fairly confident it's working now correctly :) Thanks!
January 24, 2021 at 2:13 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