Another suicide checkers challenge

I just received the following email:

From: Igor Korshunov
To: Martin Fierz
Date: 4/21/2006

Hi Martin!I am made first version of suicide checkers.I want to match your program.When we can meet in battle?

Best wishes,Igor

I'll try to hold this as an online match on Kurnik again - once I know the time and date, I will publish it here.

Igor is the author of WildCat, a strong chess engine. He has also written a checkers program playing the Russian checkers variant, but I couldn't find an internet reference for that. WildCat is much better than Muse, my chess engine. You can verify this on Leo Dijksman's rating list, where WildCat is rated 2570, while Muse is only rated 2382. In my defence, I never took up chess programming very seriously. In any case, Igor's background in computer programming makes it unlikely that the match will be quite as lopsided as the one against Roshi47.

The Book!

I'm still not satisfied with the huge opening book - but I guess I never will be... so I posted it on my checkers site. I'll probably write some more about it later; for the moment: Enjoy!

A hidden function

Sitting here in a comfortable sofa, with the Matterhorn visible through the window, I remember that many years ago I once read in a computer magazine that you could press a wild combination of keys in Excel, and you would get a flight simulator. I tried, and indeed, there was a simple flight simulator where you would fly past something like a mountain where the names of the developers of Excel (a lot of people!) were displayed. Weird stuff! CheckerBoard also has a hidden feature: the engine match. When I want to test a change in Cake, I run a match of 288 games against KingsRow to verify that I have really improved something. Of course, this is all automated, and you can run such a match too: Ctrl+Shift+M starts a match - you can figure out the rest for yourself - I have to go back to staring at Switzerland's most beautiful mountain...

Odds and Ends

I'm busy waiting for my book generator to finish its book computation - but I'm not busy with checkers! Instead, I added a touch to my Connect Four program: it has nicer graphics and now offers different levels of evaluation intelligence - you can make it really dumb so that you can beat it easily. I also just finished a Sudoku program, using C#. C# makes it much easier to create applications rapidly. At least I'm programming something at all; I didn't find much time for that during the last year. Ed Gilbert has used my laziness to catch up with Cake: In my latest match, KingsRow 1.15u still lost to Cake Manchester 1.09d with -21+17=250, but this narrow result may just as well be accidental - Ed has some more results at different levels, and sometimes Cake wins, sometimes KingsRow. When I published Cake Manchester somewhere during Summer 2004, the match results against KingsRow were extremely lopsided - those were the days!

Switzerland 6, Canada 0!

The suicide checkers match ended in an even clearer result than the hockey match between Switzerland and Canada at the olympic games: Suicidal Cake beat Roshi47 4-0. Its authors then challenged me to two games human-human, and I managed to raise the Swiss score to 6-0. All in all, a surprisingly lopsided affair. I wrote a short article on the match. I have a couple of afterthoughts on the match, which I will add to that article in a couple of days. All that is left to add right now is the following email which I received today:

To: Martin Fierz
From: Jonathan Schaeffer
Subject: Suicide Checkers
Date: Wed, 8 Mar 2006 16:48:02 -0700
X-Mailer: Apple Mail (2.746.2)

Congratulations! Experience trumps youth :) I think both
Mike and Frano are stunned at the result.

Now, that is something to be proud of :-)

The fastest suicide checkers loss?

I've been playing around a bit with my book generator for suicide checkers because of the upcoming match against the Canadians. I was looking at early losses in suicide checkers, and this is the earliest I found so far:

1. 10-15 22-17 2. 6-10 23-19??

Red to move and win! Can you solve it? Can you find a faster way to lose a game of suicide checkers?

Tweaking the book generator, part 2

At the end of last year I received the following email:

Hi, I recently played Cake Manchester 1.09d and set the time to 10 Seconds and used Best Moves, and Cake couldn't even draw. I analyzed the game and saw that Cake played terribly through out the game. I think that you should produce or if you already have then release a newer version because it's too easy for me.
Attached is the game that I won. Please view it.

Thanks

Yacoob

Attached was the following game:

[Event "I Lose"]
[Date "2005-12-29"]
[Black "Chikita Mia"]
[White "Yacoob"]
[Result "1-0"]
1. 11-15 24-19 2. 15x24 28x19 3. 8-11 22-18 4. 11-16 25-22 5. 16-20 32-28 6. 10-14 22-17 7. 9-13 17x10 8. 6x22 26x17 9. 13x22 30-26 10. 4-8 26x17 11. 8-11 29-25 12. 11-16 25-22 13. 5-9 19-15 14. 16-19 23x16 15. 12x19 17-13 16. 9-14 22-17 17. 14-18 17-14 18. 19-23 27-24 19. 20x27 31x24 20. 23-27 24-19 21. 27-31 14-9 22. 1-6 28-24 23. 31-27 24-20 24. 27-24 9-5 25. 18-23 19-16 26. 7-11 15x8 27. 3x19 5-1 28. 6-9 13x6 29. 2x9 21-17 30. 9-13 17-14 31. 23-27 20-16 32. 27-32 16-11 33. 19-23 11-8 34. 23-27 1-6 35. 27-31 6-10 36. 31-26 10-15 37. 26-22 14-10 38. 32-28 15-11 39. 13-17 8-3 40. 24-19 10-6 41. 22-18 3-8 42. 17-22 11-7 43. 18-15 6-1 44. 22-26 7-11 45. 15-18 1-6 46. 26-31 6-10 47. 31-27 8-4 48. 27-24 10-6 49. 24-20 6-10 50. 19-16 10-7 51. 16-12 7-3 52. 28-24 11-7 53. 24-19 4-8 54. 20-24 7-10 55. 18-15 10-7 56. 24-27 8-4 57. 27-23 4-8 58. 23-18 7-2 59. 19-16 2-6 60. 18-14 8-4 61. 16-11 6-1 62. 15-10 1-5 63. 10-6 5-1 64. 14-10 1-5 65. 6-1 5-9 66. 1-5 9-13 67. 10-15 13-17 68. 15-18 17-13 69. 18-22 4-8 70. 11x4 3-7 71. 4-8 7-10 72. 22-18 13-17 73. 18-14 10-15 74. 14x21 15-18 75. 8-11 18-23 76. 12-16 23-27 77. 16-19 27-32 78. 11-15 32-28 79. 5-9 28-32 80. 19-24 32-28 81. 9-14 28x17 82. 21x14 1-0

