Kingsrow International

For the past year I have been working on a version of Kingsrow that plays 10x10 international draughts. This is a very different game from 8x8 English checkers. It is played on a 10x10 board, there are 20 black pieces and 20 white pieces at the start, men can capture both forward and backward, and kings can travel the full length of a diagonal in one move, much like a bishop in chess. There is an annual tournament for international draughts programs at Culemborg, Netherlands, and I brought Kingsrow International to one that took place on December 2 of this year. A total of 10 programs attended. Most are from the Netherlands, but also present were programs from France and Switzerland. Kingsrow was the only program from a non-European country. Each program played every one of the other programs once, 9 rounds in total. In each game a program is required to complete 75 moves in 20 minutes. The programmers set the computers up on opposite ends of a table, with a real draughts board and game clock in the middle. When a program makes a move, its programmer/operator transfers the move to the table board and hits a button on the table clock, which stops his clock and starts the opponent's. The opponent then enters the move into his program and it begins its search. Thus each game proceeds much like a normal game between two human players except that the programs are selecting all the moves. Because the programmers don't have to concentrate on the game, there is plenty of time to chat and kibitz between making the moves.

When the tournament was finished, Kingsrow International had the highest score with five wins and four draws. Two programs tied for second place with four wins and five draws each, so the top three were very close. 

To create Kingsrow International, I took the source code for the English version and modified the move generator for the international rules. I created a new user interface because CheckerBoard does not support the 10x10 board format. Since the strategy is so different from English checkers, I tossed the evaluation function and wrote a new one. This is the most important part of a checkers program, and this took a long time. I had to learn some basic things about 10x10 draughts strategy. It is not a popular game in the USA, and I was unable to find any books about it that are written in English. My primary method of learning the game was watching Kingsrow play against a few other programs. I also received some helpful emails about the game strategy from Rein Halbersma, who is a strong 10x10 tournament player.

Of course a checkers program is not complete without some databases. I took the program that I had used to build the 10-piece endgame databases for English and Italian checkers and modified it to build endgame databases for international draughts. I ran this program on the same cluster of four machines that I had previously used for building databases. After about 6 months I had completed all the positions with 2 through 7 pieces, and some subsets of 8 and 9 pieces. The 8-piece subset includes all 4x4 and 5x3 positions with one king or less on each side. The 9-piece subset includes the positions with 5 men vs. 4 men, 5 men vs. 3 men and 1 king, and 4 men and 1 king vs. 4 men. These databases are quite large and occupy 339GB of space on my hard drive. AFAIK this is the largest international draughts endgame database in existence. 

By running some engine matches between two different versions of Kingsrow, I discovered that the 9-piece subsets containing kings were so large that Kingsrow played better without them than with them, so for the tournament in Culemborg I only used the 5 men vs. 4 men subset of 9 pieces. This and the 2 through 8 piece positions occupy 146GB of disk space.

I also modified my opening book generator program to build an opening book for international draughts. This program uses a technique first described in a paper by Thomas Lincke which he calls "dropout expansion". It constructs an opening book by doing systematic searches with the Kingsrow search engine and adding these positions and search results into an opening book database. The opening book that I brought to Culemborg was quite small compared to the books I've built for English and Italian checkers. It contained 120K positions. But I observed that in each of the 9 games Kingsrow stayed in book for a few moves longer than its opponents. The primary benefit is that these are moves that take no time off the game clock. This is another big difference from 8x8 checkers, where opening books are critically important to playing many of the 3-move ballots correctly.

Ed Gilbert
Dec. 5, 2007