World Draughts Forum

It is currently Mon Nov 20, 2017 12:32

All times are UTC+01:00




Post new topic  Reply to topic  [ 712 posts ]  Go to page 1 2 3 4 548 Next
Author Message
 Post subject: Search Algorithm
PostPosted: Wed Dec 19, 2012 19:51 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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:
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sat Jan 05, 2013 23:21 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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:
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


Attachments:
Fixed Depth MutiCore.xls [39 KiB]
Downloaded 220 times
Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Jan 06, 2013 14:51 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 233
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Jan 06, 2013 15:29 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Jan 06, 2013 16:04 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Jan 07, 2013 20:54 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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:
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


Attachments:
dxpgames_P22.pdn [164.2 KiB]
Downloaded 184 times
Fixed Depth MutiCore.xls [39 KiB]
Downloaded 240 times
Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Jan 07, 2013 23:57 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 233
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'.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Tue Jan 08, 2013 21:56 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Jan 09, 2013 23:15 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Quote:
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Jan 11, 2013 08:45 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 233
BertTuyt wrote:
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Jan 11, 2013 13:54 
Offline

Joined: Wed Nov 17, 2010 13:26
Posts: 44
Real name: Walter Thoen
MichelG wrote:
BertTuyt wrote:
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Jan 11, 2013 14:58 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Walter Thoen wrote:
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Jan 11, 2013 17:13 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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:
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


Attachments:
Fixed Depth MutiCore.xls [39 KiB]
Downloaded 215 times
dxpgames_P23.pdn [164.25 KiB]
Downloaded 182 times
Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Jan 11, 2013 20:35 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 233
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!


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Jan 11, 2013 22:39 
Offline

Joined: Sun Nov 02, 2003 13:05
Posts: 3340
Location: Harlingen
Rein Halbersma wrote:
Walter Thoen wrote:
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......??


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 712 posts ]  Go to page 1 2 3 4 548 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 7 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 Limited