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:
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-13As 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-13This 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.
Back to main checkers page - written on May 11th 2003