Search Algorithm

Discussion about development of draughts in the time of computer and Internet.
Post Reply
BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Jan 27, 2013 13:31

You are right I reversed Win and Loss, in the mean time I have corrected this.
Thanks for posting your remark.

Bert

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Sun Jan 27, 2013 16:32

Hi Bert,

I made an analysis of the 4 losses that Damage suffered in the ply 16 match. See the analysis attached.

It is of course a very small number of games but my assessment would be that the losses are more the result of inadequate evaluation than that the 16 ply search was inadequate. Especially the evaluation of breakthrough versus material balance seems to be a problem.

In any event, I enjoyed analysing the games. Keep posting more match results!

Regards,
Walter
Attachments
Damage analysis of games lost.pdf
(240.18 KiB) Downloaded 334 times

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Sun Jan 27, 2013 23:23

I analysed the first two losses in the PF14 match as well.
Attachments
PF14 Match analysis.pdf
(156.24 KiB) Downloaded 341 times

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Sun Jan 27, 2013 23:26

Analysing these losses sometimes makes you wonder "what was he thinking?!" :D

I think that I will have to analyse some wins as well to be fair to Damage.

Walter

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Mon Jan 28, 2013 22:13

Walter, very much appreciate your analysis and feedback.
Analyzing these losses sometimes makes you wonder "what was he thinking?!" :D
Yes, also for me it is sometimes/often a mystery what happens within Damage under the surface.

As already mentioned in another post, Im now running 10 Min/Game matches, and expect to have time during the weekend to dig somewhat deeper in the specific positions you analyzed.
In any event, I enjoyed analyzing the games. Keep posting more match results!
I have now finished the first 10 Min/Game Match (with Damage 16 Ply).
As soon as I have several match results, and also the first "insights" in the specific Depth-ELO curve, i will share and post all results.

Bert

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Tue Jan 29, 2013 20:25

I made some text corrections

Walter
Attachments
Damage analysis of games lost.pdf
(240.75 KiB) Downloaded 326 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Feb 02, 2013 11:32

Herewith the first results of the Matches in which Damage plays with fixed depth search and Kingsrow has 10 Min/Game.
In the mean time I also have started with the 22 ply Match.
After the 22 Ply Math I guess some (preliminary) conclusions can be drawn.

Code: Select all

Depth     ELO     W     L    D      U     P
12        176     74    0    84     0     0,27
14        104     46    0    112    0     0,35
16        49      23    1    134    0     0,43
18        38      18    1    138    0     0,45
20        2       6     5    147    0     0.50
I'm very much interested in the analysis (Wallter you are welcomed...) why Damage and Kingsrow lost some games (especially in the ply 20 Match).
Attached .pdn match files.
As the number of attachment is limited to 5, I will in another post include the 20 Ply Match pdn and excel file.

Bert
Attachments
dxpgames_10P18.pdn
(158.07 KiB) Downloaded 259 times
dxpgames_10P16.pdn
(157.29 KiB) Downloaded 267 times
dxpgames_10P14.pdn
(158.04 KiB) Downloaded 273 times
dxpgames_10P12.pdn
(155.37 KiB) Downloaded 260 times
DDD-20130202.png
DDD-20130202.png (14.72 KiB) Viewed 8992 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Feb 02, 2013 11:33

And here the 20 Ply Match pdn and xls file.

Bert
Attachments
Fixed Depth MutiCore.xls
(59.5 KiB) Downloaded 298 times
dxpgames_10P20.pdn
(159.03 KiB) Downloaded 266 times

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Sat Feb 02, 2013 23:31

I'm very much interested in the analysis (Wallter you are welcomed...) why Damage and Kingsrow lost some games (especially in the ply 20 Match).
Bert,

See attached the analysis.

I have concentrated again on the Damage losses as it might be easier to learn from them than from wins.

I might look at the Kingsrow losses later, but I am also having fun implementing GUIDE (exchanging moves between webpage and engine works now).

Regards,
Walter
Attachments
10P20 Match Analysis.pdf
(441.64 KiB) Downloaded 322 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Feb 03, 2013 21:54

Walter, thank you very much for the analysis so far.
I will do some re-searches with Damage later this week, to really understand what he was thinking.
In the mean time I have started with the 22 Ply search, which will be finalized on Tuesday.

So hereafter I will take some time for your analysis.
After this I will also start the 24 Ply search, which will take 8 days or so.
Most likely the 24 ply Match will be the last in a series for now, as I want to focus next on the "why does Damage sometimes loose", and how to improve.

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Tue Feb 05, 2013 21:49

Herewith the results of the 22 Ply Match.

