Counting endgame positions

[Kirill Kryukov]

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

[velmarin]

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

[Sempoo]

Vastly enormous numbers!

[Daniel Shawul]

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.

[Kirill Kryukov]

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.

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]

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]

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]

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

[Daniel Shawul]

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]

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.