Counting endgame positions

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4447
Joined: Tue Feb 28, 2012 10:56 pm

Re: Counting endgame positions

Post by syzygy » Thu Jan 09, 2014 7:37 pm

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 :)
Apparently it is not obvious to you that all KvK positions with black to move are equivalent to a KvK position with white to move, so that only KvK positions with white to move need to be counted. So 462 is correct.

Same for other symmetric tables such as KQvKQ and KPvKP.

Daniel Shawul
Posts: 3724
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 7:50 pm

syzygy wrote:
Daniel Shawul wrote:
syzygy wrote:
Daniel Shawul wrote:Using my indexing scheme, I get lower numbers for some reason.
And the reason for this is that Kirill includes the side-to-move in the position (which makes sense if you want to talk about legality of positions).
Yes Mr. obvious, but you waited to see it till after I delete my post that said the same thing ...
I have been waiting for you to delete a post? I must be psychic.
Fact is I deleted my post that I mentioned that he counts twice. Obviously the reason why I did was that i realized my mistake as I mentioned in the previous thread, but you couldn't wait to harp on it so you echoed my post back to me as if you saw it first...hater.

syzygy
Posts: 4447
Joined: Tue Feb 28, 2012 10:56 pm

Re: Counting endgame positions

Post by syzygy » Thu Jan 09, 2014 7:52 pm

Daniel Shawul wrote:
syzygy wrote:
Daniel Shawul wrote:
syzygy wrote:
Daniel Shawul wrote:Using my indexing scheme, I get lower numbers for some reason.
And the reason for this is that Kirill includes the side-to-move in the position (which makes sense if you want to talk about legality of positions).
Yes Mr. obvious, but you waited to see it till after I delete my post that said the same thing ...
I have been waiting for you to delete a post? I must be psychic.
Fact is I deleted my post that I mentioned that he counts twice. Obviously the reason why I did was that i realized my mistake as I mentioned in the previous thread, but you couldn't wait to harp on it so you echoed my post back to me as if you saw it first...hater.
Your period, again?

Grow up.

Daniel Shawul
Posts: 3724
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 7:54 pm

I was about to make a yomama joke there but ...

Daniel Shawul
Posts: 3724
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 9:00 pm

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

syzygy
Posts: 4447
Joined: Tue Feb 28, 2012 10:56 pm

Re: Counting endgame positions

Post by syzygy » Thu Jan 09, 2014 10:21 pm

Daniel Shawul wrote:Have you also considered the symmetry when both kings are on the diagonal?
Kirill wrote:4. (Only for pawnless positions with no castling rights, only for square board) Mirroring locations of all pieces around the a8-h1 diagonal (or around the line connecting top-left and bottom-right corners for other board sizes).

Note that board rotations and mirroring around the other diagonal can be produced by combining several of the listed transformations. Also you can notice that this equivalence is reflexive, symmetric and transitive.

Daniel Shawul
Posts: 3724
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 10:37 pm

syzygy wrote:
Daniel Shawul wrote:Have you also considered the symmetry when both kings are on the diagonal?
Kirill wrote:4. (Only for pawnless positions with no castling rights, only for square board) Mirroring locations of all pieces around the a8-h1 diagonal (or around the line connecting top-left and bottom-right corners for other board sizes).

Note that board rotations and mirroring around the other diagonal can be produced by combining several of the listed transformations. Also you can notice that this equivalence is reflexive, symmetric and transitive.
Aren't you a life saver? :) 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.
4-th transformation can produce identical position if all pieces are located on a8-h1 diagonal. 2-nd and 3-rd transformations can produce identical positions on an odd-sized board. The 1-st transformation however can be applied to any position, and will always produce a non-identical position. Therefore every position has at least one equivalent non-identical variant. Each transformation applied twice returns back to the original position, so the maximum possible number of equivalent non-identical variants for a position is 16.

syzygy
Posts: 4447
Joined: Tue Feb 28, 2012 10:56 pm

Re: Counting endgame positions

Post by syzygy » Thu Jan 09, 2014 10:57 pm

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.
Since he takes into account diagonal reflections, he counts your two positions with the two Ks on the diagonal as one.

What probably confuses you is that you are already starting from the 462 legal KvK positions that are unique up to symmetry. This way you have already eliminated most of the a1-h8 and a8-h1 symmetries. Only those are left with the two Ks on the diagonal.

Kirill does not start by restraining the two Ks to those 462 positions. He starts by considering all possible (legal) placements, then counts 1 position in each symmetry class. For 2 men this gives exactly the 462 KvK positions. For 3 men, this counts your 2 positions as one.

Daniel Shawul
Posts: 3724
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 11:25 pm

syzygy wrote:
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.
Since he takes into account diagonal reflections, he counts your two positions with the two Ks on the diagonal as one.

What probably confuses you is that you are already starting from the 462 legal KvK positions that are unique up to symmetry. This way you have already eliminated most of the a1-h8 and a8-h1 symmetries. Only those are left with the two Ks on the diagonal.

Kirill does not start by restraining the two Ks to those 462 positions. He starts by considering all possible (legal) placements, then counts 1 position in each symmetry class. For 2 men this gives exactly the 462 KvK positions. For 3 men, this counts your 2 positions as one.
Me confused? 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 but I already suspected he does it before I made the post. 21 of the kk should be handled differently so that will imply a complicated indexing which is the point of my question. You can say the KKs on the diagonal are roughly 16-fold symmetry for those 21 KK placements.
Last edited by Daniel Shawul on Thu Jan 09, 2014 11:31 pm, edited 1 time in total.

syzygy
Posts: 4447
Joined: Tue Feb 28, 2012 10:56 pm

Re: Counting endgame positions

Post by syzygy » Thu Jan 09, 2014 11:28 pm

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.

Post Reply