Search Algorithm

[BertTuyt]

In a previous post I shared the search extensions in Damage , Fail High Reductions (FHR), Multi Cut Pruning (MCP) and Late Move Reductions (LMR).
To better understand efficiency, i tested several combinations in short 158 games matches against Flits ( 1min each, no pondering).
Although statistics is not our friend with these numbers, it at least provides some food for thought.

Code: Select all

Search              W   L   D   ELO   File
------------------------------------------
Base               18  21  119  -7    v10
MCP                21  8   129  29    v11
LMR                24  12  122  26    v12
FHR                23  15  120  18    v13
MCP + LMR          27  10  121  38    v14
FHR + MCP          21  14  123  15    v15
FHR + LMR          20  9   129  24    v16
FHR + MCP + LMR    23  8   127  33

Bert

[BertTuyt]

During the X-mas holidays I re-tested the Damage Multi-Core search algorithms.
So far I have/had a separate algorithm for single-core and multi-core.
As i had improved the normal search the last months, I now implemented these ideas in the Multi-Core search.
To check if the algorithm was stable , I run several matches against Kingsrow, with 1 min for every Kingsrow game and 1-core, no pondering.

During these matches Damage used all 4-cores of the i7-940, and the search was restricted to a fixed depth (so no time control).
To make sure that the search implementation was solid Damage run in Debug mode (I use Visual Studio 2008 for the Engine).

During these matches, i only encountered 2 ASSERT interrupts.
One was related to a bug in the PV-Copy routine.
The other was more complex as the fault was encountered in a older part of the program (Database-Read), and I guess was related to a random error which unfortunately sometimes happens.
I will most likely post something later related this "failure".

At higher search depth i switched to Release mode, to limit the total time.
In this way 16 Matches were played, from depth 6 ply to depth 21 ply.
The results are summarized in below table, and seem to confirm diminishing returns are higher depths (i recognize that for statistics more games are needed, but think already the current results are obvious).
I have also include an excel file with the results, and a chatter chart.
In the next days i will also share all the pdn files.
I have corrected for all the unknown results, which i still need to modify in the corresponding pdn files.

Code: Select all

Depth	ELO		W	  L	  D	  U	 P
6	    412      131	0	  27	 0	0,09
7	    346      120	0	  38	 0	0,12
8	    295      109	0	  49	 0	0,16
9	    252      99	 1	  58	 0	0,19
10	   185		77	 0	  81	 0	0,26
11	   174		75	 2	  81	 0	0,27
12	   102		46	 1	  111	0	0,36
13	   62		 30	 2	  126	0	0,41
14	   55		 30	 5	  123	0	0,42
15	   15		 20	 13	 125	0	0,48
16	   11		 16	 11	 131	0	0,48
17	   -40		10	 28	 120	0	0,56
18	   -46		5	 26	  127	0	0,57
19	   -53		1	 25	  132	0	0,58
20	   -26		3	 15	  140	0	0,54
21	   -67		0	 30	  128	0	0,59

Bert

[MichelG]

Very interesting results (for both the first and second post)

I had expected that the diminishing results would be much smoother. Instead it seems that there is a quite abrupt change at about 17 ply.

[BertTuyt]

Michel, thanks for your reply.
Due to statistical variations I'm not sure if it is possible to state that there is a trend-change around ply 17.
However diminishing returns are quite obvious.
Also keep in mind that only the Kingsrow - Damage "system" has been tested so far to this extend (and with Kingsrow games based on 1 Min).
So it could be that other "systems" will show other characteristics.
I can imagine that with less advanced evaluation function, diminishing returns could occur somewhat later.
But in general I believe that the gain per additional ply will definitely reduce.

When I first joined a computer draughts tournament , my program (running on a Amiga 500) was doing 5 - 6 ply searches.
So it is obvious that we have all benefit from hardware improvements.
However these "free" improvements will not take place most likely (at least not with this order of magnitude), when we reach the search depths of 18 ply and beyond.
Especially as clock frequency seems to top at 3.5 - 4.0 GHz, and parallel processing is also not straight forward (and certainly does not yield linear performance improvement).

