World Draughts Forum

It is currently Tue Jul 22, 2014 20:29

All times are UTC + 1 hour




Post new topic Reply to topic  [ 48 posts ]  Go to page Previous  1, 2, 3, 4  Next
Author Message
PostPosted: Sat Apr 21, 2012 12:10 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 76
Location: Zeist, Netherlands
Some information on the match Maximus-Schwarzman (April 9-14 2012, Heerhugowaard)

Code:
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

Games: http://toernooibase.kndb.nl/opvraag/standen.php?taal=1&kl=23&Id=2628&jr=12&afko=&r=

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:
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

_________________
www.maximusdraughts.org


Last edited by jj on Wed Apr 25, 2012 11:31, edited 1 time in total.

Top
 Profile E-mail  
 
PostPosted: Sat Apr 21, 2012 12:59 
Offline

Joined: Tue Sep 01, 2009 16:31
Posts: 145
I thank for information Jan-Jaap with game. I have such two questions. Whether there are photographs from this match as well as whether the equipment on which you played was yours or somebody lent to you it for the purposes of the match.


Top
 Profile  
 
PostPosted: Sat Apr 21, 2012 15:11 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 76
Location: Zeist, Netherlands
Krzychumag wrote:
I thank for information Jan-Jaap with game. I have such two questions. Whether there are photographs from this match as well as whether the equipment on which you played was yours or somebody lent to you it for the purposes of the match.

You can see some photos at http://www.nkdammen2012.nl/, scroll down to the 'liveshare' part; the daily reports have more photos. The computer I used is my own.

_________________
www.maximusdraughts.org


Top
 Profile E-mail  
 
PostPosted: Fri Apr 27, 2012 10:45 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1181
Hi Jan-Jaap,

Thanks for your elaborate match report! Could you tell us a bit more about the search algorithm / eval that you used? A rough calculation from your numbers indicates an average branching factor of 2.5 and a branching factor of 3.4 for the initial position. This is far below the average number of legal moves for typical searches. Do you use aggressive reductions (e.g. LMR) to achieve that? And how fine-grained is your eval? centipawns, milipawns? What type of patterns does the eval contain?

Rein


Top
 Profile  
 
PostPosted: Fri Apr 27, 2012 17:25 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 856
I did a short check with Damage.
1 core search (although I also have implemented the parallel YBWC algorithm), 19 Ply , 823 sec, 1,900,000,000 nodes , 2309 KNodes/Sec.
My processor is an Intel i7 940 2.93 Ghz.

Bert


Top
 Profile  
 
PostPosted: Fri Apr 27, 2012 18:31 
Offline

Joined: Thu Apr 26, 2007 17:51
Posts: 612
Location: FRANCE
Hi Bert,

BertTuyt wrote:
I did a short check with Damage.
1 core search (although I also have implemented the parallel YBWC algorithm), 19 Ply , 823 sec, 1,900,000,000 nodes , 2309 KNodes/Sec.
My processor is an Intel i7 940 2.93 Ghz.

Bert


In Damy I can see several kind of nodes:
1) an internal node or a leaf
2) a node with or without a hastable access
3) a node with or without an eval calculation
4) a node corresponding to a position in the egdb
5) ...
With only the first 3 criteria I can see 8 differents nodes and you can probably add some other criterias.

What do you mean yourself by "node" in the calculation you mentioned above?

_________________
Gérard


Top
 Profile  
 
PostPosted: Fri Apr 27, 2012 22:07 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 856
Gerard,

In my case a node is both an internal node (independent on hash-cut off, evaluation, etc) as a leaf node.
The number of leaf nodes (19 ply search from the initial position) was 917.000.000 nodes.

Bert


Top
 Profile  
 
PostPosted: Fri Apr 27, 2012 23:12 
Offline

Joined: Thu Apr 26, 2007 17:51
Posts: 612
Location: FRANCE
Bert,

BertTuyt wrote:
Gerard,

In my case a node is both an internal node (independent on hash-cut off, evaluation, etc) as a leaf node.
The number of leaf nodes (19 ply search from the initial position) was 917.000.000 nodes.

Bert


Let me know if I understand correctly:
Suppose your are on a node at depth 18 and you generate 10 leaves. Then you analyse the first leaf to discover a cutoff. According to your above explanation you count the 10 leaves, even if only one of them has been evaluated. Correct?

I have another question. Taking into account reduction, extension and pruning I am completly unable to say in Damy what is the depth of a given search. What means 19 ply for Damage?

_________________
Gérard


Top
 Profile  
 
PostPosted: Fri Apr 27, 2012 23:34 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 856
Gerard,

basically a node is just another recursive call to the search-routine.
Hereafter you can get into a hash-cut, evaluation routine, DB access, or just another search-routine entry...
I increase the node-counter every time i enter the (recursive) search-routine.

So in case of the cutoff, i only increase the counter with 1.

As i also use extensions and pruning/reduction mechanisms and ...., I also display the average-search depth and the maximum search-depth.

For the mentioned 19-ply search these values are: 19 (nominal), 24.7 (average) 39 (maximum).

Hope this helps..

Bert


Top
 Profile  
 
PostPosted: Sat Apr 28, 2012 10:22 
Offline

Joined: Thu Apr 26, 2007 17:51
Posts: 612
Location: FRANCE
Hi Bert,

BertTuyt wrote:
Gerard,

basically a node is just another recursive call to the search-routine.
Hereafter you can get into a hash-cut, evaluation routine, DB access, or just another search-routine entry...
I increase the node-counter every time i enter the (recursive) search-routine.

