Breakthrough Draughts

Discussion about development of draughts in the time of computer and Internet.
Post Reply
jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Breakthrough Draughts

Post by jj » Mon Aug 07, 2017 18:24

Bert,

It may be worthwile to try PNS (proof-number search). I used it last year to solve 6x6 checkers and 6x6 draughts. With the 8-pieces databases both games are solved within a second (single thread). I didn't use a transposition table to avoid the GHI-problem, but for Breakthrough this is not an issue as there are no repetitions. But even with the 4-pieces database both games are quickly solved (checkers 12.8 sec, draughts 2.2 sec). I also solved the games using alpha-beta but this takes (a lot) longer (I don't recall the exact times).

Some 6x6 results, by the way: both games are a draw, but in 6x6 checkers the first player (White) has two losing first moves (13-10 and 14-11). In 6x6 draughts the second player (Black) has several losing first moves (replies). The longest win in the 6x6 checkers DTW 8-pieces db is 147 ply (68 consecutive king-slide-moves), for 6x6 draughts this is 83 ply. Strongly solving the games (12-pieces db's, 63,836,439,921 positions) seemed like a waste of time, but I did calculate all positions reachable from the starting positions (checkers: 27,364,174,047, draughts: 10,075,772,480).

Jan-Jaap
www.maximusdraughts.org

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

Re: Breakthrough Draughts

Post by BertTuyt » Mon Aug 07, 2017 18:45

JJ, thanks for your post.

In the meantime I got a win score from the initial position 8x8 BT Draughts for white (so the player who starts).
Single thread search 38 ply, time 3.7 hours.

Still possible that there are errors, but at least this approach seems doable.
Need to replay the pv, and will share it later.

Bert

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Breakthrough Draughts

Post by Rein Halbersma » Mon Aug 07, 2017 19:41

jj wrote:Bert,

It may be worthwile to try PNS (proof-number search). I used it last year to solve 6x6 checkers and 6x6 draughts. With the 8-pieces databases both games are solved within a second (single thread). I didn't use a transposition table to avoid the GHI-problem, but for Breakthrough this is not an issue as there are no repetitions. But even with the 4-pieces database both games are quickly solved (checkers 12.8 sec, draughts 2.2 sec). I also solved the games using alpha-beta but this takes (a lot) longer (I don't recall the exact times).

Some 6x6 results, by the way: both games are a draw, but in 6x6 checkers the first player (White) has two losing first moves (13-10 and 14-11). In 6x6 draughts the second player (Black) has several losing first moves (replies). The longest win in the 6x6 checkers DTW 8-pieces db is 147 ply (68 consecutive king-slide-moves), for 6x6 draughts this is 83 ply. Strongly solving the games (12-pieces db's, 63,836,439,921 positions) seemed like a waste of time, but I did calculate all positions reachable from the starting positions (checkers: 27,364,174,047, draughts: 10,075,772,480).

Jan-Jaap
Very interesting! I solved all the draughts variants on 6x6 almost 6 years ago using plain alpha-beta + a transposition table and no databases. Took about 15 minutes on a single thread. Only communicated this privately at the time to Ed Gilbert, but I posted about it earlier this year on the forum http://www.laatste.info/bb3/viewtopic.p ... &start=698

The code is under version control, but it was using an old version of Visual Studio and my build environment is now Linux. Going back would take a bit of effort, but if necessary I can try. My current program is not yet suited to replicate it.

Your results are consistent with mine. Can you also try the suicide variations? Or send me a PM :)

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Breakthrough Draughts

Post by TAILLE » Mon Aug 07, 2017 23:52

BertTuyt wrote:JJ, thanks for your post.

In the meantime I got a win score from the initial position 8x8 BT Draughts for white (so the player who starts).
Single thread search 38 ply, time 3.7 hours.

Still possible that there are errors, but at least this approach seems doable.
Need to replay the pv, and will share it later.

Bert
Congratulation Bert. Fine result.

I am still in the debugging phase of my db generation program and I need some more days to begin the generation.
If you have statistics available on your database maybe we will be able to exchange in order to get full confidence in our results.
My intention is to keep the following statistics for each type of position:
1) the number of legal positions
2) the number of positions without capture, white to move
3) the number of positions without capture, black to move
4) the number of winning positions without capture white to move
5) the number of winning positions without capture black to move
Gérard

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

Re: Breakthrough Draughts

Post by BertTuyt » Tue Aug 08, 2017 12:16

TAILLE wrote:
BertTuyt wrote:JJ, thanks for your post.

In the meantime I got a win score from the initial position 8x8 BT Draughts for white (so the player who starts).
Single thread search 38 ply, time 3.7 hours.

Still possible that there are errors, but at least this approach seems doable.
Need to replay the pv, and will share it later.

