Hello all:

How many possible Chess games are there?

Well, I think I've come up with an easy, intuitive disproof of a
number one often sees. Perhaps some of the mathematically savvy
readers of this group can give their opinion of my claim. (Thanks in
advance, should you choose to do so.)

Here's a number I often see:

"In a game of 40 moves, the number of possible board positions P(40)
is at least 10^(120) according to Peterson (1996)...."

http://mathworld.wolfram.com/Chess.html

(other estimates are given in the article hyperlinked above)

10^(120) is a 1 followed by 120 zeros

For comparison, one estimate of the number of particles in the
observable universe is 10^(80) -- a much, much smaller number.
( http://varatek.com/scott/bnum.html )

Well, the 10^(120) estimate is, I think, demonstrably too large (by
far). Here's my reason for thinking so:

In a game of Chess, a square can be in only one of 13 states. It is
either

1) empty,
2) occupied by one of the 6 white pieces (King, Queen, Rook, Bishop,
Knight, Pawn), or
3) occupied by one of the 6 black pieces (King, Queen, Rook, Bishop,
Knight, Pawn).

Since there are 64 squares, this means there are 13^(64) imaginable
states of the Chessboard.

Of course, 13^(64) is itself an overestimate, since there are not
enough pieces to "populate" all the squares with all possible
combinations (and even if there were, not all possible combinations
are legal).

But what we can tell from this consideration is that any number that
is GREATER than 13^(64) is obviously too high!

Now, just how big is 13^(64)? Well, my Microsoft Windows calculator
gives the estimate

1.96053...e+71 (a 72-digit number)

Assuming that is a reasonable estimate, this number is far, far
smaller than 10^(120)!!

Q.E.D.

If my disproof is sound, may I dub the number 13^(64) "Caissa's
Constant," being a fixed overestimate of the number of possible Chess
positions.

By the way, Mathworld, is an excellent resource for all subjects
mathematical (and all subjects Mathematica!) -- it is well worth a
bookmark, in my view.

http://mathworld.wolfram.com/

Your feedback is most welcome....

--
David Brett Richardson
http://www.100bestwebsites.org/
"The 100 finest sites on the Web, all in one place!"
Widely-watched non-profit ranking of top Internet sites

Ah, of course, this is the number of possible Chess POSITIONS --not
Chess GAMES!

Nevermind!

--
Brett
http://www.100bestwebsites.org/
"The 100 finest sites on the Web, all in one place!"
Widely-watched non-profit ranking of top Internet sites

Le 27-11-2007, Berkeley Brett a écrit*:
Hello all:

How many possible Chess games are there?

Well, I think I've come up with an easy, intuitive disproof of a
number one often sees. Perhaps some of the mathematically savvy
readers of this group can give their opinion of my claim. (Thanks in
advance, should you choose to do so.)

Here's a number I often see:

"In a game of 40 moves, the number of possible board positions P(40)
is at least 10^(120) according to Peterson (1996)...."

http://mathworld.wolfram.com/Chess.html

(other estimates are given in the article hyperlinked above)

10^(120) is a 1 followed by 120 zeros

[...]

Your feedback is most welcome....

--
David Brett Richardson
http://www.100bestwebsites.org/
"The 100 finest sites on the Web, all in one place!"
Widely-watched non-profit ranking of top Internet sites

Quite right. People often sloppily confuse the number of possible games
(for which 10^120 looks like a conservative estimate) with the number
of possible board positions (which is much smaller because the same
position can be reached in a vast number of different ways.)

I have seen "between 10^30 and 10^40" quoted as an approximation to the number
of possible board positions. When I tried to calculate a better estimate
I decided it was near to the bottom of that range (~10^39) but I
no longer have more than a hazy memory of how I came to that conclusion.

Mike.

Berkeley Brett wrote:
Well, I think I've come up with an easy, intuitive disproof of a
number one often sees. Perhaps some of the mathematically savvy
readers of this group can give their opinion of my claim. (Thanks
in advance, should you choose to do so.)

Your argument that 13^64 is an upper bound on the number of ways to
arrange the pieces on the board is correct. However, this in no way
proves that the total number of games cannot be more than 13^64. Many
positions can be reached in more than one way. For example, the
position after 1.e4 e5 can be reached by all kinds of routes,
including but not limited to,

1.e4 e5
1.e3 e6 2.e4 e5
1.Nf3 Nc6 2.Ng1 Nb8 3.e4 e5

Thus, the number of possible games dramatically exceeds the number of
possible positions.


Dave.

--
David Richerby Accelerated Permanent Hat (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a hat but it'll be there for ever
and it's twice as fast!

Berkeley Brett wrote:
Ah, of course, this is the number of possible Chess POSITIONS --not
Chess GAMES!

Gaaaaah, this whole thread is a pile of confusion about the difference
between positions and games. :-) I've filled in Mathworld's comment
form to point out that their page is incorrect.


Dave.

--
David Richerby Disgusting Laptop Goldfish (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a fish that you can put on your
lap but it'll turn your stomach!

Thanks to both David and Mike for their feedback.

My confusion occurred to me just after posting the message -- just as
I often see a Chess blunder milliseconds after making it!

Oh well! Sometimes our mistakes can also be instructive and valuable!

--
David Brett Richardson
http://www.100bestwebsites.org/
"The 100 finest sites on the Web, all in one place!"
Widely-watched non-profit ranking of top Internet sites

Berkeley Brett wrote:

Assuming that is a reasonable estimate, this number is far, far
smaller than 10^(120)!!

So ... you're not computing the same number. Did you check out
the reference to Peterson 1966 to see what he was referring to?

The number of different chess positions is generally stated
to be on the order of 2*10^43 (no promoted pieces), or the order of
10^50 (promoted pieces), or 10^?? (including promoted pieces,
castling state, e.p. state and 50-move clock state.)
They are, of course, approximations.

The number that Peterson mentioned was the number of
different positions in all games of a length of 40 moves. That
is not clearly one of the numbers above. (The number is just
mentioned, without any source reference or indication of how
it was computed.)

--
Anders Thulin anders*thulin.name http://www.anders.thulin.name/

On Tue, 27 Nov 2007 06:55:49 -0800 (PST), Berkeley Brett
wrote:

I've written a note about the number of chess games at:
http://members.iinet.net.au/~ray/Chessgames.htm

www.iinet.com.au/~ray

Although this is a degenerate example, it is correct: the number of
possible chess *games* is infinite, as is easily demonstrated by one
of many possible examples. Consider the sequence

1. Nf3 Nf6
2. Ng1 Ng8

Now repeat this sequence any arbitrary number of times. Though the
number of positions generated is just a few, the number of *games*
possible is as many as you wish, even though the games are not exactly
thrillers.

A draw can be claimed by repetition or the 50 move rule under this
scenario, but that is an option, not a requirement, as I understand
the rules (otherwise my example is incorrect).

wrote:
Although this is a degenerate example, it is correct: the number of
possible chess *games* is infinite [...] A draw can be claimed by
repetition or the 50 move rule under this scenario, but that is an
option, not a requirement, as I understand the rules (otherwise my
example is incorrect).

You are absolutely correct that the number of possible chess games is
infinite because draws by repetition or the fifty-move rule have to be
claimed and are not automatic.

In order to generate a non-trivial problem, one supposes that either
player will claim a draw as soon as he has the opportunity. One then
asks how many of these `interesting' games there are.


Dave.

--
David Richerby Hilarious Projector (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ 16mm film projector but it's a bundle
of laughs!