Tablebase suggestion

[syzygy]

Maybe you could also try to calculate the number of positions in a single 8-piece tablebase (say KRBPvKRNP) and calculate the time you need to evaluate each position for say 10ms. Let's have 1000 CPUs working on them in parallel. How long does it take?

Hi. This caught my attention. The KRBPvKRNP endgame has precisely 64,513,180,757,427 unique legal positions, which makes it only 59-th largest 8-piece endgame. The largest one is KRBNPvKBN with 87,076,702,767,652 unique legal positions. Of course this is the lower bound, the number of positions that will be indexed with a particular indexing method will be still larger. Hope it helps a little.

Hi Kirill, I noticed that your NULP numbers for individual endgames are not all equal to mine.
For example, for KQRvKQR you have counted 3,239,241,501 legal positions.
However, I am counting 3,211,734,620 legal positions.

In general, we seem to get the same number for 4v2 tables but not for 3v3 tables.
For example, for KQNNvKQ we both count 3,766,253,475 legal positions.

[syzygy]

Maybe you could also try to calculate the number of positions in a single 8-piece tablebase (say KRBPvKRNP) and calculate the time you need to evaluate each position for say 10ms. Let's have 1000 CPUs working on them in parallel. How long does it take?

Hi. This caught my attention. The KRBPvKRNP endgame has precisely 64,513,180,757,427 unique legal positions, which makes it only 59-th largest 8-piece endgame. The largest one is KRBNPvKBN with 87,076,702,767,652 unique legal positions. Of course this is the lower bound, the number of positions that will be indexed with a particular indexing method will be still larger. Hope it helps a little.

Hi Kirill, I noticed that your NULP numbers for individual endgames are not all equal to mine.
For example, for KQRvKQR you have counted 3,239,241,501 legal positions.
However, I am counting 3,211,734,620 legal positions.

In general, we seem to get the same number for 4v2 tables but not for 3v3 tables.
For example, for KQNNvKQ we both count 3,766,253,475 legal positions.

Ah, it's probably just the positions with castling rights that you are counting!
(So nothing to do with 4v2 vs 3v3.)

[syzygy]

Maybe you could also try to calculate the number of positions in a single 8-piece tablebase (say KRBPvKRNP) and calculate the time you need to evaluate each position for say 10ms. Let's have 1000 CPUs working on them in parallel. How long does it take?

Hi. This caught my attention. The KRBPvKRNP endgame has precisely 64,513,180,757,427 unique legal positions, which makes it only 59-th largest 8-piece endgame. The largest one is KRBNPvKBN with 87,076,702,767,652 unique legal positions. Of course this is the lower bound, the number of positions that will be indexed with a particular indexing method will be still larger. Hope it helps a little.

I generated KNNNNvKQ with my new generator and found exactly 20322111804 legal positions, divided as follows:

Code: Select all

White to move:
6464943402 positions are wins.
3529670 positions are cursed wins.
3621053071 positions are draws.
261474 positions are blessed losses.
249816723 positions are losses.

Black to move:
2079333315 positions are wins.
1611506 positions are cursed wins.
6425123115 positions are draws.
1984054 positions are blessed losses.
1474455474 positions are losses.

KNNNNvKQ positions never having castling rights, the number 20322111804 indeed coincides with the number you calculated here:
https://kirill-kryukov.com/chess/nulp/r ... ndgame.txt

Code: Select all

knnnnkq - 20322111804

So far all is fine. However, I am a bit puzzled by the discrepancy with statistics produced by my old generator:
http://tablebase.sesse.net/syzygy/7-DTZ/KRRNvKRR.txt

Code: Select all

White to move:
155158212192 positions are wins.
84711768 positions are cursed wins.
86904946284 positions are draws.
6275376 positions are cursed losses.
5995508148 positions are losses.

Black to move:
49903876416 positions are wins.
38676144 positions are cursed wins.
154202739648 positions are draws.
47617188 positions are cursed losses.
35386878132 positions are losses.

So a total of 487729441296 legal positions.

The old generator does not remove the 24-fold symmetry of NNNN, so we have to divide by 24. But then we get 20322060054, which is not the same as 20322111804.

Where are the 51750 missing positions?!

For the moment I suspect this has to do with the NNNN allowing for certain symmetrical positions that mess up the straightforward counting (dividing by 24), but I have not yet tried to pin it down.

[Ajedrecista]

Hello Ronald:

I generated KNNNNvKQ with my new generator and found exactly 20322111804 legal positions, divided as follows:
[...]

Great to see you are still working on these things and that Kirill and you agree. I want to note that the link to the statistics file of the old generator is wrong (you pasted KRRNvRR instead of the desired KNNNNvKQ), though the statistics pasted in your post are truly of KNNNNvKQ.

