5 ms·

How many chess games are possible?

85 points by jmount 8mo ago

RA_Fisher 8mo ago
Infinite. :) Chess is strictly unbounded.
- Mordisquitos 8mo ago
  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'.
  - eulgro 8mo ago
    Well there is. The three/five fold rule. And 50 moves rule.
  - DSMan195276 8mo ago
    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.
    - LegionMammal978 8mo ago
      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.
      - Sesse__ 8mo ago
        Endgame tablebases don't take into account threefold repetition; if so, you would have to basically be able to exclude any arbitrary position from the tree, which would seem impossible. The 50-move rule is respected by the Syzygy tablebases, though with the concession that they do not generally give the fewest possible moves to mate (they would rather delay the mate than delaying a pawn push or a capture). Here's an example (adapted from the URL below): https://syzygy-tables.info/?fen=3R4/5R2/8/8/8/1K6/8/4k3_w_-_-_0_1 https://syzygy-tables.info/?fen=3R4/5R2/8/8/8/1K6/8/4k3_w_-_... — if you asked pretty much any player, even a child, how to win this, they'd show the staircase mate starting with Re7+ (mate in 4). If you asked a computer or the older Nalimov tablebases, it would say Kc2! (mate in 2). However, if you ask the Syzygy tablebases, they would argue that this is not optimal if we are extremely close to the 50-move rule, so the safest and thus best move is Rf2!! which forces Black to capture the rook on the next turn (they have no other legal moves), resetting the counter and giving a mate in 18. There were a set of experimental DTM50 tablebases made at some point (though not made public); they store the shortest mate for all 100 possible zeroing counters in any position. See https://galen.xyz/egtb50/ https://galen.xyz/egtb50/ for some discussion.
    - jonah-archive 8mo ago
      In this lovely paper: https://tom7.org/chess/longest.pdf https://tom7.org/chess/longest.pdf The author points out that: "This rule only applied to games started after its introduction, so it is possible that some pre-1561 games are still in progress and may never end."
    - drpixie 8mo ago
      As I understand it, the 50-move rule must be invoked by one of the players, lets assume our immortal players agree not to invoke that rule. The 75-move rule is automatic, so that would be the limiting factor. Note, that 75-move rule is only applicable after no pawn has moved or a piece has been captured. So our immortals can do a lot of shuffling things around. I'm thinking that the number of moves of the longest game is going to be (16 pawns * 7 moves each + 16 pawns being captured + 14 other pieces each being captured, not the kings) * 75 moves for shuffling around = 10650 moves. That's only 1 week at 1 move per minute! But given the permutations, it might take much longer to calculate the actual moves required to get to the end state :)
      - Sesse__ 8mo ago
        Here's an actual constructed game that is presumably as long as possible (with explanation): https://www.reddit.com/r/chess/comments/168qmk6/longest_possible_chess_game_88485_moves/ https://www.reddit.com/r/chess/comments/168qmk6/longest_poss...
      - DSMan195276 8mo ago
        Pawns only get 6 moves :) But also they can't all make 6 moves because they can only move past each-other via capture, so half of them would get 5 moves instead (if you're counting all the captures), so that gives a maximum of ~8850.
- erehweb 8mo ago
  This link https://wismuth.com/chess/longest-game.html 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.
tromp 8mo ago
> 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/AGoogolplexOfGoGames.pdf https://matthieuw.github.io/go-games-number/AGoogolplexOfGoG... [2] https://en.wikipedia.org/wiki/Game_complexity#Complexities_of_some_well-known_games https://en.wikipedia.org/wiki/Game_complexity#Complexities_o... [3] https://tom7.org/chess/longest.pdf https://tom7.org/chess/longest.pdf
- jmount 8mo ago
  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.
- qsort 8mo ago
  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.)
GMoromisato 8mo ago
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?
- tromp 8mo ago
  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).
- bdamm 8mo ago
  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.
  - reassess_blind 8mo ago
    Yes, the stronger the players, the more often they will both go deeper into established theoretical lines that have been played before.
  - dpc050505 8mo ago
    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.
- recursivecaveat 8mo ago
  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.
  - matusp 8mo ago
paulpauper 8mo ago
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.
- LegionMammal978 8mo ago
  Assuming you're referring to [0], that's a statistical estimate of valid chess positions (based on clever methods of uniform position sampling + fast validity testing), not valid chess games (based on estimating branching factors for very long games). [0] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking
