From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Tue, 5 Apr 94 19:25:20 PDT
To: cypherpunks@toad.com
Subject: CHESS: max # of games
Message-ID: <9404060224.AA03414@growler.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Chesspunks,

Since this thread won't seem to die, I thought I might (hopefully)
present an argument that will convince you who are interested that
there are a finite number of chess games.

A chess game may end by checkmate, resignation, statemate, or draw.
The draw category is important: it can be agreed or forced.

Draws are forced when:

* the same position repeats three times.

  This is commonly used to end games by "perpetual check".

* 50 moves pass and no pawn is moved, or piece captured

  I've never seen this invoked, but it could happen if say one player
  doesn't have enough material to checkmate the other.  E.g. white has
  a king and black has a king and bishop.  Checkmate is impossible so
  the game will eventually end.  Or the players could be smart enough
  to realize no win is possible and draw the game right there.

So, there are a finite number of moves in a game.  In fact, the
following is excerpted from the FAQ for rec.games.chess:

> How long is the longest possible chess game?

> The basic idea is a player may claim a draw if fifty moves elapse without a
> capture or a pawn advance.  Ignoring the special cases where more than 50
> moves are allowed by the rules, the answer is after Black's 5948th move,
> White is able to claim a draw.  The simple calculation is (<Pawn_moves> +
> <Captures> - <Duplicates> + <Drawing_interval_grace_period>) *
> <Drawing_interval>, or (16*6 + 30 - 8 + 1) * 50 = 5950; we're able to trim
> two moves from this total by observing that sequences of Captures/Pawn_moves
> must have (at least) 4 alternations between the two players.

Now, as an EXTREMELY LOOSE upper bound on the number of positions
possible, allowing illegal positions, not differentiating between the
various pieces, etc.... chessboards have 64 squares, white has 16
pieces and black has 16 pieces.  There are 64!/32! ways to place the
pieces (1st piece gets 64 choices, 2nd gets 63, on down to the last
which gets 33 choices).  64!/32! = 4.8222 10^53.  (Right?  No
combinations or permutations here).

Again, this allows ALL positions, even illegal positions and position
which are othewise impossible.

So I calculate the ABSOLUTE maximum number of games to be

(4.8222 10^53) ^ 5048 = 1.0516 10^270993

I don't see how it is possible under the rules to have more; indeed
the true number is FAR less.

While this number is pretty big, it is less than infinity.

And send followup questions to me and not the list.

Karl Barrus
<klbarrus@owlnet.rice.edu>

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLaIdN4OA7OpLWtYzAQFNawQAsemEdO6pQlbwDhiNboNp5pR2Xs54bfCe
TCECI70wwtLToaQU76KSz0pRcZLrrkbOX9R4AfJlEWBF7Ae+TVs495xx8QzMHADs
KgHej8Y7BIncTrUcE9Y76yH299tHEyB/5yJW+/mNB+8XYRivLpdpxZ+udXwcpeZX
wo/AzrmkJvU=
=T5rF
-----END PGP SIGNATURE-----