Bert
Congratulation Bert. Fine result.

I am still in the debugging phase of my db generation program and I need some more days to begin the generation.
If you have statistics available on your database maybe we will be able to exchange in order to get full confidence in our results.
My intention is to keep the following statistics for each type of position:
1) the number of legal positions
2) the number of positions without capture, white to move
3) the number of positions without capture, black to move
4) the number of winning positions without capture white to move
5) the number of winning positions without capture black to move
Gerard, the number of legal positions is no problem.
I dont make a difference between positions with and without capture, as I dont compress.
So I could give you the number of positions, and for that DB also the number of wins and losses.

Bert

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Breakthrough Draughts

Post by TAILLE » Tue Aug 08, 2017 20:13

BertTuyt wrote:
TAILLE wrote:
BertTuyt wrote:JJ, thanks for your post.

In the meantime I got a win score from the initial position 8x8 BT Draughts for white (so the player who starts).
Single thread search 38 ply, time 3.7 hours.

Still possible that there are errors, but at least this approach seems doable.
Need to replay the pv, and will share it later.

Bert
Congratulation Bert. Fine result.

I am still in the debugging phase of my db generation program and I need some more days to begin the generation.
If you have statistics available on your database maybe we will be able to exchange in order to get full confidence in our results.
My intention is to keep the following statistics for each type of position:
1) the number of legal positions
2) the number of positions without capture, white to move
3) the number of positions without capture, black to move
4) the number of winning positions without capture white to move
5) the number of winning positions without capture black to move
Gerard, the number of legal positions is no problem.
I dont make a difference between positions with and without capture, as I dont compress.
So I could give you the number of positions, and for that DB also the number of wins and losses.

Bert
I see, it seems difficult to help each other.
The coding of DB-generation program is now finished and I am in the debug process.
In any case this 8x8 activity gives me some interesting new idea's for the db-generation of breakthrough 10x10 game.
Gérard

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Breakthrough Draughts

Post by jj » Tue Aug 08, 2017 21:22

BertTuyt wrote:In the meantime I got a win score from the initial position 8x8 BT Draughts for white (so the player who starts).
Single thread search 38 ply, time 3.7 hours.

Still possible that there are errors, but at least this approach seems doable.
Nice result!
Rein Halbersma wrote:Very interesting! I solved all the draughts variants on 6x6 almost 6 years ago using plain alpha-beta + a transposition table and no databases. Took about 15 minutes on a single thread. Only communicated this privately at the time to Ed Gilbert, but I posted about it earlier this year on the forum http://www.laatste.info/bb3/viewtopic.p ... &start=698

The code is under version control, but it was using an old version of Visual Studio and my build environment is now Linux. Going back would take a bit of effort, but if necessary I can try. My current program is not yet suited to replicate it.

Your results are consistent with mine. Can you also try the suicide variations? Or send me a PM :)
Interesting! I can confirm:
- 6x6 suicide draughts is a White win (PNS, no db, 0.58 sec); alpha-beta finds a win after 23 nominal ply (1.44 sec), pv length 36 ply
- 6x6 suicide checkers is a draw (PNS, 4p. db, 3.68 sec)

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Breakthrough Draughts

Post by Rein Halbersma » Tue Aug 08, 2017 21:49

jj wrote:
Rein Halbersma wrote:Very interesting! I solved all the draughts variants on 6x6 almost 6 years ago using plain alpha-beta + a transposition table and no databases. Took about 15 minutes on a single thread. Only communicated this privately at the time to Ed Gilbert, but I posted about it earlier this year on the forum http://www.laatste.info/bb3/viewtopic.p ... &start=698

The code is under version control, but it was using an old version of Visual Studio and my build environment is now Linux. Going back would take a bit of effort, but if necessary I can try. My current program is not yet suited to replicate it.

Your results are consistent with mine. Can you also try the suicide variations? Or send me a PM :)
Interesting! I can confirm:
- 6x6 suicide draughts is a White win (PNS, no db, 0.58 sec); alpha-beta finds a win after 23 nominal ply (1.44 sec), pv length 36 ply
- 6x6 suicide checkers is a draw (PNS, 4p. db, 3.68 sec)
Thanks for the confirmations! Always nice to know your work is correct. Is it feasible for you to try the other variants? On this perft() thread viewtopic.php?f=53&t=2822 I describe how the rules differ (plus counts to verify your move generator).

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

Re: Breakthrough Draughts

Post by BertTuyt » Tue Aug 08, 2017 23:14

Herewith a pv I replayd, hope that Gerard can confirm the end result.

22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25 8-11 24-20 16-19 23x16 12x19 31-26 1-6 25-22 4-8 30-25 8-12 27-24 ...

