Breakthrough Draughts

[BertTuyt]

And 7x7 also ok

Bert

Code: Select all

Verify:7x7 Start, P = 210.267.794.000
51530.6 7x7, P = 210.267.794.000, NCW = 14.036.633.965, E = 0

[BertTuyt]

And no surprise, also 8x6

Bert

Code: Select all

Verify:8x6 Start, P = 182.479.296.120
51355.0 8x6, P = 182.479.296.120, NCW = 15.077.388.839, E = 0

[BertTuyt]

And 9x5

Bert

Code: Select all

Verify:9x5 Start, P = 118.679.869.176
27746.3 9x5, P = 118.679.869.176, NCW = 12.149.534.525, E = 0

[TAILLE]

Hi Bert,
Very good all these confirmations!
BTW do you intend to generate also 15p and 16p db ?
You know I generate the 15p db, I generated also the 12x4 and 11x5 db, and 10x6 is under generation.
I hope to reach all the 16p db and in particular the 8x8 db which I suspect will greatly accelerate the starting position resolution!

[BertTuyt]

Gerard, herewith the last result, and also ok.

I will now focus on a full analysis of the root, and if there is only 1 winning move for white.

Hereafter I will optimize the DB generator, as time-wise scaling is not yet optimal.

But in the end I will certainly continue with 15P, 16P, and beyond.

Bert

Code: Select all

Verify:10x4 Start, P = 56.923.426.846
12137.4 10x4, P = 56.923.426.846, NCW = 7.861.805.321, E = 0

Verify:11x3 Start, P = 19.514.811.840
4080.7 11x3, P = 19.514.811.840, NCW = 3.990.227.861, E = 0

Verify:12x2 Start, P = 4.516.906.290
735.4 12x2, P = 4.516.906.290, NCW = 1.484.410.911, E = 0

[BertTuyt]

Started a all-move analysis search (1 core only ).
Will run this for some time (on my slow computer) to see what happens.
So far all 0, only 23-19 a loss.

Bert

[TAILLE]

Started a all-move analysis search (1 core only ).
Will run this for some time (on my slow computer) to see what happens.
So far all 0, only 23-19 a loss.

Bert

Hi Bert

The 16p db is built
8x7 NCW1= 20 115 443 029 NCL1= 6 679 591 801 NCW2= 24 852 206 669 NCL2= 2 364 699 914
12x4 NCW1= 4 166 779 681 NCL1= 5 992 461 900 NCW2= 11 589 752 646 NCL2= 35 230 023
11x5 NCW1= 9 595 031 572 NCL1= 9 250 527 122 NCW2= 20 727 899 849 NCL2= 118 636 406
10x6 NCW1= 17 384 530 271 NCL1= 11 376 172 814 NCW2= 30 273 708 799 NCL2= 419 307 115
9x7 NCW1= 25 947 711 189 NCL1= 11 006 516 270 NCW2= 36 452 166 868 NCL2= 1 679 531 672
8x8 NCW1= 34 000 336 726 NCL1= 6 522 909 535 NCW2= NCL2=


2-16p db : 153 Gb

The starting position is now quite easy to resolve.
Damy finds the winning move 22-18 in 5'14" and all other moves are proved losing after 8'05".
Because after 5'14" Damy has all the winning tree in memory, that means that Damy is now able to play the winning line within the 20' of a game. Does that means that we can consider the 8x8 BT is solved?

I perfectly know I would be able to generate the 8x9 and 9x9 db (I estimate I need 3 days for generating the 8x9 and 1 week for generating the 9x9 db) but the actual result seems satisfactory doesn't it?

Did you finish the starting position resolution?

I will now return to the 10x10 BT

[BertTuyt]

Gerard, I think we could call it weakly solved (but think Rein has the final verdict).
So far no other moves other than 23-19 which have a final score.
I will also go towards 15P and 16P, but not immediately to 10x10 BT.
I want to do some other tests first.

If the 2018 Computer Olympics is again in Leiden (not sure), we could meet and have the first 10x10 BT Tournament.
Maybe Fabien will also join.
Think this is more fun than regular Draughts.

Bert

[TAILLE]