So in case of the cutoff, i only increase the counter with 1.

As i also use extensions and pruning/reduction mechanisms and ...., I also display the average-search depth and the maximum search-depth.

For the mentioned 19-ply search these values are: 19 (nominal), 24.7 (average) 39 (maximum).

Hope this helps..

Bert


Thank you Bert, now it is clearer. Is it a good understanding if I say that you increase also the node counter every time you enter the (recursive) Q-search routine?
Unfortunetly this "node" definition seems not significant for Damy due to various time consuming micro-search looking for a quick cutoff.
As a simple example see the following figure
Image
Black to play
Damy find immediatly the move 20-24! by using a micro-search and the main search mechanism will continue by using first this move leading to a clear cutoff.

I understand more or less what means 19 ply. In conjonction with the number of nodes (here 917.000.000) it gives an idea of the reduction-extension mechanism. In your case that means that your branching facteur is less than 3. Is it a good number or not? I do not know and that is the question!
My view is the following: an evaluation function cannot be perfect. In some situation it could be very good and in another it could be not satisfactory at all. One of the major goal of the search mechanism is to try and reach a better evaluation of a position. In other words I consider that the search mechanism must help the evaluation function to find the best evaluation of the position. In a position where you consider the result of the evaluation function reliable, then a reduction may be applied, but in a rather unstable position you may apply an extension (very common in the Q-search isn't it?).
We all know it is very easy (a stupid pruning reach this objective) to reach 50 plies with only 1.000.000.000 positions but this is not significant isn't it?
Without a better criteria, the number of plies gives a interesting indication but we have to be here very cautious!

_________________
Gérard


Top
 Profile  
 
PostPosted: Wed May 02, 2012 18:24 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 76
Location: Zeist, Netherlands
Rein Halbersma wrote:
Hi Jan-Jaap,

Thanks for your elaborate match report! Could you tell us a bit more about the search algorithm / eval that you used? A rough calculation from your numbers indicates an average branching factor of 2.5 and a branching factor of 3.4 for the initial position. This is far below the average number of legal moves for typical searches. Do you use aggressive reductions (e.g. LMR) to achieve that? And how fine-grained is your eval? centipawns, milipawns? What type of patterns does the eval contain?

Rein


Hi Rein,

I don't use LMR but I do use some form of forward pruning - which I really should look further into. LMR is also interesting to look at because I already use the History Heuristic; move ordering is important of course. The evaluation function mainly contains patterns for runaways (table), outposts and locks. Of course there are other terms as well. Just before the match I changed from millipawns to centipawns.

But you (we) should really be asking these questions to Bert et.al. ;-) 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!

BTW, for me every call to alphabeta() is a node, no matter if it turns out a hash or egdb or eval or internal node. My maximum depth is also 39; I don't keep the average depth.

Jan-Jaap

_________________
www.maximusdraughts.org


Top
 Profile E-mail  
 
PostPosted: Sat Aug 25, 2012 22:36 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 856
I have started with a complete rebuild of Damage (Engine Version 12).
I have worked during the holiday on the search, and unfortunately dont had the time to also work on the Evaluation Function (which also needs to be modified, due to differences in the base data-structures).

I have now implemented in the PVS-based search : MCP (Multi Cut Pruning, pruning fail-high nodes), FHR (Fail-High Reduction, pruning fail-high nodes), LMR (Late Move Reduction, pruning Fail-Low Nodes), SMD (Singular Move Detection) and "LSD" (Legal/Illegal Sacrifice Detection).
SMD/LSD, not yet activated in the current test-suite.

The bad news, Unfortunately the implementation fails in some positions and i sometimes "throw away the baby with the bathwater", so more work to do.
But the good news, the 19 ply search at the initial position now takes around 10 seconds with 1 core!

Bert


Top
 Profile  
 
PostPosted: Mon Aug 27, 2012 11:58 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 76
Location: Zeist, Netherlands
Hi Bert,

Thanks for the update. 10 seconds is really impressive! (Work to do for me :shock:)
Have you played a new match yet to see if it plays stronger?

JJ

_________________
www.maximusdraughts.org


Top
 Profile E-mail  
 
PostPosted: Mon Aug 27, 2012 22:22 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 856
JJ,

yes i did run a 158-games test match.
But only to test the robustness/reliability of the new search-routine, and to check if the program would crash (which did not happen).
I did not activate all the new search-code which i have implemented, nor did i tune the related parameters.
Next to that i have changed some other routines completely (to deal with the new data-structure, like evaluation breakthrough routines ) which i also did not test in detail yet.

Anyway the match result (10 min game, 1 core, no pondering) from the perspective of KingsRow 23 losses , 3 wins , 132 draws, which was for me surprisingly good (to be honest), for the first "buggy" implementation.
For the first time at least I see that (from a nominal point of view) the Damage search-depth exceeds the search-depth of KingsRow (but there is still some issues with the baby and the bathwater)...

What is the actual score of Maximus?

Bert


Top
 Profile  
 
PostPosted: Wed Aug 29, 2012 18:06 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 76
Location: Zeist, Netherlands
Bert,

So -- Damage 23 wins and Kingsrow 3 wins?! :shock:

No new results for Maximus... I've been working on the match report Schwarzman-Maximus for ICGA Journal.

JJ

_________________
www.maximusdraughts.org


Top
 Profile E-mail  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 48 posts ]  Go to page Previous  1, 2, 3, 4  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group