From: solovay@math.berkeley.edu (Robert M. Solovay)

To: mmarkley@microsoft.com

Message Hash: dc3701b6c14d28f2541b2f6d9d18308952511301faeb980c6b959f827786774e

Message ID: <199404011906.LAA28894@math.berkeley.edu>

Reply To: <9404011831.AA05066@netmail2.microsoft.com>

UTC Datetime: 1994-04-01 19:07:20 UTC

Raw Date: Fri, 1 Apr 94 11:07:20 PST

```
From: solovay@math.berkeley.edu (Robert M. Solovay)
Date: Fri, 1 Apr 94 11:07:20 PST
To: mmarkley@microsoft.com
Subject: How Many Games of Chess?
In-Reply-To: <9404011831.AA05066@netmail2.microsoft.com>
Message-ID: <199404011906.LAA28894@math.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain
mmarkley@microsoft.com writes:
I seem to remember from way back in high school that the number of
potential moves by the third set of moves is on the order of billions
of legal moves.
The number of moves in a given chess position is less than 64
(number of starting squares) times 64 (number of destination squares)
x 4 [number of ways a pawn can promote]. Thus we get the bound 16, 384
[which can be easily improved] which is way less than "billions of
possible moves". The same computation shows that the number of
possible games of length n grows at worst expoentially pace mr
markley.
The right way to think about this is to get sharp upper bounds rather
than attempt a precise calculation. A crude upper bound would be
longerst possible game is about 6000 moves [using the 50 move rule].
At most 2**16 mves per position so at most 10**[192 * 10**6] games.
I'm sure that sharper estimates are readily available.
```

Return to April 1994

- Return to “Jim Gillogly <jim@rand.org>”
- Return to “Mike Markley <mmarkley@microsoft.com>”
- Return to “Shadow <swalters@freenet3.scri.fsu.edu>”
Return to “solovay@math.berkeley.edu (Robert M. Solovay)”

- 1994-04-01 (Fri, 1 Apr 94 10:30:30 PST) - Re: How Many Games of Chess? -
*Mike Markley <mmarkley@microsoft.com>*- 1994-04-01 (Fri, 1 Apr 94 10:54:31 PST) - Re: How Many Games of Chess? -
*Shadow <swalters@freenet3.scri.fsu.edu>*- 1994-04-01 (Fri, 1 Apr 94 12:07:11 PST) - Re: How Many Games of Chess? -
*Shadow <swalters@freenet3.scri.fsu.edu>*

- 1994-04-01 (Fri, 1 Apr 94 12:07:11 PST) - Re: How Many Games of Chess? -
- 1994-04-01 (Fri, 1 Apr 94 11:07:20 PST) - How Many Games of Chess? -
*solovay@math.berkeley.edu (Robert M. Solovay)*- 1994-04-01 (Fri, 1 Apr 94 11:31:28 PST) - Re: How Many Games of Chess? -
*Jim Gillogly <jim@rand.org>*

- 1994-04-01 (Fri, 1 Apr 94 11:31:28 PST) - Re: How Many Games of Chess? -

- 1994-04-01 (Fri, 1 Apr 94 10:54:31 PST) - Re: How Many Games of Chess? -