Tablebase suggestion

[Ajedrecista]

Hello:

[...]

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?)

[...]

Nobody asked me, but I took the time to expand that polynomial. I get the following coefficients for balanced number of kings:

Code: Select all

 1v1                              635 = 6.35e+02
 2v2                          346,610 ~ 3.47e+05
 3v3                       79,471,500 ~ 7.95e+07
 4v4                    9,395,670,480 ~ 9.40e+09
 5v5                  647,156,159,148 ~ 6.47e+11
 6v6               28,043,341,976,500 ~ 2.80e+13
 7v7              804,671,702,946,840 ~ 8.05e+14
 8v8           15,841,972,289,777,550 ~ 1.58e+16
 9v9          219,440,646,312,796,310 ~ 2.19e+17
10v10       2,176,851,194,198,517,880 ~ 2.18e+18
11v11      15,651,739,947,869,895,120 ~ 1.57e+19
12v12      82,171,634,651,800,132,320 ~ 8.22e+19
13v13     316,044,748,532,126,283,600 ~ 3.16e+20
14v14     890,085,210,010,964,159,760 ~ 8.90e+20
15v15   1,827,641,631,066,232,556,256 ~ 1.83e+21
16v16   2,712,905,546,038,783,327,650 ~ 2.71e+21
17v17   2,872,488,225,191,442,225,390 ~ 2.87e+21
18v18   2,127,769,055,759,077,734,300 ~ 2.13e+21
19v19   1,072,725,673,607,032,147,560 ~ 1.07e+21
20v20     353,999,472,353,840,959,360 ~ 3.54e+20

I also picked the coefficients of some unbalanced number of kings, with a difference not greater than two:

Code: Select all

 2v1    2 *                        14,840 =                        29,680 ~ 2.97e+04
 3v1    2 *                       230,960 =                       461,920 ~ 4.62e+05
 3v2    2 *                     5,300,880 =                    10,601,760 ~ 1.06e+07
 4v2    2 *                    59,608,980 =                   119,217,960 ~ 1.19e+08
 4v3    2 *                   874,056,900 =                 1,748,113,800 ~ 1.75e+09
 5v3    2 *                 7,516,525,680 =                15,033,051,360 ~ 1.50e+10
 5v4    2 *                78,921,989,760 =               157,843,979,520 ~ 1.58e+11
 6v4    2 *               539,297,251,050 =             1,078,594,502,100 ~ 1.08e+12
 6v5    2 *             4,314,364,289,520 =             8,628,728,579,040 ~ 8.63e+12
 7v5    2 *            24,037,149,986,160 =            48,074,299,972,320 ~ 4.81e+13
 7v6    2 *           152,235,214,857,840 =           304,470,429,715,680 ~ 3.04e+14
 8v6    2 *           704,087,755,467,250 =         1,408,175,510,934,500 ~ 1.41e+15
 8v7    2 *         3,621,022,373,235,660 =         7,242,044,746,471,320 ~ 7.24e+15
 9v7    2 *        14,081,753,144,384,760 =        28,163,506,288,769,520 ~ 2.82e+16
 9v8    2 *        59,847,449,599,652,250 =       119,694,899,199,304,500 ~ 1.20e+17
