Newsgroups: sci.math, alt.folklore.urban
Followup-To: alt.folklore.urban
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1997/12/04
Subject: Re: Chess is Dead

[obscene crossposting snecked]

bme...@bruce.cs.monash.edu.au writes:

> ... There are 32 pieces, of which 30 can be either on or off the
> board. 2^30=10^9 When all pieces are on the board (and assuming that
> each piece can be at each position), you get 64!/48!=10^61 ways of
> arranging them.

You're mistaken: 64!/48! ~ 10^28.  But that's not important, since the
formula you should use is 64!/32! ~ 5 x 10^53.

> However, the pawns, knights, castles and rooks are interchangable

There is no chesspiece called a "castle".  The piece shaped like a
castle is called a "rook".

> (in the case of rooks not really, but then, they can't
> really be at each possible position, either).

Presumably you are talking about "bishops" here.

> That reduces the number by a factor of 8!*2!*2!*2! for each side,
> or 10^11.

> Obviously, the number of possible ways of arranging _all_ pieces is
> an upper bound for the number of ways of arranging _any set_ of
> pieces, so we get an upper limit for the number of positions as

> 2*10^9*10^61/(10^11)=2*10^59.

Heaven knows where you got the 2 from.
Repairing the formulas and arithmetic this should be
  2^30 64!/(32! 8!^2 2!^6) ~ 5 x 10^51.

But you've left out the possibility of promoting pawns to queens,
rooks, bishops, or knights.  For instance, after PxP, if two black
pawns ans one white pawn are promoted to queens, this method gives us
an upper bound of

  2^29 64! / (33! 6!^2 3! 2!^7) ~ 2 x 10^52.

But we could choose the extra piece to be any of 3 kinds on either of
2 sides, so we get more like 10^53.  Promoting the three pawns in all
possible ways makes a little over 10^54, according to a short program
I wrote.  This program also claims that we can't do better with more
promotions because they would require more captures.

We should multyply by two for which player has the move.  It may be
claimed that the possibilities of castling add another four bits to
each position.  This is considerably reduced because the future
possibility of castling is usually encoded (in the negative) in the
position of the king and rooks.  The same argument dispenses with the
possibility of capturing _en passant_.  At any rate, adding a few
factors of two is not not terribly meaningful with such gross
estimates as this.

> Compare this to the "four in a row" game....

> The difference between these games is a factor of about 10^30, or 2^100....

Comparisons of this type are not meaningful, because the number
of _possible_ positions is not well correlated with the number of
_sensible_ positions, i.e. those that might appear in competitive
play.  For instance, 98% of the positions calculated above have
exactly one capture and three promotions.  Experience suggests
that this cannot occur without cooperation between the players.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil