Cake Sans Souci
In the las Vegas computer checkers world championship, Cake las Vegas finished in 3rd and last place, losing two games and playing a couple of weak moves more in other games. This was by all means an expected result, playing against the heavyweights Nemesis and KingsRow with their huge opening books. I had expected to lose a couple of games, mainly because of weaknesses in my opening book. Like real players, we programmers learn most by analysing the mistakes our programs make. After the tournament, I returned to Honolulu, and tried to understand where and why my program went wrong. It turned out that the losses were not due to the opening book, but rather due to my too aggressive and inaccurate pruning mechanism. The programs can look at millions of positions, but most of them are rubbish. Pruning tries to avoid looking at those lines which are rubbish and focus on the important lines. Humans use an excellent pruning mechanism to achieve a very high level of play, although they can only look at about one position per second. I made vast improvements to my pruning code, and the result is Cake Sans Souci. It is a major improvement on the previously published Cake las Vegas. The main improvements are:
  • Cake Sans Souci can use my 8-piece database. You will need a computer with at least 128MB RAM and 4.4GB free harddisk space for this.
  • Cake Sans Souci comes with a new and improved 93'000 move opening book.
  • Cake Sans Souci has an all new pruning algorithm with much better accuracy.
How good is it?
How much does this help in practical play? I have conducted multiple matches agains Ed Gilbert's latest KingsRow engine (1.13i), and I have tested it in 7 interesting positions. All analysis cited below with one exception was done on my XP1600+ machine, using 384MB endgame database cache and 64MB hashtable - a configuration which should just fit on a 512MB machine. Note that the size of the database cache and the hashtable can have a big influence on the results in such test positions - the larger, the better. The 8-piece matches against KingsRow were played with both sides getting 384MB endgame database cache and 16MB hashtable.
If you own a checkers program, you can see how well it does compared to Cake Sans Souci in the test positions! I believe that Cake Sans Souci currently has one of the best search engines of all checkers programs. The opening book supplied with it is weaker than that of KingsRow and Nemesis though.
Match results
I ran some matches using the 144 normal openings in the ACF deck. The final match in the list is the "heavyweight championship", with both programs at their best.
Cake Sans Souci - KingsRow 1.13i at 5sec/move
  • 6-piece endgame database, books off, normal openings: +39 =237 -12
  • 6-piece endgame database, books on, normal openings: +14 =255 -18
  • 8-piece endgame database, books off, normal openings: +46 =223 -19
  • 8-piece endgame database, books on, normal openings: +11 =263 -14
In another match, I let Cake Sans Souci with the 8-piece database play the older Cake++ 1.41. It got a "Nemesis-like" result!
Cake Sans Souci - Cake++ 1.41 at 5sec/move
  • 8-piece vs 6-piece database, books on, normal openings: +38 =246 -4