10v8    2 *       197,496,581,929,453,740 =       394,993,163,858,907,480 ~ 3.95e+17
10v9    2 *       702,210,064,587,461,920 =     1,404,420,129,174,923,840 ~ 1.40e+18
11v9    2 *     1,978,955,631,094,417,280 =     3,957,911,262,188,834,560 ~ 3.96e+18
11v10   2 *     5,936,866,882,622,701,440 =    11,873,733,765,245,402,880 ~ 1.19e+19
12v10   2 *    14,347,428,287,589,416,320 =    28,694,856,575,178,832,640 ~ 2.87e+19
12v11   2 *    36,520,726,524,348,659,600 =    73,041,453,048,697,319,200 ~ 7.30e+19
13v11   2 *    75,850,739,678,673,563,520 =   151,701,479,357,347,127,040 ~ 1.52e+20
13v12   2 *   164,343,269,262,082,878,240 =   328,686,538,524,165,756,480 ~ 3.29e+20
14v12   2 *   293,470,123,645,873,934,760 =   586,940,247,291,747,869,520 ~ 5.87e+20
14v13   2 *   541,790,997,431,281,848,000 = 1,083,581,994,862,563,696,000 ~ 1.08e+21
15v13   2 *   830,746,196,010,370,674,240 = 1,661,492,392,020,741,348,480 ~ 1.66e+21
15v14   2 * 1,305,458,307,947,276,155,200 = 2,610,916,615,894,552,310,400 ~ 2.61e+21
16v14   2 * 1,713,414,029,145,188,234,700 = 3,426,828,058,290,376,469,400 ~ 3.43e+21
16v15   2 * 2,284,552,038,789,114,376,920 = 4,569,104,077,578,228,753,840 ~ 4.57e+21
17v15   2 * 2,553,322,866,859,429,497,360 = 5,106,645,733,718,858,994,720 ~ 5.11e+21
17v16   2 * 2,872,488,225,191,442,225,390 = 5,744,976,450,382,884,450,780 ~ 5.74e+21
18v16   2 * 2,712,905,546,038,783,327,650 = 5,425,811,092,077,566,655,300 ~ 5.43e+21
18v17   2 * 2,553,322,866,859,429,497,360 = 5,106,645,733,718,858,994,720 ~ 5.11e+21
19v17   2 * 2,015,781,210,717,335,988,960 = 4,031,562,421,434,671,977,920 ~ 4.03e+21
19v18   2 * 1,567,829,830,593,805,143,200 = 3,135,659,661,187,610,286,400 ~ 3.14e+21
20v18   2 * 1,019,089,389,940,964,118,920 = 2,038,178,779,881,928,237,840 ~ 2.04e+21

17v15 and 18v17 have got the same number of positions, this is not a typo from copy and paste. I hope you will find these numbers useful.

Regards from Spain.

Ajedrecista.

[syzygy]

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!

Thanks for doing the math

[syzygy]

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!

Indeed not bad at all. And 75.5 GB vs 87.4 GB is probably not going to make the difference for the feasiblity of the computation.

I guess it might be difficult to arrange the indexing in such a way that the symmetric 5-white-king configurations are at the end of the range. But it should remain true that there is just one symmetry to check when unmoving (because 5 is odd), and this seems easy enough.

A long time ago I was suffering from unjustified fear for this unmoving problem under incompletely removed symmetries, so I ended up writing symmetry-perfect functions for all possible 5-piece combinations in suicide chess. That was not a lot of fun, but apparently doable. (Later I realised that in chess you can get better compression if you keep things flexible. If you index each set of identical pieces separately, you can permute their order and take the permutation that leads to best compression. For draughts this is less of an issue, but as the numbers show it is certainly not worth it to try to index 5v5 perfectly compared to just indexing the 5 white kings perfectly.)

[syzygy]

17v15 and 18v17 have got the same number of positions, this is not a typo from copy and paste. I hope you will find these numbers useful.

Now I wonder what the largest number of kings could be in 10x10 draughts (achieved from the starting position by legal moves).

[syzygy]

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).

Yes, I agree that "sorting" all symmetric configurations to the end of the indexing range is too difficult.

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?

For my suicide generator it is not a problem because the in-RAM generation uses a wasteful 10*64^5 indexing scheme. I convert to the small indexing range later.

For 462 * 64^(n-2) scheme (or the 462 * 62*61*... scheme), all you need to do is additionally unmove to the mirror position if a king unmove brings the king configuration from a non-symmetric configuration (with at most 1 king on the diagonal) to a symmetric configuration (with both kings on the diagonal).

Likewise, for 10 * 64^(n-1), all you need to do is to unmove to the mirror position if the leading piece moves from off-diagonal to on-diagonal.

