Breakthrough Draughts

[Rein Halbersma]

So when I Verify all 13P and 14P, I really need to find some speed improvements, otherwise I will never create a 24P DB.

Bert

Bert, you are no doubt doing this already, but just in case: do you generate the indices in the following order? Index 0 has white pieces on squares 6, 7, 8... etc., and for black on 45, 44, 43,... etc. If you do it that way, then you need only 2 passes over the data to solve it. One for the captures, and one for non-captures. The reason is that a higher index has all its successors on lower index positions. In terms of graph theory: you are doing a topological sort.

[TAILLE]

Gerard, basically your result is quite good!
When I started my speed was around 25M Positions/sec.

But it has drastically reduced as I use a quite complicated Index function without holes/gaps (with the help of Ed).
Also for larger DBs, I still use the same index function (so not based on leading rank or whatever).
To quickly get the 13P and 14P DBm I partitioned the DB, and swap partitions.
As speed was okish, i did (so far) not go into further optimization mode.
Advantage it now can scale to every size (when one has sufficient disk space), disadvantage speed.

The 7x6 + 7x6 took 4.5 hours (for non-symmetrical my program calculates pairs), the 7x7 5.8 hours (so both approximately 10M Positions/sec)

So when I Verify all 13P and 14P, I really need to find some speed improvements, otherwise I will never create a 24P DB.

Bert

Bert,

I am not really surprised to see the reduction of the facteur between our programs when the number of pieces grows. My feeling is that the number of capture positions grows faster than the number of positions when the number of pieces grows. Because I do not handle capture positions I can get an advantage when the number of pieces grows.
Do you see an other explanation?

[BertTuyt]

And some additional info (my machine has 64 GByte).

I used a 16 GByte cache for previous DB results.
DBs are stored non compressed 1 bit/position.
DBs are loaded by 4K Blocks in the Cache.

The program I used was based upon the work of Michel and Harm (you can find still some references in the source).

For the DB generation (mostly in pairs) 2 blocks of 16 GByte are allocated.
I could use (as a further optimization) the whole 32 GByte for symmetrical DBs, which i didn't implement yet.

First phase is called CP, so Capture and Promotion.
This is the only phase where other DBs are called (and as we are in Breakthrough mode we don't need to access other DBs for the score).

After this the iteration process starts, but so far moving through all indexes, so a forward scan, and not (as Michel implemented) a queue based backwards scan approach (which is far more efficient in the later stage).

The parallel implementation divides the index space in equal parts, and synchronization is done via a ::WaitForMultipleObjects function.

I still need to check if the partition for large DBs does not contain errors, and if so I will distribute the source for those interested.

Bert

[BertTuyt]

So when I Verify all 13P and 14P, I really need to find some speed improvements, otherwise I will never create a 24P DB.

Bert

Bert, you are no doubt doing this already, but just in case: do you generate the indices in the following order? Index 0 has white pieces on squares 6, 7, 8... etc., and for black on 45, 44, 43,... etc. If you do it that way, then you need only 2 passes over the data to solve it. One for the captures, and one for non-captures. The reason is that a higher index has all its successors on lower index positions. In terms of graph theory: you are doing a topological sort.

Rein, to be honest I need to check, as I tested both options for small DBs, to secure that I would not get different results.
But I guess (and afraid) I didn't change it back, as your proposed way is also my preferred approach.

As also mentioned in another post, to get towards 13P and 14P was okish time wise , so i did not spent much time in further optimization, which I need to do when moving towards 16P and beyond.

Bert

[TAILLE]

And some additional info (my machine has 64 GByte).

I used a 16 GByte cache for previous DB results.
DBs are stored non compressed 1 bit/position.
DBs are loaded by 4K Blocks in the Cache.

The program I used was based upon the work of Michel and Harm (you can find still some references in the source).

For the DB generation (mostly in pairs) 2 blocks of 16 GByte are allocated.
I could use (as a further optimization) the whole 32 GByte for symmetrical DBs, which i didn't implement yet.

First phase is called CP, so Capture and Promotion.
This is the only phase where other DBs are called (and as we are in Breakthrough mode we don't need to access other DBs for the score).

After this the iteration process starts, but so far moving through all indexes, so a forward scan, and not (as Michel implemented) a queue based backwards scan approach (which is far more efficient in the later stage).

The parallel implementation divides the index space in equal parts, and synchronization is done via a ::WaitForMultipleObjects function.

I still need to check if the partition for large DBs does not contain errors, and if so I will distribute the source for those interested.

Bert

Of course my impementation is quite different for at least two reasons: 1) I can use only 32Gb RAM, 2) I add a compression mechanism.
Let's take as an exemple the 6x5db. The number of positions is 12 423 500 232 but when it is white to play there are 2 000 174 981 positions without capture
and with black to play there are 1 974 384 083 positions whithout catpure . Because I am unable to calculate an index without holes for the positions without captures and because it of no use to have an index whithout holes for 12 423 500 232 I decided to build a quite simple index on 37 026 007 200 (number of black configurations * number of white configurations).
Now I have to choose a compression mechanism as simple as possible with an access to the db as fast as possible. I eliminate immediatly all sophistacated solutions and chose simply to store all relevant positions in a sequential order with 32bits/per position (the less significant bits of the index position) hoping that I have to store in the db less than 1% of the positions which is really the case.
To solve my lack of memory I divide the index space in block of 4G positions.
As soon as a block of 4G positions have been handled the results are stored directly in the db and the access to this part of the db is made possible by the standard access to all the db.
On the disk the db is divided in blocks of 4K.

