> For the chess problem we propose the estimate number_of_typical_games ~ typical_number_of_options_per_movetypical_number_of_moves_per_game. This equation is subjective, in that it isn’t yet justified beyond our opinion that it might be a good estimate.
This applies to most if not all games. In our paper "A googolplex of Go games" [1], we write
"Estimates on the number of ‘practical’ n × n games take the form b^l where b and l are estimates on the number of choices per turn (branching factor) and game length, respectively. A reasonable and minimally-arbitrary
upper bound sets b = l = n^2, while for a lower bound, values of b = n and l = (2/3)n^2 seem both reasonable and not too arbitrary. This gives us bounds for the ill-defined number P19 of ‘practical’ 19x19 games of
10^306 < P19 < 10^924
Wikipedia’s page on Game complexity[5] combines a somewhat high estimate of b = 250 with an unreasonably low estime of l = 150 to arrive at a not unreasonable 10^360 games."
> Our final estimate was that it is plausible that there are on the order of 10^151 possible short games of chess.
I'm curious how many arbitrary length games are possible.
Of course the length is limited to 17697 plies [3] due to Fide's 75-move rule. But constructing a huge class of games in which every one is probably legal remains a large challenge; much larger than in Go where move legality is much easier to determine.
The main result of our paper is on arbitrarily long Go games, of which we prove there are over 10^10^100.
I do not see how that’s a good estimate. For example, take a game length of, on average, 4 and a branching factor of 10. That gives an estimate of 10,000.
Chances are there are games of lengths 3 and 5, too. With that branching factor, there are 1,000, respectively 100,000 of those, for a total of 111,000. That’s over ten times as many games as estimated.
The larger the spread in game length towards games that are larger than average, the more the proposed estimate underestimates the actual number.
This link https://wismuth.com/chess/longest-game.html from the article talks about the 2014 changes (75-move rule and draw by 5-fold repetition) that make it no longer infinite.
meh. I think it would have been more interesting had the author discussed more granular estimates. Mathematicians have narrowed it down more by considering the properties of the pieces and bijections.
7 comments
[ 4.8 ms ] story [ 22.0 ms ] threadThis applies to most if not all games. In our paper "A googolplex of Go games" [1], we write
"Estimates on the number of ‘practical’ n × n games take the form b^l where b and l are estimates on the number of choices per turn (branching factor) and game length, respectively. A reasonable and minimally-arbitrary upper bound sets b = l = n^2, while for a lower bound, values of b = n and l = (2/3)n^2 seem both reasonable and not too arbitrary. This gives us bounds for the ill-defined number P19 of ‘practical’ 19x19 games of 10^306 < P19 < 10^924 Wikipedia’s page on Game complexity[5] combines a somewhat high estimate of b = 250 with an unreasonably low estime of l = 150 to arrive at a not unreasonable 10^360 games."
> Our final estimate was that it is plausible that there are on the order of 10^151 possible short games of chess.
I'm curious how many arbitrary length games are possible. Of course the length is limited to 17697 plies [3] due to Fide's 75-move rule. But constructing a huge class of games in which every one is probably legal remains a large challenge; much larger than in Go where move legality is much easier to determine.
The main result of our paper is on arbitrarily long Go games, of which we prove there are over 10^10^100.
[1] https://matthieuw.github.io/go-games-number/AGoogolplexOfGoG...
[2] https://en.wikipedia.org/wiki/Game_complexity#Complexities_o...
[3] https://tom7.org/chess/longest.pdf
Chances are there are games of lengths 3 and 5, too. With that branching factor, there are 1,000, respectively 100,000 of those, for a total of 111,000. That’s over ten times as many games as estimated.
The larger the spread in game length towards games that are larger than average, the more the proposed estimate underestimates the actual number.
Or maybe the question should be what percent of games reach a position that has never before been seen?