How many chess games are possible?

Posted by jmount 2 days ago

Comments

Comment by tromp 2 days 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/AGoogolplexOfGoG...

[2] https://en.wikipedia.org/wiki/Game_complexity#Complexities_o...

[3] https://tom7.org/chess/longest.pdf

Comment by jmount 2 days 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.

Comment by Someone 1 day ago

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.

Comment by tromp 1 day ago

> That’s over ten times as many games as estimated.

That's still a pretty good estimate of an exponentially large quantity; the exponent being off by only 1. With these estimates you cannot hope to do better than estimating the exponent.

Comment by Someone 1 day ago

But for chess, the spread in number of moves is a lot larger, and the branching factor is higher. 20 more half moves and a branching factor of 35 isn’t unreasonable, and gives you an underestimation of over 10³⁰.

And these tweaks do not complicate the math.

Comment by qsort 2 days 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.)

Comment by Sesse__ 2 days ago

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.)

Comment by qsort 2 days ago

That's not new, but how it formally works has changed. There used to be a number of explicitly enumerated cases (i.e. bare king and king with a minor piece,) now the rule instead just says that there must exist a sequence of moves to mate. Some positions, even with pawns (imagine a completely closed position with only pawns and kings) wouldn't have been automatically drawn under the previous system but now would be. I think USCF rules, unlike FIDE, still have the enumerated cases?

The difference is extremely minor and has almost no strategic implications, it's just an interesting corner case.

Comment by Sesse__ 1 day ago

The oldest rules on FIDE's pages are the ones for “before 2014”. They state:

  The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was legal. (See Article 9.6)

And 9.6 just states:

  The game is drawn when a position is reached from which a checkmate cannot occur by any possible series of legal moves. This immediately ends the game, provided that the move producing this position was legal.

And similarly 6.9, which governs loss on time:

  Except where one of the Articles: 5.1.a, 5.1.b, 5.2.a, 5.2.b, 5.2.c applies, if a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves.

So it's at least ten years old, but possibly quite more. I know I have a copy of the 1984 rules (or possibly even older) somewhere on paper, but then I'd have to go into the attic :-)

Comment by TZubiri 2 days ago

Does it depend on elo as well?

Comment by lmm 1 day ago

No. How could it possibly depend on elo?

Comment by TZubiri 1 day ago

Well it can depend on Referee discretion, and the referee can evaluate whether a position is obviously a draw or not.

Something in high elo may obviously be a draw, like KRPPP vs KRPP, or KRN vs KR but not necessarily in lower elo.

Comment by Sesse__ 1 day ago

What if the players are both much higher-rated than the arbiter?

Basically, once you've lost on time, you're giving up the right to any sort of agency, and thus the Elo doesn't matter. The rules are charitably giving you a rating of minus infinity and allow you to attempt salvaging half a point with that.

Comment by jmount 2 days ago

I just updated the article. I did use Python's insufficient material detection, in addition to the ability to call for a draw (3-fold repetition, and 50 move rule). I think the "75 move rule" that doesn't require a player to call is one of the more recent rule changes.

Comment by Someone 1 day ago

> 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.

I don’t see what makes that technically difficult. The number of possible positions is finite, so just enumerate the game tree and check whether it contains a checkmate situation.

I also don’t see why it would be almost impossible in practice. Aren’t the only weird situations ones where there are pawns that could be promoted to queens if they weren’t blocked by other pawns, and those pawns prevent all other pieces on the board from taking pawns and from checkmating the king?

Comment by qsort 17 hours ago

In the overwhelming majority of situations including almost the totality of those you care about in practice, it's trivial to say "draw" or "no draw". I mean "technically correct" in this sense: imagine you're a programmer writing a chess game. At some point, you have to write a function "isPositionDrawn()" that takes as input a board position and says "true" if the game is over as a draw, false otherwise. What do you do?

- Trivial material checks don't work: even if you're sophisticated (light color vs. dark color bishops) there exist positions, even with pawns, that are drawn as per the rule as stated.

- Enumerating the game tree is obviously correct but it's too large to do in practice, we want an answer before the heat death of the universe.

So, what code do you put inside that function? If I'm not mistaken there is an "official" algorithm to do it, but it's very complicated, and in practice in computer chess a simplified version of the rule (a list of cases with "insufficient material") is used.

Again, it's mostly nerdy navel gazing, the consequences on actual play are minuscule, but it's interesting that many games have nontrivial termination if we follow the letter of the rules.

