Search Algorithm

[BertTuyt]

Does your curve fitting program allow to fit different types of curves? Because p can't be less than 0, the exponential model has a problem with the lower depths.

Michel, as already mentioned i use a 30-day trial program CurveExpert Professional, which has many more and different options for curve fitting.
Just try it...

Bert

[BertTuyt]

After almost 6 days, and 139 hours of calculation ( 1 Min/Game Kingsrow and average 52 Min/Game Damage) I can share the 24 ply results.
Games Won 49, Games Lost 1 !!, Draw 108, which yield an ELO around -109.
See below the updated table and attached the game .pdn file and the .xls file (with some new items..).

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
24     -109      1     49    108   0   0,65

Bert

[BertTuyt]

I have Kingsrow at 1 minute/game (its doing about 4000-5000 Knodes/second). Results up to now are:

On my i7 940 ( 2.93 GHZ) Kingsrow runs on1 core at a speed of 3000 - 4000 Knodes/second , next to that Kingsrow does not use pondering and uses a 6p DB.

At least your "plies" seem to be more effective (and i recognize that ply is not very well defined as all programs use different extensions and pruning mechanisms) than the very selective ply I use, which create more depth , but at a cost.
The effectiveness could also be related to your evaluation.

I'm curious what higher depths reveal in your case.
If Kingsrow runs with more Knodes/second (as you use 2 cores) , the program most likely will be somewhat stronger (although with parallel search you can not translate kNodes/sec directly into depth anymore) than the Kingsrow I use as a base, as a consequence the asymptotic max ELO level in your test should be somewhat smaller. But as you still see more or less linear behavior it is to early to tell..

I will also do some tests at lower ply depth with all search enhancements switched off, and measure the effect...

Last but not least, what is the average game time for Dragon at ply 12?

Bert

[MichelG]

On my i7 940 ( 2.93 GHZ) Kingsrow runs on1 core at a speed of 3000 - 4000 Knodes/second , next to that Kingsrow does not use pondering and uses a 6p DB.

At least your "plies" seem to be more effective (and i recognize that ply is not very well defined as all programs use different extensions and pruning mechanisms) than the very selective ply I use, which create more depth , but at a cost.
The effectiveness could also be related to your evaluation.

I'm curious what higher depths reveal in your case.
If Kingsrow runs with more Knodes/second (as you use 2 cores) , the program most likely will be somewhat stronger (although with parallel search you can not translate kNodes/sec directly into depth anymore) than the Kingsrow I use as a base, as a consequence the asymptotic max ELO level in your test should be somewhat smaller. But as you still see more or less linear behavior it is to early to tell..

Last but not least, what is the average game time for Dragon at ply 12?

Bert

Running on differenty computers and a different setup makes it indeed difficult to make an accurate comparision between dragon and damage this way.

At 12 plies dragon spends about 2.2 times the time of kingsrow, but that isn't a fair comparision either; kingsrow gets to choose how much time it spends on each move, but because the depth is fixed, dragon (and probably damage too) will spend most of it time on the opening phase of the game, and less on the endgame.

At 14 plies dragon takes about 15 times kingsrows time. It getting hard to play large matches.

Results up to now:

Code: Select all

Depth	ELO		W	  L	  D	  U	 P
6       280      99	 2     44	    0,17
8       159      58	 1	  74	    0,29
10       75      35    6     96       0,39
12        8      15   12     100      0,49
14                0    4     15       0,61 (+/-0,10 partial result)

[BertTuyt]

I have played some new fixed depth matches with FHR, MCP and LMR switched off ( Damage -FML ), so making the search less "selective"
Below the match results.

Code: Select all

Depth     ELO     W     L     D      U     P
8         245     96    0     62     0     0,20
10        129     60    4	  94     0     0,32
12        46      30    9     119    0     0,43
14        -4      12    14    132    0     0,51

I have also attached the match files, and an update xls file.



Bert

[BertTuyt]

Below an interesting graph of the ELO rating as a function of Ply Depth, for the 3 tests done so far (Damage, Damage - FML and the provisional Dragon results).


Bert

[MichelG]

Below an interesting graph of the ELO rating as a function of Ply Depth, for the 3 tests done so far (Damage, Damage - FML and the provisional Dragon results).


Bert

In your graph, the part with elo<0 is missing. (maybe you should flip the y-axis). It's interesting to see the effect of the FML engine.

I got the results for 14 ply. 38 games ended in unknown, so i consider to rerun the test with 100 move games instead of 75.

Code: Select all

Depth	ELO		W	  L	  D	  U	 P
6       280      99	 2     44	    0,17
8       159      58	 1	  74	    0,29
10       75      35    6     96       0,39
12        8      15   12    100       0,49
14      -55       6   25     89       0,58

