Correct, because 17v15 has 18 empty squares and 18v17 has 15 empty squares. So the total is 50!/(18! * 17! * 15!) in both casesAjedrecista wrote: ↑Mon Mar 02, 2026 8:22 pm
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.
Tablebase suggestion
Moderator: Ras
-
Rein Halbersma
- Posts: 770
- Joined: Tue May 22, 2007 11:13 am
Re: Tablebase suggestion
-
Rein Halbersma
- Posts: 770
- Joined: Tue May 22, 2007 11:13 am
-
syzygy
- Posts: 5938
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Tablebase suggestion
I see. I have to think about this as well. I was thinking unmoving between lexicographically minimal representatives was going to be a hassle. But if you can do that and thereby create an indexing function that assigns to each position a unique number (but just has a somewhat larger indexing range than optimal), then that would make everything else a lot easier.Rein Halbersma wrote: ↑Mon Mar 02, 2026 11:39 pmI 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.
-
Rein Halbersma
- Posts: 770
- Joined: Tue May 22, 2007 11:13 am
Re: Tablebase suggestion
In your triangle+mtwist indexing, you fixate the symmetry by the leading orbit configuration. So any moves from pieces in the lower orbits can simply be looked up. Either they move beyond the mtwist range and are outside the valid index range, or do might yield a valid but non canonical index. If you have precomputed this as ILLEGAL, then you ignore that unmove. Even non-leading pieces in the leading orbit can move how they like, and they don’t require transformations. So that leaves unmoves from the leading piece in the leading orbit, and you only have to compute the canonical configurations of those predecessors by finding the correct group element to map it to the canonical section.syzygy wrote: ↑Tue Mar 03, 2026 12:30 am I see. I have to think about this as well. I was thinking unmoving between lexicographically minimal representatives was going to be a hassle. But if you can do that and thereby create an indexing function that assigns to each position a unique number (but just has a somewhat larger indexing range than optimal), then that would make everything else a lot easier.
-
Rein Halbersma
- Posts: 770
- Joined: Tue May 22, 2007 11:13 am
Re: Tablebase suggestion
OK, I’ll bite
do you still have your code for a perfect 5-king indexing function on a chessboard? And how did you enumerate the various cases? It should be adaptable to draughts as well, and ideally be generalizable to N-king indexing-
Rein Halbersma
- Posts: 770
- Joined: Tue May 22, 2007 11:13 am
Re: Tablebase suggestion
So after having moved the leading (primary) king, you have to find the new leading orbit, bitwise-and its contents, pext() this into an 8/4/2 bit index (depending on chess/draughts orbit length), lookup the group element that makes the leading orbit canonical, apply that transformation to the entire board (using CPW bit wizardry or my sketched pext/lookup/pdep per orbit) and compute the index for this new config.Rein Halbersma wrote: ↑Tue Mar 03, 2026 12:58 amIn your triangle+mtwist indexing, you fixate the symmetry by the leading orbit configuration. So any moves from pieces in the lower orbits can simply be looked up. Either they move beyond the mtwist range and are outside the valid index range, or do might yield a valid but non canonical index. If you have precomputed this as ILLEGAL, then you ignore that unmove. Even non-leading pieces in the leading orbit can move how they like, and they don’t require transformations. So that leaves unmoves from the leading piece in the leading orbit, and you only have to compute the canonical configurations of those predecessors by finding the correct group element to map it to the canonical section.syzygy wrote: ↑Tue Mar 03, 2026 12:30 am I see. I have to think about this as well. I was thinking unmoving between lexicographically minimal representatives was going to be a hassle. But if you can do that and thereby create an indexing function that assigns to each position a unique number (but just has a somewhat larger indexing range than optimal), then that would make everything else a lot easier.
-
syzygy
- Posts: 5938
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Tablebase suggestion
I should still have it, and I think I know on which old hard disk...Rein Halbersma wrote: ↑Tue Mar 03, 2026 1:05 amOK, I’ll bite
I didn't write a perfect 5-king, but the perfect 4-king should be even more complicated.
-
syzygy
- Posts: 5938
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Tablebase suggestion
Found it, but now I realize I overpromisedsyzygy wrote: ↑Tue Mar 03, 2026 1:16 amI should still have it, and I think I know on which old hard disk...Rein Halbersma wrote: ↑Tue Mar 03, 2026 1:05 amOK, I’ll bite
I didn't write a perfect 5-king, but the perfect 4-king should be even more complicated.
With KKKKvK, you can start with the sole K.
The most complicated case I tackled will have been KKvKKK:
Code: Select all
int encode_23(void)
{
int idx;
if (stype[0] >= 9) {
if (stype[0] == 12)
idx = (triangle[pos[0]] + triangle[pos[1]]*(triangle[pos[1]]-1)/2) * 8 + twistcnt[pos[1]];
else if (stype[0] == 11)
idx = 120 + triangle[pos[0]] * 16 + diag[pos[1]];
else if (stype[0] == 10)
idx = 120 + 96 + triangle[pos[0]];
else
idx = 120 + 96 + 6 + diag[pos[0]] + (pos[1]>>3)*((pos[1]>>3)-1)/2;
idx = idx * (62*61*60/6) + pack(2);
} else if (stype[0] >= 7) { /* B1, A2 or B1, H7 */
if (stype[2] == 6)
idx = lpack231() * (27*26/2) + lpack22();
else if (stype[2] == 5)
idx = 27*27*26/2 + lpack23();
else if (stype[2] == 4)
idx = 27*27*26/2 + 27*26*25/6 + diag[pos[2]] * (27*26/2) + lpack232();
else if (stype[2] == 3)
idx = 27*27*26/2 + 27*26*25/6 + 8*27*26/2 + diag[pos[2]] * (27*26/2) + lpack232();
else if (stype[2] == 2)
idx = 27*27*26/2 + 27*26*25/6 + 8*27*26 + (diag[pos[2]] + diag[pos[3]]*(diag[pos[3]]-1)/2) * 27 + lpack231();
else if (stype[2] == 1)
idx = 27*27*26/2 + 27*26*25/6 + 8*27*26 + 8*7*27/2 + diag[pos[2]] * 27 + lpack231();
else
idx = 27*27*26/2 + 27*26*25/6 + 8*27*26 + 8*7*27/2 + 8*27 + diag[pos[2]] + diag[pos[3]]*(diag[pos[3]]-1)/2 + diag[pos[4]]*(diag[pos[4]]-1)*(diag[pos[4]]-2)/6;
idx += (120+96+6+6)*62*61*60/6 + (triangle[pos[0]] + 6 * (8 - stype[0])) * 19046;
} else if (stype[0] >= 5) { /* A1, E5 or A1, D4 */
if (stype[2] == 6)
idx = lower[pos[4]] * (28*27/2) + lower[pos[2]] + lower[pos[3]]*(lower[pos[3]]-1)/2;
else if (stype[2] == 5)
idx = 28*28*27/2 + lower[pos[2]] + lower[pos[3]]*(lower[pos[3]]-1)/2 + lower[pos[4]]*(lower[pos[4]]-1)*(lower[pos[4]]-2)/6;
else if (stype[2] == 4)
idx = 28*28*27/2 + 28*27*26/6 + dpack221() * (28*27/2) + lower[pos[3]] + lower[pos[4]]*(lower[pos[4]]-1)/2;
else if (stype[2] == 3)
idx = 28*28*27/2 + 28*27*26/6 + 6*28*27/2 + dpack221() * (28*27/2) + lower[pos[3]] + lower[pos[4]]*(lower[pos[4]]-1)/2;
else if (stype[2] == 2)
idx = 28*28*27/2 + 28*27*26/6 + 6*28*27 + dpack22() * 28 + lower[pos[4]];
else if (stype[2] == 1)
idx = 28*28*27/2 + 28*27*26/6 + 6*28*27 + 6*5*28/2 + dpack221() * 28 + lower[pos[3]];
else
idx = 28*28*27/2 + 28*27*26/6 + 6*28*27 + 6*5*28/2 + 6*28 + dpack23();
int p = triangle[pos[0]]-6, q = triangle[pos[1]]-6;
idx += (120+96+6+6)*62*61*60/6 + 12*19046 + (p + q*(q-1)/2 + 6 * (6 - stype[0])) * 19004;
} else if (stype[0] >= 1) { /* B1, G1 or A1, H1 */
int p = flap[pos[2]];
int q = flap[pos[3]];
int r = flap[pos[4]];
if (p > flap[pos[0]]) p--;
if (q > flap[pos[0]]) q--;
if (r > flap[pos[0]]) r--;
if (stype[2])
idx = p * (31*30/2) + q + r*(r-1)/2;
else
idx = 31*31*30/2 + p + q*(q-1)/2 + r*(r-1)*(r-2)/6;
if (stype[0] > 1)
idx += (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004 + (triangle[pos[0]] + 6 * (4-stype[0])) * 18910;
else
idx += (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004 + 18*18910 + (pos[0] & 0x07) * 18910;
} else {
if (stype[2] == 8)
idx = (4 * fourcnt[pos[3]] + fourcnt[pos[4]]) * (12*11*10/6) + fourflip[pos[2]] + fourflip[pos[3]]*(fourflip[pos[3]]-1)/2 + fourflip[pos[4]]*(fourflip[pos[4]]-1)*(fourflip[pos[4]]-2)/6;
else if (stype[2] == 7) {
int q = fourflip[pos[4]];
if (q > fourflip[pos[0]]) q--;
if (pos[4] & 0x20) q += 7;
idx = 3520 + fourcnt[pos[3]] * 924 + 14 * (fourflip[pos[2]] + fourflip[pos[3]]*(fourflip[pos[3]]-1)/2) + q - 12;
} else if (stype[2] == 6) {
int p = diag[pos[3]];
int q = diag[pos[4]];
if (p > diag[pos[1]]) p--;
if (p > diag[pos[0]]) p--;
if (q > diag[pos[1]]) q--;
if (q > diag[pos[0]]) q--;
idx = 3520 + 3696 + fourflip[pos[2]] * 91 + (p + q*(q-1)/2);
} else if (stype[2] == 5) {
if (offdiag[pos[4]]) {
idx = lower[pos[4]];
int p = lower[pos[2]], q = lower[flipdiag[pos[2] ^ 0x07] ^ 0x07];
if (p < q) {
if (idx > q) idx--;
if (idx > p) idx--;
} else {
if (idx > p) idx--;
if (idx > q) idx--;
}
} else {
idx = diag[pos[4]];
if (idx > diag[pos[1]]) idx--;
if (idx > diag[pos[0]]) idx--;
idx += 26;
}
idx += 3520 + 3696 + 1092 + fourflip[pos[2]] * 32;
} else if (stype[2] == 4) {
idx = 3520 + 3696 + 1092 + 384 + fourflip[pos[2]] * 29 + adjust3((pos[4] & 0x04) ? flap[pos[4] ^ 0x3f] : flap[pos[4]], flap[pos[0]], (pos[2] & 0x04) ? flap[pos[3]] : flap[pos[2]], flap[flipdiag[pos[2]]]);
} else if (stype[2] == 3) {
if (offdiag[pos[4] ^ 0x07]) {
idx = adjust3(lower[pos[4] ^ 0x07], lower[pos[0] ^ 0x07], lower[pos[2] ^ 0x07], lower[flipdiag[pos[2]] ^ 0x07]);
} else
idx = 25 + diag[pos[4] ^ 0x07];
idx += 3520 + 3696 + 1092 + 384 + 348 + fourflip[pos[2]] * 33;
} else if (stype[2] == 2) {
idx = 3520 + 3696 + 1092 + 1128 + fourflip[pos[2]];
} else if (stype[2] == 1) {
int p = fourflip[pos[2]], q = fourflip[pos[4]];
if (p > fourflip[pos[0]]) {
if (q > p) q--;
if (q > fourflip[pos[0]]) q--;
p--;
} else {
if (q > fourflip[pos[0]]) q--;
if (q > p) q--;
}
p -= 12;
q -= 12;
idx = 3520 + 3696 + 1092 + 1128 + 12 + p * 6 + q;
} else {
int p = fourflip[pos[2]]-12, q = fourflip[pos[3]]-12, r = fourflip[pos[4]]-12;
if (r < 4) {
idx = 4 * (p + q*(q-1)/2 + r*(r-1)*(r-2)/6);
if (pos[3] & 0x20) idx += 2;
if (pos[4] & 0x20) idx += 1;
} else if (q < 4) {
if (fourflip[pos[4]] > fourflip[pos[0]]) r--;
if (pos[3] & 0x20) r += 3;
idx = 16 + (r - 4) * 6 + p + q*(q-1)/2;
} else if (p < 4) {
if (fourflip[pos[3]] > fourflip[pos[0]]) q--;
if (fourflip[pos[4]] > fourflip[pos[0]]) r--;
q -= 4;
r -= 4;
idx = 16 + 36 + p * 3 + q + r*(r-1)/2;
if ((pos[3] ^ pos[4]) & 0x20) idx += 12;
} else {
idx = 16 + 36 + 24;
if (pos[3] & 0x20) idx += 2;
if (pos[4] & 0x20) idx += 1;
}
idx += 3520 + 3696 + 1092 + 1128 + 12 + 42;
}
idx += (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004 + 22*18910 + diag[pos[0]] * 9570;
}
return idx;
}Code: Select all
void decode_23(int idx)
{
int p, q, r;
if (idx < (120+96+6+6)*62*61*60/6) {
p = idx / (62*61*60/6);
idx -= p * (62*61*60/6);
if (p < 120) {
r = p & 7;
p /= 8;
q = 1;
while (p >= q) {
p -= q;
q++;
}
pos[0] = invtriangle[p];
pos[1] = invtriangle[q];
switch (r) {
case 0:
break;
case 1:
pos[1] ^= 0x07;
break;
case 2:
pos[1] = flipdiag[pos[1]];
break;
case 3:
pos[1] = flipdiag[pos[1]] ^ 0x07;
break;
case 4:
pos[1] = flipdiag[pos[1]] ^ 0x38;
break;
case 5:
pos[1] = flipdiag[pos[1]] ^ 0x3f;
break;
case 6:
pos[1] ^= 0x38;
break;
case 7:
pos[1] ^= 0x3f;
break;
}
} else if (p < 120 + 96) {
pos[0] = invtriangle[(p - 120)/16];
pos[1] = invdiag[(p - 120) & 0x0f];
} else if (p < 120 + 96 + 6) {
pos[0] = invtriangle[p - 120 - 96];
pos[1] = flipdiag[pos[0]] ^ 0x07;
} else {
p -= 120 + 96 + 6;
q = 1;
while (p >= q) {
p -= q;
q++;
}
pos[0] = invdiag[p];
pos[1] = invdiag[q] ^ 0x07;
}
unpack(2, idx);
} else if (idx < (120+96+6+6)*62*61*60/6 + 12*19046) {
idx -= (120+96+6+6)*62*61*60/6;
p = idx / 19046;
idx -= p * 19046;
if (p < 6)
pos[0] = invtriangle[p];
else
pos[0] = invtriangle[p - 6] ^ 0x07;
pos[1] = flipdiag[pos[0]];
if (idx < 27*27*26/2) {
p = idx / (27*26/2);
idx -= p * (27*26/2);
if (p >= lower[pos[0]]) p++;
pos[4] = flipdiag[invlower[p]];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
if (p >= lower[pos[0]]) p++;
if (idx >= lower[pos[0]]) idx++;
pos[2] = invlower[idx];
pos[3] = invlower[p];
} else if (idx < 27*27*26/2 + 27*26*25/6) {
idx -= 27*27*26/2;
p = 2;
while (idx >= p*(p-1)/2) {
idx -= p*(p-1)/2;
p++;
}
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
if (p >= lower[pos[0]]) p++;
if (q >= lower[pos[0]]) q++;
if (idx >= lower[pos[0]]) idx++;
pos[2] = invlower[idx];
pos[3] = invlower[q];
pos[4] = invlower[p];
} else if (idx < 27*27*26/2 + 27*26*25/6 + 8*27*26/2) {
idx -= 27*27*26/2 + 27*26*25/6;
p = idx / (27*26/2);
idx -= p * (27*26/2);
pos[2] = invdiag[p];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
if (idx >= lower[pos[0]]) idx++;
if (p >= lower[pos[0]]) p++;
pos[3] = invlower[idx];
pos[4] = flipdiag[invlower[p]];
} else if (idx < 27*27*26/2 + 27*26*25/6 + 8*27*26) {
idx -= 27*27*26/2 + 27*26*25/6 + 8*27*26/2;
p = idx / (27*26/2);
idx -= p * (27*26/2);
pos[2] = invdiag[p];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
if (idx >= lower[pos[0]]) idx++;
if (p >= lower[pos[0]]) p++;
pos[3] = invlower[idx];
pos[4] = invlower[p];
} else if (idx < 27*27*26/2 + 27*26*25/6 + 8*27*26 + 8*7*27/2) {
idx -= 27*27*26/2 + 27*26*25/6 + 8*27*26;
p = idx / 27;
idx -= p * 27;
if (idx >= lower[pos[0]]) idx++;
pos[4] = invlower[idx];
idx = 1;
while (p >= idx) {
p -= idx;
idx++;
}
pos[2] = invdiag[p];
pos[3] = invdiag[idx];
} else if (idx < 27*27*26/2 + 27*26*25/6 + 8*27*26 + 8*7*27/2 + 8*27) {
idx -= 27*27*26/2 + 27*26*25/6 + 8*27*26 + 8*7*27/2;
p = idx / 27;
idx -= p * 27;
pos[2] = invdiag[p];
if (idx >= lower[pos[0]]) idx++;
pos[3] = invlower[idx];
pos[4] = flipdiag[invlower[idx]];
} else {
idx -= 27*27*26/2 + 27*26*25/6 + 8*27*26 + 8*7*27/2 + 8*27;
p = 2;
while (idx >= p*(p-1)/2) {
idx -= p*(p-1)/2;
p++;
}
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
pos[2] = invdiag[idx];
pos[3] = invdiag[q];
pos[4] = invdiag[p];
}
} else if (idx < (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004) {
idx -= (120+96+6+6)*62*61*60/6 + 12*19046;
p = idx / 19004;
idx -= p * 19004;
if (p < 6) {
int q = 1;
while (p >= q) {
p -= q;
q++;
}
pos[0] = invdiag[p];
pos[1] = invdiag[q] ^ 0x3f;
} else {
p -= 6;
int q = 1;
while (p >= q) {
p -= q;
q++;
}
pos[0] = invdiag[p];
pos[1] = invdiag[q];
}
if (idx < 28*28*27/2) {
p = idx / (28*27/2);
idx -= p * (28*27/2);
pos[4] = flipdiag[invlower[p]];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
pos[2] = invlower[idx];
pos[3] = invlower[p];
} else if (idx < 28*28*27/2 + 28*27*26/6) {
idx -= 28*28*27/2;
p = 2;
while (idx >= p*(p-1)/2) {
idx -= p*(p-1)/2;
p++;
}
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
pos[2] = invlower[idx];
pos[3] = invlower[q];
pos[4] = invlower[p];
} else if (idx < 28*28*27/2 + 28*27*26/6 + 6*28*27/2) {
idx -= 28*28*27/2 + 28*27*26/6;
p = idx / (28*27/2);
idx -= p * (28*27/2);
if (p >= diag[pos[0]]) p++;
if (p >= diag[pos[1]]) p++;
pos[2] = invdiag[p];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
pos[3] = invlower[idx];
pos[4] = flipdiag[invlower[p]];
} else if (idx < 28*28*27/2 + 28*27*26/6 + 6*28*27) {
idx -= 28*28*27/2 + 28*27*26/6 + 6*28*27/2;
p = idx / (28*27/2);
idx -= p * (28*27/2);
if (p >= diag[pos[0]]) p++;
if (p >= diag[pos[1]]) p++;
pos[2] = invdiag[p];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
pos[3] = invlower[idx];
pos[4] = invlower[p];
} else if (idx < 28*28*27/2 + 28*27*26/6 + 6*28*27 + 6*5*28/2) {
idx -= 28*28*27/2 + 28*27*26/6 + 6*28*27;
p = idx / 28;
idx -= p * 28;
pos[4] = invlower[idx];
idx = 1;
while (p >= idx) {
p -= idx;
idx++;
}
if (p >= diag[pos[0]]) p++;
if (p >= diag[pos[1]]) p++;
if (idx >= diag[pos[0]]) idx++;
if (idx >= diag[pos[1]]) idx++;
pos[2] = invdiag[p];
pos[3] = invdiag[idx];
} else if (idx < 28*28*27/2 + 28*27*26/6 + 6*28*27 + 6*5*28/2 + 6*28) {
idx -= 28*28*27/2 + 28*27*26/6 + 6*28*27 + 6*5*28/2;
p = idx / 28;
idx -= p * 28;
if (p >= diag[pos[0]]) p++;
if (p >= diag[pos[1]]) p++;
pos[2] = invdiag[p];
pos[3] = invlower[idx];
pos[4] = flipdiag[invlower[idx]];
} else {
idx -= 28*28*27/2 + 28*27*26/6 + 6*28*27 + 6*5*28/2 + 6*28;
p = 2;
while (idx >= p*(p-1)/2) {
idx -= p*(p-1)/2;
p++;
}
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
if (idx >= diag[pos[0]]) idx++;
if (idx >= diag[pos[1]]) idx++;
if (q >= diag[pos[0]]) q++;
if (q >= diag[pos[1]]) q++;
if (p >= diag[pos[0]]) p++;
if (p >= diag[pos[1]]) p++;
pos[2] = invdiag[idx];
pos[3] = invdiag[q];
pos[4] = invdiag[p];
}
} else if (idx < (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004 + 22*18910) {
idx -= (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004;
p = idx / 18910;
idx -= p * 18910;
if (p < 6)
pos[0] = invtriangle[p];
else if (p < 12)
pos[0] = flipdiag[invtriangle[p - 6]];
else if (p < 18)
pos[0] = invtriangle[p - 12];
else
pos[0] = invdiag[p - 18];
pos[1] = pos[0] ^ 0x07;
if (idx < 31*31*30/2) {
int q = idx / (31*30/2);
idx -= q * (31*30/2);
if (q >= flap[pos[0]]) q++;
pos[2] = invflap[q] ^ 0x07;
q = 1;
while (idx >= q) {
idx -= q;
q++;
}
if (idx >= flap[pos[0]]) idx++;
if (q >= flap[pos[0]]) q++;
pos[3] = invflap[idx];
pos[4] = invflap[q];
} else {
idx -= 31*31*30/2;
int r = 2;
while (idx >= r*(r-1)/2) {
idx -= r*(r-1)/2;
r++;
}
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
if (idx >= flap[pos[0]]) idx++;
if (q >= flap[pos[0]]) q++;
if (r >= flap[pos[0]]) r++;
pos[2] = invflap[idx];
pos[3] = invflap[q];
pos[4] = invflap[r];
}
if (p >= 12 && p < 18) {
int i;
for (i = 1; i < 4; i++)
if (pos[i] & 0x04) pos[i] ^= 0x38;
}
} else {
idx -= (120+96+6+6)*62*61*60/6 + 12*19046 + 12*19004 + 22*18910;
p = idx / 9570;
idx -= p * 9570;
pos[0] = invdiag[p];
pos[1] = invdiag[p] ^ 0x3f;
if (idx < 3520) {
p = idx / (12*11*10/6);
idx -= p * (12*11*10/6);
int r = 2;
while (idx >= r*(r-1)/2) {
idx -= r*(r-1)/2;
r++;
}
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
pos[2] = invfourflip[idx];
switch (p/4) {
case 0:
pos[3] = invfourflip[q];
break;
case 1:
pos[3] = flipdiag[invfourflip[q]];
break;
case 2:
pos[3] = flipdiag[invfourflip[q] ^ 0x07] ^ 0x07;
break;
case 3:
pos[3] = invfourflip[q] ^ 0x3f;
break;
}
switch (p & 3) {
case 0:
pos[4] = invfourflip[r];
break;
case 1:
pos[4] = flipdiag[invfourflip[r]];
break;
case 2:
pos[4] = flipdiag[invfourflip[r] ^ 0x07] ^ 0x07;
break;
case 3:
pos[4] = invfourflip[r] ^ 0x3f;
break;
}
} else if (idx < 3520 + 3696) {
idx -= 3520;
p = idx / 924;
idx -= p * 924;
q = idx / 14;
idx -= q * 14;
if (idx < 7) {
idx += 12;
if (idx >= fourflip[pos[0]]) idx++;
pos[4] = invfourflip[idx];
} else {
idx += 12-7;
if (idx >= fourflip[pos[0]]) idx++;
pos[4] = invfourflip[idx] ^ 0x3f;
}
idx = 1;
while (q >= idx) {
q -= idx;
idx++;
}
pos[2] = invfourflip[q];
switch (p) {
case 0:
pos[3] = invfourflip[idx];
break;
case 1:
pos[3] = flipdiag[invfourflip[idx]];
break;
case 2:
pos[3] = flipdiag[invfourflip[idx] ^ 0x07] ^ 0x07;
break;
case 3:
pos[3] = invfourflip[idx] ^ 0x3f;
break;
}
} else if (idx < 3520 + 3696 + 1092) {
idx -= 3520 + 3696;
p = idx / 91;
idx -= p * 91;
pos[2] = invfourflip[p];
p = 1;
while (idx >= p) {
idx -= p;
p++;
}
if (idx >= diag[pos[0]]) idx++;
if (idx >= diag[pos[1]]) idx++;
if (p >= diag[pos[0]]) p++;
if (p >= diag[pos[1]]) p++;
pos[3] = invdiag[idx];
pos[4] = invdiag[p];
} else if (idx < 3520 + 3696 + 1092 + 384) {
idx -= 3520 + 3696 + 1092;
p = idx / 32;
idx -= p * 32;
pos[2] = invfourflip[p];
pos[3] = flipdiag[pos[2]];
if (idx < 26) {
int p = lower[pos[2]], q = lower[flipdiag[pos[2] ^ 0x07] ^ 0x07];
if (p < q) {
if (idx >= p) idx++;
if (idx >= q) idx++;
} else {
if (idx >= q) idx++;
if (idx >= p) idx++;
}
pos[4] = invlower[idx];
} else {
idx -= 26;
if (idx >= diag[pos[0]]) idx++;
if (idx >= diag[pos[1]]) idx++;
pos[4] = invdiag[idx];
}
} else if (idx < 3520 + 3696 + 1092 + 384 + 348) {
idx -= 3520 + 3696 + 1092 + 384;
p = idx / 29;
idx -= p * 29;
pos[2] = invfourflip[p];
pos[3] = pos[2] ^ 0x3f;
pos[4] = invflap[unadjust3(idx, flap[pos[0]], (pos[2] & 0x04) ? flap[pos[3]] : flap[pos[2]], flap[flipdiag[pos[2]]])];
} else if (idx < 3520 + 3696 + 1092 + 1128) {
idx -= 3520 + 3696 + 1092 + 384 + 348;
p = idx / 33;
idx -= p * 33;
pos[2] = invfourflip[p];
pos[3] = flipdiag[pos[2] ^ 0x07] ^ 0x07;
if (idx < 25)
pos[4] = invlower[unadjust3(idx, lower[pos[0] ^ 0x07], lower[pos[2] ^ 0x07], lower[flipdiag[pos[2]] ^ 0x07])] ^ 0x07;
else
pos[4] = invdiag[idx - 25] ^ 0x07;
} else if (idx < 3520 + 3696 + 1092 + 1128 + 12) {
idx -= 3520 + 3696 + 1092 + 1128;
pos[2] = invfourflip[idx];
pos[3] = flipdiag[invfourflip[idx]];
pos[4] = invfourflip[idx] ^ 0x3f;
} else if (idx < 3520 + 3696 + 1092 + 1128 + 12 + 42) {
idx -= 3520 + 3696 + 1092 + 1128 + 12;
p = idx / 6;
idx -= p * 6;
p += 12;
idx += 12;
if (p >= fourflip[pos[0]]) {
p++;
if (idx >= fourflip[pos[0]]) idx++;
if (idx >= p) idx++;
} else {
if (idx >= p) idx++;
if (idx >= fourflip[pos[0]]) idx++;
}
pos[2] = invfourflip[p];
pos[3] = invfourflip[p] ^ 0x3f;
pos[4] = invfourflip[idx];
} else {
idx -= 3520 + 3696 + 1092 + 1128 + 12 + 42;
if (idx < 16) {
p = idx / 4;
int r = 2;
while (p >= r*(r-1)/2) {
p -= r*(r-1)/2;
r++;
}
int q = 1;
while (p >= q) {
p -= q;
q++;
}
pos[2] = invfourflip[p + 12];
pos[3] = invfourflip[q + 12];
pos[4] = invfourflip[r + 12];
if (idx & 2) pos[3] ^= 0x3f;
if (idx & 1) pos[4] ^= 0x3f;
} else if (idx < 16 + 36) {
idx -= 16;
p = idx / 6;
idx -= p * 6;
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
pos[2] = invfourflip[idx + 12];
pos[3] = invfourflip[q + 12];
if (p >= 3) {
p -= 3;
pos[3] ^= 0x3f;
}
p += 16;
if (p >= fourflip[pos[0]]) p++;
pos[4] = invfourflip[p];
} else if (idx < 16 + 36 + 24) {
idx -= 16 + 36;
p = idx / 3;
idx -= p * 3;
int q = 1;
while (idx >= q) {
idx -= q;
q++;
}
idx += 16;
q += 16;
if (idx >= fourflip[pos[0]]) idx++;
if (q >= fourflip[pos[0]]) q++;
pos[3] = invfourflip[idx];
pos[4] = invfourflip[q];
if (p >= 4) {
p -= 4;
pos[4] ^= 0x3f;
}
pos[2] = invfourflip[p + 12];
} else {
idx -= 16 + 36 + 24;
int q = 16;
for (p = 2; p < 5; p++, q++) {
if (q == fourflip[pos[0]]) q++;
pos[p] = invfourflip[q];
}
if (idx & 2) pos[3] ^= 0x3f;
if (idx & 1) pos[4] ^= 0x3f;
}
}
}
}Code: Select all
void normalize_2(struct TBEntry *ptr)
{
int i, j;
int n = ptr->num;
nptr = ptr;
if (triangle[pos[0]] > triangle[pos[1]])
Swap(pos[0], pos[1]);
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]];
if (triangle[pos[0]] < 6) {
if (triangle[pos[1]] < 6) {
if (triangle[pos[0]] != triangle[pos[1]]) {
stype[0] = 12; /* no syms */
} else {
switch (twistcnt[pos[1]]) {
case 4: /* A7 */
i = pos[0];
pos[0] = flipdiag[pos[1] ^ 0x38];
pos[1] = flipdiag[i ^ 0x38];
for (i = 2; i < n; i++)
pos[i] = flipdiag[pos[i] ^ 0x38];
case 3: /* H2, no syms */
stype[0] = 10;
break;
case 1: /* G1, leftright */
stype[0] = 4;
break;
case 6: /* B8, updown -> leftright */
stype[0] = 3;
for (i = 0; i < n; i++)
pos[i] = flipdiag[pos[i]];
break;
case 7: /* G8, 180 -> leftright */
stype[0] = 2;
for (i = 1; i < n; i++)
if (pos[i] & 0x04) pos[i] ^= 0x38;
break;
case 2: /* A2, A1-H8 */
stype[0] = 8;
break;
case 5: /* H7, A8-H1 -> A1-H8 */
stype[0] = 7;
for (i = 0; i < n; i++)
pos[i] ^= 0x07;
break;
}
}
} else {
stype[0] = 11; /* no syms */
}
} else {
if (twistcnt[pos[1]] == 2)
for (i = 1; i < n; i++)
pos[i] = flipdiag[pos[i]];
if (triangle[pos[0]] != triangle[pos[1]]) {
if (twistcnt[pos[1]] == 1) { /* no syms */
stype[0] = 9;
} else if (twistcnt[pos[1]] == 3) { /* A1-H8 */
stype[0] = 6;
} else { /* A1-H8 */
stype[0] = 5;
}
} else {
if (twistcnt[pos[1]] == 3) { /* A1-H8, A8-H1 */
stype[0] = 0;
} else { /* leftright */
stype[0] = 1;
}
}
}
if (ptr->norm[2] == 2) {
if (stype[0] >= 9) { /* no syms */
if (pos[2] > pos[3]) Swap(pos[2], pos[3]);
} else if (stype[0] >= 5) { /* A1H8 */
if (offdiag[pos[2]] && !offdiag[pos[3]]) Swap(pos[2], pos[3]);
if (offdiag[pos[2]]) {
if (lower[pos[2]] == lower[pos[3]])
stype[2] = 1;
else {
if (lower[pos[2]] > lower[pos[3]]) Swap(pos[2], pos[3]);
if (offdiag[pos[2]] == offdiag[pos[3]])
stype[2] = 3;
else
stype[2] = 4;
}
} else if (offdiag[pos[3]]) {
stype[2] = 2;
} else {
stype[2] = 0;
if (pos[2] > pos[3]) Swap(pos[2], pos[3]);
}
} else if (stype[0] >= 1) { /* leftright */
if (flap[pos[2]] == flap[pos[3]])
stype[2] = 0;
else {
if (flap[pos[2]] > flap[pos[3]]) Swap(pos[2], pos[3]);
if ((pos[2] & 0x04) == (pos[3] & 0x04))
stype[2] = 1;
else
stype[2] = 2;
}
} else { /* A1H8, A8H1 */
if (fourflip[pos[2]] > fourflip[pos[3]]) Swap(pos[2], pos[3]);
if (offdiag[pos[2]] > 0) {
pos[2] = flipdiag[pos[2]];
pos[3] = flipdiag[pos[3]];
}
if (offdiag[pos[2] ^ 0x07] > 0) {
pos[2] = flipdiag[pos[2] ^ 0x07] ^ 0x07;
pos[3] = flipdiag[pos[3] ^ 0x07] ^ 0x07;
}
if (fourflip[pos[2]] < 12) {
if (fourflip[pos[2]] == fourflip[pos[3]])
stype[2] = 0;
else if (fourflip[pos[3]] < 12)
stype[2] = 1;
else
stype[2] = 2;
} else {
if (fourflip[pos[2]] == fourflip[pos[3]])
stype[2] = 3;
else
stype[2] = 4;
}
}
} else { /* norm[2] == 3 */
if (stype[0] >= 9) { /* no syms */
for (i = 2; i < 4; i++)
for (j = i+1; j < 5; j++)
if (pos[i] > pos[j]) Swap(pos[i], pos[j]);
} else if (stype[0] >= 5) { /* A1H8 */
if (offdiag[pos[3]] && !offdiag[pos[4]])
Swap(pos[3], pos[4]);
if (offdiag[pos[2]] && !offdiag[pos[3]]) {
Swap(pos[2], pos[3]);
if (!offdiag[pos[4]])
Swap(pos[3], pos[4]);
}
if (!offdiag[pos[2]]) {
if (!offdiag[pos[3]]) {
if (!offdiag[pos[4]]) {
for (i = 2; i < 4; i++)
for (j = i+1; j < 5; j++)
if (pos[i] > pos[j]) Swap(pos[i], pos[j]);
stype[2] = 0;
} else {
if (pos[2] > pos[3])
Swap(pos[2], pos[3]);
stype[2] = 2;
}
} else if (lower[pos[3]] == lower[pos[4]]) {
stype[2] = 1;
} else {
if (lower[pos[3]] > lower[pos[4]])
Swap(pos[3], pos[4]);
if (offdiag[pos[3]] != offdiag[pos[4]])
stype[2] = 4;
else
stype[2] = 3;
}
} else if (offdiag[pos[2]] == offdiag[pos[3]] && offdiag[pos[2]] == offdiag[pos[4]]) {
for (i = 2; i < 4; i++)
for (j = i+1; j < 5; j++)
if (lower[pos[i]] > lower[pos[j]]) Swap(pos[i], pos[j]);
stype[2] = 5;
} else {
if (offdiag[pos[3]] == offdiag[pos[4]])
Swap(pos[2], pos[4])
else if (offdiag[pos[2]] == offdiag[pos[4]])
Swap(pos[3], pos[4]);
if (lower[pos[2]] > lower[pos[3]])
Swap(pos[2], pos[3]);
stype[2] = 6;
}
} else if (stype[0] >= 1) {
if ((pos[2] & 0x04) == (pos[3] & 0x04) && (pos[2] & 0x04) == (pos[4] & 0x04)) {
for (i = 2; i < 4; i++)
for (j = i+1; j < 5; j++)
if (flap[pos[i]] > flap[pos[j]]) Swap(pos[i], pos[j]);
stype[2] = 0;
} else {
if ((pos[2] & 0x04) == (pos[3] & 0x04))
Swap(pos[2], pos[4])
else if ((pos[2] & 0x04) == (pos[4] & 0x04))
Swap(pos[2], pos[3]);
if (flap[pos[3]] > flap[pos[4]])
Swap(pos[3], pos[4]);
stype[2] = 1;
}
} else {
for (i = 2; i < 4; i++)
for (j = i+1; j < 5; j++)
if (fourflip[pos[i]] > fourflip[pos[j]]) Swap(pos[i], pos[j]);
if (offdiag[pos[2]] > 0)
for (i = 2; i < 5; i++)
pos[i] = flipdiag[pos[i]];
if (offdiag[pos[2] ^ 0x07] > 0)
for (i = 2; i < 5; i++)
pos[i] = flipdiag[pos[i] ^ 0x07] ^ 0x07;
if (fourflip[pos[2]] < 12) {
if (fourflip[pos[2]] != fourflip[pos[3]] && (fourflip[pos[3]] != fourflip[pos[4]] || fourflip[pos[3]] >= 12)) {
if (fourflip[pos[4]] < 12)
stype[2] = 8;
else if (fourflip[pos[3]] < 12)
stype[2] = 7;
else {
if (diag[pos[3]] > diag[pos[4]]) Swap(pos[3], pos[4]);
stype[2] = 6;
}
} else {
if (fourflip[pos[2]] != fourflip[pos[3]]) {
Swap(pos[2], pos[4]);
if (offdiag[pos[2]] > 0)
for (i = 2; i < 5; i++)
pos[i] = flipdiag[pos[i]];
if (offdiag[pos[2] ^ 0x07] > 0)
for (i = 2; i < 5; i++)
pos[i] = flipdiag[pos[i] ^ 0x07] ^ 0x07;
}
if (fourflip[pos[2]] == fourflip[pos[4]])
stype[2] = 2;
else if (fourcnt[pos[3]] == 1)
stype[2] = 5;
else if (fourcnt[pos[3]] == 3) {
stype[2] = 4;
} else
stype[2] = 3;
}
} else {
if (fourflip[pos[3]] == fourflip[pos[4]]) {
Swap(pos[2], pos[4])
stype[2] = 1;
} else if (fourflip[pos[2]] == fourflip[pos[3]])
stype[2] = 1;
else
stype[2] = 0;
}
}
}
}-
syzygy
- Posts: 5938
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Tablebase suggestion
I think the most relevant function is normalize_2(), which seems to classify the leading KK configuration. Then for each class, encode_23() adds the other 3 pieces. So if encode_23() is replaced with the straightforward method of placing 3 Ks, normalize_2() does not need to do the classification (recorded in stype[]) but just calculate an index for the 2 leading Ks.
But normalize_2() is not yet close to normalize_5()...
For completeness:
And then there are functions like:
But normalize_2() is not yet close to normalize_5()...
For completeness:
Code: Select all
const int flap[] = {
0, 1, 2, 3, 3, 2, 1, 0,
4, 5, 6, 7, 7, 6, 5, 4,
8, 9, 10, 11, 11, 10, 9, 8,
12, 13, 14, 15, 15, 14, 13, 12,
16, 17, 18, 19, 19, 18, 17, 16,
20, 21, 22, 23, 23, 22, 21, 20,
24, 25, 26, 27, 27, 26, 25, 24,
28, 29, 30, 31, 31, 30, 29, 28
};
const int invflap[] = {
0, 1, 2, 3, 8, 9, 10, 11,
16, 17, 18, 19, 24, 25, 26, 27,
32, 33, 34, 35, 40, 41, 42, 43,
48, 49, 50, 51, 56, 57, 58, 59
};
const int twistcnt[] = {
0, 0, 0, 0, 1, 1, 1, 1,
2, 0, 0, 0, 1, 1, 1, 3,
2, 2, 0, 0, 1, 1, 3, 3,
2, 2, 2, 0, 1, 3, 3, 3,
4, 4, 4, 2, 3, 5, 5, 5,
4, 4, 2, 6, 7, 3, 5, 5,
4, 2, 6, 6, 7, 7, 3, 5,
2, 6, 6, 6, 7, 7, 7, 3
};
const int diag[] = {
0, 0, 0, 0, 0, 0, 0, 8,
0, 1, 0, 0, 0, 0, 9, 0,
0, 0, 2, 0, 0, 10, 0, 0,
0, 0, 0, 3, 11, 0, 0, 0,
0, 0, 0, 12, 4, 0, 0, 0,
0, 0, 13, 0, 0, 5, 0, 0,
0, 14, 0, 0, 0, 0, 6, 0,
15, 0, 0, 0, 0, 0, 0, 7
};
const int invdiag[] = {
0, 9, 18, 27, 36, 45, 54, 63,
7, 14, 21, 28, 35, 42, 49, 56
};
const int fourflip[] = {
19, 0, 1, 2, 3, 4, 5, 12,
0, 18, 6, 7, 8, 9, 13, 5,
1, 6, 17, 10, 11, 14, 9, 4,
2, 7, 10, 16, 15, 11, 8, 3,
3, 8, 11, 15, 16, 10, 7, 2,
4, 9, 14, 11, 10, 17, 6, 1,
5, 13, 9, 8, 7, 6, 18, 0,
12, 5, 4, 3, 2, 1, 0, 19
};
const int invfourflip[] = {
1, 2, 3, 4, 5, 6, 10, 11, 12, 13,
19, 20, 7, 14, 21, 28, 27, 18, 9
};
const int fourcnt[] = {
0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 2,
1, 1, 0, 0, 0, 0, 2, 2,
1, 1, 1, 0, 0, 2, 2, 2,
1, 1, 1, 0, 0, 2, 2, 2,
1, 1, 0, 3, 3, 0, 2, 2,
1, 0, 3, 3, 3, 3, 0, 2,
0, 3, 3, 3, 3, 3, 3, 0
};Code: Select all
int lpack23(void)
{
int p = lower[pos[2]];
int q = lower[pos[3]];
int r = lower[pos[4]];
if (p >= lower[pos[0]]) p--;
if (q >= lower[pos[0]]) q--;
if (r >= lower[pos[0]]) r--;
return p + q*(q-1)/2 + r*(r-1)*(r-2)/6;
}
int lpack231(void)
{
int p = lower[pos[4]];
if (p >= lower[pos[0]]) p--;
return p;
}
int lpack232(void)
{
int p = lower[pos[3]];
int q = lower[pos[4]];
if (p >= lower[pos[0]]) p--;
if (q >= lower[pos[0]]) q--;
return p + q*(q-1)/2;
}
int dpack23(void)
{
int p = diag[pos[2]];
int q = diag[pos[3]];
int r = diag[pos[4]];
if (p > diag[pos[1]]) p--;
if (p > diag[pos[0]]) p--;
if (q > diag[pos[1]]) q--;
if (q > diag[pos[0]]) q--;
if (r > diag[pos[1]]) r--;
if (r > diag[pos[0]]) r--;
return p + q*(q-1)/2 + r*(r-1)*(r-2)/6;
}
static int adjust3(int p, int q, int r, int s)
{
if (r > s)
Swap(r, s);
if (q > r) {
Swap(q, r);
if (r > s)
Swap(r, s);
}
if (p > s) p--;
if (p > r) p--;
if (p > q) p--;
return p;
}
static int unadjust3(int p, int q, int r, int s)
{
if (r > s)
Swap(r, s);
if (q > r) {
Swap(q, r);
if (r > s)
Swap(r, s);
}
if (p >= q) p++;
if (p >= r) p++;
if (p >= s) p++;
return p;
}-
syzygy
- Posts: 5938
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Tablebase suggestion
It actually does more starting from the "if (ptr->norm[2] ==2)" part. So the KK-case isn't too difficult, the real complexity is in mixing in the other three Ks and taking into account all possible symmetries, but we don't want to do that for pieces outside the non-leading set.
So I think 5Ks should be somewhat doable, also given that there is a symmetry less in draughts. But it is a non-trivial exercise, and my old code probably does not really help too much.