From: Mike Markley <mmarkley@microsoft.com>
To: solovay@math.berkeley.edu
Message Hash: 0cc1b15b3e8f53be244a693229e8d85312c403d5cd85442995d4ce8de646a954
Message ID: <9404011934.AA07422@netmail2.microsoft.com>
Reply To: N/A
UTC Datetime: 19940401 19:33:13 UTC
Raw Date: Fri, 1 Apr 94 11:33:13 PST
From: Mike Markley <mmarkley@microsoft.com>
Date: Fri, 1 Apr 94 11:33:13 PST
To: solovay@math.berkeley.edu
Subject: RE: How Many Games of Chess?
MessageID: <9404011934.AA07422@netmail2.microsoft.com>
MIMEVersion: 1.0
ContentType: text/plain

 From: Robert M. Solovay <netmail!solovay@math.berkeley.edu>
 To: Mike Markley
 Cc: <cypherpunks@toad.com>
 Subject: How Many Games of Chess?
 Date: Friday, April 01, 1994 11:06AM

 Received: from math.Berkeley.EDU by netmail.microsoft.com with SMTP
(5.65/25eef)
 id AA02131; Fri, 1 Apr 94 11:04:58 0800
 Received: by math.berkeley.edu (8.6.8/1.33(math)Ow)
 id LAA28894; Fri, 1 Apr 1994 11:06:45 0800
 MessageId: <199404011906.LAA28894@math.berkeley.edu>
 InReplyTo: Mike Markley's message of Fri, 1 Apr 94 10:20:55
 TZ <9404011831.AA05066@netmail2.microsoft.com>


 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.


I should have said billions of potential states for the board after
each move. If you think of the number of initial moves for the starting
player its only 16 potential positions for the pawns and 4 for the
knights. If the first player takes one of these positions then the
second player moves he has the same 20 potential moves giving an
potential state of 400 different positions after the first move. After
the second move there is on the order of greater than 160,000 potential
states for the board. After 3 moves it is greater than 2.56 * 10^10
potential states. I was thinking in terms of states rather than valid moves.
Mike.
=================
Mike Markley  The opinions here do not represent the
mmarkley@microsoft.com  opinions of my employer. Attempts to
 associate the two are pointless.
"I want to look at life, In the available light"
 Neil Peart 
Return to April 1994
Return to “Mike Markley <mmarkley@microsoft.com>”
19940401 (Fri, 1 Apr 94 11:33:13 PST)  RE: How Many Games of Chess?  Mike Markley <mmarkley@microsoft.com>