Our implementation being completely different we could be 100% confident when we reach the same figures don't we?

[TAILLE]

Hi,

my complete results for the 13p db:
12x1 NCW1= 33 476 623 NCL1= 245 544 989 NCW2= 302 994 901 NCL2= 554 039
11*2 NCW1= 256 003 791 NCL1= 792 466 163 NCW2= 1 166 313 100 NCL2= 4 586 420
10x3 NCW1= 960 952 868 NCL1= 1 678 713 208 NCW2= 2 903 179 449 NCL2= 19 383 244
9x4 NCW1= 2 383 300 890 NCL1= 2 594 371 451 NCW2= 5 306 714 075 NCL2= 65 461 407
8x5 NCW1= 4 397 273 809 NCL1= 3 044 664 016 NCW2= 7 569 127 412 NCL2= 219 524 913
7x6 NCW1= 6 551 349 681 NCL1= 2 548 915 577 NCW2= 8 381 897 748 NCL2= 855 539 740

Are they consistent with yours?
Are you interested by my results for higher db?

[BertTuyt]

Gerard, certainly I will go into 13P and 14P DB verify.

Will keep you posted, and share results

Bert

[TAILLE]

Gerard, certainly I will go into 13P and 14P DB verify.

Will keep you posted, and share results

Bert

Bert,

Here are results for some 14, 15p db:
12x2 NCW1= 302 705 387 NCL1= 1 008 172 641 NCW2= 1 484 410 775 NCL2= 3 938 749
11x3 NCW1= 1 227 707 632 NCL1= 2 320 901 210 NCW2= 3 990 227 861 NCL2= 17 199 718
12x3 NCW1= 1 369 046 327 NCL1= 2 816 203 101 NCW2= 4 802 121 915 NCL2= 13 717 233
10x4 NCW1= 3 283 778 890 NCL1= 3 909 798 894 NCW2= 7 861 805 321 NCL2= 58 604 100
11x4 NCW1= 3 952 646 546 NCL1= 5 159 925 700 NCW2= 10 185 702 850 NCL2= 47 571 778

12x4 is under generation (my very first db from the 16p db!). Results expected tomorrow morning.

[TAILLE]

Hi,


Black to play

FYI with 13p db + the db 12x2, 11x3, 12x3, 10x4 and 11x4 Damy is able to prove black loss in about 2h.

