Breakthrough Draughts

Discussion about development of draughts in the time of computer and Internet.
Post Reply
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Breakthrough Draughts

Post by TAILLE » Wed Sep 20, 2017 22:52

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.
23-18, 21-17, 24-20, 23-19
So with the already proved 22-18, 2 moves to go.
And on my other computer I already proved 22-17 as a loss.
So 1 move down only

Very strange that only 1 move is winning, think no-one 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
Hi 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

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

Re: Breakthrough Draughts

Post by Rein Halbersma » Thu Sep 21, 2017 07:23

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):
In 1981, David Singmaster [25,26] proved a rather conclusive and elegant
theorem why first-player wins should abound over second-player wins. The
positions in a game with two outcomes (won, lost) are split up into P-positions
(from which the previous player can force a win) and N-positions (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 P-position. For the second player to have a
forced win, all of the moves must lead to N-positions. For games with three
outcomes, possible draws can be easily included in this line of reasoning,
stating that first-player wins should abound over draws and second-player
wins.
And let's not forget that 8x8 BT checkers (aka Kingscourt) is a second-player win!

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

Re: Breakthrough Draughts

Post by BertTuyt » Thu Sep 21, 2017 19:05

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 22-18.

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) 32-28

Bert

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

Re: Breakthrough Draughts

Post by TAILLE » Thu Sep 21, 2017 23:46

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 22-18.

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) 32-28

Bert
Hi,

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

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

Re: Breakthrough Draughts

Post by BertTuyt » Fri Sep 22, 2017 18:56

Did some-one 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 22-17 recognized as a loss.
So when 24-19 is solved, I most likely can confirm the claim that only 22-18 wins.

Bert

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

Re: Breakthrough Draughts

Post by BertTuyt » Sun Sep 24, 2017 11:51

It took some time, but also on my side the result is now confirmed that 22-18 remains a win, and all other initial moves are a loss.
I will take now a short break, before restarting.

Bert

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

Re: Breakthrough Draughts

Post by TAILLE » Sun Sep 24, 2017 17:56

BertTuyt wrote:It took some time, but also on my side the result is now confirmed that 22-18 remains a win, and all other initial moves are a loss.
I will take now a short break, before restarting.

Bert
Good confirmation 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:

Image
White to play : losing position!

Image
white to play
The only winning move here is maybe the most doubtful move 21-17!!

Very strange indeed.
I am just able to make pure statistics reasonning.
Gérard

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

Re: Breakthrough Draughts

Post by BertTuyt » Sun Sep 24, 2017 19:43

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.

Code: Select all

Ply	Move		Score
-----------------------
30	23-19		Loss
32	24-20		Loss
33	23-18		Loss
33	21-17		Loss
35	22-17		Loss
36	24-19		Loss
37	22-18		Win
Bert

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

Re: Breakthrough Draughts

Post by BertTuyt » Sun Sep 24, 2017 21:20

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

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

Re: Breakthrough Draughts

Post by BertTuyt » Sun Sep 24, 2017 21:23

Gerard, do you have already an insight for all initial while losing moves (for example 23-19), how many moves on black side are winning.
For 23-19 at least the 12-16 move (which immediately loses 1 man), seems to me already losing for black.

Bert

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

Re: Breakthrough Draughts

Post by TAILLE » Sun Sep 24, 2017 23:42

BertTuyt wrote:Gerard, do you have already an insight for all initial while losing moves (for example 23-19), how many moves on black side are winning.
For 23-19 at least the 12-16 move (which immediately loses 1 man), seems to me already losing for black.

Bert
Hi Bert,

The complete answer to your question is the following:

22-18 winning move
24-20 losing move; 3 black winning moves : 11-16, 11-15, 9-13
23-19 losing move; 4 black winning moves : 11-16, 9-13, 9-14, 11-15
21-17 losing move; 1 black winning move : 9-13
24-19 losing move; 3 black winning moves : 11-16, 10-14, 11-15
23-18 losing move; 3 black winning moves : 12-16, 11-15, 11-16
22-17 losing move; 1 black winning move : 11-15

On average : 2,5 black winning moves on 7 possible moves

You can note some strange results like 24-20? 9-13 and white has a losing position!
Gérard

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Breakthrough Draughts

Post by MichelG » Mon Oct 09, 2017 08:59

It's nice to see a draughts-like game not ending in a almost-certain 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?

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
Michel

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

Re: Breakthrough Draughts

Post by TAILLE » Mon Oct 09, 2017 10:49

MichelG wrote:It's nice to see a draughts-like game not ending in a almost-certain 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?

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
Michel
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= -
Gérard

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

Re: Breakthrough Draughts

Post by Rein Halbersma » Mon Oct 09, 2017 12:32

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= -
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

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

Re: Breakthrough Draughts

Post by TAILLE » Mon Oct 09, 2017 13:10

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
I don't quite understand your question.

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

Post Reply