Breakthrough Draughts
Re: Breakthrough Draughts
Hi Bert,BertTuyt wrote:Rebooting of the system is not very helpful when you are doing calculations for days
Anyway, after some interrupts, now 4 moves proved as a loss.
2318, 2117, 2420, 2319
So with the already proved 2218, 2 moves to go.
And on my other computer I already proved 2217 as a loss.
So 1 move down only
Very strange that only 1 move is winning, think noone sees a logical explanation for this (yet).
Maybe in a galaxy far far away......
In the beginning I also thought that black was winning, which I now understand.
Based upon games with random moves ordering, you might come to this wrong conclusion.
I'm also afraid, that we for ages we wont have a clue what the BT 10x10 outcome will be.
My educated guess would be a white win, but for unknown reasons.
Bert
I think I have a logical statistic explanation to propose.
Look at the statistics on symmetrics configuration:
1x1 NCW1= 388 NCL1= 306
2x2 NCW1= 56 410 NCL1= 33 269
3x3 NCW1= 2 699 916 NCL1= 1 255 259
4x4 NCW1= 56 865 877 NCL1= 20 714 313
5x5 NCW1= 613 334 701 NCL1= 177 227 198
6x6 NCW1= 3 751 257 816 NCL1= 893 491 452
7x7 NCW1= 14 036 633 965 NCL1= 2 910 252 528
8x8 NCW1= 34 000 336 726 NCL1= 6 522 909 535
You see clearly that NCW1/NCL1 grows regularly to reach more than 5 for 8x8. It is simply a confirmation of a basic fact: when the position looks equal the side to move has the best chance to win!
For a 8x8 position the side to move has really more than 80% chance of winning.
Based on this consideration I would claim without calculation that the starting position (a 12x12 position) is certainly a winning position (more than 80% chance of winning).
Let's go a little farther: after any of the 7 legal white moves from the starting position it is now black to move and the 7 positions looks again quite egal. That means that on average more than 80% of these positions are winning for black point if view.
As a conclusion you see we have to expect two things:
1) The starting position has very good chances to be a winning position
2) The number of winning moves in the starting position is probably very low
Is it still very strange for you to have only one winning move?
My guess is that it is also true for the 10x10 BT game!
Gérard

 Posts: 1669
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Breakthrough Draughts
Gerard's reasoning was first made in 1981 as a statistical property of game trees. Citing Uiterwijk and Van den Herik (2000, see http://citeseerx.ist.psu.edu/viewdoc/su ... 1.109.3661):
And let's not forget that 8x8 BT checkers (aka Kingscourt) is a secondplayer win!In 1981, David Singmaster [25,26] proved a rather conclusive and elegant
theorem why firstplayer wins should abound over secondplayer wins. The
positions in a game with two outcomes (won, lost) are split up into Ppositions
(from which the previous player can force a win) and Npositions (from which
the next player can force a win). For the first player to have a forced win, just
one of the moves needs to lead to a Pposition. For the second player to have a
forced win, all of the moves must lead to Npositions. For games with three
outcomes, possible draws can be easily included in this line of reasoning,
stating that firstplayer wins should abound over draws and secondplayer
wins.
Re: Breakthrough Draughts
Gerard/Rein, thanks for your reactions.
I meant that from a visual point of view, it is for me not clear why there is only 1 winning move 2218.
I can imagine that moving to the edges is not as optimal.
But (not looking to the statistics) why all other moves fail, is a riddle.
And how to include these nuances in an evaluation function is another challenge.
So I also think that BT 10x10 is winning for white.
But does anyone dare to state (already) that there is only 1 winning move (for example) 3228
Bert
I meant that from a visual point of view, it is for me not clear why there is only 1 winning move 2218.
I can imagine that moving to the edges is not as optimal.
But (not looking to the statistics) why all other moves fail, is a riddle.
And how to include these nuances in an evaluation function is another challenge.
So I also think that BT 10x10 is winning for white.
But does anyone dare to state (already) that there is only 1 winning move (for example) 3228
Bert
Re: Breakthrough Draughts
Hi,BertTuyt wrote:Gerard/Rein, thanks for your reactions.
I meant that from a visual point of view, it is for me not clear why there is only 1 winning move 2218.
I can imagine that moving to the edges is not as optimal.
But (not looking to the statistics) why all other moves fail, is a riddle.
And how to include these nuances in an evaluation function is another challenge.
So I also think that BT 10x10 is winning for white.
But does anyone dare to state (already) that there is only 1 winning move (for example) 3228
Bert
Of course nobody knows what would happen for BT 10x10 but for sure the winning line is very narrow and obviously our programs will make a lot of mistakes in the 30 first moves. The point is the following : when you give your opponent a position which looks equal the probability is very high that your opponent has a winning position!!!
I will not surprise if more than 50% of the first 30 moves played by our programs are really mistakes!
As a consequence I consider the BT 10x10 game far more difficult than the international 10x10 draughts game.
Gérard
Re: Breakthrough Draughts
Did someone already try the Scan BT version?
Interesting what a 1000 (or other large number) game match self play (example both programs on 10 Ply, or whatever) would learn.
As we all tend to believe that it is a white win, every black win would than contain at least one error.
In the meantime also 2217 recognized as a loss.
So when 2419 is solved, I most likely can confirm the claim that only 2218 wins.
Bert
Interesting what a 1000 (or other large number) game match self play (example both programs on 10 Ply, or whatever) would learn.
As we all tend to believe that it is a white win, every black win would than contain at least one error.
In the meantime also 2217 recognized as a loss.
So when 2419 is solved, I most likely can confirm the claim that only 2218 wins.
Bert
Re: Breakthrough Draughts
It took some time, but also on my side the result is now confirmed that 2218 remains a win, and all other initial moves are a loss.
I will take now a short break, before restarting.
Bert
I will take now a short break, before restarting.
Bert
Re: Breakthrough Draughts
Good confirmation Bert,BertTuyt wrote:It took some time, but also on my side the result is now confirmed that 2218 remains a win, and all other initial moves are a loss.
I will take now a short break, before restarting.
Bert
In addition, on the 6 losing white move, black has on average 2,5 winning moves which is higher than I expected.
Anyway, on the best defense, the winning line seems very narrow!
After having looked at some other positions I admit I am completly unable to find any clue for deciding between winning and losing position.
Two examples:
White to play : losing position!
white to play
The only winning move here is maybe the most doubtful move 2117!!
Very strange indeed.
I am just able to make pure statistics reasonning.
Gérard
Re: Breakthrough Draughts
Gerard, herewith some data.
In below table I have listed at which ply which move was proved.
Keep in mind that due to different ply definitions, extensions or pruning, not all plies are equal, among programs.
Maybe it also gives a clue about the complexity of the path.
Bert
In below table I have listed at which ply which move was proved.
Keep in mind that due to different ply definitions, extensions or pruning, not all plies are equal, among programs.
Maybe it also gives a clue about the complexity of the path.
Code: Select all
Ply Move Score

