Counting endgame positions
Moderators: bob, hgm, Harvey Williamson
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.
 Kirill Kryukov
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Counting endgame positions
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://kirillkryukov.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
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
Re: Counting endgame positions
We know, but read those numbers,.
impressive,..Guauu!!
impressive,..Guauu!!
Re: Counting endgame positions
Vastly enormous numbers!

 Posts: 3749
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Counting endgame positions
Can we do 'reverseperft 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 uncaptures to find 5men and then move the pieces around to reach all 5men. Like I said a passing thought but someone maybe interested to find a working algorithm for egtbreverseperftestimation. 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.
 Kirill Kryukov
 Posts: 492
 Joined: Sun Mar 19, 2006 3:12 am
Re: Counting endgame positions
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).Daniel Shawul wrote:Can we do 'reverseperft 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 uncaptures to find 5men and then move the pieces around to reach all 5men. Like I said a passing thought but someone maybe interested to find a working algorithm for egtbreverseperftestimation.
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.
Yes, this should work. It's also possible to incorporate the uniqueness concept into this method.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.

 Posts: 3749
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Counting endgame positions
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
2men 462
3men 201726
4men 82105254
5men 17828992230
6men 3003449945790
7men 372079445395518
8men 38043260670994110
Re: Counting endgame positions
And the reason for this is that Kirill includes the sidetomove in the position (which makes sense if you want to talk about legality of positions).Daniel Shawul wrote:Using my indexing scheme, I get lower numbers for some reason.

 Posts: 3749
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Counting endgame positions
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.
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.
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
Code: Select all
2men 924
3men 403452
4men 164210508
5men 35657984460
6men 6006899891580
7men 744158890791036
8men 76086521341988220
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 (*)
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.

 Posts: 3749
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Counting endgame positions
Yes Mr. obvious, but you waited to see it till after I delete my post that said the same thing ...syzygy wrote:And the reason for this is that Kirill includes the sidetomove in the position (which makes sense if you want to talk about legality of positions).Daniel Shawul wrote:Using my indexing scheme, I get lower numbers for some reason.
Re: Counting endgame positions
I have been waiting for you to delete a post? I must be psychic.Daniel Shawul wrote:Yes Mr. obvious, but you waited to see it till after I delete my post that said the same thing ...syzygy wrote:And the reason for this is that Kirill includes the sidetomove in the position (which makes sense if you want to talk about legality of positions).Daniel Shawul wrote:Using my indexing scheme, I get lower numbers for some reason.