Determine permutation size of an endgame.

[jshriver]

Trying to figure out how many permutations there are in a given endgame.
Say for example you have KNPknp would you calculate that as
64!/(58! * 1! * 1! * 1! * 1! * 1! * 1!) = 53,981,544,960 possible positional variations.

64 total squares, 58 empty squares and 6 unique pieces.

Another exmaple KNNknn
Would that be: 64!/ (58! * 1! * 2! * 1! * 2!) = 13,495,386,240

Granted it'll be smaller because some of those positions wont be legal, such as king next to a king.

Or am I way off.

-Josh

[guyhaw]

You are along the right lines.
See Nalimov, Wirth, H "KQQKQQ and the Kasparov-World Game" ICCA_J, from my w'site.
If 'k' like-men are to be placed on 's' remaining squares, you can multiply the 'choices so far' by s!/k!.
Alternatively, one can have an index-space 64^k and sort more out later.
Nalimov had a good idea to reduce RAM required, namely to avoid creating unblockable checks by the side-not-to-move.
Distinguish between 'illegal' positions and 'unreachable' positions: some unreachables are hard to find. Also, to compare stats with another EGT-generation method, one might just stick to finding 'illegals' and marking them as 'broken index positions'.
Most methods now recognise that there are 462 Kk positions without Pawns and 1806 with Pawns and index to these explicitly.

The tougher matho challenge here, one I have to think hard about every time, is how to enumerate the positions of the 'k' like men. Last time round, it was Mark B who told me the formula: I'd already forgotten a referee gave me the formula in Nalimov, Haworth, Heinz, "Space-Efficient Indexing of Endgame Databases for Chess", ICGA_J v23.3, also on my w'site.

There are, however, extra positions caused by e.p. and castling, the last typically not attempted in EGT-generation. Each combination of the five properties gives a separate 'zone' of positions, so there are potentailly 32 zones, or 2 if one ignores castling. These zones have much fewer, maybe no, positions in them - e.g. when you have no Pawns, or 0-1 Rooks.

The next decision to make is what _order_ to 'place' the pieces on the board. After the Kings, the new idea is to place the Pawns first, slicing the endgame into 'slices', each with its Pawns fixed. Each of these can be computed and filed separately if need be, or a set of them can be filed together. I'd then place Rooks as they might be castleable.

Final point is that one index-scheme might be the best for generating the EGT, and another the best for storing and accessing it. A 1-1 mapping can take place after generation to achieve the latter. Thus YK-MB do not use the Nalimov index scheme, but can map to it later if they wish for storage and access (and compatability with the scheme the market has adopted thus far.)

g

[guido]

Trying to figure out how many permutations there are in a given endgame.
Say for example you have KNPknp would you calculate that as
64!/(58! * 1! * 1! * 1! * 1! * 1! * 1!) = 53,981,544,960 possible positional variations.

64 total squares, 58 empty squares and 6 unique pieces.

Another exmaple KNNknn
Would that be: 64!/ (58! * 1! * 2! * 1! * 2!) = 13,495,386,240

Granted it'll be smaller because some of those positions wont be legal, such as king next to a king.

Or am I way off.

-Josh

Better late than never!

Computing TBs it is necessary to reduce the number of positions as much as possible, but there is also the necessity to have a biunivocal correspondence between the men positions and an index.
So in your cases a good solution can be the following:

KNPknp = 1806 * 48 * 47 * 60 * 59 = 14,423,149,440 << 53,981,544,960

- 1806 are the positions of the two kings with pawns. The white king, because of the vertical symmetry, must be in the a1,d1,d8,a8 rectangle, while the black king can occupy any position not in contact with the white king.
Obviously the transformation between the positions of the kings and this partial index can be obtained only by means of tables.
- The pawns must be put before the pieces. Normally the possibility of reducing the available squares, keeping into account the positions of the kings, i.e. if one or both the kings are in the a2, h2, h7, a7 rectangle, is not considered
because it would complicate too much the computation of the final index, even if this would be a sensible reduction if there are many pawns.
- Finally the collocation of the pieces keeps into account all the preceding men (king + pawns)


KNNknn = 462 * (62 *61)/2! * (60*59)/2! = 1,546,346,340 << 13,495,386,240

- 462 are the positions of the two kings without pawns. The white king, because of the 8 possible symmetry, must be in the a1,d1, d4 triangle, while the black king can occupy any position not in contact with the white king, but if the white king is on the a1, h8 diagonal, the black king can be only in the a1, h1, h8 triangle. As before, the transformation between the positions of the kings and this partial index can be obtained only by means of tables.

- When there are two or more equal men a only partial index must be computed for all these men. The total positions are given by the product of the possible positions of each man divided by 2! or 3! or in general n! where n is the number of equal men. So also in this case it is necessary to have an algorithm for transforming index into positions and viceversa. The transformation from positions to index uses a direct mathematical formula while the inverse transformation can only be made by an iterative numerical algorithm. For two equal men another possibility
is the use of tables.

The use of unblockable checks as in Nalimov is very good but creates some complications and it seems that makes impossible to transform the index in the men positions. You can only compute the index from the men positions.

Ciao
Guido