Internet engine matches

[BertTuyt]

Rein, I normally save versions every X months after all kind of modifications.
But not this time

Anyway I'm confident that after all changes in the pipeline i will get there.
And if there is an undetected change i will find it, as i try to check/improve line by line.
It also could be that the 2 first matches were just lucky shots (although statistics indicated something else)..

Bert

[Rein Halbersma]

Rein, I normally save versions every X months after all kind of modifications.
But not this time

Anyway I'm confident that after all changes in the pipeline i will get there.
And if there is an undetected change i will find it, as i try to check/improve line by line.
It also could be that the 2 first matches were just lucky shots (although statistics indicated something else)..

Bert

I use the Mercurial distributed version control system (for an intro http://hginit.com/), which is similar to Git that most open source programs use. I save my changes every day and it's super easy to roll back to any point in time. For the last 2 years I had almost 500 different commits. It's simply not practical to manually save all that in different directories, you really should let a version control system do that for you.

Rein

[BertTuyt]

Herewith the most recent match results.
Unfortunately the last match was terminated after 105 games due to an auto update from Windows (and a computer restart).

Code: Select all

Date            W    L    D    U    P     P%

16-sep-2012     7    3   148   0   162   51,3%
28-sep-2012    14    7   137   0   165   52,2%

1-Oct-2012      4   11   143   0   151   47,8%
10-oct-2012     2    8   148   0   152   48,1%
13-oct-2012     5   11   141   1   151   48,1%
16-oct-2002     4   11   143   0   151   47,8%
19-Oct-2012     3    9   146   0   152   48,1%
23-Oct-2012     5    9   143   1   153   48,7%

25-Oct-2012     2    5   150   1   154   49,0%
28-Oct-2012     5    8   145   0   155   49,1%
30-Oct-2012     3    5   150   0   156   49,4%

5-nov-12	     9	10   139	0	157	49,7%
12-nov-12	    5	 6   147	0	157	49,7%
19-nov-12	    4	 2    99	0	107	51,0%

Although I don't trust statistics any more I get the feeling I'm closing the gap...
At least the last match was promising (but it is just quantum mechanics).

Bert

[Rein Halbersma]

Herewith the most recent match results.
Unfortunately the last match was terminated after 105 games due to an auto update from Windows (and a computer restart).

Code: Select all

Date            W    L    D    U    P     P%

16-sep-2012     7    3   148   0   162   51,3%
28-sep-2012    14    7   137   0   165   52,2%

1-Oct-2012      4   11   143   0   151   47,8%
10-oct-2012     2    8   148   0   152   48,1%
13-oct-2012     5   11   141   1   151   48,1%
16-oct-2002     4   11   143   0   151   47,8%
19-Oct-2012     3    9   146   0   152   48,1%
23-Oct-2012     5    9   143   1   153   48,7%

25-Oct-2012     2    5   150   1   154   49,0%
28-Oct-2012     5    8   145   0   155   49,1%
30-Oct-2012     3    5   150   0   156   49,4%

5-nov-12	     9	10   139	0	157	49,7%
12-nov-12	    5	 6   147	0	157	49,7%
19-nov-12	    4	 2    99	0	107	51,0%

Although I don't trust statistics any more I get the feeling I'm closing the gap...
At least the last match was promising (but it is just quantum mechanics).

Bert

Hi Bert,

What time controls do you use for these matches? Have you tried running 10,000 games with 1 second per move? (= max 3 minute per game x 6 cores = 120 games per hour = 3,000 games per day = 3 days of work).

Rein

[BertTuyt]

I use 10 minutes/game for each side, so around 3 games/hour, 158 games in around 2 days.
Also based on suggestions from Michael, I will test what happens with extreme time settings ( so 1 min/move) for either side, and also will study the impact of extreme short matches (such as 1 minute/game).

Bert

[BertTuyt]

Based on forum suggestions I played 3 158-games matches with short time control (so 1 min/game for Damage/Kingsrow), 2 minutes total game time.
Below the result from the perspective of Damage.
So a close overall victory for Kingsrow, think ELO difference for the 3 combined matches is around 1 point or so.
Will continue with 2 matches were one side has 10 Min/Game and the other 1/Min.

Code: Select all

Date           W   L   D
--------------------------
22-Nov-2012    12  15  131
22-Nov-2012    14  13  131
23-Nov-2012    15  15  128
--------------------------
Total          41  43  390

Bert

[Walter Thoen]

That's a crucial point. Searching a combination is essential in draughts and it is also quite essentiel to avoid searching a combination in positions where you do not need a combination to take an advantage! That is the main idea of my new algorithm. I try to avoid searching unuseful combinations in order to have more time to search deeper combinations for other positions.
To answer your question, in the position with the extra men at 1 and 50 I do not consider it is a waste of time to search a combination similar to the previous one!

I find the discussions in this topic about the optimisations of the search algorithm to find tactical chances very interesting. However, with the introduction of more and more cores in the processors (and the new 50-core co-processor like the Xeon Phi) I have been wondering whether it is still the best approach to have one search algorithm that is distributed over as many cores as possible and try to optimise for everything or whether it would be better to use multiple search algorithms and then compare the 'best moves' returned by each search.

For instance, you can have a workstation with 16 Xeon E5 cores and 50 Xeon Phi cores for less than $10,000 these days. You can distribute the search over all these cores or you could run the 'normal' search on a lower number of cores and run special searches on the other cores to avoid missing tactical opportunities or to try a deeper search but with simplified evaluation.

Is there anything known about this?

[Rein Halbersma]

That's a crucial point. Searching a combination is essential in draughts and it is also quite essentiel to avoid searching a combination in positions where you do not need a combination to take an advantage! That is the main idea of my new algorithm. I try to avoid searching unuseful combinations in order to have more time to search deeper combinations for other positions.
To answer your question, in the position with the extra men at 1 and 50 I do not consider it is a waste of time to search a combination similar to the previous one!

I find the discussions in this topic about the optimisations of the search algorithm to find tactical chances very interesting. However, with the introduction of more and more cores in the processors (and the new 50-core co-processor like the Xeon Phi) I have been wondering whether it is still the best approach to have one search algorithm that is distributed over as many cores as possible and try to optimise for everything or whether it would be better to use multiple search algorithms and then compare the 'best moves' returned by each search.

For instance, you can have a workstation with 16 Xeon E5 cores and 50 Xeon Phi cores for less than $10,000 these days. You can distribute the search over all these cores or you could run the 'normal' search on a lower number of cores and run special searches on the other cores to avoid missing tactical opportunities or to try a deeper search but with simplified evaluation.

Is there anything known about this?

There a few related algorithms: here's a story about 3-hirn (2 computers + 1 human)
Furthermore, Monte Carlo simulation is a kind of multi-game playout strategy that could easily be done with different engine versions in parallel

[BertTuyt]

Herewith the 3 pdn files related to the 1 min/Game matches.

Bert

[BertTuyt]

The thought to use 2 different algorithms in parallel is interesting.
In my memory 3-hirn was a test from Ingo Althofer where he used 2 engines, and in case the engines suggested different moves he made the choice.

The ideas which I had, and basically the Damage engine architecture support such an implementation, is to use a normal search with a "heavy" evaluation, and a parallel search which was only based on material evaluation.
So the idea was that the second search would very fast long term combinations and promotions, and in case there was not such an opportunity the move would be based on the "normal" search.
I have never tested this actually, but i might do this when i have some spare time..

And also the Monte Carlo approach which yielded breakthrough performance in Go, is also something i might consider in the (near) future.

Bert

[Krzychumag]

Bert and you can make available Damage12.1

[Catherine]

Thanks Bert for posting the games, Ithink that it will be usefull for us.

[MichelG]

There a few related algorithms: here's a story about 3-hirn (2 computers + 1 human)
Furthermore, Monte Carlo simulation is a kind of multi-game playout strategy that could easily be done with different engine versions in parallel

I tried to implement Monte Carlo in dragon a while back, but it did not work very well. The main problem i think is that the moves that you pick should not be complete nonsense, and that requires a search of at least a few ply.

But then it takes to much time to complete the required number of games.

When i played the MC version of dragon against the normal one, the MC was losing all games because of tactics. Ofcourse, one can think of many improvements (combining it with a deep tactic search would be one), and an increasing number of cores will favour MC more. (Anyone thinking of running it's engine on a 3200 core GPU?)

Michel

[BertTuyt]

I have now finished several matches with Kingsrow playing at 1 Min/Game, and Damage with variable time settings.
Results are summarized in below table.

Code: Select all

Min/Game  W   L   D     ELO
---------------------------
2         16  3   139   29
4         14  5   139   20
8         25  2   131   51
10        30  3   125   60

Result from the perspective of Damage.

In Computer Chess several experiments indicate an ELO gain of 50 - 70 points for every doubling of speed.
Maybe the game of Draughts is different and/or we already are in the Diminishing region, remains an open question, for now.
At least in this case the gain is significant smaller, 60 ELO-points for a 10-fold speed increase.
If one assumes that for the ELO improvement the next formula can be applied (and for 1 Min/Game for both ELO difference is 0):

Code: Select all

Delta ELO = Constant * LOG(F)

then for the case F = 10 and Delta ELO is 60 the Constant becomes 60.
With linear regression the value for Constant appears to be 56 ( R2 = 0.85 ).

Although statistics can be approved this seems to be an interesting result, as I expect that for longer search (such as 10 Min/Game - 100 Min/Game) we might see more diminishing returns.

I will do the test ( 1 Min/Game for Damage, and 10 Min/Game for KingsRow) to see if the Constant ( here 56), will be reproduced...
I'm very interested if (based on self play or other experiences) similar results have been observed int he past.

Bert

[BertTuyt]

The match with Kingsrow 10 Min/Game and Damage 1 Min/Game resulted in:
27 wins, 1 loss and 130 draws (from the perspective of Kingsrow).

This yields an ELO difference of 58 points (at least based on my ELO calculator), which is remarkable in line with the previous match results.

For those interested the games attached.

Bert