From: shauck@adobe.com (William R. Shauck)
Subject: Re: Chess games upperbound
Followup-To: rec.games.chess
Keywords: chess trivia
Organization: Adobe Systems, Inc.
Date: Sun, 4 Oct 1992 22:48:19 GMT

In article <1992Oct3.054232.20102@samba.oit.unc.edu>
John.Risk@bbs.oit.unc.edu (John Risk) writes:

>This somewhat follows the solvability thread.  I began to wonder how many
>games are possible.  I looked at upperbounds to compute this,
>understanding that the actual number is most certainly less.

But you then state absolutes, rather than referring to upper bounds.

>1) A game is drawn after 50 move pairs without a pawn push or a capture.

No, a game **MAY** be claimed a draw by the player on move
demonstrating that (at least) 50 moves (by each player) have elapsed
without a capture or pawn move.

>Since there are at most 96 pawn moves (6x16) and 30 captures, the maximum
>numbers of moves (not move pairs) is (50x2)(96+30)=12600 moves

No, this is AN UPPER BOUND (and not the best; why not look in the FAQ
list under "Chess Trivia"?).  A better upper bound is (2*5950) =
11900; you could have found this yourself by noticing there are 8
duplicates in your (pawn moves)/(piece captures) categories, and that
you forgot to leave the drawing interval in; the FAQ states an even
better upper bound, but the proof is too drawn out for me to type in
here; it's based on the fact that you must allow the players to do
some alternations in sequences of captures/pawn moves.

>2) The number of choices to move are K=8, Q=27, R=14, B=13, K=8, rook pawns=2,
>other pawns=3 (accounting for capturing) (Also ignoring moving 2 on first
>move, since that would reduce the number of possible pawn moves in
>paragraph 1.)   This totals 127 maximum (clearly this diminishes as pieces
>are captured, and is usually much less because of lines being blocked.)

You seem to count pawn promotion as a simple move, but imagine this
scenario: White pawn on b7; Black knights at a8 and c8; White to move.
I claim the White pawn has 12 possible moves.

You also seem to overlook that when pawns get promoted into queens, the
number of possible moves usually jumps upwards by a large amount.  So,
the maximum could be quite a bit more than 127 (imagine several queens
on each side).

>3) The upper bound of the number of possible chess games is 127**12600=
>some pretty good sized number, but finite. In round numbers that is a 1
>with 25000 zeros after it. (About the size of the national debt!) :->
>
>John

You could claim this as "an" upper bound, but certainly not "the"
upper bound (and you could only accurately make the claim after
changing your numbers).  I think attempting to pose an upper bound in
the manner you chose is problematic.

Here's info from _The Complete Chess Addict_ by Fox & James (sent to
rec.games.chess in Aug. 1990):

  "A few more large numbers.  The number of different legal positions
   on a chessboard is 2X10^43.  The number of different 40-move games
   has been estimated at 25X10^115.  This is considerably larger than
   the estimated number of electrons in the universe: 10^79."

Another posting (in Aug '90): "10^80 games was given as a reasonable
estimate." [_Verdens bedste skak_ by Jens Enevoldsen in Danish]

As you can see, these books vary widely in what they suggest as upper
bounds for the number of different games.
-- 
William R. Shauck                 Internet: shauck@mv.us.adobe.com
Adobe Systems Incorporated     uucp: ...!{decwrl|sun}!adobe!shauck
Newsgroups: rec.games.chess