Bert

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Breakthrough Draughts

Post by jj » Wed Aug 09, 2017 22:00

Rein Halbersma wrote:Thanks for the confirmations! Always nice to know your work is correct. Is it feasible for you to try the other variants? On this perft() thread viewtopic.php?f=53&t=2822 I describe how the rules differ (plus counts to verify your move generator).
Sorry, trying the other 8 variants would take quite some time, which I'd rather spend on my ongoing projects (10x10 engine redesign and -finally- generating my own 6-pieces endgame db).
I can, however, confirm your 12x12 perft counts. I wrote a general (array based) engine that can play checkers/draughts on any NxN board, and did some calculations and experiments to determine the complexity of checkers 6x6/8x8 and draughts 6x6/8x8/10x10/12x12/14x14. I will post some results in a separate thread shortly.

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

Re: Breakthrough Draughts

Post by BertTuyt » Wed Aug 09, 2017 23:53

Jan Jaap, just curiousity, how did you calculate (or measure) all positions reachable from the starting positions (checkers: 27,364,174,047, draughts: 10,075,772,480).

Bert

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Breakthrough Draughts

Post by jj » Thu Aug 10, 2017 12:27

BertTuyt wrote:Jan Jaap, just curiousity, how did you calculate (or measure) all positions reachable from the starting positions (checkers: 27,364,174,047, draughts: 10,075,772,480).
By counting them, using a non-recursive function that traverses the entire tree/graph. Non-recursive because otherwise the huge depth reached causes a stack overflow. To keep track of all positions reached, I use an array with 1 bit per position. The number of 6x6 positions for 1 color to move is 63,838,220,543, x 2 = 127,676,441,086 for both colors. This takes ~15 GB (implemented as an array of arrays of size 1 GB) which fits in RAM on my 24 GB RAM desktop computer. I also saved the database for future use.

Code: Select all

Game          SSC             % of all  Max.Depth      Time  Nodes/sec
6x6 checkers  27,364,174,047     21.4%    407,888  14:07:29    538,146
6x6 draughts  10,075,772,480      7.9%    123,536   5:33:57    502,858
For 8x8 you would need an array of 2 x 500,995,484,682,338,672,639 bits, which is a bit of a stretch. ;-)

Jan-Jaap

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Breakthrough Draughts

Post by Rein Halbersma » Thu Aug 10, 2017 12:42

jj wrote:
BertTuyt wrote:Jan Jaap, just curiousity, how did you calculate (or measure) all positions reachable from the starting positions (checkers: 27,364,174,047, draughts: 10,075,772,480).
By counting them, using a non-recursive function that traverses the entire tree/graph. Non-recursive because otherwise the huge depth reached causes a stack overflow. To keep track of all positions reached, I use an array with 1 bit per position. The number of 6x6 positions for 1 color to move is 63,838,220,543, x 2 = 127,676,441,086 for both colors. This takes ~15 GB (implemented as an array of arrays of size 1 GB) which fits in RAM on my 24 GB RAM desktop computer. I also saved the database for future use.

Code: Select all

Game          SSC             % of all  Max.Depth      Time  Nodes/sec
6x6 checkers  27,364,174,047     21.4%    407,888  14:07:29    538,146
6x6 draughts  10,075,772,480      7.9%    123,536   5:33:57    502,858
For 8x8 you would need an array of 2 x 500,995,484,682,338,672,639 bits, which is a bit of a stretch. ;-)

Jan-Jaap
If you use breadth-first-search on this tree, you would find a max.depth a lot smaller than 400K.

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Breakthrough Draughts

Post by jj » Thu Aug 10, 2017 12:48

Rein Halbersma wrote:If you use breadth-first-search on this tree, you would find a max.depth a lot smaller than 400K.
Wouldn't this require to keep (a large portion of) the entire tree in memory? That would be a problem.

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Breakthrough Draughts

Post by Rein Halbersma » Thu Aug 10, 2017 12:56

jj wrote:
Rein Halbersma wrote:If you use breadth-first-search on this tree, you would find a max.depth a lot smaller than 400K.
Wouldn't this require to keep (a large portion of) the entire tree in memory? That would be a problem.
If you have position2index and vice versa on this array, you can simply start with the initial position and scan the array repeatedly. It would be handy if you also kept an intermediate bitarray of 7.5 Gb of all positions reached in the previous iteration. Then you can iterate over all 1-bits and compute successors of all positions reached in the last iteration and add those to the base array and the next queue. Essentially this is equal to the 2-bit algorithm for database generation, I think by Wu & Beal, but here you use repeated forward passes instead of retrograde computations. It does require indexing, but if you have already that infractructure in place, it should be similar to building regular databases :)

Post Reply