So i really believe we should re-focus on the evaluation function, in stead of further search-speed improvements.

I'm now doing a 22 ply test (so Damage 22 ply search and Kingsrow still 1 min game).
The 21 ply search match took 26 hours, so Damage required around ~9 min game.

Will keep you posted,

Bert

[BertTuyt]

Forgot to mention that most likely in every program the definition of a ply is different.
Also due to FHR, MCP and LMR, I ( = Damage) sometimes throw away the baby with the bathwater (which is most cases is corrected as higher ply depths.).
So I don't believe that 17 is the magic number here......

Bert

[BertTuyt]

The 158 games match with Kingsrow 1 Min/Game and Damage 22 ply search is now finished.
The match took somewhat less than 44 hours.
Match result (from the perspective of Kingsrow), 0 Win, 36 Lost and 122 Draw.
The ELO difference was 81 points.
See attached .xls file and the Match .pdn.

Code: Select all

Depth   ELO      W     L     D     U    P
6       412      131   0     27    0   0,09
7       346      120   0     38    0   0,12
8       295      109   0     49    0   0,16
9       252      99    1     58    0   0,19
10      185      77    0     81    0   0,26
11      174      75    2     81    0   0,27
12      102      46    1     111   0   0,36
13      62       30    2     126   0   0,41
14      55       30    5     123   0   0,42
15      15       20    13    125   0   0,48
16      11       16    11    131   0   0,48
17      -40      10    28    120   0   0,56
18      -46      5    26     127   0   0,57
19      -53      1    25     132   0   0,58
20      -26      3    15     140   0   0,54
21      -67      0    30     128   0   0,59
22      -81      0    36     122   0   0,61

Bert

[MichelG]

36 wins out of 158! It seems there is still some headroom for programs to increase strength at this playing speed:-)

Are you going for another ply depth or will that take too much computer time?

btw, how are you dealing with the unknowns results? Do you evaluate these manually, or did you set the number of moves per game to some high value? In a current match i am playing against kingsrow at 1 minute, 12 out of 104 games ended in 'unknown'.

[BertTuyt]

In the mean time I have started the 23 ply Match.
After 24 hours the verdict is 14 Wins for Damage 36 Draws and 2 Unknowns. Which yields an ELO rating around 100.
If no crashes occur than the match will be finished in another 48 hours.
Think 24 ply also might doable, 25 ply could be a bridge to far.

I'm very curious what happens, personally I expect the ELO to stabilize between 150 - 200 in the end.
At higher ply depths Damage (and every other program) starts to play perfectly (from the perspective of the time limited opponent).
As also the error-rate for the opponent is fixed (and assuming Draughts is a draw game) , there could be no gain anymore in further search depth increase.
However it could also be, that going deeper and deeper, the game reveals new strategies and options for winning games, so the real error rate of current programs is much larger than we might believe.

In average I encounter 6 - 12 Unknowns in every match.
I already stop the game when Damage enters into 7p (or less) DB-positions.
Even in the Draw case, i dont want Damage to win against Kingsrow (given the fact that i have a version with a limited DB).
In the most cases a very shallow search already reveals the score for an Unknown.
In many cases this is a recognized Draw (example with a 4m - 4m position) , but I did not include this mechanism in Damage yet to stop the game if for a number of fixed moves the program only "sees" DB-Draw scores (which in the Damage case is 0 ).

Bert

[BertTuyt]

In the mean time I have started the 23 ply Match.
After 24 hours the verdict is 14 Wins for Damage 36 Draws and 2 Unknowns. Which yields an ELO rating around 100.
If no crashes occur than the match will be finished in another 48 hours.

The situation after around 48 hours: 102 games, 27 Win Damage, 70 Draws and 5 Unknowns, which translates into 99 ELO points.
So 24 hours to go.......

Bert

[MichelG]

