Progress in Computer Checkers

In my brief computer checkers history, I described some of the more important programs, and their achievements. At the end of that article, I quoted Martin Bryant, programmer of Colossus, who wrote in 1990:

Some fear has been expressed that in five or ten years computers will be able to beat the World Champion "every time" or even "solve" the game completely. Well I've been in this field for a long time and in my opinion computers will NOT be able to beat the World Champion in any of our lifetimes and will NEVER be able to "solve" the game completely.

I didn't say why he was wrong about that - this article tries to explain how much better the programs are now than they were then, and why. In my opinion, over the last 10 years, a lot of progress has been made in four areas:

Endgame databases
Around the time of Martin's quote, Chinook was the only program with endgame databases, and it only had a 6-piece endgame database. Today, all good PC programs have an 8-piece endgame database. Why is this so important? Let's take a look at another statement of Martin Bryant, this time from 1992:

The following notes should clear things up and highlight an interesting weakness of all computers in such positions, which humans should try to utilise!
10-14 22-17 14-18 23x14 9x18 26-23 6-9 23x14 9x18 30-26 5-9 26-23 9-14 17x10 7x14 24-19 3-7 28-24 11-16?(a) 25-22 18x25 29x22 7-10(b) 32-28! 1-5(c) 24-20 2-6(d) 20x11 8x24 28x19 6-9* 22-18!*(e) 9-13* 18x9 5x14 31-26 13-17(f) 27-24 4-8 24-20 17- 22 26x17 8-11 17-13 11-15 13-9 15x24 23-19* 14-18 21-17*(g) White Win (S.Carlin v N.Proffitt, 1992 British Home Internationals, from a slightly different move order)