Gerard, I think we could call it weakly solved (but think Rein has the final verdict).
So far no other moves other than 23-19 which have a final score.
I will also go towards 15P and 16P, but not immediately to 10x10 BT.
I want to do some other tests first.

If the 2018 Computer Olympics is again in Leiden (not sure), we could meet and have the first 10x10 BT Tournament.
Maybe Fabien will also join.
Think this is more fun than regular Draughts.

Bert

If a program is specifcally built to solve the starting game position then I can see a significant difference between "weakly solved" and "strongly solved". In the case here the db built covers all positions with 16 pieces or less, and youcan note that most of these positions are not reachable from the starting position.
Taking into account that the starting position is certainly one of the most difficult position to solve the probability is very high to see Damy solves any position in less than 10'.
What are the needed conditions to say that the game is strongly solved?

Good idea to have a 10x10 BT Tournament. At least it could be now strong motivation!

[Rein Halbersma]

Gerard, I think we could call it weakly solved (but think Rein has the final verdict).
So far no other moves other than 23-19 which have a final score.
I will also go towards 15P and 16P, but not immediately to 10x10 BT.
I want to do some other tests first.

If the 2018 Computer Olympics is again in Leiden (not sure), we could meet and have the first 10x10 BT Tournament.
Maybe Fabien will also join.
Think this is more fun than regular Draughts.

Bert

If a program is specifcally built to solve the starting game position then I can see a significant difference between "weakly solved" and "strongly solved". In the case here the db built covers all positions with 16 pieces or less, and youcan note that most of these positions are not reachable from the starting position.
Taking into account that the starting position is certainly one of the most difficult position to solve the probability is very high to see Damy solves any position in less than 10'.
What are the needed conditions to say that the game is strongly solved?

Good idea to have a 10x10 BT Tournament. At least it could be now strong motivation!

Wikipedia has an article on it. Strongly solved means having perfect play from any position. This still leaves some room for interpretation, and AFAICS the literature is not very precise.

