Breakthrough Draughts

[BertTuyt]

I have now access to my 8-core computer, and worked during the weekend on 8x8 BT Draughts.
To generate the 12P DB took 3.7 hours.
I plaid 1 game (with 32 ply search) and the win (for white) was observed after 7 moves (black to play, so 14 ply).

This would indicate a 46 ply search from the start.
I started a (unfortunately) single thread search, as I did not implement the BT parallel search yet.
After 12.5 hour the program reached 41 ply (based upon above it should be 46 ply), but still with no win/loss score.

So work to do, I might need go to 13P DB (or further as Rein predicted) , and/or use a parallel search.....


Bert

[Rein Halbersma]

I have now access to my 8-core computer, and worked during the weekend on 8x8 BT Draughts.
To generate the 12P DB took 3.7 hours.
I plaid 1 game (with 32 ply search) and the win (for white) was observed after 7 moves (black to play, so 14 ply).

This would indicate a 46 ply search from the start.
I started a (unfortunately) single thread search, as I did not implement the BT parallel search yet.
After 12.5 hour the program reached 41 ply (based upon above it should be 46 ply), but still with no win/loss score.

So work to do, I might need go to 13P DB (or further as Rein predicted) , and/or use a parallel search.....


Bert

Hi Bert,

Nice to see some progress. Could you post some search logs and end-of-PV positions after each iteration? What kind of eval are you using?

As I wrote before, the checkers solution had something like 62 ply, and with checkers men can't capture backwards, so a breakthrough is a lot easier to force:



With checkers, white can simply walk through here with h6-g7. With Brazilian draughts (international rules on 8x8 board), it's not possible as black can capture backwards f6xe8. So I expect that Brazilian draughts cannot be solved within 62 moves, perhaps in many more moves. For 10x10, I would be very surprised if it would take less than a 100 ply search to force the win without databases. Of course, databases will speed this up enormously, so hopefully you are very close already. Who knows

BTW, you can download Martin Fierz's Checkerboard + Cake + Kingscourt opening book to replay his solution: http://www.fierz.ch/download.php

[BertTuyt]

Rein, I now started to generate the 13P DB.
Memory requirements are extremely close to available memory (= 64 GByte), so I hope it works.
I expect that the generation process is finalized in the evening.

Will run some searches (if all went Okish) , and post the results...
I also did not run a verify on the DBs yet, so still possible that the program introduced some DB errors.

So conclusions (if any) are still preliminary.

Bert

[TAILLE]

Hi,

I have just built an eval function with the help of a basic breackthrought table but without any experience in draughts breackthrough I do not know if this current Damy version may be promising.

As an example let's take the Woldouby position


Black to play

With no egdb Damy takes 20" to prove the white win. Could you tell me what are your results in such configuration (i.e. no egdb)?

FYI my PV begins with
(17-22) 28x17 (21x12) 33-28 (24-29) 39-34 (29x40) 35x44 (23-29) 37-31 (26x37) 32x41 (18-23) 28-22 etc.

[BertTuyt]

Gerard, I can (and will) have a look at it, when Im done with 8x8 BT.
I need to re-modify my BT Engine towards 10x10, as it now only plays 8x8.
But I certainly will work on it.
I think Fabien has a 10x10 implementation (with EGDB, if im not wrong), so that might serve as a starting point to evaluate the strength of Damy BT.

Bert

[BertTuyt]

Rein, forgot to answer your eval question.
So far I only use material and DB.

In all cases where I see a material loss for either side, I always have seen a loss for the same side.
Only when a breakthrough is deteced the program starts to sacrifice pices (for the breakthrough).

But other then that it seems to me that material loss in an early stage is deadly in BT Draughts.

Bert

[BertTuyt]

The 13P DB was generated in 10.8 hours (from the start with 0 DB).
I will run a deep search during the night, to see if it finds final win/loss results.

Bert

[BertTuyt]

The search only reached 39 ply this night, maybe related to the larger DB which now contains upto 13 pieces.
So I need to implement parallel search.

Bert

[BertTuyt]

Herewith an example.



The following position is obtained after: 1. 23-18 12-16 2. 24-20 10-15 3. 21-17 9-13 4. 26-23 8-12 5. 25-21 5-9

(not sure if this is the official notation,)

The program now finds the win for white:

17-14 15-19 14x5 19x7 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-29 7-10 30-25 3-7 32-28 2-6 22-18 14-17 25-21 17-22 18x25 10-14 31-26 6-10 26-22 12-16 19x12 (DB)

Bert

[TAILLE]

Herewith an example.



The following position is obtained after: 1. 23-18 12-16 2. 24-20 10-15 3. 21-17 9-13 4. 26-23 8-12 5. 25-21 5-9

(not sure if this is the official notation,)

The program now finds the win for white:

