Monday, February 20, 2006

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?

Wednesday, February 15, 2006

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?

Sunday, February 05, 2006

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!

Saturday, February 04, 2006

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...