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
Counting endgame positions
Moderators: hgm, Rebel, chrisw
-
- Posts: 492
- Joined: Sun Mar 19, 2006 4:12 am
-
- Posts: 1600
- Joined: Mon Feb 21, 2011 9:48 am
Re: Counting endgame positions
We know, but read those numbers,.
impressive,..Guauu!!
impressive,..Guauu!!
-
- Posts: 15
- Joined: Sun Jul 21, 2013 5:04 pm
Re: Counting endgame positions
Vastly enormous numbers!
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Counting endgame positions
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.
-
- Posts: 492
- Joined: Sun Mar 19, 2006 4: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 '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.
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: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
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
2-men 462
3-men 201726
4-men 82105254
5-men 17828992230
6-men 3003449945790
7-men 372079445395518
8-men 38043260670994110
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Counting endgame positions
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 wrote:Using my indexing scheme, I get lower numbers for some reason.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
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
2-men 924
3-men 403452
4-men 164210508
5-men 35657984460
6-men 6006899891580
7-men 744158890791036
8-men 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 8:16 pm, edited 1 time in total.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
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 side-to-move 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: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
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 side-to-move 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.