Book update

I released a new version of Cake's Huge Opening Book (CHOB) recently. The new version is now based on about 2.35 million positions that were analyzed by Cake, the previous version (released in mid-April) was based on about 2.2 million positions. The new book would be approximately one ply deeper in the shallower main lines than the old book; however, I also threw out all positions which are in the leaf of my book tree - i.e. those positions where no successors have been searched. The reason I threw out those positions is that they are based on a 90-second book-generating search on a fast computer (AMD Athlon 64 3400+ with 2GB ram), which is good, but perhaps not good enough. The book-generating search produces evaluations for all moves in a given position, and takes longer than the regular search to reach a specified search depth. Therefore, it is approximately equivalent to a 30-second regular search on a fast machine. That means that if you set Cake to search for more than 30 seconds on a fast machine (and if you have the 8-piece database), then you might get a better move than what is in the book. This alone is enough to throw out the leaf positions, but there is more: Ed Gilbert actually found a losing book move in my first release of CHOB, and it was just such a leaf node. Now, this move is no longer in the book, and if you give Cake enough time, it won't make this losing move. Looking at the data from the opening book generator, it seems that it will have to run for another 2-3 months until it will expand that position with the losing move further.
Having found (or been told about, rather) one error in CHOB 1.0, I have to assume that there were more errors. After all, Even in a 288-game-match only about 288x10 = ~3000 book moves are actually played by Cake. Now that I know that one of these was a loser, I could extrapolate and say that 1 of 3000 moves is bad, and that therefore there are approximately 1000 losing moves in the book. I don't think it's this bad at all though, but there is no way to really know.

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!

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!

2 million moves!

My book generator just passed the 2 million move mark. For me this was a psychologically important moment, although as a physicist I am usually immune against that kind of innumeracy. The reason this one number means something to me is an email I received from Murray Cash (programmer of Nemesis) over 3 years ago. He had just completed a match between Nemesis and Cake++ 1.4 (the details are still available on the Nemesis benchmarks page). His conclusion then was that Cake was a decent engine, but that it would need a book of 2 million moves or so. It took me and my computer farm quite some time to come up with this book! I'm glad I had the patience to build this book...

The new book, finally

This week I released a new install package for CB - with the latest versions of CB, Cake, and the opening book. The new book has 93'000-something moves, just like the old one, but it should be quite a bit better. The last result of the matches against KingsRow with the final book was

• mailplay:
  +0 -4 = 20
  
• lost:
  +16 -18 =2
  
• normal:
  +4 -13 =271
  

In fact, this is a worse result than I got at 74'000 moves; however this is most likely just because of KingsRow's random opening choice. With the original book, the result is

• mailplay:
  +0 -7 =17
  
• lost:
  +8 -18 =10
  
• normal:
  +4 -15 =269
  

which is clearly worse, although the improvements are mainly in mailplay+lost openings. This is mostly because of the new book generator which looks at unbalanced ballots deeper than the old book generator.
I also wrote a book merge tool with which I have replaced the old database entries in the opening database with their new counterparts. Since quite a lot of play has changed in the opening stages, it will now take a long time for the book generator to expand these new lines to the same level as the old lines, so don't expect a new big book any time soon.

Another book update

Back from my chess tournament, I tested the latest version of the new book - it is now at 74'000 positions. It has improved further and got the following results in the 2s-per-move match against KingsRow 1.14p (with its massive 800'000 move book):

• mailplay:
  +1 =19 -4
  
• lost:
  +14 =4 -18
  
• normal:
  +4 =274 -10
  

I'll keep the generator running for another week, when the new book will be about the same size as the old book that was published on the web - then I will publish a whole new installation package for CB; it's high time I did that anyway - the last versions of CB were all only available as zip-files. One of the reasons for computing a new small book was that I wanted to both have a stronger book for the installation package and not turn CB into bloatware (software which uses more diskspace on every new release), like most other programs out there. It looks like my ideas about the new book were quite right - it is already better than the old book!

Chess, not Checkers

I'm off to a chess tournament which will last for 9 days. However, the title of the post is misleading, I plan to fix two bugs and add a couple of features to CheckerBoard when I'm not playing chess! I also want to write a book merge tool to replace the old values in the opening database with the newly calculated ones. I hope I'll find the time for all the things I want to do...

In the meantime, I have new results from the new book, which was at 46'000 moves when I last tested it:

• mailplay:
  +1 = 18 -5
  
• lost:
  +14 = 4 -18
  
• normal:
  +3 = 271 -14
  
  

That's hardly better than at 20'000 moves, although there is some randomness to these matches, because KingsRow chooses among equal moves at random.

The need for a book update

