Breakthrough Draughts

[Rein Halbersma]

Based on the postings by Fabien and Joost, I now suspect the best time investment would be to write a Proof-Number search algorithm for the forward search of your project. Joost's PN search was 100x to 1000x faster than my plain alpha-beta in solving 6x6 draughts.

Did Joost also solve 6x6 using PNS or do you mean me?
Jan-Jaap

Oops, corrected!

[TAILLE]

Gerard, hope that Damy can agree with the whole move sequence, so that it is confirmed that white wins.
My holiday ends, so I will have less time in the next months for BT Draughts.

I will at least do a verification step for all DBs, and evaluate if the generate proces can be improved (so faster), as with the current speed it still takes too long to strongly solve 8x8 BT draughts (although from a scalability point of view it would be possible if I have a 5 TByte HD, as the current implementation does not compress).

For really fast analysis of all moves in any position, I guess I most likely need to generate the 15P and 16P DBs (as Rein predicited).

Bert

Hi Bert,

After all a night computation I do not have good news : for Damy the starting position is winning but ONLY with 22-17.
Because you propose 22-18 etc. it is obvious that a bug exists somewhere in our programs (of course I do not exclude a Damy bug !!!).
How do you win after
22-18 11-16

[BertTuyt]

Gerard, the good news is that at least we both seem to agree upon an initial white win.

It could be that my program is wrong in 22-18, but maybe also sees 22-17 as winning.
Could you also give your 22-17 move sequence, so I can replay?

As Im back to work I dont have access to my faster computer, but I stored all DBs on a portable HD (which I will trasfer to the faster SSD), so I might be able to verify, but at a slower speed, as I dont have 8 cores and 4 GHZ here.

Bert

[TAILLE]

Gerard, the good news is that at least we both seem to agree upon an initial white win.

It could be that my program is wrong in 22-18, but maybe also sees 22-17 as winning.
Could you also give your 22-17 move sequence, so I can replay?

As Im back to work I dont have access to my faster computer, but I stored all DBs on a portable HD (which I will trasfer to the faster SSD), so I might be able to verify, but at a slower speed, as I dont have 8 cores and 4 GHZ here.

Bert

The upper part of the tree after 22-17 is the following
22-17 11-16 25-22
22-17 9-14 17-13
22-17 11-15 24-20
22-17 12-16 24-20
22-17 10-15 17-13
22-17 10-14 17x10 6x15 24-20
22-17 10-14 17x10 7x14 25-22
22-17 9-13 24-19

I hope we will soon find the bug detected

[BertTuyt]

Gerard, in a previous post you mentioned the confirmation of the 22-18 10-14 26-22 11-16 22-17 sequence.

So if 22-17 is the only initial winning move, we should also find the break here.
Could you check, so we can find the difference from both sides.

In the meantime I'm checking the 22-17 10-14 17x10 ...
Result expected tomorrow.

Bert

[TAILLE]

Gerard, in a previous post you mentioned the confirmation of the 22-18 10-14 26-22 11-16 22-17 sequence.

So if 22-17 is the only initial winning move, we should also find the break here.
Could you check, so we can find the difference from both sides.

In the meantime I'm checking the 22-17 10-14 17x10 ...
Result expected tomorrow.

Bert

Oops, since the previous post you mentionned I discovered a bug which disturbed my db during big generation (more than 4G added to the db for a given type of position).
After having fixed the bug I had to regenerate all the db and as a consequence I had to reconsider what I claimed.

Taking the sequence 22-18 10-14 26-22 11-16 22-17 9-13 the current Damy analysis shows four mistakes:
22-18? [22-17!] 10-14? [11-16!] 26-22 11-16 22-17? [24-20!] 9-13? [8-11! 17x10 6x22 25x18 1-6]

BTW I remind you that I cannot be sure that Damy is bug free !!!
Surely we can help each other

[BertTuyt]

Gerard, the 22-17 10-14 17x10 is a white win (at least according to my DBs).
I will reply your proposed 22-18 sequence.