Comment by program_whiz 1 day ago

You're approach seems straight-forward in theory -- just check every possible move and make sure that none lead to a checkmate. The only issue is that "checking every possible move" is a huge state space (way above what is computable). Not only that, but there are cycles (so you need to deduplicate). And if the game is a draw, then that means the number of moves is technically unbounded (since there would always be a move that makes the search tree deeper), as by definition, there is no way to end the game. So the question is 'when do you stop searching?'. It could be that checkmate is possible, but you haven't searched the 1 in 1 billion part of the strategy tree. In practice, its probably down to some heuristics and a reasonable depth search, but its not formally verifiable. Its a variant of the halting program -- prove that there is a stopping point for this game.

Comment by BobaFloutist 1 day ago

>there are pawns that could be promoted to queens if they weren’t blocked by other pawns, and those pawns prevent all other pieces on the board from taking pawns and from checkmating the king?

I'm having a hard time picturing this scenario. Is it that any move to take a pawn places the mover in check?

Comment by Someone 1 day ago

I have a hard time envisioning that, too, but I think one can construct boards with rook or two bishops being closed in behind a setup with all 16 pawns still on the board, with the opposing king on the other half of the board.

Comment by lxgr 1 day ago

For 7 remaining pieces or less, there are actually tablebases of all possible positions showing whether there's a possible win or loss for either side: https://en.wikipedia.org/wiki/Endgame_tablebase

Comment by eszed 1 day ago

Huh! I don't follow chess closely enough to have known the tables go that deep. Do high-level players memorize (enough of) those that their strategy in a losing position shifts to creating a drawing piece combination? Or do the tables only formalize something was that always done intuitively?

Comment by lxgr 1 day ago

I don't think human players memorize tables in the same way that they memorize opening lines. The number of possible endgame position values is astronomical; "Syzygy" for 7 pieces is a few TB of data, for example.

Heuristics get them very close, but I vaguely remember hearing that sometimes the tables will find an obscure move sequence to turn around a draw to a win 15 or 20 moves in that a human has no chance of spotting.

These tablebases do have something eerie to them, as they represent the phase transition from heuristics to the "solved" part of chess. Lichess will automatically swap to them once it's feasible, and instead of a position evaluation, you'll just instantly see whether it's winning, losing, or drawing. Ken Thompson called it "playing chess with God": https://en.wikipedia.org/wiki/Endgame_tablebase#%22Play_ches...

That said, this can happen with chess engines as well; if a position can be exhaustively analyzed, it'll show you "winning/losing/drawing in n moves" just like the tablebases. The tablebases just guarantee that they'll find that solution in constant time.

Comment by 1 day ago

Comment by GMoromisato 2 days 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?

Comment by recursivecaveat 2 days 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.

Comment by squidbeak 1 day ago

It depends totally on the opening. You can be out of book and database far quicker than that for offbeat stuff, or in book far longer for popular openings.

Another distinction needs to be made between positions seen and positions played. Almost every viable position will have been seen in preparation well beyond 10 moves. But seeing them on the board is rarer.

Comment by empiko 1 day ago

I don't think the math is correct here. The 25% of positions that have been seen more than once represent more than 25% of the occurrences. Even if all of them would be seen only twice, you should already see them in 40% occurences.

Comment by tromp 2 days 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).

Comment by bdamm 2 days 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.

Comment by dpc050505 2 days 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.

Comment by reassess_blind 2 days ago

Yes, the stronger the players, the more often they will both go deeper into established theoretical lines that have been played before.

Comment by jonas_kgomo 2 days 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

Comment by adonovan 2 days 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.

Comment by BobaFloutist 1 day 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.)

Comment by paulpauper 2 days 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.

Comment by LegionMammal978 2 days 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

Comment by RA_Fisher 2 days ago

Infinite. :) Chess is strictly unbounded.

Comment by erehweb 1 day ago

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.

Comment by Mordisquitos 2 days 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'.

Comment by DSMan195276 2 days 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.

Comment by jonah-archive 2 days ago

In this lovely paper: 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."

Comment by drpixie 1 day 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 :)

Comment by Sesse__ 1 day 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_poss...

Comment by DSMan195276 1 day 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.

Comment by LegionMammal978 2 days 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.

Comment by Sesse__ 1 day 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_-_... — 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/ for some discussion.

Comment by eulgro 2 days ago

Well there is. The three/five fold rule. And 50 moves rule.