I read this tweet recently:
"There are more possible games of chess lasting 40 moves than there are atoms in the entire universe. Intriguing to know."
I find this highly doubtful.
Could anyone verify this for me please?
Skeptics Stack Exchange is a question and answer site for scientific skepticism. It only takes a minute to sign up.Sign up to join this community
There are vastly many more 40-move chess games than atoms in the visible universe, which we will prove below. But first, some clarification:
The game-tree complexity of chess, 10123 is based on an average branching factor of 35 and an average game length of 80"
(In fact, there are an infinite number of possible games of chess, provided no player claims a draw through repetition nor the 50 move rule. The above estimates are based on more practical numbers.)
We will give a constructive proof that there are more 40-move chess games than atoms in the visible universe. Consider the following set of possible 40-move chess games starting with:
Now, for the remainder of the game white can make one of the following moves:
The black pieces are restricted symmetrically. Continue this for the next 74 ply. Then the white player resigns.
We observe that:
The pieces never obstruct one another. Captures are never made. Check never occurs. Hence, for each ply, there are 14 legal moves.
We have used very few of the actual possible moves available to us. There will be vastly many more possible 40-move games than in this class.
These games last exactly 40 moves. (If you count resigning as a ply, then you can have black resign on the previous ply.)
Hence we have constructed a set of 1474 distinct 40-move games of chess. Moreover, 1474 > 1084, while 1080 is an estimate of the number of atoms in the observable universe.
In chess, players may claim a draw through the "three move rule", although are not obliged to claim. (This leads to cases where players play on indefinitely, sometimes caused by chess coaches insisting that their students do not accept nor offer a draw, sometimes caused by players unaware of the rules.) Also, typically, the three move rule is ignored in theoretical studies.
These positions end with a player resigning, but they could probably be modified to end in helpmate if required. However, this would reduce the overall number (and you'll probably need to use a more clever argument).
There are probably better constructions around than what I give here.
Edit 2019-01: answering this question boils down to knowing how many possible ways there are to play 40 move games of chess and how many atoms there are in the universe. The latter is known, and all of these answers ultimately cite chess experts, only varying in their interpretation of their figures.
I like the answer from Douglas S. Stones the most as it is the most original. It constructs a move tree that by itself exceeds the number of atoms in the universe, thus directly answering the question.
DavePhD also has the quotes laid out most explicitly, showing that my reliance on the Wolfram site was wrong.
Edit: I'll leave the original as it stands, but want to add a correction thanks to Mike Dunlavey's comment. I misread the question and thus if the question is, indeed, asking whether games lasting 40 moves or less (I read 40 moves or more) is greater than the number of atoms in the universe, I'm switching my answer to disagree. The numbers are all there below, but now we're comparing 10^80 (# of atoms) vs. 10^43 (# of 40 move or less chess games). Thus the number of atoms is greater.
I would agree.
First, Wiki provides this figure on the number of atoms in the universe:
Two approximate calculations give the number of atoms in the observable universe to be close to 10^80.
Next, Wiki provides the Shannon number as the number of possible chess games that can be played:
The game-tree complexity of chess was first calculated by Claude Shannon as 10^120, a number known as the Shannon number.
Lastly, Wolfram Mathworld provides a figure for the number of games less than 40 moves:
The number of possible games of 40 moves or less P(40) is approximately 10^40 (Beeler et al. 1972) ...Shannon (1950) gave the estimate: P(40) = 64! / (32! * 8!^2 * 2!^6) = 10^43.
I see some other answers have come in while I've been typing. They seem to compare total possible games (10^120) to the number of atoms in the universe (10^80), but you're looking for the number of atoms compared to games longer than 40 moves. In that case, we look at:
10^80 vs. 10^120 - 10^43 (to be conservative)
To be fair, the poster's (@Vian) own answer is correct, as 10^43 doesn't even dent 10^120 and thus it's still essentially comparing 10^80 and 10^120. Just wanted to spell out why I think the question is slightly different than just comparing # of atoms and # of all possible chess games.
The accepted answer is wrong, due to the fallacy of accepting a link to a another website as the truth, rather than actually doing the math.
Particularly, the site http://mathworld.wolfram.com/Chess.html confused the number of positions, with the number of 40-move games.
Though mathworld says
The number of possible games of 40 moves or less P(40) is approximately 10^(40) (Beeler et al. 1972)
The Beeler reference itself is very clear that it means positions, not games:
There are about 10^40 possible positions
and though mathworld says
Shannon (1950) gave the estimate ... 10^43
Shannon really wrote in XXII. Programming a Computer for Playing Chess Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950 :
In typical chess positions there will be of the order of 30 legal moves. The number holds fairly constant until the game is nearly finished as shown in fig. 1. This graph was constructed from data given by De Groot, who averaged the number of legal moves in a large number of master games (De Groot, 1946, a). Thus a move for White and then one for Black gives about 1000 possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10^120 variations to be calculated from the initial position.
Another (equally impractical) method is to have a "dictionary" of all possible positions of the chess pieces. For each possible position there is an entry giving the correct move (either calculated by the above process or supplied by a chess master.) At the machine's turn to move it merely looks up the position and makes the indicated move. The number of possible positions, of the general order of 64! / 32!(8!)^2(2!)^6, or roughly 10^43
In chess, "40 move game" means each player moves a piece 40 times: 80-ply or 80 half moves.
in standard chess terminology, one move consists of a turn by each player; therefore a ply in chess is a half-move. Thus, after 20 moves in a chess game, 40 plies have been completed—20 by white and 20 by black.
So for a 40 move game, if it is approximated that there is some constant (c) number of legal half-moves, the approximation of the number of 40 move games is of the form:
c ^ 80
So as long as "c" is greater than 10, the number of 40 move games is greater than the number of atoms in the universe.
For example, there are 20 possible first half-moves (16 pawn moves and 4 knight moves), and 20 possible second half moves.
So Shannon, citing to De Groot uses the estimate of "30" for "c" and therefore:
30^80 = ~1.5 x 10^118
So, yes, there are more exactly 40 move (80-half move) games than the number of atoms in the universe.
After some better searching I found this:
The Shannon number
Allis also estimated the game-tree complexity to be at least 10^123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^79 and 10^81.
Also, here is someone who tries to explain it more clearly.