Interestingly, for checkers the state space is about the square root of the game space in size (c. 10^20 versus 10^40). For chess, the game space is nearer the cube of the state space (10^44 and 10^123)
Where does the figure 10^123 come from? I would have expected it to be very much higher even under competition rules. (And still very much higher than the cube of the state space even though the state space increases by a factor of 100 under competition rules).
#186
In checkers every move is irreversible: either a move forward or a capture.
In chess only pawn moves and captures are irreversible.
That means in chess pieces can shuffle around for at most 50 moves before a pawn move or a capture happens.
Also in checkers captures are compulsory while in chess captures are discretionary.
That all explains why in chess there are more games per position than in checkers.
Interestingly, for checkers the state space is about the square root of the game space in size (c. 10^20 versus 10^40). For chess, the game space is nearer the cube of the state space (10^44 and 10^123)
Where does the figure 10^123 come from? I would have expected it to be very much higher even under competition rules. (And still very much higher than the cube of the state space even though the state space increases by a factor of 100 under competition rules).
I'd guess it is ancient, probably the first Shannon paper. The wiki article needs updating - it doesn't have the 10^37 number, but has a somewhat bigger bound. Doesn't matter much - the point is that the square root of the game tree size is HUGE.
#189
It is the square root of the number of positions.
The number of games is irrelevant.
#191
The number of relevant positions intervening in the proof is the square root of the number of legal positions.
Interestingly, for checkers the state space is about the square root of the game space in size (c. 10^20 versus 10^40). For chess, the game space is nearer the cube of the state space (10^44 and 10^123)
Where does the figure 10^123 come from? I would have expected it to be very much higher even under competition rules. (And still very much higher than the cube of the state space even though the state space increases by a factor of 100 under competition rules).
I'd guess it is ancient, probably the first Shannon paper. The wiki article needs updating - it doesn't have the 10^37 number, but has a somewhat bigger bound. Doesn't matter much - the point is that the square root of the game tree size is HUGE.
But I'd expect log(game space) to base (state space) to be also HUGE. You can never believe Wikipedia. If you read Shannon's paper it isn't meant to give the size of the game space, only a rough approximation to the number of positions that might need to be considered in a practical game of 40 moves.
The figure is just an approximation to 30^(2*40) where 30 was a sampled average of the number of moves available in some recorded games. If he'd made it n ply instead of 40 moves it would have just come out as 30^n . E.g. if he'd used 8848.5 (the longest possible game under competition rules) instead of 40 his number would have been Overflow according to my calculator.
i am very confused
#194
No confusion.
A scientific paper shows there are 3.81*10^37 legal chess positions.
A scientific paper shows checkers was solved using the square root of the number of legal positions.
Hence for chess it is plausible that the square root of the number of legal positions is needed as well to account for the fact that each pawn move and each capture renders huge numbers of positions irrelevant.
A cloud engine reaches 10^9 nodes per second.
There are 500 ECO opening codes A00 to E99.
Only like 50 of these are needed to solve chess.
Hence chess can be solved using 3 cloud engines during 5 years.
The roadblock is money to pay for the cloud engines.
#194
No confusion.
A scientific paper shows there are 3.81*10^37 legal chess positions.
...
Under basic rules. That would be 3.81*10^39 under competition rules.
I agree that the 10^123 games is unlikely to be reliable, but the point is that the number of legal chess games is way bigger relative to the size of the state space than checkers (on a log scale).
IMO, this makes the "square root" saving from unilaterally selective analysis ineffective.
The reason checkers allowed such a saving is that the first phase of the game is 100% unidirectional. At any stage either pieces are irreversibly removed or pieces are irreversibly advanced. It's only with kings on that this stops being true. Chess is mostly unlike this, there is is a lot of reversibility.
There is a loose argument why unilateral selection reduces the size of the game tree by a square root in an irreversible game. I think the reason you get similar reduction in checkers for the state space is because of the number of irreversible moves.
I observe that in a tablebase there is effective irreversibility, because each position has a distance from the end of the game. This distance orders the positions that are reached. In principle this could be extended back to the start of the game. But I am not sure you can be selective in retrogade analysis. At each stage you want to add every position that could reach a -previously evaluated position.
#194
No confusion.
...
Hence chess can be solved using 3 cloud engines during 5 years.
...
On @tygxc's own calculation, since his solution intends to use competition rules, that should read 50 years.
The authors of the last paper he links to regarding the checkers solution probably disagree. I quote
With checkers finished, the obvious question is whether chess is solvable. Checkers has roughly the square root of the number of positions in chess (somewhere in the 10⁴⁰ to 10⁵⁰ range). Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology
I agree that the 10^123 games is unlikely to be reliable, but the point is that the number of legal chess games is way bigger relative to the size of the state space than checkers (on a log scale).
IMO, this makes the "square root" saving from unilaterally selective analysis ineffective.
The reason checkers allowed such a saving is that the first phase of the game is 100% unidirectional. At any stage either pieces are irreversibly removed or pieces are irreversibly advanced. It's only with kings on that this stops being true. Chess is mostly unlike this, there is is a lot of reversibility.
There is a loose argument why unilateral selection reduces the size of the game tree by a square root in an irreversible game. I think the reason you get similar reduction in checkers for the state space is because of the number of irreversible moves.
I agree. I was just pointing out that your case is probably very substantially understated.
I don't know if this was mentioned earlier in this forum -
but the math of maximum possible positions as opposed to games -
looks better. Thought of it decades ago. Yes I'm sure others have too.
32 squares must always be empty. One can use factorials to take care of that.
A square can have only thirteen states -
but the two Kings are very limited in their maximum possible number of arrangements. One can simply put an upper bound on it instead of figuring for corner and edge arrangements.
That upper bound would be 64 x 60 I believe.
So then you get a first 'upper bound' for all possible positions ...
which will have a term with 11 to the 32nd power in it.
(Q-R-B-N-P) so 5 x 2 colors plus 1 for the possible empty square. = 11.
It starts getting tougher when you take into account things like only 48 possible squares for pawns.
Only a max of 9 queens each - a max of ten for each of the other three piece-types.
I ended up with an upper bound much more than 10 to the fortieth power. But that was without some of the 'cut-downs'.
One could compare that with the number of seconds in a year -
could a supercomputer 'brute force' an analysis of all the possible positions ?
One could 'cut' all positions with only a knight plus kings or lone bishop plus kings. But that and similiar isn't going to help enough !
@playerafaer re #200
John Tromp has probably done the most work on this and gives a provisional upper bound of 10^45.888 legal positions.
See https://tromp.github.io/chess/chess.html section Number of chess diagrams and positions.
That is under current basic rules. It would need to be multiplied by 100 if the 50 move rule is added (as it is in competition rules or basic rules prior to 2017) and by a lot more if the triple repetition rule is taken into account (same comment). But the triple repetition rule can be ignored in weakly solving chess under either set of rules.
@MARattigan
You mean 'the position' has to take into account how many moves of the 50 has happened?
That would suggest we'd also have to factor in whether castling is still legal - in other words whether a King has moved or not before castling and even whether somebody just pushed pawn to the 4th rank sliding to adjacent of an opponent's 5th rank pawn - in other words en passant available.
And the number of positions would have to be multiplied by 2 - because it could be either player's move. That's neater. 
#201
The vast majority of the positions counted by Tromp make no sense at all with multiple excess promotions. These positions play no role at all in solving chess. The more recent paper gives more accurate numbers.
At the time checkers was solved that was not yet known about chess.
Interestingly, for checkers the size of the state space is about the square root of the size of the game tree (c. 10^20 versus 10^40). For chess, the size of the game tree is a lot more than the square of the size of the state space (c. 10^38 and 10^123)