Counting endgame positions
Moderators: hgm, Harvey Williamson, bob
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 Posts: 3707
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Counting endgame positions
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.
Re: Counting endgame positions
That he uses 8fold symmetry follows both from the symmetries he lists (transformations 2, 3, 4) and from the 8 "white to move" diagrams.Daniel Shawul wrote:My question was if he uses 8fold symmetry , like most egbb generator, as well. I don't see that in your previous reply nor his diagrams
Re: Counting endgame positions
Ok, I'll try with my algorithm.Daniel Shawul wrote: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.
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
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Re: Counting endgame positions
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.Daniel Shawul wrote: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
I'll try to think how to explain it better on my page.
 Kirill Kryukov
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Re: Counting endgame positions
Yes, I consider this symmetry. So I consider these two positions equivalent.Daniel Shawul wrote:I have now found your enumeration rules here. http://kirillkryukov.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
 Kirill Kryukov
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Re: Counting endgame positions
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 webpage.Daniel Shawul wrote: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 a8h1 diagonal being handled as well as the a1h8 diagonal.
Maybe the correct quote is the one below but it is not clear because the diagrams don't show it.
 Kirill Kryukov
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Re: Counting endgame positions
Do you think this formulation can be automated for N pieces?syzygy wrote: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.
 Kirill Kryukov
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Re: Counting endgame positions
It will be quite amazing if this method can be generalized to arbitrary endgame. It seems difficult, especially if you add enpassant 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.syzygy wrote:Ok, I'll try with my algorithm.Daniel Shawul wrote: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.
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).

 Posts: 685
 Joined: Tue May 22, 2007 9:13 am
Re: Counting endgame positions
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:syzygy wrote: It should be possible to do this by hand for 3 and 4 pieces, but after that it seems to get too messy.
Code: Select all
Z[x1,x2,x4] = (x1^64 + 2 * x1^8 * x2^28 + 3 * x2^32 + 2 * x4^16)/8
Now the real power: for an Npiece endgame, substitute labels for the pieces values P0, P1, ..., P_N1 (with P0 = empty, P1 = white king, P2 = black king, etc.)
Code: Select all
x1 > P0 + P1 + ... + P_N1
x2 > P0^2 + P1^2 + ... + P_N1^2
x4 > P0^4 + P1^4 + ... + P_N1^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 colorneutral.
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
 Posts: 1394
 Joined: Wed Jul 13, 2011 7:04 pm
 Location: Madrid, Spain.
 Contact:
Re: Counting endgame positions.
Hello Rein:
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:
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 64character 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.
How do you reach this number? I do the following: select the empty squares and then fill with the pieces. I get:Rein Halbersma wrote: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.
Code: Select all
64!/{(32!)*[(8!)²]*[(2!)^6]*4!} ~ 1.931136123161587350496685825968e+41 ~ 1.9311e+41.
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.
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.