Tablebase suggestion

[syzygy]

I now found an old chessboard that becomes a 10x10 draughts board when flipped, so who knows I might give it a try some day

[syzygy]

I now found an old chessboard that becomes a 10x10 draughts board when flipped, so who knows I might give it a try some day

Just a quick start.

There are 15 orbits
10 lower orbits, each with 4 squares
5 higher orbits, each with 2 squares.

Let's first assume not all Ks are in the higher orbits (i.e. not all Ks on the diagonal).

Case 1:
The lowest non-empty orbit contains 1 K.
This is easy: map it to the upper quarter of the board, then place the other 4Ks in the higher orbits in the normal way.

Case 2:
The lowest non-empty orbit contains 3Ks.
This is just as easy: map the empty square in the orbit to the lower quarter of the board (or the upper, just fix one).

Case 3:
The lowest non-empty orbit contains 4Ks.
This is also easy: map the remaining K to the upper quarter of the board.

Case 4:
The lowest non-empty orbit contains 2Ks.
Now there are three cases: 1+6, 1+50, 1+45

Case 4a: 1+6, anti-diagonal symmetry
Enumerate the orbits under the anti-diagonal symmetry. Each orbit contains 2 squares.
If the lowest non-empty orbit has one K, then map it to the upper half. The rest is easy.
If the lowest non-empty orbits has 2 Ks, then map the 5th K to the upper half of the board.

Case 4b: 1+50, 180 degrees rotational symmetry.
Basically same as case 4a.

Case 4c: 1+45, diagonal symmetry
Do the same, but now there two types of orbits left.
But this seems doable.

And then we still have to deal with the case where all the 5Ks are on the diagonal. They can't be anti-diagonally symmetric because 5 is odd, so this should be easy. Basically find the lowest orbit with 1 K and map it to the upper half of the board.

[Rein Halbersma]

An absolute horror show would be to write a symmetry-perfect indexing function for 8Kv8K on an 8x8 checkerboard.
That has choose(32, 8) * choose(24, 8) = 7.7 trillion positions, with 1 bit per position and full 4-fold symmetry reduction you get it down to 225 Gb.
You'd have to partition the pieces over 6 orbits of length 4 and 4 orbits of length 2, and enumerate all the cases
Not a serious proposal since the full 16 piece checkers endgame database would be ~20 times larger than the full 8 piece chess endgame database. But at least 8Kv8K is already computable. I'm aware of an attempt to compute the full 12 piece checkers db (4x the size of the chess 7 dbs) on regular hardware (<= 256 Gb RAM).

[syzygy]

An absolute horror show would be to write a symmetry-perfect indexing function for 8Kv8K on an 8x8 checkerboard.
That has choose(32, 8) * choose(24, 8) = 7.7 trillion positions, with 1 bit per position and full 4-fold symmetry reduction you get it down to 225 Gb.
You'd have to partition the pieces over 6 orbits of length 4 and 4 orbits of length 2, and enumerate all the cases
Not a serious proposal since the full 16 piece checkers endgame database would be ~20 times larger than the full 8 piece chess endgame database. But at least 8Kv8K is already computable. I'm aware of an attempt to compute the full 12 piece checkers db (4x the size of the chess 7 dbs) on regular hardware (<= 256 Gb RAM).

One they might solve checkers! Oh, wait...

[syzygy]

Let's have a look again at 5v5 kings.
We index them with a white-kings index range of 530,828 and a black-kings index range of 1,221,759.
So each position has two coordinates (wk_idx, bk_idx). We can combine these into one range wk_idx * 1,221,759 + bk_idx, but let's not do that immediately.

Instead, we split up the ranges in blocks, e.g. 16 x 16 blocks.
Let's call the ranges w0,...,w15 and b0,...,b15.
The idea is to store each bitmap as 256 blocks/slices w_i x b_j.

If we unmove wtm positions into btm positions, we only look at black moves.
So the position of the white kings will not change, i.e. the moves and unmoves do not change the wk_idx coordinate.
So what we do is:

Code: Select all

for i = 0..15 {
    clear a bitmap for the range w_i x (b_0 + b_1 + ... + b_15)
    for j = 0..15 {
      load the wtm bitmap of newly wins or losses for the range w_i x b_j
      unmove from these positions into w_i x (b_0 + b_1 + ... + b_15)
    }
    save the bitmap for the range w_i x (b_0 + b_1 + ... + b_15) as 16 blocks w_i x b_j
}

And similar for verifying losses by checking all successor positions of a potential loss.
And similar for unmoving btm positions into wtm positions.

This reduces the amount of memory required by a factor of 16. And clearly you can pick any factor you need to make things fit in RAM.

[syzygy]

Oops...

If we unmove wtm positions into btm positions, we only look at black moves.
So the position of the white kings will not change, i.e. the moves and unmoves do not change the wk_idx coordinate.

Unfortunately this is not true, or at least not equally true, the other way around.

The first problem is that bk_idx does change if the positions of the white kings change, at least if we let the black indexing scheme skip over the squares with white kings.
I guess this can be fixed by just indexing the black kings with an index range of 0 to Bin(50,5) - 1 and accept the broken positions.

The second problem is that bk_idx does change if we unmove from a position with non-symmetric white kings to a position with symmetric white kings. We then have to unmove also the position with the black king configuration mirrored. So ideally the corresponding bk_idx positions are in the same block. But that seems difficult to achieve, even if we use the simplificed Bin(50,5) scheme.

We could instead try to always use the lower of the two bk_idx values (if wk_idx corresponds to a symmetric position). But the lower one can still be in a different block...

Or we could take a very wasteful Bin(50,5) x Bin(50,5) indexing scheme and split that into 16x16 blocks. Then that fits in 32.7 GB...

There should be a better solution....

[syzygy]

The second problem is that bk_idx does change if we unmove from a position with non-symmetric white kings to a position with symmetric white kings. We then have to unmove also the position with the black king configuration mirrored. So ideally the corresponding bk_idx positions are in the same block. But that seems difficult to achieve, even if we use the simplificed Bin(50,5) scheme.

Since unmoves from wk-non-symmetric to wk-symmetric might be relatively rare, it might work to store the indexes of the updated positions in a separate file and add them to the relevant bitmaps after all blocks have been treated.

[Rein Halbersma]

There should be a better solution....

I’ll have time to further analyze this later in the week. The approach I’m looking at now is to first partition pieces over orbits, then enumerate residual symmetry groups per orbit, and (bottleneck so far) across-orbit residual symmetry interaction, then assign squares within orbits. I’m hoping to fully decompose 4 kings indexing on a checkerboard into a sum of binomial products in a way that matches the Polya-counted number. The goal is to be able to this for general piece counts. For checkers/draughts this is a lot easier than chess, because the Hasse diagram (that encodes the relations between the various subgroups) for D2 is much simpler than for D4.