Test positions
Position 1 shows why you should use the 8-piece database. It is the (in-)famous 100-year position. White is to move. This position was analysed extensively by humans (see Jim Loy's page on this, which gives more details on the history of this position, and the variations involved). The conclusion was that it is a win for white. Then along came Chinook with it's 8-piece database and showed it was a draw. If I let Cake Sans Souci think on this position with the 6-piece database for half an hour, then it thinks that white is close to winning - it really has no clue about what is going on, despite a 41-ply search. When I use the 8-piece database, it recognizes that this is a draw in less than one second! This position also shows that the 8-piece database is useful in positions where there are more than 8 pieces on the board, because the program can see into the database in it's lookahead.

6-piece database: 

depth 37/53/8.3  time 897.21s  value=64  597kN/s  pv  8-11 14-17 
depth 39/56/14.1 time 1512.87s value=62  599kN/s  pv  8-11 14-17
8-piece database: 
depth 19/26/9.6   time 0.53s  value=18 107kN/s   pv  8-11 14-17  
depth 21/26/10.2  time 0.59s  value=4  113kN/s   pv  8-11 14-17  
depth 23/26/11.0  time 0.70s  value=0  114kN/s   pv  8-11 14-17
Position 2 is the starting point of the famous white doctor opening. Black to move must pitch a man here with 19-16, else he will lose the game. Cake Sans Souci needs only 71 seconds to find this move! It is far from recognizing that this is a draw though, but it will sac the man as is necessary. Man-down play is the main weakness of the programs, as they don't like to part with their material. 
depth 19/38/21.4  time 6.75s   value=-36  1036kN/s  pv  7-10 28-24  
depth 21/42/23.4  time 22.31s  value=-44  995kN/s   pv  7-10 28-24  
depth 23/44/25.0  time 70.92s  value=-58  973kN/s   pv 16-19 23x16  
depth 25/47/27.0  time 165.51s value=-54  958kN/s   pv 16-19 23x16
Position 3 is from a game Cake las Vegas - Nemesis, played in the computer world championship in las Vegas. Here, Cake las Vegas as black to move lost the game by playing 4-8? after about 2-3 minutes of thinking. Cake Sans Souci will play the correct 9-14 to draw in 50 seconds. This position is also an example on man-down play, as black can win the white piece on 10. Cake las Vegas incorrectly assessed this position as good for black because of the material advantage. Cake Sans Souci's superior pruning algorithm sees how dangerous this is much faster. Here are the remaining moves of the game Nemesis won: 10. 4-8 20-16 11. 2-7 25-22 12. 7x14 16-11 13. 8-12 28-24 14. 19x28 22-18 15. 14x23 26x10 16. 9-14 11-7 17. 5-9 7-2 18. 12-16 29-25 19. 14-18 2-6 20. 16-19 6-2 21. 9-14 2-7 22. 3-8 7-3 23. 8-12 3-7 24. 19-24 7-11 25. 18-23 10-7 26. 23-27 32x23 27. 28-32 7-3 28. 32-27 23-19 29. 27-32 19-16 30. 12x19 11-16 31. 19-23 16-19 32. 32-28 19x26 33. 14-18 3-7 34. 1-6 7-2 0-1 
depth 17/32/16.9  time 4.32s   value=6   917kN/s  pv  9-14 25-22  
depth 19/35/19.1  time 28.25s  value=-8  885kN/s  pv  4- 8 20-16  
depth 21/36/21.2  time 49.90s  value=-4  866kN/s  pv  9-14 20-16  
depth 23/40/23.2  time 107.32s value=-8  841kN/s  pv  9-14 20-16
Position 4 is from a game Cake las Vegas - KingsRow, played in the computer world championship in las Vegas. Cake is playing the black side of a Gemini, and is in a difficult position because of a weak move in it's opening book - but it is not over yet. Cake las Vegas lost by 8-11? after about 5 minutes of thinking. Cake Sans Souci will play the correct 2-7 in 23 seconds! I'm not sure if 2-7 will draw. Murray Cash and Ed Gilbert played out a game between their programs, Nemesis and KingsRow, from this position which ended in a draw. One thing is clear though: 8-11 loses immediately, while 2-7 offers good drawing chances. Once again the theme is man-down: after 8-11 and the exchange, white plays 19-16 to gain an early king. In return, black wins the white man on 25 with a squeeze but ends up losing the game. Here are the remaining moves of the game: 13. 8-11 15x8 14. 4x11 19-16 15. 12x19 23x7 16. 2x11 26-23 17. 13-17 23-19 18. 6-10 19-16 19. 11-15 16-11 20. 15-18 11-7 21. 17-22 7-2 22. 22x29 2-6 23. 10-15 6-10 24. 15-19 10x17 25. 19-23 17-14 26. 29-25 0-1 
depth 19/34/19.2  time 1.12s   value=-6   698kN/s   pv  8-11 15x 8  
depth 21/37/21.6  time 2.83s   value=0    615kN/s   pv  8-11 15x 8   
depth 23/40/23.0  time 22.49s  value=-68  621kN/s   pv  2- 7 19-16 
depth 25/44/25.1  time 40.52s  value=-36  581kN/s   pv  2- 7 19-16
Position 5 is from a game between Don Lafferty and Chinook, in the match where Chinook successfully defended it's man-machine title, just after it had won it from Marion Tinsley. When Jonathan Schaeffer set out to revive the field of computer checkers, he was often confronted by the question: "Didn't Samuel solve checkers?" - referring to Arthur Samuel, who pioneered computer checkers. In an instance of history repeating itself, many people, artificial intelligence experts and checkers players alike, believe that Chinook "solved" the game of checkers, that it was very close to perfection. This is not true. Today's PC programs are better than Chinook was when it retired. I'm not sure whether this is because the PC's of today are much faster than the multiprocessor workstations Chinook ran on, or whether this is because today's programs are simply better software. In this position, Chinook as black blundered with 2-6? and lost the game. 24-28 instead will draw, and Cake Sans Souci chooses 24-28 in less than one second, and sticks with it. Chinook later won a game and the match ended in a 1-1 tie, with Chinook retaining the title. 
depth 11/22/11.3  time 0.10s  value=0    969kN/s   pv  2- 6 27-23 
depth 13/25/13.5  time 0.16s  value=0    954kN/s   pv  2- 6 22-18 
depth 15/30/15.4  time 0.50s  value=4    904kN/s   pv 24-28 27-23 
depth 17/32/17.5  time 1.66s  value=-16  843kN/s   pv 24-28 27-23
Position 6 is a test position for Sage composed by Derek Oldbury. White is to move and win. Programs which use a lot of pruning, like Cake Sans Souci, can have problems with tactics like this where one side gives up nearly all material to win with The Big Jump in the end. Older versions of Cake certainly did have problems with this. Cake Sans Souci finds the solution in a tenth of a second. Note that dumb programs with a pure brute force search without pruning will usually solve this kind of problem faster than the more intelligent programs. 
depth 13/21/11.0  time 0.02s  value=0      632kN/s  pv 14- 9  7x14 
depth 15/23/12.7  time 0.04s  value=0      657kN/s  pv 14- 9  7x14 
depth 17/27/14.5  time 0.12s  value=1983   493kN/s   pv 27-24 20x27
Position 7 is a known win in the black widow opening. 12-16? which looks very good only draws. 5-9 instead is the winner. Cake Sans Souci finds 5-9 in 45 minutes, although it does not see the win. This is well within a normal search time for mail play. I forgot the settings I used for this position, I think 768MB db cache and 64MB hashtable, but I am not sure. 
depth 27/43/26.9 time 308.11s  value=38 nodes 217051737 704kN/s pv 12-16 19x12 
depth 29/45/8.4  time 823.27s  value=34 nodes 578754627 702kN/s pv 12-16 19x12
depth 31/49/2.7  time 2733.81s value=32 nodes 1948387516 712kN/s pv 5- 9 25-22 
depth 33/52/1.1  time 7149.60s value=30 nodes 756410570 105kN/s pv 5- 9 25-22
Credits
All code in Cake is original code. However, a lot of other people have been important in the development of Cake. Jonathan Schaeffer and his Chinook project got me interested in checkers programming in the first place. I also used the Chinook endgame database for a long time until I computed my own endgame database. In the early days, Nelson Castillo and his Dama program provided me with some competition. Nelson stopped programming checkers though, and for a while I had no big incentive to improve Cake any further. Then Ed Gilbert came along and pushed me to my limits with his KingsRow engine. We discuss checkers programming frequently, which helps both of us a lot. Thomas Lincke computed the first opening book for Cake and introduced me to drop-out-expansion. George Miller kindly gave me a copy of DEO's Encyclopedia of Checkers, from which I learned a little something about checkers. George Miller, Mac Banks and Gerry Lopez made the las Vegas computer world championship possible, which made me work harder on Cake than ever before, both before and after the event. Last but not least, whenever I was tired of programming, I got a little help from the little Gecko in my office!
Back to main checkers page
Last updated by Martin Fierz on Thursday, March 20, 2003. Feedback to checkers_at_fierz.ch