Breakthrough Draughts

[jj]

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

[BertTuyt]

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]

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]

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

[BertTuyt]

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]

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.

[jj]

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!

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]

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]

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]

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]

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]

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]

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]

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]

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