I have to admit: I'm not really a good programmer. I still program in plain C, have no idea about object-oriented programming and new developments like Java have passed me by. Good practices like documenting code, using CVS and the like are not on my skills list either. Why do I mention this? My programs are usually "work in progress". Often, I know better but don't bother to fix certain things. The book generator is such an example. As a small excuse, I wrote it at a time where I didn't have the 8pc database yet and didn't ever expect to generate opening databases with millions of positions. But now that this has happened, some rather obvious flaws in the design of the book generator have appeared. The basic problem is that with the 8pc database and a huge book (meaning lines are searched very deeply), most openings turn out to have the value 0 - the book generator manages to more or less find a path directly from the 3-move starting position into the endgame database. It also turns out that in most positions, there are a number of moves that all have value 0 - all of these moves draw. However, typically one of these moves might leave you in a strong position, and the opponent has to play accurately to draw, while another of these moves could leave you struggling for the draw. Of course, I would want Cake to choose the move that leaves it in what is called a strong draw. But how do you do this? The solution I envisaged at the time I wrote the book generator works as follows: In every position, the opening database contains the values of all moves as they were computed when this position was first examined, plus the values that come from propagation of further expansion. The propagated values are the true values, but if two or more of these are the same, I want Cake to choose the move which looked better on a shallower search. That's just what it does right now. Does all of this make sense? Doesn't this sound like a sensible approach? Well, there is a flaw: When I started generating the opening database, I used a beta version of Cake Sans Souci for the first approximately 90'000 moves. Then I switched to Cake Sans Souci, and much later, already after over 1 million positions, I switched to Cake Manchester. At the same time, I upgraded the hardware from an Athlon XP 1600+ to a XP2400+ and later to an Athlon64 3000+. All of this means that the first positions examined - the most important ones! - were searched with a clearly weaker machine+engine-combination than what I have today. The first positions are the most important ones, because that's where you decide how to play - at later stages things are often forced or simply a draw. Therefore, the most important decisions in the opening are not made by Cake Manchester, but by Cake Sans Souci beta, and I'm not happy about that! I'm in the process of computing a small opening book with Cake Manchester, which I will then import into the full opening database, which should improve things. There are many other details that are not good in my book generator, but this post is already too long to write about them now!

Book update

I have been computing a new book for Cake starting from scratch for the last 10 days. With 20'000 moves in the book, I had Cake Manchester 1.09 play against KingsRow 1.14p with its massive opening database on my AMD64 3200+, @2s/move, with 512MB db cache and 64MB hashtable each. The result, predictably, was quite lopsided:

• 12 mailplay openings (now part of the standard deck):
  +0 =17 -7
• 18 lost openings:
  +13 =6 -17
• 144 normal openings:
  +6 -16 =266

This certainly isn't too good, however, the book is still very small and will improve rapidly. Keep in mind that my full book is based on 1.6 million positions! I haven't tested how the old 90'000 move book that is distributed with the CB installation does in a match with KingsRow, but probably not much better than this new tiny book. Once the new book is reasonably good (probably around 100'000 to 200'000 positions), I will release it. Why am I doing this instead of releasing my full book? Good question, and I will answer it in my next post.

Cake for Linux with opening book released

Peter Chiochetti has published Cake 1.20 with an opening book for Linux. The book is based on a huge opening database of over 1.5 million positions, and is probably nearly error-free. Get the new version of Linux-Cake on the xcheckers page!

Cake Manchester's opening book

The book I just created for Cake++ for Linux is much better than the book that you can download for Cake Manchester. Manchester's book is still the same I once created in 6 weeks with a beta of Cake Sans Souci after the computer checkers world championship in Las Vegas in 2002. That book is based on the first 90'000 positions my book generator explored. Now, among these 90'000 moves roughly half will never occur when you set the book to play best moves only. Of the remaining say 50'000 moves, about one quarter are just forced captures. So effectively, that book has a mere 40'000 useful book moves, and they are based on an opening database with "only" 90'000 positions, which means there are also quite a number of errors in that book.
The book for Cake++ only contains lines that Cake will actively select, i.e. there are no wasted moves for lines it will never play. I also left out the forced captures in that book. Finally, all moves are based on the 1'600'000 position opening database, which means that there are only very few errors left (if there are any at all).
Cake Manchester will also get an updated book - I'm just waiting for the book generator to discover the bad move that caused Cake's only loss in the big match between Cake and KingsRow late last year.

An opening book for Linux-Cake

Peter Chiochetti recently revamped his checkers interface for Linux. The best engine for this interface is an old version of my checkers program, Cake++ 1.19. Yesterday, I added some code to it to handle an opening book and built a 115'000 move opening book from my opening database for it. Peter will first have to check my new code for compatibility issues with Linux, so it may take a while for this new version to appear on Peter's website. The book should be virtually error-free and worth the wait.

A well-deserved retirement

Back in early 2002 I wrote a program that automatically generates a checkers opening book, without any human intervention. The algorithm for this was invented by Thomas Lincke and it's called drop-out expansion. I have a computer at home which works on the opening book day and night. Yesterday, I replaced its mainboard, CPU and memory for newer components. After 20 months of nonstop computing, this AMD Athlon XP 2400+ CPU has certainly deserved retirement! During this time, it searched through nearly 100'000'000'000'000 checkers positions, generating the largest part of my now 1.6 million-move opening book.
The replacement is an AMD Athlon 64 3400+ CPU, like the old machine this one also has 1.5GB memory. The reason that I don't have Intel inside is that the AMD processors are better suited for integer computations than the Intel CPUs - for floating point it's the other way round. But since checkers programs (chess programs too) only use integer numbers, you get much more bang for the buck when you choose an AMD processor.