Tablebase suggestion

[syzygy]

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.

I forgot to add tags:
[d]8/8/KKKKK3/KKKKKKKK/2KKKKKK/8/8/1k6 w - - 0 1

Ah got it! You are essentially moving the 8-square king moves ring through a1-h8, dropping a completed SW slice as you add a new NE slice. Very nice. So the total loop is bK through the 10 square triangle times the wK loop over all legal squares. So 462 slices in total, with 19 in RAM, all sequentially loaded/saved from disk.

Exactly. At first it looks like a complicated problem but it has a straightforward solution.
I looked a bit at other possible paths for the moving king and convinced myself that 19 is optimal, even though I did not try to prove it.

I'm wondering what the number would be if this is tried with a white knight and a black knight. Knights have a similar range to the king, but you probably need more than 19 squares/slices simultaneously loaded.
Perhaps moving the knight a1-h1,a2-h2,...,a8-h8 is still optimal. Once you get to c3, the a1 square can be released. It seems 7+3*8+4 = 35 should then suffice.
[d]8/8/8/NNNN4/NNNNNNNN/NNNNNNNN/NNNNNNNN/1NNNNNNN w - - 0 1
But a better path for the knight might exist.

One could also use say a white king and a black knight, e.g. for chess variants like suicide chess where you don't always have a king. If one side has neither a king nor a knight. then I guess you need to load the full 64 squares, unless you have a bishop in which case you can do 2x32 (a bit better than the knight). Still the non-moving side doesn't create any problems, so I guess you still win a factor of about 1/8 (the b1/c1/d1/c2/d2/d3 squares each representing about 1/8 and a1/b2/c3/d4 each about 1/16).

[syzygy]

I’m also thinking of 10x10 draughts with e.g. 5v5 king endgames. The question is how to pick canonical 2-king configs to slice over. Not sure how to do that.

I guess one approach is to distinguish the canonical kings from the other kings, but this reduces symmetry.

What is the normal way to enumerate the 5v5 positions, taking into account symmetries?

If I start with a canonical white king and a canonical black king, I can restrict the white king to the bottom triangular quarter of the board, and the black king to the lower triangular half of the board if the white king is on the diagonal.
This seems to give 10*49 + 5*29 = 635 slices.
Each slice then has 48*47*46*45*44*43*42*41/24/24 = 26414429580 positions.
With 1 bit per position, this requires about 3.075 GB.

