Counting endgame positions

[Daniel Shawul]

I am trying to calculate them by hand for KQK. I think it is possible so I will try before I look at the algorithm you mentioned.

[syzygy]

My question was if he uses 8-fold symmetry , like most egbb generator, as well. I don't see that in your previous reply nor his diagrams

That he uses 8-fold symmetry follows both from the symmetries he lists (transformations 2, 3, 4) and from the 8 "white to move" diagrams.

[syzygy]

I am trying to calculate them by hand for KQK. I think it is possible so I will try before I look at the algorithm you mentioned.

Ok, I'll try with my algorithm.

KQ v K, black to move (easier):

Fixed legal placements:
identity: 4 * 60 * 62 + 24 * 58 * 62 + 36 * 55 * 62 = 223944
diagonals: 2 * 6 * 6 + 6 * 5 * 6 = 252
(Basically the Q can be placed anywhere.)

So (223944 + 2*252) / 8 = 28056.

KQ v K, white to move:
Hmmm, this is a mess
Maybe some other day.

The biggest problem is determining the number of fixed points of the identity, i.e. the total number of legal placements while ignoring symmetries. If it is possible to determine that number, then obtaining the number of unique legal placements up to symmetry only needs a bit of additional work (for most piece combinations you only need to count the number of fully diagonal placements, for combinations such as KRRvK you need to do a bit more).

[Kirill Kryukov]

Edit: Maybe it is you who should not use 462 because Kk.w and Kk.b are different? If that is the case add 462 to all your numbers

Edit2: Indeed you seem to have mixed white and black to move since Kk should have both white and black to move. 462 is just for one of them. This one is for the hater in the other thread not for you Krilli

For each position in kk.b there is an equivalent one in kk.w, so there's no need to consider kk.b, as well as .b variant of any other symmetrical piece configuration.

I'll try to think how to explain it better on my page.

[Kirill Kryukov]

I have now found your enumeration rules here. http://kirill-kryukov.com/chess/nulp/method.html. Have you also considered the symmetry when both kings are on the diagonal? The 16 figures do not include those, but Nalimov's indexing exploit that as well. Jesper Torp's thesis says the following two are equivalent.
[D]8/8/8/8/8/1rk5/8/K7 w - - 0 1
[D]8/8/8/8/8/2k5/2r5/K7 w - - 0 1

Yes, I consider this symmetry. So I consider these two positions equivalent.

[Kirill Kryukov]

But what you quoted says nothing about what I asked, that the two kings being on the diagonal. The quote talks about reflection on the a8-h1 diagonal being handled as well as the a1-h8 diagonal.

Maybe the correct quote is the one below but it is not clear because the diagrams don't show it.

Indeed I did not say anything about two kings being on the main diagonal, because I don't make any special treatment for such case. I apply the general definition of equivalence to all positions. I now see that perhaps I should explain this more clearly on the web-page.

[Kirill Kryukov]

If you ignore the issue of legality, the number of unique positions up to symmetry is relatively easy to count using Burnside's lemma. For a combination of pieces without pawns, the group of symmetries of a chess board is D4. This group has 8 elements:
- identity;
- horizontal and vertical reflections;
- two diagonal reflections;
- rotation by 90 and 270 degrees;
- rotation by 180 degrees.

The number of unique positions up to symmetry with a chosen combination of pieces is the number of orbits of D8 acting on the set of all possible placements of those pieces on a chess board.

According to Burnside's lemma, this number is equal to the average number of placements fixed by an element of D8.

Let's consider KvK. There are 64*63 ways to place these on a chess board. The number of placements fixed by each element:
- identity: 64 * 63
- horizontal / vertical: 0
- diagonals : 8 * 7 (both Ks must be on the diagonal)
- rotation by 90/270: 0
- rotation by 180: 0

So the number of orbits is (64 * 63 + 2 * 8 * 7) / 8 = 518.

For suicide chess these are all legal. For regular chess obviously not.

To count only legal orbits, we should only look at legal placements. Unfortunately this gets nasty:
- identity: 4 * 60 + 24 * 58 + 36 * 55 = 3612
- diagonals: 2 * 6 + 6 * 5 = 42
So the number of orbits is (3612 + 2 * 42) / 8 = 462.

It should be possible to do this by hand for 3 and 4 pieces, but after that it seems to get too messy.

Do you think this formulation can be automated for N pieces?

[Kirill Kryukov]

I am trying to calculate them by hand for KQK. I think it is possible so I will try before I look at the algorithm you mentioned.

Ok, I'll try with my algorithm.

KQ v K, black to move (easier):

Fixed legal placements:
identity: 4 * 60 * 62 + 24 * 58 * 62 + 36 * 55 * 62 = 223944
diagonals: 2 * 6 * 6 + 6 * 5 * 6 = 252
(Basically the Q can be placed anywhere.)

