#61
Here is proof of the legality of the position with the black pawn on h3, which at the same time proves illegality of the position with the black pawn at h4.
On the number of chess positions
Sort:
Ah, I failed to consider the knight on b8 just having promoted. Very nice retrograde problem indeed. Do you know where it originates from?
#64
It was posted in the illegal position thread.
It illustrates how difficult it is to prove legality or illegality of a position.
Milestone 10k is completed now with 533 proof games and 386 illegality arguments.
The 533 legal positions have an average multiplicity of 559/533~1.049, slightly larger than the 1.0355 average of all 10000. This yields an estimated number of legal positions of (5.33% +- 1.96 sqrt(5.33% * 94.67% / 10000)) * N / 1.049, or approximately 4.4e44.
This establishes a curious link between chess and 4-in-a-row:-)
On revisiting my illegality proof sketches, I found 2 mistakes, where I was able to construct a proof game after all. So there are now 535 proof games and the estimate is (4.45 +- 0.37) x 10^44
Sep 28, 2021
0
#67
Let me get this right. This is legal positions, right? And says nothing of the move orders that come before or follow, or whose turn it is, right? The same position is a different position depending on whose turn it is… roughly double.
Yes, I'm estimating the number of legal positions. Where a position includes whose turn it is, what the castling rights are, and what pawn if any can be captured en-passant. But the move history is not part of a position of course.
#62
If the world record R = 185 is the maximum, then each of the NL9 = 4.45 * 10^44 legal positions possible with up to 9 boxes of chess men can be reached from the initial position in at most R moves or 2R plies.
How many different moves x are there to be considered at any ply to do that?
NL9 = x^(2R)
x = NL9^(1/2R) = 4.45e44^(1/370) = 1.32
So all 4.45 * 10^44 legal positions with up to 9 boxes of chess men can be reached from the initial position in at most 185 moves or 370 plies with less than 2 moves to consider at each position.
#70
of course there are a lot more than 1.3 moves possible at each ply. You can reach the same position in many different ways. I would consider this result of 1.32 moves per ply as rather arbitrary.
#71
Of course there are more possible moves, 20 to start with, but with only 2 candidate moves at each ply you can reach all 4.45 * 10^44 legal positions in at most 185 moves.
Look at it another way: 4.45*10^44 = 2^148.3, so there must exist a way to designate each legal position with 149 bit or 19 byte. Thus 149 choices 0/1 between 2 candidate moves suffice to reach 4.45*10^44 possible positions. We have a position where 185 moves = 370 ply are necessary.
Having completed a full review of all illegality proof sketches, I found 3 more mistakes. That brings the final counts to 538 legal and 381 illegal, with an estimate of (4.48 +- 0.37) x 10^44.
There is still a chance that one of the 381 illegality proof sketches in
https://github.com/tromp/ChessPositionR ... %3Aillegal
is overlooking something, but I consider it small enough that I'll happily offer a $64 bounty for a proof game for any of the 381.
There are also bigger bounties of $128 and $256 for software bugs, see the README at https://github.com/tromp/ChessPositionRanking
I'll be writing a paper about my results in the months to come.
Happy bounty hunting!
#72
Can we have a table like table 1 in the Schaeffer proof that checkers is a draw?http://library.msri.org/books/Book29/files/schaeffer.pdf
What is a chess position?
(1) A position a monkey given 9 boxes of chess men can put on a chess board and found legal afterwards.
(2) A position that can occur in a game between 2 reasonably skilled players.
Legal position = position that can arise from the initial position by a series of legal moves
Sensible position = position that is legal and needs chess men from 1 box of chess men, i.e. without having to borrow pieces from other boxes of chess men for excess promotions.
Here is what I compiled from your posts #12, #13, and #72.
Assumptions:
(a) Your legality factor 0.0538 also applies to sensible positions and applies uniformly for all numbers of men from 32 to 9.
(b) The sensibility factor: positions from 1 box / positions from 9 boxes applies uniformly for all numbers of chess men from 32 to 9.
(c) For 8 to 2 chess men I entered the known table base size, though it contains illegal and non sensible positions, but pruned for symmetry.
men: sensible positions
32: 5.23E+26
31: 1.08E+32
30: 2.99E+35
29: 5.90E+37
28: 7.49E+38
27: 2.04E+38
26: 1.93E+37
25: 1.40E+36
24: 9.15E+34
23: 5.45E+33
22: 2.97E+32
21: 1.49E+31
20: 6.85E+29
19: 2.91E+28
18: 1.14E+27
17: 4.08E+25
16: 1.34E+24
15: 4.05E+22
14: 1.11E+21
13: 2.75E+19
12: 6.13E+17
11: 1.22E+16
10: 2.14E+14
9: 3.28E+12
8: 3.82E+16
7: 4.24E+14
6: 3.79E+12
5: 2.59E+10
4: 1.25E+08
3: 3.68E+05
2: 4.62E+02
T: 1.03E+39
Someone posted a game recently where he checkmated with 5 rooks.
It's in no way "sensible" to eliminate all positions with promotions of any kind 
.
#75
It is not about eliminating all promotions, it is about eliminating excess promotions.
A typical position as counted looks like this. It is legal. but it will never arise in a real game.
tygxc wrote:
#75
It is not about eliminating all promotions, it is about eliminating excess promotions.
A typical position as counted looks like this. It is legal. but it will never arise in a real game.
You'd have to allow for at least 4 promotions to be realistic (2 per side).
It's easy to sample positions and posit you can eliminate a bunch of them. Kind of the lowest hanging fruit. The problem is, even if only one in a billion positions is "sensible" to you, that's still 10^35...and no, not a 10^35 that you can then take the square root of.
tygxc wrote:
Sensible position = position that is legal and needs chess men from 1 box of chess men, i.e. without having to borrow pieces from other boxes of chess men for excess promotions.
I claim that is NOT a good definition of sensible position. In fact, I bet if I were to randomly generate positions according to this definition, then you would find the vast majority of them to be look nothing like human play.
#79
I agree that some positions with 4 queens or 3 knights are sensible. I also agree that some positions without any excess promotions are not sensible e.g. with quintuple pawns. The number of legal positions without excess promotions errs to the + side by including non sensible positions with e.g. quintuple pawns and it errs to the - side by excluding sensible positions with e.g. 4 queens or 3 knights.
I agree with your claim that the vast majority of legal positions without excess promotions look nothing like human (or engine) play. Thus the number of legal positions without any excess promotions is an upper bound for the number of sensible positions that can arise in a real game between reasonably skilled human or engine players. The real number of sensible positions including those with e.g. 4 queens or 3 knights is smaller than the number of legal positions without any excess promotions.
tygxc wrote:
The real number of sensible positions
This is my main gripe with all your discussion of "sensible positions". You talk about it as something that is quantifiable, as if it is possible to give a proper definition of "sensible" that would allow anyone to determine whether an arbitrary position satisfies it or not.
Until you can present such a definition, we should just consider the notion of sensible as something elusive and unquantifiable, with no scientific merit.
#60
In the meantime I found some interesting stuff: There is one legal position that requires 185 moves. See https://timkr.home.xs4all.nl/chess2/diary.htm. I have written an essay about that subject called "the radius of the chess universe" (not yet published) and in there I say that the "radius" is at least 185 moves, based on this position. So we have a decent lower bound.