Wednesday, February 18, 2009

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.