Since the kings move too quickly, you probably cannot reduce the number of slices in RAM to less than 49. (For example, before you can release a corner square, you need to have processed the whole diagonal, but to process the whole diagonal, you need to have loaded all the other squares of the board. One could try to release other squares before processing the whole diagonal, but I don't think that is going to help. The problem is really that the kings move too quickly.)

So 49 slices in RAM, which would require 150.7 GB of RAM.

But if you can enumerate perfectly or close to perfectly, the total number of position is 647156159148 (if ChatGPT applied Burnside's lemma correctly), which is just 75.34 GB with 1 bit per position. (And this number seems correct if we approximate using 50!/40!/5!/5!/4/8/1024/1024/1024.)

So assigning canonical kings and distinguishing them from the other kings of the same colour is a bad idea.

Maybe there is a better way, but I'd first like to understand how 5v5 positions are enumerated.

According to the 10-piece Chinook database paper (so 8x8 checkers), the 5v5 kings endgame has 16,257,084,480 positions, which is exactly 32!/22!/5!/5!, so they did not make use of the 4 board symmetries.
Without those symmtries, you need about 4*75 = 300 GB, so then 150.7 GB halves the RAM requirement (but still this does not seem to be a practical solution if you look at 635 x 3.07 GB compared with 300 GB).

[Rein Halbersma]

I’m also thinking of 10x10 draughts with e.g. 5v5 king endgames. The question is how to pick canonical 2-king configs to slice over. Not sure how to do that.

I guess one approach is to distinguish the canonical kings from the other kings, but this reduces symmetry.

What is the normal way to enumerate the 5v5 positions, taking into account symmetries?

Without using symmetries, the indexing is a product of binom(50,5)*binom(45,5) for which you can use the usual binomial decomposition of K=5 identical pieces on N squares. Note that you can use pext()/pdep() for indexing and de-indexing e.g. black kings in the presence of white kings (by mapping the 50 physical squares 0...49 to the 45 logical squares 0...44 giving that somewhere in between there are 5 white kings).

I don't know of an exact way to enumerate taking into account the full symmetry group (D2, the dihedral group of a rectangle). A problem is that some position are invariant under the entire symmetry group (4-fold symmetry), then there are positions that are invariant under one of the three 2-fold symmetry subgroups (single corner diagonal mirroring, double corner diagonal mirroring and 180 degree rotations) and there are positions that don't have any symmetry. I haven't found a formula which decomposes into products of binomials.

If I start with a canonical white king and a canonical black king, I can restrict the white king to the bottom triangular quarter of the board, and the black king to the lower triangular half of the board if the white king is on the diagonal.
This seems to give 10*49 + 5*29 = 635 slices.
Each slice then has 48*47*46*45*44*43*42*41/24/24 = 26414429580 positions.
With 1 bit per position, this requires about 3.075 GB.

Since the kings move too quickly, you probably cannot reduce the number of slices in RAM to less than 49. (For example, before you can release a corner square, you need to have processed the whole diagonal, but to process the whole diagonal, you need to have loaded all the other squares of the board. One could try to release other squares before processing the whole diagonal, but I don't think that is going to help. The problem is really that the kings move too quickly.)

So 49 slices in RAM, which would require 150.7 GB of RAM.

A king on a 10x10 board can have at most 9+8 = 17 moves. So doing (wK, bK) slicing and binom(48,4)*binom(44,4) positions per slice, you would need at most 18 slices in RAM for 55.4 Gb (similar to the 9 king-slices for chess), but then you have indeed excessive I/O.

But if you can enumerate perfectly or close to perfectly, the total number of position is 647156159148 (if ChatGPT applied Burnside's lemma correctly), which is just 75.34 GB with 1 bit per position. (And this number seems correct if we approximate using 50!/40!/5!/5!/4/8/1024/1024/1024.)

I'm curious to learn what prompt you gave ChatGPT to get that result. I instructed Gemini to expand the Cycle Index Polynomial and the result is the same (647,156,159,148 positions):

Expand ((e+b+w)^50 + 2*(e^2+b^2+w^2)^25 + (e+b+w)^10 * (e^2+b^2+w^2)^20)/4 and collect the coefficient of the term e^40 b^5 w^5

The problem is how to enumerate that number. Do you have any idea or suggestion? Ideally, I'd like it to be a sum of products of binomials, so that one can index each term in the sum efficiently. But there are many cases (e.g. there can be 0, 2, or 4 kings on the main diagonal for each color, the other kings are unrestricted, and for those positions you have to restrict one to a 15 square triangle, but which king?)

So assigning canonical kings and distinguishing them from the other kings of the same colour is a bad idea.

Maybe there is a better way, but I'd first like to understand how 5v5 positions are enumerated.

According to the 10-piece Chinook database paper (so 8x8 checkers), the 5v5 kings endgame has 16,257,084,480 positions, which is exactly 32!/22!/5!/5!, so they did not make use of the 4 board symmetries.
Without those symmtries, you need about 4*75 = 300 GB, so then 150.7 GB halves the RAM requirement (but still this does not seem to be a practical solution if you look at 635 x 3.07 GB compared with 300 GB).

For 8x8 checkers, the board is so small that 6v6 king endgames can easily be computed without any slicing. Since kings in checkers only have 4 moves at the most, it's all very local and you can even get by with 5 (wK, bK) slices in RAM so that with lots of I/O 7v7 kings is feasible. Using your "king striping" for chess and keeping 19 slices in RAM, you need 461 Gb of RAM.

[Rein Halbersma]

Using your "king striping" for chess and keeping 19 slices in RAM, you need 461 Gb of RAM.

In fact, since checkers kings only move on the dark squares, it's more efficient to "stripe" over diagonals. E.g. starting a1, then a3-c1, then a5-e1, then a7-g1, then b8-h2, then d8-h4, then f8-h6 and finally h8. you will need at most 14 slices in RAM if I'm not mistaken. That's 340 Gb of RAM for 7v7 kings on an 8x8 checkerboard. Doing the 5 slices with lots more I/O needs 121 Gb.

[syzygy]

I’m also thinking of 10x10 draughts with e.g. 5v5 king endgames. The question is how to pick canonical 2-king configs to slice over. Not sure how to do that.

I guess one approach is to distinguish the canonical kings from the other kings, but this reduces symmetry.

What is the normal way to enumerate the 5v5 positions, taking into account symmetries?

Without using symmetries, the indexing is a product of binom(50,5)*binom(45,5) for which you can use the usual binomial decomposition of K=5 identical pieces on N squares. Note that you can use pext()/pdep() for indexing and de-indexing e.g. black kings in the presence of white kings (by mapping the 50 physical squares 0...49 to the 45 logical squares 0...44 giving that somewhere in between there are 5 white kings).

Yes, this is what I'm now also doing for identical pieces (using pdep() to find the nth empty square and popcnt() to count the number of preceding occupied squares).

I don't know of an exact way to enumerate taking into account the full symmetry group (D2, the dihedral group of a rectangle). A problem is that some position are invariant under the entire symmetry group (4-fold symmetry), then there are positions that are invariant under one of the three 2-fold symmetry subgroups (single corner diagonal mirroring, double corner diagonal mirroring and 180 degree rotations) and there are positions that don't have any symmetry. I haven't found a formula which decomposes into products of binomials.

Yes, it is very annoying to write perfect mapping functions, but it should be possible to get within a few percent of optimal.
I guess just concentrate on placing the 5 white kings and ignore the case when the 5 white kings are placed symmetrically (which would in theory leave room for reducing the number of placements of the black kings).

My suicide indexing code (which has to deal e.g. with KKKKKvK) does this:

Code: Select all

  } else { /* 3 and higher, e.g. KKKvK and KKKKvK */
    for (i = 1; i < norm[0]; i++)
      if (triangle[pos[0]] > triangle[pos[i]])
        Swap(pos[0], pos[i]);
    if (pos[0] & 0x04)
      for (i = 0; i < n; i++)
        pos[i] ^= 0x07;
    if (pos[0] & 0x20)
      for (i = 0; i < n; i++)
        pos[i] ^= 0x38;
    if (offdiag[pos[0]] > 0)
      for (i = 0; i < n; i++)
        pos[i] = flipdiag[pos[i]];
    for (i = 1; i < norm[0]; i++)
      for (j = i + 1; j < norm[0]; j++)
        if (mtwist[pos[i]] > mtwist[pos[j]])
          Swap(pos[i], pos[j]);

    idx = multidx[norm[0] - 1][triangle[pos[0]]];
    for (i = 1; i < norm[0]; i++)
      idx += binomial[i][mtwist[pos[i]]];
  }

Here triangle[s] is basically the "orbit" of square s under the symmetry group.

Code: Select all

static const uint8_t triangle[] = {
  6, 0, 1, 2, 2, 1, 0, 6,
  0, 7, 3, 4, 4, 3, 7, 0,
  1, 3, 8, 5, 5, 8, 3, 1,
  2, 4, 5, 9, 9, 5, 4, 2,
  2, 4, 5, 9, 9, 5, 4, 2,
  1, 3, 8, 5, 5, 8, 3, 1,
  0, 7, 3, 4, 4, 3, 7, 0,
  6, 0, 1, 2, 2, 1, 0, 6
};

I select the piece/king with the "lowest" orbit and mirror the board so the king ends up in the triangle a1-d1-d4. Let's call it the primary king. Then I sort the rest according to their mtwist[] values:

Code: Select all

const uint8_t mtwist[] = {
  15, 63, 55, 47, 40, 48, 56, 12,
  62, 11, 39, 31, 24, 32,  8, 57,
  54, 38,  7, 23, 16,  4, 33, 49,
  46, 30, 22,  3,  0, 17, 25, 41,
  45, 29, 21,  2,  1, 18, 26, 42,
  53, 37,  6, 20, 19,  5, 34, 50,
  61, 10, 36, 28, 27, 35,  9, 58,
  14, 60, 52, 44, 43, 51, 59, 13
};

This maps the remaining identical pieces to numbers that are from 0 to the mtwist[] value of the primary king.
This is not optimal, in particular when the primary king is on the diagonal or when there are multiple kings in the lowest orbit, but it works and isn't too complicated. Of course in chess (variants) a KKKKKvK table is already tiny compared to a KQRBNvK table.

A king on a 10x10 board can have at most 9+8 = 17 moves. So doing (wK, bK) slicing and binom(48,4)*binom(44,4) positions per slice, you would need at most 18 slices in RAM for 55.4 Gb (similar to the 9 king-slices for chess), but then you have indeed excessive I/O.

Yes, perhaps it is still acceptable if it's just a one-time exercise.

But if you can enumerate perfectly or close to perfectly, the total number of position is 647156159148 (if ChatGPT applied Burnside's lemma correctly), which is just 75.34 GB with 1 bit per position. (And this number seems correct if we approximate using 50!/40!/5!/5!/4/8/1024/1024/1024.)

I'm curious to learn what prompt you gave ChatGPT to get that result.

I asked: "how many ways are there to place 5v5 kings on a 10x10 draughts board, taking into account any symmetries of the board."

I instructed Gemini to expand the Cycle Index Polynomial and the result is the same (647,156,159,148 positions):

Expand ((e+b+w)^50 + 2*(e^2+b^2+w^2)^25 + (e+b+w)^10 * (e^2+b^2+w^2)^20)/4 and collect the coefficient of the term e^40 b^5 w^5

The problem is how to enumerate that number. Do you have any idea or suggestion? Ideally, I'd like it to be a sum of products of binomials, so that one can index each term in the sum efficiently. But there are many cases (e.g. there can be 0, 2, or 4 kings on the main diagonal for each color, the other kings are unrestricted, and for those positions you have to restrict one to a 15 square triangle, but which king?)

So see above for a way to get an approximation. I did not calculate how close it gets.

To do better, you have to treat the special cases:
- primary king on the diagonal. Then find a secondary king by looking at the orbits under the remaining symmetry.
- choice of primary kings from 2, 3 or 4 kings in the same lowest orbit.
You probably only want to treat the cases that are worth it, i.e. that lead to a substantial reduction.

The black kings are then treated in the usual way.

[syzygy]

If I wanted to generate the 5v5 kings draughts endgame databases, I would probably just write a symmetry-perfect indexing function for 5 white kings. There are 530,828 unique positions, which probably split up into not that many cases.

I would then make sure that the symmetric positions are indexed at the end of the range, so that it is easy to check whether the placement of the white kings results in a symmetric position (before the placement of the black kings). This is helpful to correctly implement unmoving: if white unmoves from a non-symmetric position (white-kings index < threshold) to a symmetric position (white-kings index >= threshold), then you also need to unmove to the (index of the) position obtained by mirroring the board.

I think with 5 white kings only the diagonal symmetry can remain, namely with an odd number of kings on the diagonal and the other kings on pairs of diagonal-symmetric squares. The anti-diagonal symmetry can only remain if you have an even number of white kings. So with 4 kings getting the unmoving right is a bit more messy.

With perfect indexing of the 5 white kings and regular indexing of the 5 black kings, you get a total range of 530,828 * 1,221,759 = 648,543,886,452 positions, which is very close to the optimal number 647,156,159,148.

[Rein Halbersma]

I select the piece/king with the "lowest" orbit and mirror the board so the king ends up in the triangle a1-d1-d4. Let's call it the primary king. Then I sort the rest according to their mtwist[] values:

[...]

This maps the remaining identical pieces to numbers that are from 0 to the mtwist[] value of the primary king.
This is not optimal, in particular when the primary king is on the diagonal or when there are multiple kings in the lowest orbit, but it works and isn't too complicated. Of course in chess (variants) a KKKKKvK table is already tiny compared to a KQRBNvK table.

[...]

I did not calculate how close it gets.

OK, so for 5Kv1K on a chessboard, there are 449,846,208 unrestricted positions. The fully symmetry reduced count is 56,238,070. Fully symmetry reducing only the 5 white kings and adding 1 black king gives 56,299,334. Using your scheme for the 5 white kings and adding 1 black king gives 73,123,774. So instead of an 8-fold reducction you get a 6.15-fold reduction, which has an overhead of 30%, not too bad!

[Rein Halbersma]

If I wanted to generate the 5v5 kings draughts endgame databases, I would probably just write a symmetry-perfect indexing function for 5 white kings. There are 530,828 unique positions, which probably split up into not that many cases.

I would then make sure that the symmetric positions are indexed at the end of the range, so that it is easy to check whether the placement of the white kings results in a symmetric position (before the placement of the black kings). This is helpful to correctly implement unmoving: if white unmoves from a non-symmetric position (white-kings index < threshold) to a symmetric position (white-kings index >= threshold), then you also need to unmove to the (index of the) position obtained by mirroring the board.

I think with 5 white kings only the diagonal symmetry can remain, namely with an odd number of kings on the diagonal and the other kings on pairs of diagonal-symmetric squares. The anti-diagonal symmetry can only remain if you have an even number of white kings. So with 4 kings getting the unmoving right is a bit more messy.

With perfect indexing of the 5 white kings and regular indexing of the 5 black kings, you get a total range of 530,828 * 1,221,759 = 648,543,886,452 positions, which is very close to the optimal number 647,156,159,148.

If I adapt your orbit + mtwist approach to 10x10 draughts, I get the following numbers. For 5Kv5K on a 10x10 draughts board, there are 2,588,614,098,840 unrestricted positions. The fully symmetry reduced count is 647,156,159,148 (I had to prompt Gemini twice to get the correct count!). Fully symmetry reducing only the 5 white kings and adding 5 black kings gives 648,543,886,452. Using your scheme for the 5 white kings and adding 5 black kings gives 751,080,010,527. So instead of a 4-fold reduction I'd get a 3.45-fold reduction, which is an overhead of 16%, also not too bad!

[Rein Halbersma]

I would then make sure that the symmetric positions are indexed at the end of the range, so that it is easy to check whether the placement of the white kings results in a symmetric position (before the placement of the black kings). This is helpful to correctly implement unmoving: if white unmoves from a non-symmetric position (white-kings index < threshold) to a symmetric position (white-kings index >= threshold), then you also need to unmove to the (index of the) position obtained by mirroring the board.

This seems rather difficult. There are multiple symmetry subgroups to consider (for general positions, say 4 white kings). E.g. white can also unmove from a position that is symmetric under only a subgroup (e.g. only flips in anti-diagonal) to a position that is symmetric under another subgroup (180 degree rotations).

How do you treat unmoving into (partially or fully) symmetric positions using your orbit+mtwist scheme? These are ordered by lowest orbit followed by a binomial for the remaining pieces, no? Do you have a quick way of determining whether a position is symmetric?

BTW, in the first iteration, you can compute the lexicographical minimal tuple of kings under all symmetries and set positions which are not minimal to ILLEGAL, so that these are skipped during subsequent iterations. That way, you will only compute the fully symmetry reduced positions. Is that something you do?

[Rein Halbersma]

Do you have a quick way of determining whether a position is symmetric?

The board has 6 orbits of size 8, and 4 orbits of size 4. So with bitmasks for each of the orbits you can do a logical AND over the 10 masks of popcount(mask & occupied) % SIZE (with SIZE is 8 or 4). That should identify the fully symmetric positions. For subgroups, you can also have one mask per orbit. But I'm not sure how unmoving from unsymmetric -> partially symmetric and partially symmetric -> fully symmetric should be treated.