From: collins@newton.apple.com (Scott Collins)
Date: Fri, 1 Apr 94 13:44:00 PST
To: cypherpunks@toad.com
Subject: How Many Games of Chess?
Message-ID: <9404012052.AA04563@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


  >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