From: Mike Markley <mmarkley@microsoft.com>
Date: Fri, 1 Apr 94 10:30:30 PST
To: cypherpunks@toad.com
Subject: Re: How Many Games of Chess?
Message-ID: <9404011831.AA05066@netmail2.microsoft.com>
MIME-Version: 1.0
Content-Type: text/plain


----------
| From: Lefty  <netmail!lefty@apple.com>
| To:  <cypherpunks@toad.com>
| Subject: Re: How Many Games of Chess?
| Date: Friday, April 01, 1994 9:31AM
|
| Received: from relay2.UU.NET by netmail.microsoft.com with SMTP (5.65/25-eef)
| 	id AA25823; Fri, 1 Apr 94 09:50:19 -0800
| Received: from toad.com by relay2.UU.NET with SMTP
| 	(5.61/UUNET-internet-primary) id AAwjtu01006; Fri, 1 Apr 94 12:44:37 -0500
| Received: by toad.com id AA11484; Fri, 1 Apr 94 09:33:09 PST
| Received: from colossus.apple.com by toad.com id AA11477; Fri, 1 Apr 
94 09:33:01 PST
| Received: from [90.1.0.18] by colossus.apple.com with SMTP 
(5.65/8-Oct-1993-eef)
| 	id AA17501; Fri, 1 Apr 94 09:31:21 -0800
| Received: from lefty.apple.com by gallant.apple.com with SMTP 
(5.64/27-Sep-1991-eef)
| 	id AA18102; Fri, 1 Apr 94 09:31:18 PST
| 	for cypherpunks@toad.com
| Message-Id: <9404011731.AA18102@internal.apple.com>
| Mime-Version: 1.0
| Content-Type: text/plain; charset="us-ascii"
| Sender: netmail!owner-cypherpunks@toad.com
| Precedence: bulk
|
| >This is tangentially related to crypto.  I've been reading A.K. Dewdney's
| >I was glancing through the chapters on complexity,
| >computabilty, and minimax trees, and I got to wondering something:  how
| >many possible games of chess are there?  I know that it has to be a finite
| >number, but I'm not sure how to go about finding this number.  Any
| >pointers would be appreciated.
|
| It doesn't seem to me that this _can_ be readily calculated in any
| reasonable amount of time.  It's not a simple (realtively) combinatorial
| problem: the configuration of the board at any given point limits the legal
| moves in an extremely nontrivial way.
|
| I believe I can get you as far as the second move, though: I make it to be
| twenty-one possible openings and twenty-one responses.
|
| --
| Lefty (lefty@apple.com)
| C:.M:.C:., D:.O:.D:.
|
|
|

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. I am also pretty sure that it is not exponential but a 
factoral growth. I don't think that it is possible to determine every 
possible game.

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 -