11

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?

10

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.

  • 1
    I thought he was asking for games of 40-moves (or less), not 40-moves (or more). – Mike Dunlavey Jun 2 '11 at 22:02
  • 1
    @Mike Dunlavey: ever had that feeling where you feel like an idiot? Yeah... that's about now :) I guess I did misread that. The numbers are all there, though. 40 moves (or less) is, then, less than the number of atoms and thus the statement would be false... Am I getting that right? – Hendy Jun 2 '11 at 22:22
  • 1
    Hi, I just wanted to add that in Chess a "move" is two "plys" by either side. (A move consists of both black and white making a move.) So essentially one chess move = two pieces moved. I think that's where the disparity comes from between true and false. – Vian Esterhuizen Jun 3 '11 at 4:17
  • 1
    @Vian: I tried to figure that out myself and wasn't sure, but I did make the assumption that Shannon had it right when he provided the figure for games 40 moves or less, so I don't think our definition of "move" affects anything as long as Shannon got it right -- we have all the numbers necessary at this point to answer the question as far as I can tell. – Hendy Jun 3 '11 at 12:24
  • 1
    @Hendy 10^120 is for the number of games lasting exactly 40 moves. A 40 move game in chess means each player has 40 turns. The 10^40 and 10^43 numbers are for the number of possible positions (not games). The Wolfram site is misreporting its references. – DavePhD Jan 17 at 17:59
19

There are vastly many more 40-move chess games than atoms in the visible universe, which we will prove below. But first, some clarification:

  • Earlier posts mention the Shannon number, which is his estimate for the game-tree complexity of chess (i.e., the number of possible games). Shannon gave the estimate 10120 as a remark in "Programming a Computer for Playing Chess". Another estimate by Victor Allis was 10123 (this is mentioned in his PhD thesis linked from the Wikipedia page). He writes:

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

  • The above seems to be confused with the state space complexity, i.e., the number of possible legal and reachable positions on a chess board (which is a drastically different number than asked for in the question). In fact, a strict upper bound for this was derived by Allis (op. cit.) as 5 * 1052 , which is greatly less than the number of atoms in the visible universe (estimated at 1080; cf. Wikipedia).

Notation: A move in chess consists of two ply, one ply by white and one ply by black. Thus we have the "two move mate" (1. f3 e5 2. g4 Qh4#). The notation used here is algebraic notation.

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:

  1. e4 e5
  2. d4 d5
  3. c3 c6

Now, for the remainder of the game white can make one of the following moves:

  • The white white-squared bishop can move to any square on the f1-a6 diagonal (6 squares => 5 possible moves).
  • The white black-squared bishop can move to any square on the c1-h6 diagonal (6 squares => 5 possible moves).
  • The white queen can move to any square on the d1-a4 diagonal (4 squares => 3 possible moves).
  • The white knight on g1 can move to any square in the set {g1,f3} (2 squares => 1 possible move).

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.

Some comments:

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

  • +1 Great answer! – DavePhD Jan 17 at 19:37
  • 1
    This answer is better than mine. I like that it gets into the legality and feasibility of moves in the context of a real game, not just possible permutations. Sadly, the SO family will trend toward accepting/voting answers given first, and rarely will readers skim all of them and overturn a previously accepted answer afterward. – Hendy Jan 18 at 16:04
  • The first three moves can be done in any order, multiplying the number of games further by 6 x 6. – gnasher729 Jan 19 at 0:55
6

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.

  • 2
    +1 I'm glad you're resurrecting interest in this question. – Mike Dunlavey Jan 17 at 18:42
  • Good answer but seems to be missing the number of atoms in the universe. Although every other answer has listed it, they could theoretically be deleted... – pipe Jan 18 at 3:28
  • @pipe ok, I added link to "the number of atoms in the universe". – DavePhD Jan 18 at 11:35
  • Observation: you're criticizing me for not doing the math, yet your answer amounts to checking sources (which I absolutely applaud, and is far better than what I did 7 years ago) and ultimately figuring out that some c^80 is bigger than 10^80. When I read your opening line, I thought you were about to derive something... – Hendy Jan 18 at 16:01
  • 1
    @Hendy I totally agree with your observation. Douglas Stones's answer is the best, because he tries to prove it. But my first line is more toward the moderators, who ban logic-based answers in favor of links to other sites. – DavePhD Jan 18 at 16:13
4

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.

http://en.wikipedia.org/wiki/Shannon_number

Also, here is someone who tries to explain it more clearly.

  • 1
    The question was about 40-move games. For 80-move games there would of course be a bigger number as you say. – Mike Dunlavey Jun 2 '11 at 21:56
  • Yeah, didn't realize that at the time, but I guess in a way it does still get the point across. In a backwards sort of way that is. – Vian Esterhuizen Jun 3 '11 at 15:05
  • @MikeDunlavey In chess, a 40 move game means each player has 40 move, so 80 branching events, with an estimated 35 branches per node. – DavePhD Jan 17 at 15:00
0

A little google searching turns up these estimates:

Atoms in universe: 10^80

40-move chess games: 10^40

give or take a few zeroes.

  • 3
    This assumes an average branching factor of 10. This seems much too low, because even for the first move you have 16 different pawn moves and four different knight moves, giving you a total of 20 legal moves. In the mid game, there should be on the order of 30 to 50 different moves – Lagerbaer Jun 2 '11 at 21:51
  • @Lagerbaer: You're welcome to argue with the link. – Mike Dunlavey Jun 2 '11 at 21:52
  • @MikeDunlavey the link misreports its sources, as I explain in my answer. – DavePhD Jan 17 at 15:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .