World Draughts Forum

It is currently Mon Nov 20, 2017 20:05

All times are UTC+01:00




Post new topic  Reply to topic  [ 183 posts ]  Go to page 1 2 3 4 513 Next
Author Message
 Post subject: Breakthrough Draughts
PostPosted: Mon Jul 24, 2017 11:44 
Offline

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


Top
   
PostPosted: Mon Jul 24, 2017 12:32 
Offline

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

Image

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


Top
   
PostPosted: Mon Jul 24, 2017 15:26 
Offline

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


Top
   
PostPosted: Mon Jul 24, 2017 15:47 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
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

Image
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.

_________________
Gérard


Top
   
PostPosted: Mon Jul 24, 2017 16:22 
Offline

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


Top
   
PostPosted: Mon Jul 24, 2017 16:28 
Offline

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


Top
   
PostPosted: Mon Jul 24, 2017 23:41 
Offline

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


Top
   
PostPosted: Tue Jul 25, 2017 09:37 
Offline

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


Top
   
PostPosted: Tue Jul 25, 2017 11:11 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith an example.

Image

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


Top
   
PostPosted: Tue Jul 25, 2017 16:35 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
Herewith an example.

Image

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 ?

_________________
Gérard


Top
   
PostPosted: Tue Jul 25, 2017 17:03 
Offline

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


Top
   
PostPosted: Tue Jul 25, 2017 17:54 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
Quote:
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 ?

_________________
Gérard


Top
   
PostPosted: Wed Jul 26, 2017 11:30 
Offline

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


Top
   
PostPosted: Wed Jul 26, 2017 12:23 
Offline

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


Top
   
PostPosted: Wed Jul 26, 2017 13:41 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
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?

_________________
Gérard


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

All times are UTC+01:00


Who is online

Users browsing this forum: Bing [Bot] 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