Looking into the divided statistics, I noted that only 'white to move cursed losses' (6275376) and 'black to move cursed wins' (38676144) are multiples of 24 of 'white to move blessed losses' (261474) ('blessed losses?' New name instead of 'cursed losses'?) and 'black to move cursed wins' (1611506), respectively. The rest of the old statistics are a few below 24 times the new statistics, thus the 51750 surplus that you found in the new metric (new statistics). Furthermore, 'white to move losses' and 'black to move losses' old values are not divisible by 24, only by 12.

------------

Later, I manually checked the old statistics file hosted here:

http://tablebase.sesse.net/syzygy/7-DTZ/KNNNNvKQ.txt

I summed the values of each ply and classified the results as wins, cursed wins and so on; except draws, that are logically given without dividing in plies and can not be cross-checked. I verified all sums but one, the 'black to move cursed wins':

Code: Select all

[...]

Black to move:

[...]

96 positions win in 49 ply.
8467032 positions win in 103 ply.
2043288 positions win in 105 ply.
595848 positions win in 107 ply.
214800 positions win in 109 ply.
83856 positions win in 111 ply.
41208 positions win in 113 ply.
18504 positions win in 115 ply.
7968 positions win in 117 ply.
5280 positions win in 119 ply.
3504 positions win in 121 ply.
1488 positions win in 123 ply.
1680 positions win in 125 ply.
672 positions win in 127 ply.
216 positions win in 129 ply.
264 positions win in 131 ply.
168 positions win in 133 ply.
144 positions win in 135 ply.
96 positions win in 137 ply.
48 positions win in 139 ply.
72 positions win in 141 ply.

49903876416 positions are wins.
38676144 positions are cursed wins.
154202739648 positions are draws.
47617188 positions are cursed losses.
35386878132 positions are losses.

[...]

The statistics file says '38676144 positions are cursed wins', but I get 11486136. The difference is 27190008, which is divisible by 24 (1132917).

The sum of all the values that are classified by depth is 487702251288 (with my correction) or 487729441296 (without correction), the latter being the old value of your post. The sum with my correction is divisible by 24 (20320927137), which is still different of both 20322060054 and 20322111804 suggested by you.

I hope I am not adding noise. Good luck in your research!

Regards from Spain.

Ajedrecista.

[Rein Halbersma]

Where are the 51750 missing positions?!

For the moment I suspect this has to do with the NNNN allowing for certain symmetrical positions that mess up the straightforward counting (dividing by 24), but I have not yet tried to pin it down.

Not sure about the exact number of 51,570 positions, but the cause seems clear: identical pieces can be placed on pairs of squares that are mapped to each other by any of the board symmetries, whereas different pieces can only be placed on the diagonals to be invariant under mirroring.

[syzygy]

Hello Ronald:

I generated KNNNNvKQ with my new generator and found exactly 20322111804 legal positions, divided as follows:
[...]

Great to see you are still working on these things and that Kirill and you agree.

My new generator for generating 8-piece tablebases with 0 or 1 pawns with 128 GB RAM is now quite far along. For most tables (with at least two pieces of the same kind) 64 GB will be enough.
For tablebases with 2+ pawns I will adapt my in-RAM generator.

Whether it will actually be used to generate the complete 8-piece set is another question. The generated files will be quite large.

I want to note that the link to the statistics file of the old generator is wrong (you pasted KRRNvRR instead of the desired KNNNNvKQ), though the statistics pasted in your post are truly of KNNNNvKQ.

Oops, I copied the URL from the wrong browser tab.

Looking into the divided statistics, I noted that only 'white to move cursed losses' (6275376) and 'black to move cursed wins' (38676144) are multiples of 24 of 'white to move blessed losses' (261474) ('blessed losses?' New name instead of 'cursed losses'?) and 'black to move cursed wins' (1611506), respectively. The rest of the old statistics are a few below 24 times the new statistics, thus the 51750 surplus that you found in the new metric (new statistics). Furthermore, 'white to move losses' and 'black to move losses' old values are not divisible by 24, only by 12.

Yes, cursed losses is now blessed losses. This was the original term used in this thread:
https://kirill-kryukov.com/chess/discus ... php?t=3748
(I was almost certain that kronsteen came up with it, but it may have been me. Kronsteen came up with cursed win.)

Regarding the KNNNNvKQ statistics, I think I understand now. The reason lies in the way my old generator corrects for the diagonal symmetry that remains after restricting the wK to a1-d1-d4 and, if the wK is on the a1-d4 diagonal, the bK to a1-h1-h8.

If both the wK and the bK are on the a1-h8 diagonal (so wK on a1-d4 and the bK anywhere on a1-h8), most positions will have a mirror position which is also in the generated table. So when collecting statistics, a position with the Ks on the diagonal is counted 0.5 times if mirroring the position in the a1-h8 diagonal leads to a different position (= a position with a different index).

