-----Original Message----- From: math-fun-bounces+andy.latto=pobox.com@mailman.xmission.com [mailto:math-fun-bounces+andy.latto=pobox.com@mailman.xmission.com]On Behalf Of David Wilson Sent: Wednesday, August 23, 2006 4:33 PM To: math-fun Subject: Re: [math-fun] Chess problem
The problem is to find a legal chess position with the maximal number of possible plays for White.
The problem arose in trying to determine whether a two-computer chess program could be played where the computers transmitted one 8-bit byte per move. The best encoding for moves seems to be to order all possible moves canonically (say lexically on start and destination square) and send the index of the move. If some position admits more than 256 possible moves, this scheme, and presumably the whole idea, fails.
The idea can be patched in any number of ways, though. Reserve the byte value 255 to mean "I want to make a move that isn't in the first 255 possible moves from this position; I will transmit a second byte (and a third, in the almost certainly impossible situation that there are more than 511 moves from a single position) to further detail my move". If the protocol requires that the two computers alternate sending bytes for some reason, the special 255 byte can be conventionally replied to with a 0 byte, meaning "No move yet: continue specifying your move".