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?
Monday, February 20, 2006
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?
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!
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...
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...
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.
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.
Monday, December 05, 2005
CheckerBoard 1.64!
I know I should have waited a bit to give you a chance to comment on beta 2 - but with busy season coming up, I just wanted to get this off my mind. I proudly present CheckerBoard 1.64, which you can download on the CheckerBoard site. Besides, I remade the site using advanced techniques (ahem) like CSS and PHP. ahem because these things have been around for so long that they are probably outdated now that I finally found some time to look at them :-)
Sunday, December 04, 2005
CheckerBoard 1.64 beta 2
I've updated the CB 1.64 beta which you can download as http://www.fierz.ch/CB_setup_164.exe (1670 KB). It doesn't have a new version number but it displays December 2 as date in the status bar on startup. I have a particular question: one user reported that the "add comment" feature wasn't working - he would add a comment and that would just disappear. Does anybody else see this problem (because I don't...)?
Saturday, December 03, 2005
Getting organized!?
The other day I was looking at a PHP tutorial and followed a couple of links and finally ended up on backpackit - quite a coincidence, since over the last couple of months I've been frustrated with how disorganized I am! I'm not sure yet whether this is the real solution, so: how do you organize your ideas, projects etc?
Saturday, November 26, 2005
CheckerBoard 1.64 beta
I've posted CheckerBoard 1.64 to my website; there is no link as yet but you can download it as http://www.fierz.ch/CB_setup_164.exe.1.64 introduces a change to the directory structure: there is a new dir called "engines" where all engines should go. In the "bmp" directory, there are now subdirectories where you can put all kinds of piece sets which then show up in the options menu. There are 3 sets pre-installed, my standard set and two new ones by Ron Carney. For serious checkers players, there is the option to analyze an entire PDN database. Ed Gilbert sent me some code to improve my PDN parser, which is now more forgiving of non-PDN input, such as games which you copy-paste from a webpage. CB 1.64 also introduces alternate languages, albeit only for the menu and not for the dialogs. It's a start... Angel Galan Galan did the Spanish translation. My thanks to all those who contributed to this release!
To install CB 1.64, download and execute the CB_setup file. There are several ways to get it working properly:
-> Install CB 1.64 over your old CB directory: In this case, CB 1.64 will not recognize checkers engines which are not in the "engines" directory. You must manually copy these engines (all the *.dll files and associated files) into the engines folder.
-> Install CB 1.64 side-by-side with your old CB: choose a new directory such as C:\program files\CheckerBoard164 for your new installation. The two versions should be able to coexist on your system.
-> Uninstall the previous version of CB: First, remove your old version of CB. Make sure to keep games that you have saved! Re-install the new version over it.
To install CB 1.64, download and execute the CB_setup file. There are several ways to get it working properly:
-> Install CB 1.64 over your old CB directory: In this case, CB 1.64 will not recognize checkers engines which are not in the "engines" directory. You must manually copy these engines (all the *.dll files and associated files) into the engines folder.
-> Install CB 1.64 side-by-side with your old CB: choose a new directory such as C:\program files\CheckerBoard164 for your new installation. The two versions should be able to coexist on your system.
-> Uninstall the previous version of CB: First, remove your old version of CB. Make sure to keep games that you have saved! Re-install the new version over it.
Tuesday, November 22, 2005
GUI checkers 1.05
Is it a bird? Is it a plane? No, it's GUI checkers running at an amazing 4.5 million nodes per second on my Athlon 64 3000+! I managed to coax Jon Kreuzer from his checkers retirement by requiring a tiny change in the way engines interact with CheckerBoard, and instead of just implementing this change, he went on to improve GUI further. It is now searching about 3 times as fast as Cake Manchester. You can download GUI on Jon's checkers page.
Jon also wrote a nice tutorial on bitboards in checkers programs, which gives you an idea on how to program a blazingly fast checkers program.
PS: of course, speed is not everything. There are reasons why Cake is so much slower than GUI, and it's not only that Jon is a more accomplished programmer. Cake has larger endgame databases which take time to probe, and it also has a more complex evaluation function. As you know from our human checkers experience, it is not necessary to examine millions of positions to find a good move - it is more important to examine the right positions, and to evaluate them correctly. Cake Manchester is better than GUI checkers despite searching less positions per second.
Jon also wrote a nice tutorial on bitboards in checkers programs, which gives you an idea on how to program a blazingly fast checkers program.
PS: of course, speed is not everything. There are reasons why Cake is so much slower than GUI, and it's not only that Jon is a more accomplished programmer. Cake has larger endgame databases which take time to probe, and it also has a more complex evaluation function. As you know from our human checkers experience, it is not necessary to examine millions of positions to find a good move - it is more important to examine the right positions, and to evaluate them correctly. Cake Manchester is better than GUI checkers despite searching less positions per second.
Subscribe to:
Posts (Atom)