17-14 15-19 14x5 19x7 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-29 7-10 30-25 3-7 32-28 2-6 22-18 14-17 25-21 17-22 18x25 10-14 31-26 6-10 26-22 12-16 19x12 (DB)

Bert

Hi Bert,

I am not able to appreciate 39 plies in a 8x8 breackthrought draughts context. Considering your experience what could be the equivalent in 10x10 breackthrought draughts context or in 10x10 international draughts context? Do you use a use a sophisticated eval function to reach such result?

I have some questions concerning your db but I do not know if it is a secret for you !?
1) What is the size of your 13 pieces db ?
2) Do you store in your db the positions with capture ?
3) I guess you use an SSD. If it is the case what is the size of the blocks you read on the SSD ?

[BertTuyt]

Hi Bert,

I am not able to appreciate 39 plies in a 8x8 breackthrought draughts context. Considering your experience what could be the equivalent in 10x10 breackthrought draughts context or in 10x10 international draughts context? Do you use a use a sophisticated eval function to reach such result?

I have some questions concerning your db but I do not know if it is a secret for you !?
1) What is the size of your 13 pieces db ?
2) Do you store in your db the positions with capture ?
3) I guess you use an SSD. If it is the case what is the size of the blocks you read on the SSD ?

Gerard, I dont know how to value the 8x8 search depth in comparison with 10x10, but I will find out later this year.

I dont use a evaluation function, other than material and DB, as I expect with sufficient search-depth, and a DB of size 12P-14P, to weakly solve the game.

1) The size of the 13P DB is 76.8 GByte
2) To speed up the search I use a raw DB format, so captures included, and 8 positions (win or loss) per byte.
3) I use a Samsung SSD (1 TByte), and blocksize is 4KByte.

Bert

[TAILLE]

Hi Bert,

I am not able to appreciate 39 plies in a 8x8 breackthrought draughts context. Considering your experience what could be the equivalent in 10x10 breackthrought draughts context or in 10x10 international draughts context? Do you use a use a sophisticated eval function to reach such result?

I have some questions concerning your db but I do not know if it is a secret for you !?
1) What is the size of your 13 pieces db ?
2) Do you store in your db the positions with capture ?
3) I guess you use an SSD. If it is the case what is the size of the blocks you read on the SSD ?

Gerard, I dont know how to value the 8x8 search depth in comparison with 10x10, but I will find out later this year.

I dont use a evaluation function, other than material and DB, as I expect with sufficient search-depth, and a DB of size 12P-14P, to weakly solve the game.

1) The size of the 13P DB is 76.8 GByte
2) To speed up the search I use a raw DB format, so captures included, and 8 positions (win or loss) per byte.
3) I use a Samsung SSD (1 TByte), and blocksize is 4KByte.

Bert

Oops very quick answer! Thank you Bert.

What do you mean by raw DB format? If my calculation is correct the number of positions for all the 2-13 pieces db is about 2 642 G positions that means 330 Gbyte for a strict raw db. Do you use a compression to gain a factor 5 in order to reach 76.8 GByte ?

[BertTuyt]

Gerard, the number op positions in the BT Databases P2 - P13 is 659.715.926.649.
The number of 4KB blocks needed is 20.132.973 which yields 78.6 GB.

Bert

[BertTuyt]

Even with the 13P DB the program was not able to find the final win/loss from the inital position.
After 18.7 hours (single core search) reaching ply 42, still a 0-score.

So I will go towards the 14P DB, for which I need to optimize the program further, as it (only) scales towards 13P (within the limit boundaries of 64GB).
I could also go towards a parallel search, but I need to modifiy the DB program anyway, to go beyond 13P.

The P2 - P14 contains 1.634.806.066.916 positions and 49.890.372 4KB blocks.

Bert

[TAILLE]

Gerard, the number op positions in the BT Databases P2 - P13 is 659.715.926.649.
The number of 4KB blocks needed is 20.132.973 which yields 78.6 GB.

Bert

I guess you are right but I do not see where is my bug in my calculation of the number of positions. Can you help me?
Let's take only the positions with 7 white men against 6 black men.
The number of positions for the 7 white pieces is (28*27*26*25*24*23*22)/(2*3*4*5*6*7) = 1.184.040
The number of positions for the 6 black pieces is (28*27*26*25*24*23)/(2*3*4*5*6) = 376.740
Of course I perfectly know that it is not completly correct to multiply theses 2 numbers because we cannot have a white man AND a black man on the same square but I guess you did not add this complexity to diminish the number of positions!
The number of 7x6 positions is then 1.184.040 * 376.740 = 446.075.229.600
and you must multiply this number by 2 in order to take into account who is on the move.
Finaly the number of 7x6 positions is 892.150.459.200 which is already far higher than your figure (659.715.926.649)
Where am I wrong?