Counting endgame positions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Kirill Kryukov
Posts: 492
Joined: Sun Mar 19, 2006 3:12 am

Counting endgame positions

Post by Kirill Kryukov » Wed Jan 08, 2014 10:56 am

Recently I've been curious about counting chess endgame positions. I counted for up to 8 pieces so far, obtaining 38,603,956,906,065,185 positions in chess (with 2 to 8 pieces) and 40,029,249,937,521,109 in FRC. See details here: http://kirill-kryukov.com/chess/nulp/

With no independent verification it's hard to be sure that the numbers are correct. So, if anyone else tried this, it would be very nice to compare the results.

Best,
Kirill

User avatar
velmarin
Posts: 1600
Joined: Mon Feb 21, 2011 8:48 am

Re: Counting endgame positions

Post by velmarin » Wed Jan 08, 2014 12:34 pm

We know, but read those numbers,.
impressive,..Guauu!!
:oops:

Sempoo
Posts: 15
Joined: Sun Jul 21, 2013 3:04 pm

Re: Counting endgame positions

Post by Sempoo » Wed Jan 08, 2014 8:24 pm

Vastly enormous numbers!

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

Re: Counting endgame positions

Post by Daniel Shawul » Wed Jan 08, 2014 8:46 pm

Can we do 'reverse-perft estimation' for end games? Just a passing thought. It seems impossible to do it atleast the same way we handled the start position. Starting from 4 men and making one un-captures to find 5-men and then move the pieces around to reach all 5-men. Like I said a passing thought but someone maybe interested to find a working algorithm for egtb-reverse-perft-estimation. :) A more feasible MC method maybe to repeatedly generate random positions and measure how many of them end up being illegal. Then if you can calculate the number of positions (including illegals) like the Shannon number, then you can multiply by the faction of legal positions to get an estimate.

User avatar
Kirill Kryukov
Posts: 492
Joined: Sun Mar 19, 2006 3:12 am

Re: Counting endgame positions

Post by Kirill Kryukov » Thu Jan 09, 2014 5:48 am

Daniel Shawul wrote:Can we do 'reverse-perft estimation' for end games? Just a passing thought. It seems impossible to do it atleast the same way we handled the start position. Starting from 4 men and making one un-captures to find 5-men and then move the pieces around to reach all 5-men. Like I said a passing thought but someone maybe interested to find a working algorithm for egtb-reverse-perft-estimation. :)
I'm sure the reverse perft is possible, but the meaning of such number would be totally different from position count (same like the usual perft does not give us the number of different positions reachable from the initial one).

Whether the reverse perft number is interesting enough to try computing it - I'm not sure. At least I don't see immediate interpretation of that number that I can connect to something else. I mean, sure, it will be huge number, as it will increase much faster than forward perft, but I'm not sure what I can learn from it. And then there is the question of what position should it be based on.
Daniel Shawul wrote:A more feasible MC method maybe to repeatedly generate random positions and measure how many of them end up being illegal. Then if you can calculate the number of positions (including illegals) like the Shannon number, then you can multiply by the faction of legal positions to get an estimate.
Yes, this should work. It's also possible to incorporate the uniqueness concept into this method.

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

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 5:56 pm

Using my indexing scheme, I get lower numbers for some reason. The numbers are also different for lower number of pieces, so it is probably a difference in definition. Note that I didn't check for legality of positions due to checks, just the the total number of positions enumerated by my indexing scheme during egbb generation. I guess that Nalimov's indexing scheme, that removes illegal check positions, will be even smaller. I think there are only a few things his scheme misses so it could be very close to the true value.

Code: Select all

2-men 462
3-men 201726
4-men 82105254
5-men 17828992230
6-men 3003449945790
7-men 372079445395518
8-men 38043260670994110

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

Re: Counting endgame positions

Post by syzygy » Thu Jan 09, 2014 6:51 pm

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).

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

Re: Counting endgame positions

Post by Daniel Shawul » Thu Jan 09, 2014 6:57 pm

Never mind, my numbers should be multiplied by 2. I forgot that I generate both white and black to move at the same time, so I have two different tables for them but only counted one of them.

Code: Select all

2-men 924
3-men 403452
4-men 164210508
5-men 35657984460
6-men 6006899891580
7-men 744158890791036
8-men 76086521341988220
I double the Kk table as well but I am not sure I should do that. Your table is shown below, which says that you gain almost a 100% saving with legality checking for 8 pieces.

Code: Select all

2	 462 (*)
3	 368,079 (*)
4	 125,246,598 (*)
5	 25,912,594,054 (*)
6	 3,787,154,440,416 (*)
7	 423,836,835,667,331 (*)
8	38,176,306,877,748,245 (*)
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 :)
Last edited by Daniel Shawul on Thu Jan 09, 2014 7:16 pm, edited 1 time in total.

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

Re: Counting endgame positions

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

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 ...

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

Re: Counting endgame positions

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

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.

Post Reply