Asri-unix.1120
net.chess
utzoo!decvax!ucbvax!ARPAVAX:C70:sri-unix!YODER@USC-ECLB
Thu Apr  1 00:52:12 1982
Error in n=29 calculation
	There is a case 3c (pxP, 2 promotions):  consider the game
1. d4 d5 2. e4 e6 3. e5 Qd6 4. ed6 and now both white's advanced
d-pawn and black's e-pawn can promote without further captures.

	With an eye to preventing such errors, as well as automating
some of the hairier cases about to arise, I throw out another half-baked
idea.  Define the signature of a position to be the 8-tuple of the
signatures of its files;  define the latter to be a string of 0 or
more bits which represent the colors of the pawns, reading from white's
side of the board.  For mnemonicity it is probably wise to write the 'bits'
as w/b rather than 0/1;  the signature of the opening position is
(wb, wb, wb, wb, wb, wb, wb, wb).  The number of ways to arrange pawns
on a file to have a given signature is just C(6,k) where k is the length
of the signature.  Using this it can be shown that the number of structures
with a given (full) signature is greatest when the pawns are evenly
distributed, so is at most
	15^(n-8)*6^(16-n), 8 <= n <= 16,
	6^n, 0 <= n <= 8,
where n is the total number of pawns.

	If we define a 'situation' as a pair consisting of a signature
plus a piece decomposition for the non-pawns, then each of the events
PxP, Pxp, pxP, pxp, p promotes has a well-defined effect on
situations.  Perhaps one can prove theorems involving a formalism of
situations.  Are the following true?

1. Given a signature AND a history of generating it, the possible piece
   decompositions are determined solely by the number of promotions and
   the number of captures.

2. It is clear that any situation can be generated by a history in which
   all of the PxP transforms come at the end.  Can a similar thing be
   done to move all promotions to the end?  In order to do this one must
   allow (in general) intermediate signatures with length more than 6,
   but this doesn't matter if we are careful about what is formalism and
   about when we actually settle down to do counting.

	This approach pretty clearly needs some theorem-proving (not
surprising since it is just a less ambitious version of my first unworkable
proposal).  However one might be able to get it into a state where a
computer could use it to grind out upper bounds for the n=29, 28, and 27
cases -- the work for each new case seems to be greater by a factor of
30 to 60.

	Another possibility: pretend the board is cylindrical so as to
get extra symmetries.  This will overestimate, but probably not by much.
It might enable the computer to do the n=26 case.
-------