Surely the starting position will be completly solved with the complete 14p db.

[TAILLE]

Hi Bert,

Results for 12x4 and 9x5 db
12x4 NCW1= 4 166 783 295 NCL1= 5 992 458 286 NCW2= 11 589 750 298 NCL2= 35 232 371
9x5 NCW1= 6 517 270 728 NCL1= 5 063 957 488 NCW2= 12 149 534 759 NCL2= 194 626 802

8x6 and 7x7 need one day each => results in two days for complete 14p db

[BertTuyt]

Gerard, a weekend in Holland.
I started a Verfify for the 13P DB (still single threaded, so slow).

Here already some results.

Im not sure if my interpretation of your results is right, but it seems that we have a difference for 1x12.
Is this true?

Did you do a verify, as my verify didnt indicate an error so far (which is not 100% evidence that the DB is correct).

Code: Select all

1x12 P = 538.899.660, Capture = 259.878.048
1x12 P = 538.899.660, CW NCW CL NCL = 30.133.817 33.476.610 229.744.231 245.545.002
80.6 1x12, P = 538.899.660, E = 0
2x11 P = 3.512.903.160, Capture = 2.464.433.206
2x11 P = 3.512.903.160, CW NCW CL NCL = 403.418.771 256.003.791 2.061.014.435 792.466.163
722.0 2x11, P = 3.512.903.160, E = 0

Bert

[BertTuyt]

Code: Select all

1x12 P = 538.899.660, Capture = 259.878.048
1x12 P = 538.899.660, CW NCW CL NCL = 30.133.817 33.476.610 229.744.231 245.545.002
80.6 1x12, P = 538.899.660, E = 0
2x11 P = 3.512.903.160, Capture = 2.464.433.206
2x11 P = 3.512.903.160, CW NCW CL NCL = 403.418.771 256.003.791 2.061.014.435 792.466.163
722.0 2x11, P = 3.512.903.160, E = 0
3x10 P = 13.747.443.160, Capture = 11.107.777.084
3x10 P = 13.747.443.160, CW NCW CL NCL = 2.444.292.860 960.952.868 8.663.484.224 1.678.713.208
3676.5 3x10, P = 13.747.443.160, E = 0

Bert

[TAILLE]

Gerard, a weekend in Holland.
I started a Verfify for the 13P DB (still single threaded, so slow).

Here already some results.

Im not sure if my interpretation of your results is right, but it seems that we have a difference for 1x12.
Is this true?

Did you do a verify, as my verify didnt indicate an error so far (which is not 100% evidence that the DB is correct).

Code: Select all

1x12 P = 538.899.660, Capture = 259.878.048
1x12 P = 538.899.660, CW NCW CL NCL = 30.133.817 33.476.610 229.744.231 245.545.002
80.6 1x12, P = 538.899.660, E = 0
2x11 P = 3.512.903.160, Capture = 2.464.433.206
2x11 P = 3.512.903.160, CW NCW CL NCL = 403.418.771 256.003.791 2.061.014.435 792.466.163
722.0 2x11, P = 3.512.903.160, E = 0

Bert

Strange indeed; error on 12x1 but no errors for 11x2 and 10x3
Anyway my verification test confirm the bug and I have now to investigate!
Thank you for your help Bert

[BertTuyt]

Gerard, 4x9 seems ok.

Bert

Code: Select all

4x9 P = 36.064.560.004, Capture = 31.086.887.663
4x9 P = 36.064.560.004, CW NCW CL NCL = 8.874.803.506 2.383.300.890 22.212.084.157 2.594.371.451
10748.1 4x9, P = 36.064.560.004, E = 0

[BertTuyt]

Gerard, also 5x8 seems ok.

Bert

Code: Select all

5x8 P = 67.013.445.840, Capture = 59.571.508.015
5x8 P = 67.013.445.840, CW NCW CL NCL = 22.741.820.718 4.397.273.809 36.829.687.297 3.044.664.016
21468.1 5x8, P = 67.013.445.840, E = 0