Next to that I can modify the verify routine (did not do a verify so far) to verify all DB nodes, and add statistics for capture and non-capture moves. If you could sent your DB statistics, I can generate similar figures, so we also can compare the DBs.

Last but not least I need to implement PN Search and see if this is faster, so I can weakly solve positions faster or with fewer DBs.

Bert

[TAILLE]

Gerard, the 22-17 10-14 17x10 is a white win (at least according to my DBs).
I will reply your proposed 22-18 sequence.

Next to that I can modify the verify routine (did not do a verify so far) to verify all DB nodes, and add statistics for capture and non-capture moves. If you could sent your DB statistics, I can generate similar figures, so we also can compare the DBs.

Last but not least I need to implement PN Search and see if this is faster, so I can weakly solve positions faster or with fewer DBs.

Bert

My pv from the initial position is the following
22-17 11-16 25-22 8-11 17-13 11-15 29-25 16-19 23x16 12x19 24-20 4-8 27-24 8-12 31-27 7-11 21-17 12-16 25-21 9-14 26-23 19x26 22x31 15-18 27-23 18x27 32x23 3-8 31-26 8-12 30-25 2-7 25-22

Taking now the move 22-18? the black winnig highlighted by Damy is the following
22-18? 9-13 25-22 6-9 24-19 11-16 18-15 10-14 22-18 16-20 26-22 7-10 15x6 1x10 31-26 3-7 18-15 2-6 etc.

Concerning my statistics let's begin by the 12pieces db and the joint file

[BertTuyt]

Gerard, for my understanding, TB Position is white (Blanc) to move and TN Position is black (Noir) to move?

If so than I would expect that in symmetrical DBs (so 1x1, 2x2, ...) both values for winning should be equal, or do I miss something obvious?

Bert

[TAILLE]

Gerard, for my understanding, TB Position is white (Blanc) to move and TN Position is black (Noir) to move?

If so than I would expect that in symmetrical DBs (so 1x1, 2x2, ...) both values for winning should be equal, or do I miss something obvious?

Bert

First of whole your understanding of french wording is correct!
Concerning symmetrical DBs the corresponding figures in my attach file are certainly coding dependant.
The natural approach would be to store in the db only the white (or black as you want) to move positions but in my implementation the corresponding generation algorithm would be very different comparing to my general generation algorithm.
My choice was the following : I ignore all positions in which white men are nearer the king's row than black men.
As an exemple:


the above position is in the db for both white to move and black to move but the following position


is not at all in the db.

BTW a completly symmetrical position like

appears currently to time in my db : in the white to move db and in the black to move db. I am not sure I will try to optmise this point in the future

In order to verrify our db the most simple approach is to ignore the symmetrical positions figures: if we do not compare our 4x4 figures but if we have the same figures for the 5x4 db it means that our 4x4 db is also correct doesn't it?

[BertTuyt]

Gerard, at least for the Dbs upto 4x4 (and excluding symmetrical DBs) we have the same results.
See below table, also no verification errors.

CW = Capture Win
NCW = Non Capture Win
CL = Capture Loss
NCL = Non Capture Loss

All from the perspective white to play.
For DBs where black only has 1 man (so example 4x1), the number of captures should be equal to the Capture Wins.

Code: Select all