So (223944 + 2*252) / 8 = 28056.

KQ v K, white to move:
Hmmm, this is a mess
Maybe some other day.

The biggest problem is determining the number of fixed points of the identity, i.e. the total number of legal placements while ignoring symmetries. If it is possible to determine that number, then obtaining the number of unique legal placements up to symmetry only needs a bit of additional work (for most piece combinations you only need to count the number of fully diagonal placements, for combinations such as KRRvK you need to do a bit more).

It will be quite amazing if this method can be generalized to arbitrary endgame. It seems difficult, especially if you add en-passant and castling to the mix. I think brute force counting (which I do) is still feasible for 9 or 10 pieces (my counter is very very slow), but with more pieces some other method may be needed.

[Rein Halbersma]

It should be possible to do this by hand for 3 and 4 pieces, but after that it seems to get too messy.

There is a generalization of Burnside's lemma known as Polya's Enumeration Theorem. This produces a generating function of coloring arbitrary sets modulo the symmetry of a group. In the case of the chess board, the polynomial reads:

Code: Select all

Z[x1,x2,x4] = (x1^64 + 2 * x1^8 * x2^28 + 3 * x2^32 + 2 * x4^16)/8

This is a sum over group elements (the first term is the identity, the next one represents the two diagonal mirrorings, then there are vertical/horizontal mirrorings and 180 degree rotations, and finally the two 90 degrees rotations). The monomials represent the order of the group element (i.e. x4^16 means that 90 degrees rotations acts on 16 quartets of squares).

Now the real power: for an N-piece endgame, substitute labels for the pieces values P0, P1, ..., P_N-1 (with P0 = empty, P1 = white king, P2 = black king, etc.)

Code: Select all

x1 -> P0 + P1 + ... + P_N-1
x2 -> P0^2 + P1^2 + ... + P_N-1^2
x4 -> P0^4 + P1^4 + ... + P_N-1^4

You then simply read off the coefficient for a particular combination of pieces. E.g. KK corresponds to the term P0^62 P1 P2, which turns out to be 518 as you showed. You can also get e.g. KRRKBB from the terms P0^58 P1 P2 P3^2 P4^2 as 1,686,946,884 possible entries (comparison with the true result shows that this yields ~38% illegal positions).

Handling illegal positions is cumbersome even with this polynomial. You can do some fancy stuff however, by transforming the above sum over group elements to a sum over subgroups (i.e. Mobius inversion on the subgroup lattice poset). For each subgroup, you can then subdivide the endgames according to the placement of kings. E.g. a king on a corner, edge or central square will impose different constraints on e.g. an opponent piece. It is still tedious because you have to do this piece dependent, so the nice polynomial is no longer color-neutral.

PS just for fun, a 5 second Mathematica calculation tells that the number of placements of all the 32 initial pieces can be done in 579340836948476205149027870013146842320000 ways (5.8 10^41), completely discounting the legality of course.

[Ajedrecista]

Hello Rein:

PS just for fun, a 5 second Mathematica calculation tells that the number of placements of all the 32 initial pieces can be done in 579340836948476205149027870013146842320000 ways (5.8 10^41), completely discounting the legality of course.

How do you reach this number? I do the following: select the empty squares and then fill with the pieces. I get:

Code: Select all

64!/{(32!)*[(8!)²]*[(2!)^6]*4!} ~ 1.931136123161587350496685825968e+41 ~ 1.9311e+41.

I explain my numbers: 64! because of 64 squares on the chessboard; 32! because of 32 empty squares; 8! because of 8 pawns per side, and squared due to two sides (white and black); 2! because of 2 rooks, bishops and knights, and exponent 6 due to 3 types of pieces (rooks, bishops and knights) and 2 sides (3*2 = 6); and 4! due to the last 4 squares to fill with white king, black king, white queen and black queen.

My number is 1/3 of yours. What am I doing wrong?

Other alternative is:

Code: Select all

64!/[(32!)*(8!)*(8!)*(2!)*(2!)*(2!)*(2!)*(2!)*(2!)*(1!)*(1!)*(1!)*(1!)] ~ 4,6347266955878096411920459823233e+42 ~ 4.6347e+42.

If we have 32 '0', 8 'P', 8 'p', 2 'R', 2 'r', 2 'B', 2 'b', 2 'N', 2 'n', 1 'K', 1 'k', 1 'Q' and 1 'q', we will have circa 4.6347e+42 different 64-character strings, one for each different position (the first character (piece or empty) is on a1 square, the second character is on a2 square and so on).

Then your number is 1/8 of this second attempt. Same question again: what I am doing wrong? It is obvious that I am not a combinatorics master. Thanks in advance for your help or anyone's help.

------------

@Kirill: interesting project. Good luck!

Regards from Spain.

Ajedrecista.