How many sensible chess games are there?

The following is reposted from my post on chess.stackexchange.

Introduction

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?

TL;DR

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.

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.

Similarly with checks and non-checks:

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.

I think another interesting question is: how many HALF-sensible chess games are there. That is, how many games in which one player is not making any obvious blunders. This is something that I considered when I was building a basic arsenal of opening moves.

@1

You seem to forget about the huge impact of transpositions.