jonas_kgomo 8mo ago
I watched a movie a few days ago and they basically said there are more states in the game of chess than atoms in the universe? https://www.youtube.com/watch?v=xfMQ7hzyFW4 https://www.youtube.com/watch?v=xfMQ7hzyFW4
- adonovan 8mo ago
  Sure, but in combinatorics the number of atoms in the universe (say 1e80) is not a large number. For example, the factorial of 59 is larger. If you own 30 pairs of shoes, there are factorial(60) ways to arrange the individual shoes in a sequence.
  - BobaFloutist 8mo ago
    To be fair, that's atoms in the observable universe. The total size of the universe is unknown, and could (and likely does) have way more atoms than that. Actually, that's a fun thought: assuming homogenuity of matter between the observable and unobservable universe, how much bigger would the unobservable universe need to be to render some of these claims no longer true? Because you're right to point out that factorials grow absurdly quickly. It's entirely possible my caveat straight up doesn't matter. Edit: Ok, I'm seeing Wikipedia has a (disputed) estimate for the diameter of the total universe as 10^10^10^128 megaparsecs. Then, radius cubed should be 1/2(10^10^10^128^3)=1/210^10^10^131, as opposed to the radius of the observable universe being a nice, clean 14 billion parsecs = 1410^3 megaparsecs, making the radius cubed 1410^4 megaparsecs. I don't think I have a big enough calculator for this, but for fun, let's say 128^3 is roughly 2,000,000. Then we can rewrite T, the relative volume of the total universe, as 1/210^10^10^2*(10^ 6). I guess if we call 14 close enough to 10, then our density is 10^80/10^6=10^74 atoms for every pi megaparsecs cubed. Going off the heuristic that n!<n^n, and the total universe can trivially produce (10^10)^(10^10), we would need to rearrange >10^10 objects just to even start to think about the number of (megaparsecs cubed)/pi it might have, let alone the 10^74 those each have. We might not have enough decks of cards for this one. (Feel free to criticize/tear down my math or logic anywhere in this one, it's very much off the cuff and I'm sure I made at least as many egregious errors in computing exponents as I did computations. No math class I've taken yet really prepares you to handle exponents raised four deep.)

85 points by jmount 8mo ago

RA_Fisher 8mo ago

Infinite. :) Chess is strictly unbounded.

Mordisquitos 8mo ago
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'.
- eulgro 8mo ago
  Well there is. The three/five fold rule. And 50 moves rule.
- DSMan195276 8mo ago
  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.
  - LegionMammal978 8mo ago
    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.
    - Sesse__ 8mo ago
      Endgame tablebases don't take into account threefold repetition; if so, you would have to basically be able to exclude any arbitrary position from the tree, which would seem impossible. The 50-move rule is respected by the Syzygy tablebases, though with the concession that they do not generally give the fewest possible moves to mate (they would rather delay the mate than delaying a pawn push or a capture). Here's an example (adapted from the URL below): https://syzygy-tables.info/?fen=3R4/5R2/8/8/8/1K6/8/4k3_w_-_-_0_1 https://syzygy-tables.info/?fen=3R4/5R2/8/8/8/1K6/8/4k3_w_-_... — if you asked pretty much any player, even a child, how to win this, they'd show the staircase mate starting with Re7+ (mate in 4). If you asked a computer or the older Nalimov tablebases, it would say Kc2! (mate in 2). However, if you ask the Syzygy tablebases, they would argue that this is not optimal if we are extremely close to the 50-move rule, so the safest and thus best move is Rf2!! which forces Black to capture the rook on the next turn (they have no other legal moves), resetting the counter and giving a mate in 18. There were a set of experimental DTM50 tablebases made at some point (though not made public); they store the shortest mate for all 100 possible zeroing counters in any position. See https://galen.xyz/egtb50/ https://galen.xyz/egtb50/ for some discussion.
  - jonah-archive 8mo ago
    In this lovely paper: https://tom7.org/chess/longest.pdf https://tom7.org/chess/longest.pdf The author points out that: "This rule only applied to games started after its introduction, so it is possible that some pre-1561 games are still in progress and may never end."
  - drpixie 8mo ago
    As I understand it, the 50-move rule must be invoked by one of the players, lets assume our immortal players agree not to invoke that rule. The 75-move rule is automatic, so that would be the limiting factor. Note, that 75-move rule is only applicable after no pawn has moved or a piece has been captured. So our immortals can do a lot of shuffling things around. I'm thinking that the number of moves of the longest game is going to be (16 pawns * 7 moves each + 16 pawns being captured + 14 other pieces each being captured, not the kings) * 75 moves for shuffling around = 10650 moves. That's only 1 week at 1 move per minute! But given the permutations, it might take much longer to calculate the actual moves required to get to the end state :)
    - Sesse__ 8mo ago
      Here's an actual constructed game that is presumably as long as possible (with explanation): https://www.reddit.com/r/chess/comments/168qmk6/longest_possible_chess_game_88485_moves/ https://www.reddit.com/r/chess/comments/168qmk6/longest_poss...
    - DSMan195276 8mo ago
      Pawns only get 6 moves :) But also they can't all make 6 moves because they can only move past each-other via capture, so half of them would get 5 moves instead (if you're counting all the captures), so that gives a maximum of ~8850.