[BertTuyt]

In the mean time I have also started with the 16 ply search without FHR, MCP and LMR (Damage -FML).
After 24 hours calculation (this will take same days ), 5 Wins, 14 Draws and 2 Unknowns, with an ELO so far ( not including the unknowns) of around -94.
Average game time for Damage is 67 Min (Kingsrow 1 Min/Game !).

As the match is still in progress I did not yet include the match file.
See below an updated graph, including also the latest results of Michel with Dragon.
I think some interesting comments can be made related to this graph and results. Maybe I will provide some thoughts in a next post.

Bert

[BertTuyt]

As already mentioned in the previous post, herewith some thoughts related to the most recent tests.
Basically I started the test(s), to get an indication to what extend the current programs already play "near perfect", and to what extend future hardware improvements will impact a further performance increase.

I guess that some conclusions can be drawn (but keep in mind that the test "only" cover the Damage-Kingsrow system.), where in all tests Kingsrow (1 Min/Game) was used as a base (and the tests is not meant as a comparison between Kingsrow and Damage ! ).

* Apparently there is more than 100 ELO points to gain for a program , compared with the KingsRow base.

* Curve fitting of the data, suggests that 300 ELO points gain could also be possible. As the curve expression was not based on any underlying known (and/or proven) mechanism, one has to be careful with this statement. If the 300 points is reached with almost (unrealistic) search depths, and will yield almost perfect play, than it could be possible that this 300 is a threshold for all draughs programs even on superior future hardware (the statement is however also valid that this is based on only computer-computer domain, who maybe only addresses a subspace of the draughts universe).

* It is clear that for the Damage search implementation one observes diminishing returns at a higher ply depth.

* The Damage - FML (so whithout FHR , MCP and LMR) does not reveal diminishing returns (at calculated search depth) compared to the normal Damage search (yet).

* The non-selective search ( - FML ) does yield far better move decision quality compared with the Damage search, reflected trough a better ELO score at lower search depth. Apparently the selective search "throws often to much away with the bathwater", with a negative impact on the gain per ply (so increasing the diminishing return effect).

* As the base search is still faster (22 ply base 15 min/game, ELO 81, 16 ply (provisional result) Damage -FML, 67 Min/Game ELO 84), it so far still makes/made sense to apply the selective reductions.

* It might be interesting to think about selective improvement comparing the Damage base search with the Damage - FML search.

* An interesting thought is whether based on the diminishing returns there is a cross-over for the 2 search implementations, and that the non-selective search performs better at higher plies ( so depth > 16), given a specific time-threshold ?

Bert

[BertTuyt]

After 48 hours of 16-Ply depth calculations, herewith the provisional status after 43 games ( > 25% of the match).
Games Win 7, Lost 3, Draw 30, Unknown 3, which yields an ELO rating (excluding Unknown) of around 35.
See below updated graph. It is too early to tell but does the - FML search already reveals diminishing returns..... ?


Bert

[BertTuyt]

The 16 ply match is progressing well with >40% of the games now played ( 65 Games, 7 Win, 3 Lost, 51 Draws, 4 Unknown).
Without (major) interrupts i expect the match to end during the weekend (and as usual I will post match results).
Hereafter I will start some matches with the Kingsrow search time expanded to 10 Min/Game.

Bert

[BertTuyt]

Michel, do you have an update of your match results with variable depth?
The current Damage - Kingsrow Match will (most likely) end this Sunday, so I will publish results this weekend.

Bert

[MichelG]

Michel, do you have an update of your match results with variable depth?
The current Damage - Kingsrow Match will (most likely) end this Sunday, so I will publish results this weekend.

Bert

I don't have further updates at the moment, first some bugs need to be fixed that people found and there should be a new version soon.

I eagerly await your results

Michel

[BertTuyt]

Herewith the results of the most recent match , Damage 16 Ply ( without search reductions, - FML ) and Kingsrow 1 Min.
The match took 7 days and 9 hours, so around 66 Min for every Damage game.

Code: Select all

Depth     ELO     W     L     D      U     P
8         245     96    0     62     0     0,20
10        129     60    4     94     0     0,32
12        46      30    9     119    0     0,43
14        -4      12    14    132    0     0,51
16       -49      4     26    128    0     0.57 

Attached the pdn file and the updated xls file.
The graph shows weakly diminishing returns for the Damage -FML Search.

I will now start with matches where Kingsrow will have 10 Min/Game.

Keep you all posted....

Bert

[Walter Thoen]

Bert,

Is your updated table correct?

The 16 ply result of 4 wins and 26 losses looks worse than the 14 ply result of 14 wins and 12 losses.

Or am I reading the table wrong?

Regards,
Walter