Mate in 69 on 4x4 board

[jkominek]

In 4x4 chess, the kqqrbnp-kbnnp endgame has 6,688,343,790 unique legal positions with white to move. Only one of these positions is a stalemate, which makes it the rarest stalemate (per ESM), for all 2 to 12 piece endgames. I wonder if anyone wants to try constructing this position.

This is funny, in a joke's-on-me kind of way. I read your question and thought "Yeah, maybe I should write a mini-chess tablebase generator and compute kqqrbnp-kbnnp. Then scan for the lone stalemate. Someday." It never occurred to me to construct the position directly, through sheer thinking.

Ken Thompson once advised: when in doubt, use brute force.

[Kirill Kryukov]

This is funny, in a joke's-on-me kind of way. I read your question and thought "Yeah, maybe I should write a mini-chess tablebase generator and compute kqqrbnp-kbnnp. Then scan for the lone stalemate. Someday." It never occurred to me to construct the position directly, through sheer thinking.

Ken Thompson once advised: when in doubt, use brute force.

I imagined something more like shuffling the pieces madly on the board. But for that I wound need two chess sets (for the extra queen), and I have zero at my current home, so you can clearly see how I was stuck before even trying.

[Uri Blass]

In 4x4 chess, the kqqrbnp-kbnnp endgame has 6,688,343,790 unique legal positions with white to move. Only one of these positions is a stalemate, which makes it the rarest stalemate (per ESM), for all 2 to 12 piece endgames. I wonder if anyone wants to try constructing this position.

My thinking about this big number and how to make it smaller lead to the following:

kqqrbnp-kbnnp endgame is practically a union of some sets of positions when in every set you can always go from position A to B and from position B to A.
Define every set of these sets to be a class(not only in this endgame).

Part of the classes have a single position(for example all the mates stalemates and positions when the side to move has to capture).

Questions:
1)what is size of the biggest class?
2)How many classes do we have?
3)How many sizes of classes do we have?
4)Define for chess positions not from the same class A>B if you can go from A to B.
What is the biggest n that we have a sequence of positions such that A(i)>A(i+1) for every 1<=i<n

[hgm]

This is an extension of the concept of P-slices, which are classes for a given constellation of the Pawns. Note that classes with few elements, such as mates, do very little in helping generating the EGT, as they hardly reduce the remaining classes. P-slices tend to be of similat size, though, and can cut the total number of positions in a large number of classes, each being much smaller.

The problem is that all the P-slices eventually lead to positions where the Pawns get promoted, so naive generation of the EGT by retrogradely stepping through the P-slices still would start with an enormously large table. (This would be reduced by symmetry, though, due to absence of Pawns, and duplicate piece types.) It is often possible to prove a P-slice is already fully won by only considering the possibility of converting by Queening, so that you don't need to generate tables resulting from underpromotion. And it is also often possible to prove a P-slice is fully won when allowing the opponenent to make a surviving promotion is counted as a loss. That then makes it possible to calculate the predecessor slices in DTM, without having to consider successor EGTs where opponent Pawns converted.

[Kirill Kryukov]

P-slices are useful, because the largest endgames are those with pawns. Stepping through P-slices allows consuming less RAM while solving. Another useful feature for subdividing the tables is bishop light- or dark-coloredness, when there are at least two bishops - this should be done before dividing into P-slices.

I don't understand how you can avoid considering underpromotion, or how you can declare an entire P-slice as won. In larger endgames, every P-slice will contains millions of positions, including wins, draws and losses, and many will depend on underpromotion. (I guess I am probably doing naive generation).