1x1 P = 760, Capture = 66
1x1 P = 760, CW NCW CL NCL = 66 388 0 306
0.0 1x1, P = 760, E = 0
1x2 P = 9.936, Capture = 1.600
1x2 P = 9.936, CW NCW CL NCL = 858 2.378 742 5.958
0.0 1x2, P = 9.936, E = 0
1x3 P = 83.304, Capture = 18.690
1x3 P = 83.304, CW NCW CL NCL = 4.700 14.054 13.990 50.560
0.1 1x3, P = 83.304, E = 0
1x4 P = 503.100, Capture = 140.020
1x4 P = 503.100, CW NCW CL NCL = 24.454 68.240 115.566 294.840
0.3 1x4, P = 503.100, E = 0
2x1 P = 9.936, Capture = 1.593
2x1 P = 9.936, CW NCW CL NCL = 1.593 7.155 0 1.188
0.0 2x1, P = 9.936, E = 0
2x2 P = 125.664, Capture = 35.985
2x2 P = 125.664, CW NCW CL NCL = 27.881 56.410 8.104 33.269
0.1 2x2, P = 125.664, E = 0
2x3 P = 1.018.056, Capture = 392.818
2x3 P = 1.018.056, CW NCW CL NCL = 195.609 269.004 197.209 356.234
0.9 2x3, P = 1.018.056, E = 0
2x4 P = 5.933.850, Capture = 2.757.200
2x4 P = 5.933.850, CW NCW CL NCL = 860.766 1.147.410 1.896.434 2.029.240
5.3 2x4, P = 5.933.850, E = 0
3x1 P = 83.304, Capture = 18.495
3x1 P = 83.304, CW NCW CL NCL = 18.495 59.902 0 4.907
0.1 3x1, P = 83.304, E = 0
3x2 P = 1.018.056, Capture = 390.894
3x2 P = 1.018.056, CW NCW CL NCL = 332.094 523.486 58.800 103.676
0.8 3x2, P = 1.018.056, E = 0
3x3 P = 7.959.904, Capture = 4.004.729
3x3 P = 7.959.904, CW NCW CL NCL = 2.772.633 2.699.916 1.232.096 1.255.259
7.2 3x3, P = 7.959.904, E = 0
3x4 P = 44.717.500, Capture = 26.450.365
3x4 P = 44.717.500, CW NCW CL NCL = 13.265.287 9.722.656 13.185.078 8.544.479
44.5 3x4, P = 44.717.500, E = 0
4x1 P = 503.100, Capture = 137.520
4x1 P = 503.100, CW NCW CL NCL = 137.520 348.776 0 16.804
0.3 4x1, P = 503.100, E = 0
4x2 P = 5.933.850, Capture = 2.729.211
4x2 P = 5.933.850, CW NCW CL NCL = 2.412.383 2.915.566 316.828 289.073
4.7 4x2, P = 5.933.850, E = 0
4x3 P = 44.717.500, Capture = 26.334.152
4x3 P = 44.717.500, CW NCW CL NCL = 20.669.129 15.601.037 5.665.023 2.782.311
39.9 4x3, P = 44.717.500, E = 0
4x4 P = 241.788.751, Capture = 164.208.561
4x4 P = 241.788.751, CW NCW CL NCL = 109.903.327 56.865.877 54.305.234 20.714.313
245.6 4x4, P = 241.788.751, E = 0

Bert

[TAILLE]

Gerard, at least for the Dbs upto 4x4 (and excluding symmetrical DBs) we have the same results.
See below table, also no verification errors.

CW = Capture Win
NCW = Non Capture Win
CL = Capture Loss
NCL = Non Capture Loss

All from the perspective white to play.
For DBs where black only has 1 man (so example 4x1), the number of captures should be equal to the Capture Wins.

Bert

Good news, no doubt we willl find where is the bug detected!
BTW I am trying to optimise my symmetrical db in order to be able to compare our figures.

[BertTuyt]

Gerard, also upto 5x5 same results (without posting the details).

Bert

[BertTuyt]

Gerard, calculations still going on.
The first (and only one so far) difference found now is the 2x10 DB, your value for wins is 188.218.694.
My value 188.219.310.

I expect all results available by tomorrow, so will inform you about the final status.

Bert

[BertTuyt]

Gerard, as I run the verify in debug mode (and 1 core) speed is limited.
So far the verify did not found a DB consistency error (which does not indicate there is nothing wrong!).

In the meantime another difference has been found, the 3x9 DB.
Your count 654.342.042, my count 654.448.795.

And the 1x11 DB.
Your count 26.601.065 and my 22.286.688

So all (= 3, 9x3, 10x2 and 11x1) member of the 12P DB.
Did you also do a verify for the 12P DBs?

Bert