Code: Select all
Match Result 1 2 3 4 5 6 Tot.
---------------------------------------
Alexander Schwarzman 1 2 1 1 1 1 7
Maximus 1 0 1 1 1 1 5
Hardware: Intel Core i7-3930K @ 3.2 GHz 32GB RAM, a 6-core with hyperthreading
OS: Windows 7 pro 64-bit
Java 1.7 HotSpot 64-bit server VM
Maximus version 0.92
Besides the hardware, the main difference between this Maximus version and the previous one is time management. Until now Maximus only had a fixed time per move mode. This means implementing the time controls of the match (50 moves in 2 hour followed by 25 moves in 1 hour and finally 20 seconds per move) and the Fischer-time system for a possible tie-break (5 minutes plus 5 seconds per move). Also I had to spend some time on online broadcasting of the games (including clock information) while connected to the digital draughts board.
As I suppose everyone can confirm, using variabele time per move does a little bit better than fixed time. A test match of Maximus 5min/75moves vs. Maximus 5sec/move (using 6 threads each) was won by the former: +10 -5 =143 51.6%. The fixed time "olympic" version before won matches against Flits (+14 -12 =132 50.6%) and Truus (+19 -14 =125 51.6%) using 3:1 threads on my old quad core computer.
Maximus settings for the Schwarzman match were: 12 search threads (10 for pondering), a hash table of 128M entries and an egdb of 2-6 pieces (generated by Michel Grimminck & Harm Jetten). The Java process uses 6.5 GB RAM in total. A 19 ply search from the initial position takes 418.77 seconds (25172 kN/s).
Alexander Schwarzman won the match, IMHO fully deserved. As a draughts player I am very impressed by his play, even without recognizing all hidden combinations. He was the better strategic player. Game 2 will haunt me for a while. The match-losing move seems te be 37...6-11?, played after a 27 ply search (10 minutes) with a relative search value of -0.37. I can only reproduce this move with an empty hash table, then Maximus switches from 12-18 to 6-11 at ply 23 and back again at ply 27 and beyond. The next move in the game the score dropped to -0.89. Nevertheless the game continued to be exciting (nerve-wracking, actually) as Alexander Schwarzman was in time trouble. He played his 50th move with 9 seconds left and then it was game over for Maximus.
But even before Maximus played some bad moves in this game, mainly 26...3-8? as mentioned by Wieger Wesselink. Also Kingsrow shows a number of "minor" mistakes by Maximus adding up to a major advantage for white. The evaluation function failed to recognize the trouble black was in for too long in this game. In games 1 and 3 Maximus played well but could not cause Schwarzman more than a little trouble (analytically speaking). In game 4 Maximus took a big risk weakening its left wing but defended well, and in game 5 Maximus could have been again in trouble if Schwarzman hadn't played 26...22-28. In game 6, I took a chance by anticipating a short wing lock opening (KVO, which Maximus doesn't like to be in!) in a "kamikaze" attempt to win the last game. But again Schwarzman played very well, although Kingsrow dares to suggest a few better moves, e.g. 37.47-42! instead of 48-42.
In contrast to playing (automated matches) against other programs, when playing against a human grandmaster one has to consider some additional things. What if your opponent finds a weak spot in your opening book and follow-up, like in games 2 and 4 with black? To address this and to keep things interesting I programmed Maximus to play a different first move in every game, even a risky one in game 6. Of course in a longer match you cannot keep doing this...
Then, you definitely don't want to lose on time - or worry about this during the game. I used an operator-time setting of 5 seconds per move. Only for Maximus' moves that is, Schwarzman's moves were transmitted automatically from the board to Maximus. And an additional "buffer" of 1 minute per hour. This worked fine; probably 4 seconds operator-time would have been sufficient to keep the internal and external clocks in sync and to have at least 2 minutes left at move 50.
There was already enough stress. My digital board adapter appeared broken on arrival but could be replaced. During the first 2 games I had to enter Schwarzman's moves by hand because somehow ftp could not work through the Hotel network. This was solved on day 3 with help of Hotel IT support. During game 5 the adapter (which I forgot to switch off after the previous games) died making loud noises, so again I had to switch to hand control - and used some of the buffer time. Draughts as an ICT sport!
My conclusion is that Maximus' evaluation function (which I consider to be still relatively light-weight) is not good enough against a player of this calibre, despite all the brute force. "Sometimes" it is wrong, not only in magnitude but more importantly in sign ("better for white or black?"). As in game 2, where the search cannot make up for a group of poorly evaluated (or just difficult) positions in the middle game, leading to bad moves 10-15 moves before. The search algorithm can also be improved, but I think that the most important issue is (missing) knowledge. Of course the programmer in me is a bit disappointed that "we" lost and did not make it to the blitz tie-break, but the draughts player and researcher in me is happy with the result. It was a privilege to play a world champion and I look forward to a possible revenge match.
So, at least for this match, Alexander Georgiev is right: "In draughts, human has more chances against the computer than in chess. In chess, concrete playing begins from the first moves, and even in these cases, the computer may give an incorrect evaluation sometimes, for instance, after positional sacrifices. And in draughts, concrete playing often begins in the second half of the game, so there is a chance to make advantage in the first half..." (viewtopic.php?f=65&t=3344&start=420#p92843).
I can see how I can work towards not losing, but winning is another matter. The fact remains that in 10x10 draughts no computer program has ever beaten a (former) world champion in a serious game, 20 years after Truus beat Tsjizjov in a blitz game.
Jan-Jaap
Some statistics from the Maximus log files:
Code: Select all
Opponent:
#moves 342
#ponder hit 185 54% (incl. forced moves)
Maximus:
#book 52 15% (avg. 8.7 per game)
#forced 23 7%
#search 267 78%
#ignored 2 1%
-----
344
avg. search depth 24.5 ply
avg. Knodes/sec 23357
avg. search time 232.98 sec
I also did a 19-ply search from the initial position using 1 search thread and this takes Maximus 2339 seconds (3994 kN/s). Compared to Damage - 823 seconds (on a 9% slower CPU?) - this is 2.8 x as long. The Damage node count is even 5.8 x less! 
) 