The new generator uses an indexing scheme where permuting the Ns does not change the index of the position. So mirroring in the a1-h8 diagonal leads to the same index if the Ks and the Q are on the diagonal and the Ns are on b1<->a2 and c1<->a3.

The old generator treats each N as a different piece. So now exchanging the Ns on b1 and a2 results in a different position. So these positions are counted twice (2x1) instead of once (2x0.5).

Apparently I did not pay much attention when looking at the statistics of other tables with two identical pieces. The same must happen e.g. with KNNvK.
New generator:

Code: Select all

White to move:
77 positions are wins.
735227 positions are draws.
0 positions are losses.

Black to move:
0 positions are wins.
873627 positions are draws.
15 positions are losses.

So 1608946 legal positions.

Old generator;

Code: Select all

White to move:
154 positions are wins.
1437574 positions are draws.
0 positions are losses.

Black to move:
0 positions are wins.
1707858 positions are draws.
30 positions are losses.

So 3255616 legal positions, and dividing by 2 gives 1627808, which indeed is not equal to 1608946.

To get consistent results, I would have to compare the statistics collected without the "diagonal" correction. But the old 7-men statistics were generated with the correction, so I will just have to live with it.

I must have noticed this issue long ago already, because otherwise I would have made the old generator divide the statistics by 24 for the KNNNNvKQ table.

[syzygy]

Where are the 51750 missing positions?!

For the moment I suspect this has to do with the NNNN allowing for certain symmetrical positions that mess up the straightforward counting (dividing by 24), but I have not yet tried to pin it down.

Not sure about the exact number of 51,570 positions, but the cause seems clear: identical pieces can be placed on pairs of squares that are mapped to each other by any of the board symmetries, whereas different pieces can only be placed on the diagonals to be invariant under mirroring.

Indeed. I somehow believed the discrepancy was not present with fewer identical pieces, but of course it is.
It is interesting that the number 51,570 is so very small.

I guess ignoring illegal positions, the number would be 28*27/2 [pairs of symmetric Ns] * 21 [wk,bK on diagonal] * 6 [Q on the diagonal] * 2 [side-to-move] = 95,256. So 51,570 after discarding illegal positions looks very plausible.

[syzygy]

The same must happen e.g. with KNNvK.
New generator:

Code: Select all

White to move:
77 positions are wins.
735227 positions are draws.
0 positions are losses.

Black to move:
0 positions are wins.
873627 positions are draws.
15 positions are losses.

So 1608946 legal positions.

Old generator;

Code: Select all

White to move:
154 positions are wins.
1437574 positions are draws.
0 positions are losses.

Black to move:
0 positions are wins.
1707858 positions are draws.
30 positions are losses.

So 3255616 legal positions, and dividing by 2 gives 1627808, which indeed is not equal to 1608946.

Oops, the first set of numbers was without the diagonal correction, and I failed to add the second set of numbers correctly. With the diagonal correction, the new generator gives:

Code: Select all

White to move:
77 positions are wins.
719053 positions are draws.
0 positions are losses.

Black to move:
0 positions are wins.
854223 positions are draws.
15 positions are losses.

So 1573368 legal positions.
The old generator counts 3145616 legal positions, which is 2 * 1572808.
The difference is 560. Ignoring legality, my calculation would give 28 * 21 * 2 = 1176. Now 560 seems too low, so my approach to estimating the number ignoring legality is probably not correct.

[syzygy]

Let's use Burnside's Lemma.

KNNvK with distinct Ns and ignoring legality (but KKs on not touching).

There are 3612 ways to place the Ks, so 1806 * 62 * 61 ways to place KNNvK with distinct Ns.
Fixed points under symmetries:
id -> 3612 * 62 * 61 = 13660584
diagonal (2x) -> 42 [KK on diagonal] * 6 * 5 [Ns on the diagonal] = 1260
All other symmetries do not preserve the position of the wK so have no fixed points.
So total number of orbits = (13660584 + 2*1260) / 8 = 1,707,888 = 2 * 853,944.

Now KNNvK with identical Ns and ignoring legality.
Fixed points under symmetries:
id -> 3612 * 62 * 61 / 2 = 6830292
diagonal (2x) -> 42 * (6*5/2 + 28) = 1806
So total number of orbits = (6830292 + 2*1806) / 8 = 854,238.
This is 294 more, or 2 x 294 = 588 if we distinguish between white to move and black to move.
So that is pretty close to 560, and the difference can be explained by position illegality.

My 28*21*2 estimate apparently had to be divided by 2.

With KNNNNvKQ we can do the same calculation.
distinct Ns:
id -> 3612 * 62 * 61 * 60 * 59 * 58
diagonal (2x) -> 42 * 6 * 5 * 4 * 3 * 2
identical Ns:
id -> 3612 * 62 * 61 * 60 * 59 * 58 / 24
diagonal (2x) -> 42 * 6 * (5*4*3*2/24 + 5*4/2*28 + 28*27/2)