I think in your 5v5 case, the five white kings are either non-symmetrically placed or their configuration is symmetric in the diagonal. Symmetry in the anti-diagonal is not possible because 5 is odd. So you would need to check if you unmove (with white) from a non-symmetric 5-white-kings configuration to a symmetric 5-white-kings configuration and, if so, also unmove to the mirror position.

If you move from symmetric to symmetric, it is not needed to unmove to the mirror position because that position is going to be covered anyway. (But you could still do it.)

If you do the same with 4 white kings, things get more complicated because there are different kinds of symmetries.
But I guess you can then check each symmetry separately. If you unmove from a non-symmetric position to a symmetric position with respect to a paricular symmetry, then you need to also unmove to the corresponding mirror position (i.e. once you have placed the black kings).

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?

No, I just store the "correct" values in all mirrored positions. It would indeed be possible to only store a value for a well-defined position in the orbit and set the rest to "don't care" (if you do some extra work when probing), but I have never tried this.

I don't know if you can do this in the first iteration. It seems to make more sense to reduce the final compressed file size than to reduce generation time, because it would seem to add a lot of extra computation.

[syzygy]

17v15 and 18v17 have got the same number of positions, this is not a typo from copy and paste. I hope you will find these numbers useful.

Now I wonder what the largest number of kings could be in 10x10 draughts (achieved from the starting position by legal moves).

Apparently 20v20 is legally reachable...

[Ajedrecista]

Hello:

Now I wonder what the largest number of kings could be in 10x10 draughts (achieved from the starting position by legal moves).

I have no idea, I went up to 20v20 brainlessly just as an upper bound. I remember that in 8x8 checkers, all the pieces from the starting position can be promoted without captures because I saw a proof game some years ago, so 12v12 are legally possible.

Regards from Spain.

Ajedrecista.

[syzygy]

I think in your 5v5 case, the five white kings are either non-symmetrically placed or their configuration is symmetric in the diagonal. Symmetry in the anti-diagonal is not possible because 5 is odd. So you would need to check if you unmove (with white) from a non-symmetric 5-white-kings configuration to a symmetric 5-white-kings configuration and, if so, also unmove to the mirror position.

Perhaps this overlooks that your 5-white-kings encoding would not be unique.

Still I think the same principle applies. If you unmove from a position that occurs twice to a position that occurs twice (or even just once), then there is no problem. If you unmove from a position that occurs once to a position that occurs twice (and more than twice does not seem possible with 5 white kings and/or 5 black kings), then you also need to unmove to the other position.

However, the danger is now that if you have two mirror positions p1 and p2 and you do the same unmove from both, that you end up in the same position q1 even though there is a mirror position q2.
This cannot happen, I think, if you unmove a black move, because a black unmove will not change the configuration of the white kings. But it has to be investigated whether this could occur for white unmoves.

There might still be advantages to having symmetry-perfect indexing for 5 white kings

[syzygy]

Hello:

Now I wonder what the largest number of kings could be in 10x10 draughts (achieved from the starting position by legal moves).

I have no idea, I went up to 20v20 brainlessly just as an upper bound. I remember that in 8x8 checkers, all the pieces from the starting position can be promoted without captures because I saw a proof game some years ago, so 12v12 are legally possible.

Apparently it is the same for 10x10 draughts. Unfortunately the link to the proof game I found did not work (and was not available from archive.org).

[Rein Halbersma]

I don't know if you can do this in the first iteration. It seems to make more sense to reduce the final compressed file size than to reduce generation time, because it would seem to add a lot of extra computation.

I have to think about this. I'd much rather remove all non-canonical positions up front (similar to eliminating illegal board configurations) and not having to repeat these calculations. It's rather easy to detect whether the non-leading orbit kings move into forbidden territory (square index above the mtwist value) than having to think about full or partial symmetry breaking, and diagonals being fixed points of certains symmetries but not others. The dihedral group is just small enough to brute force all this.