Here's my view on how to differentiate these notions. The strongest solution would be to always return the DTW metric from endgame database (i.e. Bert's goal, I would call this "ultra-strongly" solved). One could relax this to DTW + quick (10's) searches. Or relax even further: GTV dbs (game theoretic value, so WL for BT draughts) from small searches (what Gerard and Bert have now).

In any case, the essential difference from weakly solved is that the solution there is for the initial position only, without a quick solution for other positions. So 8*8 checkers is weakly solved, but 8*8 BT draughts is strongly solved, though not "ultra-strongly" (no full DTW for every position). Would you all agree?

[TAILLE]

Gerard, I think we could call it weakly solved (but think Rein has the final verdict).
So far no other moves other than 23-19 which have a final score.
I will also go towards 15P and 16P, but not immediately to 10x10 BT.
I want to do some other tests first.

If the 2018 Computer Olympics is again in Leiden (not sure), we could meet and have the first 10x10 BT Tournament.
Maybe Fabien will also join.
Think this is more fun than regular Draughts.

Bert

If a program is specifcally built to solve the starting game position then I can see a significant difference between "weakly solved" and "strongly solved". In the case here the db built covers all positions with 16 pieces or less, and youcan note that most of these positions are not reachable from the starting position.
Taking into account that the starting position is certainly one of the most difficult position to solve the probability is very high to see Damy solves any position in less than 10'.
What are the needed conditions to say that the game is strongly solved?

Good idea to have a 10x10 BT Tournament. At least it could be now strong motivation!

Wikipedia has an article on it. Strongly solved means having perfect play from any position. This still leaves some room for interpretation, and AFAICS the literature is not very precise.

Here's my view on how to differentiate these notions. The strongest solution would be to always return the DTW metric from endgame database (i.e. Bert's goal, I would call this "ultra-strongly" solved). One could relax this to DTW + quick (10's) searches. Or relax even further: GTV dbs (game theoretic value, so WL for BT draughts) from small searches (what Gerard and Bert have now).

In any case, the essential difference from weakly solved is that the solution there is for the initial position only, without a quick solution for other positions. So 8*8 checkers is weakly solved, but 8*8 BT draughts is strongly solved, though not "ultra-strongly" (no full DTW for every position). Would you all agree?

I understand your point Rein and I agree with your conclusion. 8x8 BT is "strongly" solved because any position (and not only the starting one) can be solved in a reasonable time but not "ultra-strongly" solved because we do not know the DTW for every position.

I am not sure Bert goal was to "ultra-strongly" solved 8x8 BT because, if I understood correctly, Bert view is to have the complete db but not the full DTW!

Thank you for your clarification Rein.

[Rein Halbersma]

If a program is specifcally built to solve the starting game position then I can see a significant difference between "weakly solved" and "strongly solved". In the case here the db built covers all positions with 16 pieces or less, and youcan note that most of these positions are not reachable from the starting position.
Taking into account that the starting position is certainly one of the most difficult position to solve the probability is very high to see Damy solves any position in less than 10'.
What are the needed conditions to say that the game is strongly solved?

Good idea to have a 10x10 BT Tournament. At least it could be now strong motivation!

Wikipedia has an article on it. Strongly solved means having perfect play from any position. This still leaves some room for interpretation, and AFAICS the literature is not very precise.

Here's my view on how to differentiate these notions. The strongest solution would be to always return the DTW metric from endgame database (i.e. Bert's goal, I would call this "ultra-strongly" solved). One could relax this to DTW + quick (10's) searches. Or relax even further: GTV dbs (game theoretic value, so WL for BT draughts) from small searches (what Gerard and Bert have now).

In any case, the essential difference from weakly solved is that the solution there is for the initial position only, without a quick solution for other positions. So 8*8 checkers is weakly solved, but 8*8 BT draughts is strongly solved, though not "ultra-strongly" (no full DTW for every position). Would you all agree?

I understand your point Rein and I agree with your conclusion. 8x8 BT is "strongly" solved because any position (and not only the starting one) can be solved in a reasonable time but not "ultra-strongly" solved because we do not know the DTW for every position.

I am not sure Bert goal was to "ultra-strongly" solved 8x8 BT because, if I understood correctly, Bert view is to have the complete db but not the full DTW!

Thank you for your clarification Rein.

Ah good point on full WL vs full DTW dbs. My opinion is that full DTW (or smaller DTW + quick search with correct win distance) is much more valuable than full WL, especially since smaller WL + quick search are good alternative.

[TAILLE]

Ah good point on full WL vs full DTW dbs. My opinion is that full DTW (or smaller DTW + quick search with correct win distance) is much more valuable than full WL, especially since smaller WL + quick search are good alternative.

Hi Rein,

DTW is obviously very valuable for international Draughts game where loops are possible. As an example, in order to win, it does not help very much to have a complete picture of the 5Kx2K winning positions We need really a complete picture of the DTW for each 5Kx2K positions in order to reach really the win.

BT is quite different because it could not exist loops. In such game a full WL is suffisant; of course DTW allows to highlight a smallest path to the win but this is not essential.
BTW DTW is a pure computer criterion which often makes no sense for a human.
Let’s take the two following positions:

Position 1


Position 2


In the first one I guess that the DTW is quite high but for a human point of view there are no doubts at all : white wins full stop.
In the second one I think the DTW is far less but now the human player needs a very long and difficult analysis to decide between a win or a loss.
As you see the DTW may not be the best criterion for a human. I am not able to propose a objectively better criterion but, as human, I prefer a non 100% sure approach like the following: suppose you have a good eval function (like the scan one ?). You can define a position as “almost win” is the eval function tells you that the advantage is superior or equal to one man. With this definition you can consider the DTAW (distance to almost win) concept.
With DTAW the first position above is already a “almost win position” and DTAW = 0 and this sounds quite satisfactory for a human.
On the other hand DTAW is obviously far higher in the second position and this makes really sense for a human, doesn't it?

[BertTuyt]

It was my purpose to strongly solve this (so not ultra strong), which in my case translates that in every position I would get the final result within 10 seconds (or alike).
Which is not yet the case as due to less memory and a HD instead of a SSD , the search seems to be IO bound.

After quite some time still only resolved 23-19 and 24-20 as a loss for white, so not yet there.
As I only use 1 core, I can at least use my (4 core) system for other purposes while the program runs in the background.

Bert

[BertTuyt]

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