Tablebase suggestion

[syzygy]

For regular chess we know that we have two kings with multiplicity 1. We can start by placing them in the usual way. This also avoids a lot of illegal positions.
Then in 441 out of 462 cases we're already done: no symmetries left, and the remaining pieces can be placed group by group using combinadics.

In the remaining 21 cases, both kings are on the main diagonal. There is now exactly one diagonal symmetry left.
There are 28 orbits of size 2, 6 orbits of size 1.

ChatGPT happily ploughed through all this. I let it generate prefix tables for 22 classes: 1 with the trivial stabilizer (both kings uniquely fix the position) and 21 different tables (1 for each king pair, with white king on a1, b2, c3 or d4). Remaining pieces are still placed orbit by orbit, but the kings positions are remembered, i.e. effectively, the state for the recursion is now (kings positions, #orbits, #material, stabilizer)

Different tables for the 21 king placements on the diagonal should not be needed. Perhaps you need to renumber the orbits on the diagonal so that the empty ones are 0-5 and the king ones are 6,7, for example. This reordering commutes with the reflection.

My perfect ranking function is now fully integrated into my new generator:
https://github.com/syzygy1/tb8gen/blob/ ... #L485-L723

The precomputed table has 2160 entries of 56 bytes, so about 120kb, but only 201 are actually valid (for up to 8 pieces including kings):

Code: Select all

// Per transition, one case per number of 2-orbits filled.
struct TransitionCase {
  uint8_t d;
  uint8_t rem;
  uint64_t diag_tail;
  uint64_t diag_block;
  uint64_t broken_tail;
  uint64_t per_full_block;
  uint64_t block;
  uint64_t prefix;
};

// There are 201 valid cases.
static struct TransitionCase transition_cases[45][12][4];

45 is the number of pairs (partition_of_<= 6 , member m of the partition). This is the material still to be placed (not including the kings). with m being the size of the group of identical pieces to be placed next.

12 refers to the number of pairs (p, s) with p, s >= 0 and 2 * p + s <= 5.
Here p is the number of 2-orbits (pairs of squares symmetric in the main diagonal) and s is the number of 1-orbits (squares on the main diagonal) that are fully occupied by the non-king pieces already placed. (In the code it is the inverse: empty 2-orbits, empty 1-orbits.)

4 is the possible number of 2-orbits d being occupied by group of pieces being placed next. So 0 <= d <= 3.

There are additional restrictions such as 2 * p + s + m <= 5 and 2 * d <= m, resulting in a total of 201 cases as mentioned.
I should probably pad the TransitionCase struct to 64 bytes and align the table on a cache line, so the table can only ever occupy 201 lines in the cache. (And then I can as well unfold p and s and make the array [45][3][6][4].)

Initially I only wanted to use the perfect ranking function for the final compressed format, but I decided to use it also during generation. Mainly because the generator can now directly report the final "clean" statistics as it calculates the wins and losses for each ply.

I think it should be possible to iterate through all unranked positions incrementally, but I haven't yet studied the code that ChatGPT generated for this .