As also the error-rate for the opponent is fixed (and assuming Draughts is a draw game) , there could be no gain anymore in further search depth increase.

I think there still should be some game. As long as are game-positions that require, say a 40 ply search to find the right move (some positions in the endgame database require that for instance), searching deeper will help.

Ofcourse these positions may get very rare as search depth increases.

[Walter Thoen]

As also the error-rate for the opponent is fixed (and assuming Draughts is a draw game) , there could be no gain anymore in further search depth increase.

I think there still should be some game. As long as are game-positions that require, say a 40 ply search to find the right move (some positions in the endgame database require that for instance), searching deeper will help.

Ofcourse these positions may get very rare as search depth increases.

The benefits of search depths might be dependant on the phase of the game. Draughts engines tend to be strongest in the later stages of the game when the play is 'concrete'. In that phase deeper searching can be very important to convert advantage into wins. This is also the phase in which 'optimising chances', i.e. trying to get the opponent to make mistakes, might sometimes be more important than the analytical best move. In earlier phases in the game the search depth might be less important than good evaluation.

It might be interesting if Bert could do some test with varying search depths during a game. For instance, first 25 moves 15 ply, then 22 ply for move 26 onwards. Comparing such a strategy with a fixed 22 ply for all moves might give some insight into when searching deeper works best.

[Rein Halbersma]

The benefits of search depths might be dependant on the phase of the game. Draughts engines tend to be strongest in the later stages of the game when the play is 'concrete'. In that phase deeper searching can be very important to convert advantage into wins. This is also the phase in which 'optimising chances', i.e. trying to get the opponent to make mistakes, might sometimes be more important than the analytical best move. In earlier phases in the game the search depth might be less important than good evaluation.

This is also Georgiev's opinion. He thinks that he can outplay computers in the opening and early middle game because of his superior evaluation skills. In the late middle game / endgame, computers are superior because of the endgame databases.

[BertTuyt]

After 76 hours calculation, KingsRow 1 Min/Game, Damage 23-Ply ( so average 28 Min/Game), herewith the match results.
Damage Win 45, Draw 113, ELO around 102.
Below the updated table, and attached the xls file and the match .pdn file.

Code: Select all

Depth   ELO      W     L     D     U    P
6       412      131   0     27    0   0,09
7       346      120   0     38    0   0,12
8       295      109   0     49    0   0,16
9       252      99    1     58    0   0,19
10      185      77    0     81    0   0,26
11      174      75    2     81    0   0,27
12      102      46    1     111   0   0,36
13      62       30    2     126   0   0,41
14      55       30    5     123   0   0,42
15      15       20    13    125   0   0,48
16      11       16    11    131   0   0,48
17      -40      10    28    120   0   0,56
18      -46      5     26    127   0   0,57
19      -53      1     25    132   0   0,58
20      -26      3     15    140   0   0,54
21      -67      0     30    128   0   0,59
22      -81      0     36    122   0   0,61
23     -102      0     45    113   0   0,64

Bert

[MichelG]

At least we know there is considerable room yet to improve our programs

As you say, improvements would have to be in the evaluation function, i don't think there is any way you can make damage 30 times faster!

[Piet Bouma]

The benefits of search depths might be dependant on the phase of the game. Draughts engines tend to be strongest in the later stages of the game when the play is 'concrete'. In that phase deeper searching can be very important to convert advantage into wins. This is also the phase in which 'optimising chances', i.e. trying to get the opponent to make mistakes, might sometimes be more important than the analytical best move. In earlier phases in the game the search depth might be less important than good evaluation.

This is also Georgiev's opinion. He thinks that he can outplay computers in the opening and early middle game because of his superior evaluation skills. In the late middle game / endgame, computers are superior because of the endgame databases.

Michael Palmer has published an endgame-analysis of the game Rick Twilhaar - Dinant Spieker:
Toernooibase.
It seems that Kingsrow does not recognize the blockade-system in the endgame (8 pieces) according to a remark of Tjalling Goedemoed.
So there will be positions in the endgame where human can beat the computer......??