From: collins@newton.apple.com (Scott Collins)

To: cypherpunks@toad.com

Message Hash: 8d37f7ad5d342a037a3d579d23c68d56323f6a0cdc2e5e7dfe0f0eb5436d5a5b

Message ID: <9404012052.AA04563@newton.apple.com>

Reply To: *N/A*

UTC Datetime: 1994-04-01 21:44:00 UTC

Raw Date: Fri, 1 Apr 94 13:44:00 PST

```
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
```

Return to April 1994

- Return to “collins@newton.apple.com (Scott Collins)”
Return to “Jim choate <ravage@bga.com>”

- 1994-04-01 (Fri, 1 Apr 94 13:44:00 PST) - How Many Games of Chess? -
*collins@newton.apple.com (Scott Collins)*- 1994-04-04 (Mon, 4 Apr 94 07:44:49 PDT) - Re: How Many Games of Chess? -
*Jim choate <ravage@bga.com>*

- 1994-04-04 (Mon, 4 Apr 94 07:44:49 PDT) - Re: How Many Games of Chess? -