1

Analytic procedures for estimating the number of possible games of chess typically reason that on each ply, a player has some limited number of sensible options, O, and the average game of chess lasts about p plys. Thus, there are about O^p games of chess. Choosing O=3 and p=80, you get something like 1.5x10^38. This is the strategy taken by Shannon and others.

However, such procedures are likely to mis-estimate the true number of sensible games. Chess games are frequently characterized by long sequences of forcing moves, where there is only one option worth considering. Further, the estimated number of options for each ply seems pulled out of thin air. Thus, the true number of decision points is different than assumed.

What is a better estimate?

5
  • 1
    Do you have a definition of "sensible"?
    – D M
    Mar 10 at 4:03
  • I suspect that you are asking after something like a computational tractable definition. I am resistant to give such a definition because I think it takes the question out of the realm of what I'm actually interested, which is characterizing human chess. With that in mind, I mean 'sensible' in its everyday sense. It is a move that would be generally agreed to be sound, favorable, or generally worth considering when encountered in the context of a game of chess. Of course, this is relative to the skill of the player and the constraints they are working under.
    – Nathan
    Mar 10 at 5:26
  • This is why I was careful to specify the source of my data in my answer. I think that it is likely that players of different skill would consider a different number of moves from any given position. Taken to the extreme, suppose that you played perfectly. Then you would only ever consider one move, the winning move. However, such differences are perfectly sensible under the broad framework of the question, which is to try and estimate the number of such moves in any position and the number of moves in a game. Such parameters may well vary drastically, and it would be interesting to see how.
    – Nathan
    Mar 10 at 5:32
  • "It is a move that would be generally agreed to be sound, favorable, or generally worth considering when encountered in the context of a game of chess." - Hmm. But that's a definition of "sensible move", not "sensible game". For example, it's perfectly plausible for a strong player to blunder and hang a pawn somewhere between moves 5-10. But it's not plausible that they would hang a pawn on each of the moves 5-10. If the goal is "characterizing human chess" then the distinction might matter.
    – D M
    Mar 10 at 11:39
  • A sensible game is a game in which all moves are sensible. Handling blunders is relatively easy. Assume that on any given move, a player has some constant probability of making a blunder. We adjust the estimate of the number of sensible moves down by a similar constant factor. If the chance of a blunder on any move is b, you estimate (O*b)^p. It's harder if blunders are forcing. That would affect the estimate of p in a way that is difficult to account for because a blunder can plausibly shorten or lengthen a game.
    – Nathan
    Mar 10 at 16:42
4

TLDR: Forced plies are relatively rare, and when given an option, a player tends to have more options than supposed by the example calculation. Using the methodology below, I estimate that there are about 74 unforced plies in a game of chess and that a player has about 4.35 sensible options on each one. Thus, the number of sensible chess games is 4.35^74 = 2.37x10^47. Note that this is much larger than the analytic estimate in the question, roughly 1.5 billion times larger!

Methodology and data

The following procedure is based on the assumption that if a given ply is sensible, then we should observe it given a large enough sample of games. If it is not sensible, then it would never be made, and hence would never be observed.

First, I downloaded the Lichess Elite database. This is a database of non-Bullet games played on Lichess by players with ratings of +2200. Note that the actual selection criteria are a bit more complicated. The point is that these are fairly expert players, who presumably are unlikely to make silly errors. There are 3,818,709 games in the database, of which ~99.8% are unique. The average game is 84 plys long, and the median is 80.

4 million games is too many to feasibly process, so I randomly sampled 100,000 for further analysis.

From this data, I constructed a tree representing all observed games. At the root of the tree is a single node representing the start of the game. The children of this node represent all observed first plies. Each child in turn has its own children, representing all observed replies to the first ply, and so on and so forth. When a game is terminated, then the last ply made has a single child denoting the number of observed games that arrive at that game state. I also pruned the tree, so that if some node is associated with only a single continuing game, I cut it out so that it only is associated a single, terminating node.

Finally, I marked whether each ply was forcing or not. A ply was forcing if (i) there was only one observed reply, and (ii) more than one game reached that ply.

A few notes about the data:

  1. There are 207,635 unique game states in the tree. This is a slight overestimate, as it doesn't take into account transpositions.
  2. Over half of them, or 107,833, have been visited by more than one game.
  3. 10,630 of the nodes, or roughly 10%, have been visited by more than 10 games.
  4. Forcing is confounded with game depth. As we go further in the tree, fewer and fewer games are associated with each node. Thus, for some node deep in the tree, it may be that there were more sensible moves to make, but we just didn't play that game enough times to find them. To deal with this, I will only be looking at nodes that were reached by at least 10 games.
  5. The above considerations mean that our look at the end game is dim. I don't have good intuitions on this point, as it could seem reasonable to suppose that endgames are characterized by more, fewer, or the same number of forced plys. More of the board is open to make slightly different moves, but the probability of a forcing check is presumably higher.

Results

For plies with more than 10 associated games, the average number of observed replies is 3.95. Omitting non-forcing moves, this increases to 4.35 replies. These numbers did not vary by player color.

Of the nodes with more than 10 associated games, 11.67% of them are forcing. Captures and checks are more likely to be forcing: a capture was forcing 30.4% of the time vs 0.09% for non-capturing moves. Similarly, 38.6% of checks were forcing, vs 11.3% of non-checks. Neither White nor Black were more likely than the other to make a forcing move.

As shown in the following figure, the number of available options changes over the course of a game. In the opening, players are free to make any choice they wish. Indeed, of the 400 possible opening moves, most (288) of them were observed at least once, and 139 of them were observed at least 10 times. Later, players are gradually more restricted, until they have about 2.5 options per ply.

enter image description here

Breaking it down by captures and non-captures is illuminating. The following figure displays the proportion of plies that are forcing, broken down by whether or not they were a capture.

Proportion of plies that are forcing by captures

Similarly with checks and non-checks:

Proportion plies by check/non-check

Conclusions

Forcing moves are relatively rare, and that players tend to have many sensible options for any given reply. Thus, there are more sensible games of chess than purely analytic methods would indicate.

4
  • At some point, I will make my code available for review. More selfishly, I worked pretty hard on making this data set, so I would like to get more out of it. I would be grateful for any questions that might plausibly be addressed by it.
    – Nathan
    Mar 8 at 20:19
  • Finally, I am currently doing the leg work to perform this analysis with a different database incorporating information about player skill to see if these conclusions vary by that factor.
    – Nathan
    Mar 8 at 20:21
  • 1
    Very interesting data! I suggest to repeat the analysis with a less complex (YMMV) game like checkers. (Obviously, chess has the advantage of so much easily accessible input data.) Also, did you put some typical position into, say, Stockfish, and count all sensible O (say, +-0.2 pawn units)? O=3 seems to be far too low for my gut feeling. Mar 8 at 21:17
  • @HaukeReddmann Thanks! In addition to some clean-up, those are exactly the next steps I was considering. Looking at draughts is interesting because some moves are literally forced. But as you point out, the data is less available. Go would be cool, but it's got too complicated of an opening phase. You are unlikely to get many games that go the same way. I'm also thinking about how best to do the computer evaluation. Right now my plan is to sample states from the game tree and get the evaluation of all possible continuations. And I agree on O=3 being low.
    – Nathan
    Mar 8 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.