(a) It now seems almost certain that this is a dead loss!
(b) If 16-20? then 22-18 1-5 18x9 5x14 31-26 wins.
(c) 8-11? loses to 24-20. Richard Pask comments that "Fortman considers 2-6* immediately, drawable (though very messy), but Tinsley believes White can force a win in the ending. Certainly not a practical proposition anyway!"
(d) The proposed drawing move.
(e) Improving on 31-26.
(f) If 4-8 then 26-22* wins for White (NOT 27-24? as Black does not oblige with 13-17 back into trunk but plays 8-11* winning for Black by 26-22 [as 24-20? forms Drummond's position, see Famous Positions p.151, when Black wins by 11-15 19-16 12x19 23x16 14-18 etc.] then 11-15 24-20 15x24 22-18 24-28 18x9 10-15) after 13-17 22x13 8-11 27-24 11-15 13-9* (24-20? is not back into trunk as the move is different!) 15-18 9-6 etc. back into trunk.
(g) Black's king is not quite fast enough to save the day as after 24-27 9-6 27-31 6-2 31-27 2-7 Black unfortunately has to waste a move to save the vulnerable man on 18. Now the important point about computer analysis of this (and other similar types of positions) is the length of the longest losing variation. Given the position at note (a) there are 40 moves until Black actually loses a piece! Even taking into consideration that most good computer programs don't 'count' captures as part of their 'length- of-line' measurement, there are still 30 non-captures. This is way beyond Colossus' ability and even that of Chinook's. Earlier this year Chinook walked straight into the famous Dunne's loss because the longest losing sequence was just beyond it's lookahead capability. No strong human would fall into that trap because they 'recognise' the position. Colossus is protected from it by it's massive opening's book knowledge. Yet Chinook, which can hold it's own with the very top grandmasters, played a 'boner' par excellence. So if you want to beat a computer, like any other opponent, you must play to their weaknesses. Try to get them to play into a very deep strategic loss (which is often 'obviously bad' to a human), possibly involving a grip of some sort, which doesn't pay dividends until many moves later. Now I've given away one of the computers Achilles heels, I may reveal some more in the future! They've got plenty!!

I decided to check whether computers could see these lines today. The problem with his note (a) is that 11-16 is not a clear loser because of note (c), Fortman's improvement 2-6. So I had Cake Sans Souci 1.02 (with learning disabled, naturally) check out the position after the 1-5 loser. Here's what it comes up with when it uses the 6-piece database (P4 1.4GHz)

depth 21/35/21.2  time 1.59s  value=22  nodes 881496  554kN/s  db 100%  pv 24-20  2- 6 20x11  8x24 28x19  6- 9 31-26  4- 8 
depth 23/37/23.6  time 4.45s  value=16  nodes 2335263  524kN/s  db 100%  pv 24-20  2- 6 20x11  8x24 28x19  6- 9 31-26  4- 8 
depth 25/40/25.0  time 7.74s  value=52  nodes 4036216  521kN/s  db 100%  pv 24-20  2- 6 20x11  8x24 28x19  6- 9 22-18  9-13 
depth 27/41/26.6  time 14.39s  value=102  nodes 7328209  509kN/s  db 100%  pv 24-20  2- 6 20x11  8x24 28x19  6- 9 22-18  9-13 
depth 29/44/29.4  time 25.48s  value=102  nodes 12735492  499kN/s  db 100%  pv 24-20  2- 6 20x11  8x24 28x19  6- 9 22-18  9-13 
depth 31/47/32.5  time 122.37s  value=122  nodes 57663879  471kN/s  db 100%  pv 24-20  2- 6 20x11  8x24 28x19  6- 9 22-18  9-13
As you can see, it needs about 15 seconds to display a score that shows that it sees that it's winning a man (>100). For this, it searched to a nominal depth of 27 ply. Cake extends certain lines, and so it can see the win of the man already at 27 ply instead of the 33 necessary to really win the man in the end. Now look what the 8-piece database does: I did this search with the same P4 1.4GHz machine, giving Cake Sans Souci only 64MB database cache:
depth 13/22/12.8  time 0.06s  value=16  nodes 34422  573kN/s  db 75%  pv 24-20  5- 9 20x11  8x24 28x19  4- 8 22-18  8-11 
depth 15/26/14.6  time 0.22s  value=110  nodes 87422  397kN/s  db 64%  pv 24-20  8-11 27-24  4- 8 31-27  2- 7 22-18 14-17 
depth 17/27/16.0  time 0.33s  value=102  nodes 147953  448kN/s  db 64%  pv 24-20  8-11 27-24  5- 9 22-18 11-15 18x11  9-13
This time, Cake only needs 0.22 seconds to see the win, that's about 70 times faster than with the 6-piece database. Why is this? After 15x24 in the main line of the above analysis, only 8 pieces are left on the board. Without further search, an 8-piece program now knows that this position is a win. As you can see, this knowledge managed to replace a 12-ply search difference.
Opening books
In the beginning of the Chinook project, Chinook often lost games due to a blunder in the opening - in one famous game it lost to Karl Albrecht by falling into Dunne's trap. Many checkers openings traps are very deep, and are not visible to the programs even on long thinks (several minutes) with an 8-piece database. That is the reason why the programs need opening books. The "early" Chinook had a small opening book with only a few thousand positions. For the Tinsley matches, they acquired Martin Bryant's Colossus book, which is said to have had around 40'000 moves in it. Even then, it lost a game against Don Lafferty because he was able to surprise it with a cook - which had been prepared by Tinsley for the Chinook-Tinsley match. Today's top programs have much larger books than Chinook had - for example, my private opening book has about 400'000 moves, and the Nemesis book has over a million moves. This huge amount of book knowledge greatly improves the programs, and reduces the chance of catching them by surprise somewhere.
Algorithms
This area is a bit hard to compare, since the "old" programs are not around for comparison. Cake Sans Souci is a huge improvement over older versions of Cake++, and the change is mainly due to better pruning algorithms. The "classic" computer program searches every possible move order to a fixed depth, then evaluates the positions. Humans do something completely different - they only look at some lines, and discard others instantly. I have attempted to make Cake Sans Souci more human-like in this respect - to be able to discard certain lines of play if they look bad. This has to be done very carefully, so as not to fall into man-down traps, which is what happened to Cake Las Vegas at the computer world championship. I'm pretty certain that Cake Sans Souci had the best pruning algorithms in the checkers program world at the time of it's release, but of course the other programmers took note and started working on their pruning too! Another area where I believe programs are better today is in the evaluation. Again, this is hard to prove. The best example for this seems to me to be one of the very last games Chinook ever played, against Ron King in the 1996 US nationals. King blundered early in the game, and was completely lost, but Chinook let the win slip by allowing King to bottle up it's kings in a corner. King blundered again, and lost. It believe Chinook had a clear weakness in it's evaluation code that this could happen. I've been analyzing all Chinook's games of US national tournaments and will write more about this later!
Computers
Computers today are much faster than 10 years ago, have more memory and more harddisk space available. This allows the use of the 8-piece endgame database on normal PCs today, and of course, the programs run much faster. This trend is likely to go on for the next 10 years or even Moore!

Back to main checkers page - written on May 11th 2003