> 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 remember from a lot of combinatorial problems (like cutting up space with hyper-planes or calculating VC dimension) that one sees what looks like exponential growth until you have a number of items equal to the effective dimension of the system and then things start to look polynomial.
BTW: I was going through some of your lambda calculus write-ups a while ago. Really great stuff that I very much enjoyed.
I wonder if/how that interacts with the new draw rule. (For the uninitiated: the formal rule to adjudicate games as draws automatically or on time is that the game is a draw if there exists no sequence of moves that could lead to checkmate. Interestingly, although this has almost no strategic implications, it means that... it's almost impossible to write a program to detect draws that's technically correct. A similar corner case is draws in Magic the Gathering, which is literally undecidable in general.)
Is that a new rule? I was under the impression that it had been the case for a very long time that if you went out on time but there was no possible sequence of moves leading to checkmating you, it was a draw instead. (Meaning, of course, that having more pieces could be a disadvantage in such situations, which feels a bit unfair. E.g., KvKB is a draw, but KPvKB can lead to a mate if both sides cooperate, and thus would be a time loss for white even if black would never win in practical play.)
Apparently ~75% of the positions in the lichess database (as of 6 years ago) have only been seen once ever. Average game length is 30-40 moves, so for the completely average player it would be like 10+ moves I suppose. The stronger the players the longer it will take: I found some comments suggesting 20+ for high level players.
A very strong player would show the novice the scholar's mate once and then move on to hanging tactics and pieces on purpose so that the novice starts seeing things, probably leading to positions that are a lot more rare.
That was also my intuition. Unless there's a rule that can stop two immortal but dumb-as-bricks players from indefinitely cycling through the same non-capturing moves surely the answer is 'infinity'.
It depends what rules you're using, but there are the three-fold repetition and 50-move rules which allow a player to force the game to end in a draw. The catch is they both require one of the players to claim a draw under the rule, otherwise they can keep playing.
There is additionally the 75-move rule where the the game is forced to be over without either player claiming the rule (the arbiter just ends the game), that rule would give an upper bound regardless of the players knowledge of the rules.
How I'd put it is that there are two sets of stopping points under FIDE rules:
- After threefold repetition or 50 moves, either player may claim a draw.
- After fivefold repetition or 75 moves, the game is automatically drawn.
Most modern counts of the longest possible chess game, or the total number of possible chess games, are based on fivefold repetition and the 75-move rule.
Meanwhile, threefold repetition and the 50-move rule are still relevant in endgame tablebases, since they rule out certain forced mate sequences.
> 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.
[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
Nice stuff, thanks for sharing that.
I remember from a lot of combinatorial problems (like cutting up space with hyper-planes or calculating VC dimension) that one sees what looks like exponential growth until you have a number of items equal to the effective dimension of the system and then things start to look polynomial.
BTW: I was going through some of your lambda calculus write-ups a while ago. Really great stuff that I very much enjoyed.
I wonder if/how that interacts with the new draw rule. (For the uninitiated: the formal rule to adjudicate games as draws automatically or on time is that the game is a draw if there exists no sequence of moves that could lead to checkmate. Interestingly, although this has almost no strategic implications, it means that... it's almost impossible to write a program to detect draws that's technically correct. A similar corner case is draws in Magic the Gathering, which is literally undecidable in general.)
Is that a new rule? I was under the impression that it had been the case for a very long time that if you went out on time but there was no possible sequence of moves leading to checkmating you, it was a draw instead. (Meaning, of course, that having more pieces could be a disadvantage in such situations, which feels a bit unfair. E.g., KvKB is a draw, but KPvKB can lead to a mate if both sides cooperate, and thus would be a time loss for white even if black would never win in practical play.)
One thing I always wondered is how many moves, on average, do you have to play before reaching a position that has never before seen on Earth?
Or maybe the question should be what percent of games reach a position that has never before been seen?
Apparently ~75% of the positions in the lichess database (as of 6 years ago) have only been seen once ever. Average game length is 30-40 moves, so for the completely average player it would be like 10+ moves I suppose. The stronger the players the longer it will take: I found some comments suggesting 20+ for high level players.
You'd probably need to make a determination of the skill of the players. A very strong player vs a novice could be scholar's mate most of the time.
A very strong player would show the novice the scholar's mate once and then move on to hanging tactics and pieces on purpose so that the novice starts seeing things, probably leading to positions that are a lot more rare.
Yes, the stronger the players, the more often they will both go deeper into established theoretical lines that have been played before.
I think that the average chess game played between humans contributes between 20 and 40 new positions (note that a 30 move chess games has 60 plies).
Infinite. :) Chess is strictly unbounded.
That was also my intuition. Unless there's a rule that can stop two immortal but dumb-as-bricks players from indefinitely cycling through the same non-capturing moves surely the answer is 'infinity'.
It depends what rules you're using, but there are the three-fold repetition and 50-move rules which allow a player to force the game to end in a draw. The catch is they both require one of the players to claim a draw under the rule, otherwise they can keep playing.
There is additionally the 75-move rule where the the game is forced to be over without either player claiming the rule (the arbiter just ends the game), that rule would give an upper bound regardless of the players knowledge of the rules.
How I'd put it is that there are two sets of stopping points under FIDE rules:
- After threefold repetition or 50 moves, either player may claim a draw.
- After fivefold repetition or 75 moves, the game is automatically drawn.
Most modern counts of the longest possible chess game, or the total number of possible chess games, are based on fivefold repetition and the 75-move rule.
Meanwhile, threefold repetition and the 50-move rule are still relevant in endgame tablebases, since they rule out certain forced mate sequences.
Well there is. The three/five fold rule. And 50 moves rule.