Tuesday, January 17, 2006

Kingscourt solved!

Today, my opening book generator for the game of Kingscourt terminated because it solved the game: white wins in approximately 62 half-moves ( Kingscourt is the checkers variant where crowning a man wins the game). The method with which I solved the game only gives a result and a complete opening book with which the win can be played out; there is no guarantee that this is the shortest possible win. If you want to try to outwit the perfect opponent, you can download the book: kingscourt_book.zip (~2MB). You will have to extract the book in your CheckerBoard directory (not the engines directory), and kingscourt.dll should recognize it. Once you get out of the opening book, you will have to let the dll compute the win, but this should take no longer than a few seconds.

The opening book for the proof contains about 200'000 nodes, and was constructed in about 4-5 months on an AMD Athlon 64 system, using kingscourt.dll to search each of these 200'000 nodes. Initially I thought the game would be easier to solve, and I didn't put too much effort into optimizing the algorithms - I'm sure there is a lot of room for improvement left.

The whole idea of automated opening book computation on which this proof is based is due to Thomas Lincke.

4 comments:

Ed Gilbert said...

Cool, I just tried it. It's interesting that black loses by playing first.

Martin, you should put a link to your blog on the CheckerBoard page. I had to hunt around to find this.

-- Ed

Nelson Castillo said...

¡Congratulations! :P

Chris Wroth said...

Hi ~ Love your blog. I invented King's Court in 1979. Mile Goodspeed wrote a program for it in Java. You can find it here: http://code.google.c/p/supercheckers/ Send me a mailing address and I will send you a free game. Peace. ~ Christopher Wroth

Chris Wroth said...

Hi ~ By the way, my King's Court is not your King's Court. The inventor of Chinook told me that King's Court (my game) will never be solved. What do you think? Peace. ~ Chris Wroth