You can make up your own mind as to what I thought when I read that email and looked at the game - in particular check out the game headers :-)
But leaving these petty details aside, I checked on this game quickly - after all, it's not often that Cake loses a game so I decided to investigate. Most of the time, it's because Cake's published opening book has some errors left, and they are fixed in my 2-million-move-book. It turns out that in this game too, Cake is lost when it leaves the book with 9...30-26. I looked at my large book, and - the same error is in that book too! According to Basic Checkers, white should play 22-17 instead of 32-28 on his 5th move. I changed my book generator so that this line will be expanded sooner.
So what was the problem that this line wasn't expanded? Basically, it has a lot to do with the design of the book generator, which I wrote in december 2001. At that time, I only had a 6-piece endgame database, and I didn't foresee what would happen once I had the 8-piece database and 2 million book positions: Most of the positions that my book generator is looking at now are positions which are a more or less clear draw - Cake can see ahead far enough to hit the 8-piece database and return an evaluation of 0. When this started happening (years ago already!), I decided I didn't want the book generator to spend lots of time computing obviously drawn positions. There are many solutions to this problem, and unfortunately, I chose a rather bad solution (it was a quick fix - often a bad idea!): I decided to reduce the priority of positions (i.e. decrease the chance that the book generator would look at them again) which have a heuristic evaluation of 0. With heuristic evaluation I mean that Cake can already see the 0 evaluation in that position - it doesn't have to expand further to be able to back-propagate a 0 evaluation. That is what happens to all first moves: all seven first moves also have a 0 evaluation which has been propagated from the book tree - but they all have non-zero heuristic evaluations. In the example above, Cake produces a heuristic 0 towards the end of the book line, and that was enough for that line not to be expanded further. Now it's your turn to think: what could I do to make my book generator smarter?

Tweaking the book generator

I was in the alps on my winter holiday for the past two weeks, and used the times in between skiing (when my knee hurt...) to tweak my book generator a bit. I knew of two lines in the book generator that were not what they should be. The first one goes like this:

1. 11-16 22-18 2. 10-14 25-22 3. 8-11 24-20

My openings database thinks that 8-11 is a big mistake because of 24-20 - because red must play 4. 16-19, sacrificing a man to draw. Now, if this 4. 16-19 line was expanded just a couple of moves further, it would play into the white doctor opening (1. 10-14 22-18 2. 12-16 24-20, and now 3. 16-19 is required to draw), which is in the book as a draw. However, this line is not expanded further because of the way the book generation works: if a move is thought to be clearly inferior, then it is not expanded any deeper, or only much later than the best move. In this example, 3. 7-10 is recognized as a draw, and therefore 3. 8-11 never got expanded much further. In a way, this is no serious error in the book, because it is meant only to find sound lines, and if you know one way to draw you don't need another. On the other hand, I would like my book to be a reference which checkers players can trust (once I publish it...), and if it doesn't know about this line, then people could easily be disappointed. The simplest fix to this problem is to tell the book generator to expand this specific line more deeply. This is also a very stupid approach, because the fact that the generator didn't expand this line is telling me that there may be other similar lines that it didn't expand and which would be worthy of expansion too. With over 2 million positions in the book, there is no way for me to check everything, so I have to make sure that whatever fix I make, it will affect the way that this line and others like it are expanded after the fix. In this case, I decided to penalize mistakes on the first 10 moves less than on later moves, causing an earlier expansion of the line above. I wanted the transition to be somewhat smooth so I used a weight of 0.05*depth + 0.5 with which I multiply the penalty for errors on the first 10 moves; for later moves the weight is 1.0. This change has had the desired effect: The line in question is now going to be expanded soon.

There is another line which I had to find a fix for, where even my 2-million-moves book still had a losing move in the book. It's a longer story so I'll keep that for my next post!

Suicide checkers challenge!

I just received a mail from the Chinook creator, Jonathan Schaeffer. It says:

I have a couple of students who built a suicide checkers program
as a course project. They have tinkered around with it since then
and are curious to know just how good it is. Obviously it kills
all humans. I understand you have a strong suicide checkers program.
Would you be willing to have your program play a match with them?

I'm looking forward to giving SC another spin. On the downside, in the process of saving, synchronizing and backing up things, I seem to have lost the source code of both the latest SC and the latest endgame database builder for SC - I'm feeling pretty stupid! I still have the latest version of the programs and I hope I won't manage to lose those too...

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.