So the difference will now be 2 * 2 * 42 * 6 * (5*4/2*28 + 28*27/2) / 8 = 82,908.
So 51,570 after correcting for legality again seems plausible.

[syzygy]

When we are in g2, we have loaded 19 slices (a1-h1,a2-h2,f3,g3,h3).
[d]8/8/8/8/8/5kkk/kkkkkkkk/kkkkkkkk b - - 0 1

[...]

19 K-slices take up 97.9 GB, so 128 GB of RAM would be comfortable.

I'm trying to understand this thread. So far I understand the 462 wK/bK slicing, and also that unmoving a bK requires 9 slices in RAM at the minimum. But where does the number 19 come from? For the g2 diagram, what benefits bring the 10 slices in the a1-e1-a2-e2 rectangle being in RAM?

The 19 comes from the maximum number of slices that have to be kept in memory before you can save slices to disk (or release them from memory if they were loaded from disk) because they are "finished". A slice is finished if all its "neighbouring" slices have been processed.

For example, consider computing the wtm predecessors of the btm loss-in-n positions.
In this case we are looking at moves and unmoves by white, so the bK stays on the same square.
So we first place the bK on b1 and let the wK move through the squares in normal order a1-h1, a2-h2,....,a8-h8.
The wK cannot be on a1,b1,c1, so we start with wK on d1.
If we unmove btm loss-in-n positions with bK,wK on b1,d1, we reach wtm positions with bK on b1 and wK on one of d1,d2,e1,e2. So we need 4 slices in RAM corresponding to (b1,d1), (b1,d2), (b1,e1), (b1,e2).
Now we move wK to e1 and we need to add RAM slices for (b1,f1) and (b1,f2).
And so on: as we move wK to f1,g1,h1,d2,e2, we create RAM slices for bK on b1 and wK on g1,g2,h1,h2,c3,d3,e3,f3.
Now notice that once we have finished unmoving from (b1,e2), we are done with the slice (b1,d1): it is not possible to reach this wtm slice by unmoving from a btm slice which has not already been processed. So we save the wtm slice corresponding to (b1,d1) to disk, and we can use the freed up RAM for another slice (like (b1,g3) since we will now place the wK on f2).

The "worst" case scenario is when the bK is not near the wK and the wK is not on ranks 1 and 8. In this worst case, 2*8+3=19 slices are enough:
8/8/KKKKK3/KKKKKKKK/2KKKKKK/8/8/1k6 w - - 0 1
Here we are processing (b1,d5). Once finished, (b1,c4) can be released, the wK moves to e5, and (b1,f6) is added to RAM.
Once (b1,h8) is done, every slice still in RAM can be saved to disk, the bK moves to c1, and wK traverses the board again.
The bK can be restricted to a1-d1-d4. If the bK is on the diagonal a1-d4, the wK only visits the a1-h1-h8 triangle.

The verification step (to verify a potential loss-in-n found by unmoving from a win-in-(n-1)) works in exactly the same way, except now we load K-slices into RAM from disk (with "wins" bitmaps) before processing instead of saving them to disk after processing.

With colours reversed, it is the same. Just fix the wK in one of the a1-d1-d4 squares and let the bK traverse the board.

Now it's just a matter of mapping all these slices to the same naming scheme.

On chessprogramming.org I came across a link to this older post by Urban Koistinen:
https://kirill-kryukov.com/chess/discus ... php?t=5163

If you index using the kings (KK) positions as most signifigant index and then the rest of the pieces have 64^5 possibilities. (Actually less, due to illegal positions and sometimes due to mirroring)
This means that for each KK position there are 1G positions of the other pieces.
When computing the new values for one side, one king can be constant and so used to partition the table into smaller parts. Fix it in one of the squares, a1, b1, c1, d1, b2, c2, d2, c3, d3, d4.
The king that is moving can move at most one step, first load a1..h1, a2..h2 and a3..c3. This is 19*1G positions.Then compute a1..h1 and a2..b2.
After that a1 is not needed and can be replaced by d3. Then c2 can be computed and so on for all squares.

So that's exactly the same scheme that I am using!

Urban suggested using 2 bits per position (with 64^5 positions per K-slice), which then allows you to treat dtz=n and dtz=n+1 in the same iteration in 19*64^5*2 bits = 4.75GB for 7-piece table. Instead I am using 1 bit per position and just do 1 dtz value per iteration, and I use a more compact indexing than 64^5, which means less than 2 GB for a 7-piece table and about 100 GB for the largest 8-piece tables. I don't see much reason anymore to implement a 2-bit scheme because loading/saving 2-bit tables won't be much more efficient than twice loading/saving 1-bit tables. Plus, every other iteration tends to be pretty fast anyway.