Posts

ChessWar and WBEC Ridderkerk

Due to all Android distractions, it has been a while since I posted on BikJump. It recently ended at a somewhat disappointing 54th place in OpenWar 5th Edition . Version 2.01 is now playing in the final of the 5th Division WBEC Ridderkerk edition 16 .

A New Checkers Engine: BikMove

I ported the Java source code of the engine in Checkers for Android into C++ and implemented the parts required to form a plug-in engine for Martin Fierz' CheckerBoard application. The result is BikMove (with an obvious wink to my UCI chess engine BikJump). I also added the ability to query checkers endgame databases based on Martin Fierz' probing code (used with his kind permission). The main features of BikMove are listed below: Checkerboard compliant checkers engine. Iterative deepening, alpha-beta pruning. Queries endgame databases during search. The engine needs some more work to become competitive with others checkers engines, but it already plays what looks to me like decent checkers. Give it a try if you are interested!

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

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 .

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