Re: Counting endgame positions
Posted: Fri Jan 10, 2014 12:33 am
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.
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.Daniel Shawul wrote: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
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.
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
Yes, I consider this symmetry. So I consider these two positions equivalent.Daniel Shawul wrote: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
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.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 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.
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.
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.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).
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
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
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.
Code: Select all
64!/[(32!)*(8!)*(8!)*(2!)*(2!)*(2!)*(2!)*(2!)*(2!)*(1!)*(1!)*(1!)*(1!)] ~ 4,6347266955878096411920459823233e+42 ~ 4.6347e+42.