erehweb 8mo ago
This link https://wismuth.com/chess/longest-game.html 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.

tromp 8mo ago

> 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/AGoogolplexOfGoGames.pdf https://matthieuw.github.io/go-games-number/AGoogolplexOfGoG... [2] https://en.wikipedia.org/wiki/Game_complexity#Complexities_of_some_well-known_games https://en.wikipedia.org/wiki/Game_complexity#Complexities_o... [3] https://tom7.org/chess/longest.pdf https://tom7.org/chess/longest.pdf

jmount 8mo ago
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.
qsort 8mo ago
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.)

GMoromisato 8mo ago

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?

tromp 8mo ago
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).
bdamm 8mo ago
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.
- reassess_blind 8mo ago
  Yes, the stronger the players, the more often they will both go deeper into established theoretical lines that have been played before.
- dpc050505 8mo ago
  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.
recursivecaveat 8mo ago
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.
- matusp 8mo ago

paulpauper 8mo ago

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.

LegionMammal978 8mo ago
Assuming you're referring to [0], that's a statistical estimate of valid chess positions (based on clever methods of uniform position sampling + fast validity testing), not valid chess games (based on estimating branching factors for very long games). [0] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking

jonas_kgomo 8mo ago

I watched a movie a few days ago and they basically said there are more states in the game of chess than atoms in the universe? https://www.youtube.com/watch?v=xfMQ7hzyFW4 https://www.youtube.com/watch?v=xfMQ7hzyFW4

adonovan 8mo ago
Sure, but in combinatorics the number of atoms in the universe (say 1e80) is not a large number. For example, the factorial of 59 is larger. If you own 30 pairs of shoes, there are factorial(60) ways to arrange the individual shoes in a sequence.
- BobaFloutist 8mo ago
  To be fair, that's atoms in the observable universe. The total size of the universe is unknown, and could (and likely does) have way more atoms than that. Actually, that's a fun thought: assuming homogenuity of matter between the observable and unobservable universe, how much bigger would the unobservable universe need to be to render some of these claims no longer true? Because you're right to point out that factorials grow absurdly quickly. It's entirely possible my caveat straight up doesn't matter. Edit: Ok, I'm seeing Wikipedia has a (disputed) estimate for the diameter of the total universe as 10^10^10^128 megaparsecs. Then, radius cubed should be 1/2(10^10^10^128^3)=1/210^10^10^131, as opposed to the radius of the observable universe being a nice, clean 14 billion parsecs = 1410^3 megaparsecs, making the radius cubed 1410^4 megaparsecs. I don't think I have a big enough calculator for this, but for fun, let's say 128^3 is roughly 2,000,000. Then we can rewrite T, the relative volume of the total universe, as 1/210^10^10^2*(10^ 6). I guess if we call 14 close enough to 10, then our density is 10^80/10^6=10^74 atoms for every pi megaparsecs cubed. Going off the heuristic that n!<n^n, and the total universe can trivially produce (10^10)^(10^10), we would need to rearrange >10^10 objects just to even start to think about the number of (megaparsecs cubed)/pi it might have, let alone the 10^74 those each have. We might not have enough decks of cards for this one. (Feel free to criticize/tear down my math or logic anywhere in this one, it's very much off the cuff and I'm sure I made at least as many egregious errors in computing exponents as I did computations. No math class I've taken yet really prepares you to handle exponents raised four deep.)