I don't know how much overhead it would give up front. There is a 30% savings as well of course since we can skip all ILLEGALS thereafter. Here is a very preliminary sketch of how I would tackle eliminating non-canonical configurations (I used the workd "lexmin" for now, should probably be "canonical" or something):

Code: Select all

enum struct dihedral
{ 
	id, flipH, flipV, flipAD, flipMD, rot90L, rot90R, rot180, 
	SIZE 
};

// TODO: we also need a group multiplication table (8x8) to compose multiple
// symmetry operations when fixing succesive orbit configurations.

using BB = uint64_t;
using u8 = uint8_t;
NUM_ORBITS8 = 6; // b1, c1, d1, c2, d2, d3
NUM_ORBITS4 = 4; // a1, b2, c3, d4

BB orbit8[NUM_ORBITS8];
BB orbit4[NUM_ORBITS4];

// precomputed indices of dihedral transformations for each orbit config
u8 transform8[0x100][NUM_ORBITS8][dihedral::SIZE]; // 256 * 6 * 8 * 1 = 12   Kb
u8 transform4[0x010][NUM_ORBITS4][dihedral::SIZE]; //  16 * 4 * 8 * 1 =  0.5 Kb

// pext() each orbit config into an 8-bit or 4-bit index
// look up the sym-transformed index in the corresponding table
// pdep() the index back into an 64-bit orbit bitboard

auto transform8(BB occupied, unsigned idx, dihedral sym) -> BB
{
	pdep(transform8[pext(occupied & orbit8[idx], 0xff)][idx][sym], orbit8[idx])
}

auto transform4(BB occupied, unsigned idx, dihedral sym) -> BB
{
	pdep(transform8[pext(occupied & orbit4[idx], 0xff)][idx][sym], orbit4[idx])
}

// apply any of the dihedral group elements on a bitboard
// YES, there are optimized functions for this on CPW, too lazy to look them up, 
// these should be pretty fast too, and they can be re-used in lexmin()
//
// spread an occupied bitboard into orbit bitboards under the dihedral group
// transform each orbit
// gather the orbit configs back to a sym-transformed occupied bitboard
auto transform(BB occupied, dihedral sym) -> BB
{
	auto res = 0ull;
	for (auto idx = 0; idx < NUM_ORBITS8; ++idx) {
		res |= transform8(occupied, idx, sym);
	}
	for (auto idx = 0; idx < NUM_ORBITS4; ++idx) {
		res |= transform4(occupied, idx, sym);
	}
	return res;
}

// precomputed 8-bit masks of all dihedral transformations that lex-minimize an orbit's config
u8 lexmin8[0x100][NUM_ORBITS8]; // 256 * 6 * 1 = 1.5 Kb;
u8 lexmin4[0x010][NUM_ORBITS4]; //  16 * 4 * 1 =  64  b;

// minimum lexicographical config of a single bitboard, and its remaining symmetries
auto lexmin(BB occupied, u8 symmetries) -> std::pair<BB, u8>
{
	// TODO:
	// split bitboard into orbits
	// loop until no orbits or symmetries left: 
	//	find the first one with lexmin8 % 8 or lexmin4 % 4 unequal to zero
	//  apply a lexmin symmetry (to the orbit only), 
	//  and remove it from the set of remaining symmetries
	//  find next non-symmetrically occupied orbit, apply remaining symmetries, composed with previous element(s)
	//  NOTE: can test with % 8, % 4 or % 2 depending on the remaining subgroup size
	// return transformed bitboard and remaining symmetries (to be re-used on the next bitboard)
}

// sequentially lexmin a set of two bitboards, and its remaining symmetries
auto lexmin(BB wK, BB bK) -> std::tuple<BB, BB, u8>
{
	auto [wKt, wSym] = lexmin(wK, 0xFF); 
	auto [bKt, bSym] = lexmin(bK, wSym);
	return { wKt, bKt, bSym };
}

// initialize all positions to ILLEGAL for which this returns <false>
auto is_lexmin(BB wK, BB bK) -> bool
{
	return std::get<2>(lexmin(wK, bK)) == 0;
}