Code: Select all

Depth     ELO     W     L    D      U     P
12        176     74    0    84     0     0,27
14        104     46    0    112    0     0,35
16        49      23    1    134    0     0,43
18        38      18    1    138    0     0,45
20        2       6     5    147    0     0.50
22        2       6     5    147    0     0.50
So (by coincidence) the Ply 22 results are equal to the Ply 20 results.

In the mean time I have found a small bug, which does occur once or twice during a match, and which resulted in the loss of game 29 ( 16 Ply -FML Match, as analyzed by Walter).
Also the same bug was responsible for the loss (game was draw) during this match (game 142 move 60).

Anyway this Damage - Kingsrow system at least reveals some diminishing returns, and (next to that) it seems really difficult for Damage to really move below the other ELO side..
I will now focus on detecting the bug (although it has a small overall impact, I want to get rid of it), and hereafter will run the 24 ply match.

Attached the excel file and pdn match file.

Bert
Attachments
Fixed Depth MutiCore.xls
(60.5 KiB) Downloaded 282 times
dxpgames_10P22.pdn
(159.2 KiB) Downloaded 282 times
DDD-20130205.png
DDD-20130205.png (14.78 KiB) Viewed 8867 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Wed Feb 06, 2013 21:34

Think I solved the bug.
Did a quick test with a 10 Ply search ( versus ) a 10 Min/Game Kingsrow.

See below table, and attached the usual files.

Code: Select all

Depth     ELO     W     L    D      U     P
10        299    110    0    48     0     0,15
12        176     74    0    84     0     0,27
14        104     46    0    112    0     0,35
16        49      23    1    134    0     0,43
18        38      18    1    138    0     0,45
20        2       6     5    147    0     0.50
22        2       6     5    147    0     0.50
Bert
Attachments
Fixed Depth MutiCore.xls
(61.5 KiB) Downloaded 308 times
dxpgames_10P10.pdn
(152.99 KiB) Downloaded 270 times
DDD-20130206.png
DDD-20130206.png (15.76 KiB) Viewed 8839 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Feb 16, 2013 21:01

One of the things on my to-do list is to share sources.
So herewith the first one related to the Damage MoveGenerator.
(in .doc format, otherwise I was not able to store the files :) ).

I'm not a hyper/ultra c/c++ expert like Rein, but anyway.

If you have suggestions, ideas, questions, please let me know....

Bert
Attachments
CMoveGen64_h.doc
(27.5 KiB) Downloaded 285 times
CMoveGen64_cpp.doc
(66.5 KiB) Downloaded 279 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Feb 16, 2013 21:45

In the mean time (before starting a 24 ply search) I also worked on the Hybrid version ( Horizon 4.0) with Damage search and Horizon evaluation (with Kingsrow 10 Min/Game).
As mentioned before I will share all sources (including the .exe), for this Hybrid version.

I was interested to see if this system behaves in a similar way as seen in the tests before.

Code: Select all

Depth     ELO     W     L    D      U     P
14        191     80    1    77     0     0,25
16        114     52    2    104    0     0,34
18        55      29    4    125    0     0,42
It is evident that the Horizon evaluation is not as effective as Damage.
The explanation for this is not obvious, as the Horizon evaluation is quite large, and seem to include all relevant information.
The Horizon evaluation is also quite time-consuming (which is reflected in the relatively low nodes/sec count), but for a fixed depth search this has no impact (as Kingsrow does not ponder in between moves).

I'm now doing a 20 ply search to check if also here we will observe diminishing returns.
I also expect that with increasing search-depth the difference between the 2 evaluations will become less !

Keep you all posted,

Bert

* As usual attached the match .pdn files.
Attachments
dxpgames_H10P18.pdn
(159.31 KiB) Downloaded 289 times
dxpgames_H10P16.pdn
(158.51 KiB) Downloaded 222 times
dxpgames_H10P14.pdn
(155.33 KiB) Downloaded 243 times
Fixed Depth MutiCore.xls
(62.5 KiB) Downloaded 258 times
DDD-20130216.png
DDD-20130216.png (16.87 KiB) Viewed 8782 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Feb 16, 2013 22:40

I have added to the program the option to generate a .log file, to see what was cooking below the surface.
I might add other information in the future.
If you have special request, items you think should be included, let me know, so I can work on this.

Herewith the .log file for the most recent 18 Ply Search Match.

If you also want to receive the .log files for the 14 ply and 16 ply Matches, just drop a line....

Bert
Attachments
DXPMatch_H10P18.zip
(2.84 MiB) Downloaded 231 times

Post Reply