From: Jim choate <ravage@bga.com>
Date: Mon, 4 Apr 94 07:44:49 PDT
To: collins@newton.apple.com (Scott Collins)
Subject: Re: How Many Games of Chess?
In-Reply-To: <9404012052.AA04563@newton.apple.com>
Message-ID: <199404041444.AA13205@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text


> 
>   >This is tangentially related to crypto.  I've been reading A.K. Dewdney's
>   >_The New Turning Omnibus_ recently to refresh my memory of all that stuff
>   >I learned in undergrad that I'm going to see again on the Comp Sci GRE
>   >shortly. :-)  Anyway, 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.
> 
> First, I think there are a finite number of games only if all stale-mates
> are are required to terminate.
> 
> Second, here's one way if `just walking the tree` is too boring for you:
> 
>   0 - Start your computer on this while you hop in a starship and circle in
> local space at a significant fraction of C.
> 
>   1 - Generate every legitimate board position (don't forget, pawns may be
> promoted to other pieces) without regard for playing games.  A board
> position might be expressed as a 64 digit, base 13 number.  More efficient
> representation is probable (and desirable).  Plainly the number of board
> positions is something vastly smaller than 13^64 which is 1.96e71 or
> 
>   196053476430761073330659
>   760423566015424403280004
>   115787589590963842248961
> 
> At this time, use two extra bits per state to note the mate condition.
> 
> Additionally, the total number of games must be less than or equal to the
> total number of permutations of every possible board position.  Thus the
> total number of possible chess games is something (again vastly) less than
> (13^64)! (i.e., factorial --- sorry, Mathematica found this a little too
> daunting to give me an estimate).
> 
>   2 - Connect nodes with edges representing possible moves.  For each
> position, there can be no more than 64 pieces that might move, and for
> each, no more than 63 possible results (including pawn promotion), so the
> maximum number of edges is (13^64)*64*63 or about 7.90e74.
> 
> At this time, or slightly later, use the mate bits to indicate stale-mates.
> 
>   3 - Remove all subgraphs unreachable from the distinguished node that
> represents the starting position.
> 
>   4 - Count the number of distinct paths through the graph that end in a
> mate or a stale-mate.
> 
>   5 - Land your spaceship, collect your answer and find out how much money
> accumulated in your hedge-fund while you were gone.
> 
> 
> Scott Collins   | "That's not fair!"                         -- Sarah
>                 | "You say that so often.  I wonder what your basis
>    408.862.0540 |  for comparison is."                 -- Goblin King
> ................|....................................................
> BUSINESS.    fax:974.6094    R254(IL5-2N)    collins@newton.apple.com
> Apple Computer, Inc.  5 Infinite Loop, MS 305-2D  Cupertino, CA 95014
> .....................................................................
> PERSONAL.    408.257.1746       1024:669687       catalyst@netcom.com
> 
> 
> 
Seems to me a simpler method would be to start at the end game and work
backward. Start w/ a single piece and it has 64 positions. a game which
ends w/ 2 pieces on the board has 64*63 possible positions, 3 pieces have
64*63*62 possible positions, and so on. The fact is that the end game is what
defines a game of chess and not the infinitude of possible paths between the
first and last move.