30 2319 Loss
32 2420 Loss
33 2318 Loss
33 2117 Loss
35 2217 Loss
36 2419 Loss
37 2218 Win
Re: Breakthrough Draughts
Hope that Fabien would be able to provide a Scan 8x8 BT with a evaluation based upon ML.
If the Scan 8x8 BT Database is limited (example 6P), we could really learn what the error rate is for the search (as a function of ply).
If Scan 8x8 BT would play white, every lost game would at least contain 1 error (assuming that the other side is the all knowing DB).
Bert
If the Scan 8x8 BT Database is limited (example 6P), we could really learn what the error rate is for the search (as a function of ply).
If Scan 8x8 BT would play white, every lost game would at least contain 1 error (assuming that the other side is the all knowing DB).
Bert
Re: Breakthrough Draughts
Gerard, do you have already an insight for all initial while losing moves (for example 2319), how many moves on black side are winning.
For 2319 at least the 1216 move (which immediately loses 1 man), seems to me already losing for black.
Bert
For 2319 at least the 1216 move (which immediately loses 1 man), seems to me already losing for black.
Bert
Re: Breakthrough Draughts
Hi Bert,BertTuyt wrote:Gerard, do you have already an insight for all initial while losing moves (for example 2319), how many moves on black side are winning.
For 2319 at least the 1216 move (which immediately loses 1 man), seems to me already losing for black.
Bert
The complete answer to your question is the following:
2218 winning move
2420 losing move; 3 black winning moves : 1116, 1115, 913
2319 losing move; 4 black winning moves : 1116, 913, 914, 1115
2117 losing move; 1 black winning move : 913
2419 losing move; 3 black winning moves : 1116, 1014, 1115
2318 losing move; 3 black winning moves : 1216, 1115, 1116
2217 losing move; 1 black winning move : 1115
On average : 2,5 black winning moves on 7 possible moves
You can note some strange results like 2420? 913 and white has a losing position!
Gérard
Re: Breakthrough Draughts
It's nice to see a draughtslike game not ending in a almostcertain draw. I'll do some experiments with it as well.
I created a BT endgame database for 10x10. Can any of you confirm the numbers if you have 10x10 available?
Michel
I created a BT endgame database for 10x10. Can any of you confirm the numbers if you have 10x10 available?
Code: Select all
Solved 1  1: wins= 1.148, size= 1.985, rate=0.0 Mpos/sec
Solved 2  1: wins= 35.925, size= 42.790, rate=0.1 Mpos/sec
Solved 1  2: wins= 13.785, size= 42.790, rate=0.1 Mpos/sec
Solved 2  2: wins= 567.700, size= 903.440, rate=0.9 Mpos/sec
Solved 3  1: wins= 545.176, size= 600.710, rate=0.9 Mpos/sec
Solved 1  3: wins= 137.563, size= 600.710, rate=1.0 Mpos/sec
Solved 3  2: wins= 9.794.441, size= 12.416.680, rate=5.8 Mpos/sec
Solved 2  3: wins= 5.540.861, size= 12.416.680, rate=5.9 Mpos/sec
Solved 3  3: wins= 107.237.253, size= 166.991.800, rate=17.4 Mpos/sec
Solved 4  1: wins= 5.811.821, size= 6.175.015, rate=4.3 Mpos/sec
Solved 1  4: wins= 1.141.870, size= 6.175.015, rate=6.0 Mpos/sec
Solved 4  2: wins= 106.895.851, size= 124.899.950, rate=16.2 Mpos/sec
Solved 2  4: wins= 42.802.678, size= 124.899.950, rate=17.1 Mpos/sec
Solved 4  3: wins= 1.244.935.203, size= 1.642.957.750, rate=22.9 Mpos/sec
Solved 3  4: wins= 822.763.214, size= 1.642.957.750, rate=21.2 Mpos/sec
Solved 4  4: wins=10.175.184.347, size=15.802.050.675, rate=14.5 Mpos/sec
Re: Breakthrough Draughts
Hi Michel,MichelG wrote:It's nice to see a draughtslike game not ending in a almostcertain draw. I'll do some experiments with it as well.
I created a BT endgame database for 10x10. Can any of you confirm the numbers if you have 10x10 available?
MichelCode: Select all
Solved 1  1: wins= 1.148, size= 1.985, rate=0.0 Mpos/sec Solved 2  1: wins= 35.925, size= 42.790, rate=0.1 Mpos/sec Solved 1  2: wins= 13.785, size= 42.790, rate=0.1 Mpos/sec Solved 2  2: wins= 567.700, size= 903.440, rate=0.9 Mpos/sec Solved 3  1: wins= 545.176, size= 600.710, rate=0.9 Mpos/sec Solved 1  3: wins= 137.563, size= 600.710, rate=1.0 Mpos/sec Solved 3  2: wins= 9.794.441, size= 12.416.680, rate=5.8 Mpos/sec Solved 2  3: wins= 5.540.861, size= 12.416.680, rate=5.9 Mpos/sec Solved 3  3: wins= 107.237.253, size= 166.991.800, rate=17.4 Mpos/sec Solved 4  1: wins= 5.811.821, size= 6.175.015, rate=4.3 Mpos/sec Solved 1  4: wins= 1.141.870, size= 6.175.015, rate=6.0 Mpos/sec Solved 4  2: wins= 106.895.851, size= 124.899.950, rate=16.2 Mpos/sec Solved 2  4: wins= 42.802.678, size= 124.899.950, rate=17.1 Mpos/sec Solved 4  3: wins= 1.244.935.203, size= 1.642.957.750, rate=22.9 Mpos/sec Solved 3  4: wins= 822.763.214, size= 1.642.957.750, rate=21.2 Mpos/sec Solved 4  4: wins=10.175.184.347, size=15.802.050.675, rate=14.5 Mpos/sec
Good news to see your interesting by this beautitul draughts variant.
As with Bert I have the same difficulty with you : I did not generate the capture positions. Bert managed to add statitistics on non capture position in order to compare our figures but I do not know if it is easy for your implementation to do the same.
FYI my figures are
1x1 NCW1= 1 028 NCL1= 837 NCW2=  NCL2= 
2x1 NCW1= 30 993 NCL1= 6 865 NCW2= 11 268 NCL2= 26 595
2x2 NCW1= 424 883 NCL1= 285 789 NCW2=  NCL2= 
3x1 NCW1= 446 168 NCL1= 55 534 NCW2= 113 391 NCL2= 388 438
3x2 NCW1= 6 778 061 NCL1= 1 948 633 NCW2= 3 775 435 NCL2= 4 952 702
3x3 NCW1= 63 546 643 NCL1= 35 985 469 NCW2=  NCL2= 
4x1 NCW1= 4 518 137 NCL1= 363 194 NCW2= 927 678 NCL2= 3 954 768
4x2 NCW1= 67 423 737 NCL1= 11 426 249 NCW2= 28 548 951 NCL2= 50 312 655
4x3 NCW1= 652 076 102 NCL1= 184 976 683 NCW2= 438 218 089 NCL2= 398 830 286
4x4 NCW1= 4 486 519 068 NCL1= 2 080 557 566 NCW2=  NCL2= 
Gérard

 Posts: 1669
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Breakthrough Draughts
Hi Gerard,TAILLE wrote: Hi Michel,
Good news to see your interesting by this beautitul draughts variant.
As with Bert I have the same difficulty with you : I did not generate the capture positions. Bert managed to add statitistics on non capture position in order to compare our figures but I do not know if it is easy for your implementation to do the same.
FYI my figures are
1x1 NCW1= 1 028 NCL1= 837 NCW2=  NCL2= 
2x1 NCW1= 30 993 NCL1= 6 865 NCW2= 11 268 NCL2= 26 595
2x2 NCW1= 424 883 NCL1= 285 789 NCW2=  NCL2= 
3x1 NCW1= 446 168 NCL1= 55 534 NCW2= 113 391 NCL2= 388 438
3x2 NCW1= 6 778 061 NCL1= 1 948 633 NCW2= 3 775 435 NCL2= 4 952 702
3x3 NCW1= 63 546 643 NCL1= 35 985 469 NCW2=  NCL2= 
4x1 NCW1= 4 518 137 NCL1= 363 194 NCW2= 927 678 NCL2= 3 954 768
4x2 NCW1= 67 423 737 NCL1= 11 426 249 NCW2= 28 548 951 NCL2= 50 312 655
4x3 NCW1= 652 076 102 NCL1= 184 976 683 NCW2= 438 218 089 NCL2= 398 830 286
4x4 NCW1= 4 486 519 068 NCL1= 2 080 557 566 NCW2=  NCL2= 
Is it possible for you to modify your routine so as to print the capture positions after the last generation pass? And then drop them for the final compression stage? Or would this be a too invasive change of your generator?
Rein
Re: Breakthrough Draughts
I don't quite understand your question.Rein Halbersma wrote:
Hi Gerard,
Is it possible for you to modify your routine so as to print the capture positions after the last generation pass? And then drop them for the final compression stage? Or would this be a too invasive change of your generator?
Rein
Basically my routine looks like:
for (db = first db; db < last db; db = following db)
{
for (p = first position of the db; p < last position; p = following position)
{
if (p == capture position) continue;
else {generate successors; evaluate p; save result in memory db}
}
compress memory db and store on disk;
}
Of course I added some complexity in order to have a multithread routine
Gérard