Except for a queen, no piece can have more than 14 possible moves (unobstructed rook). A queen can have up to 27 moves. Leaving blocking aside, that means the maximum moves will come with 9 queens on the board (9 queened pawns), not with pawns capturing and moving to the eighth rank. For other pieces, the maximums are 14 for rooks, 13 for bishops, and 8 for knights and kings. Castling will block more rook moves than it makes possible. So an upper bound is 9*27 + 2*14 + 2*13 + 3*8 = 321. The actual maximum will be less than this; so 256 may or may not enough. Realistically, when a player gets 2 queens on the board, it usually doesn't last long. This would give a bound of 2*27 + 2*14 + 2*13 + 3*8 + 7*12 = 216. So, even more than 256 is theoretically possible, it is extremely unlikely to happen in practice. Franklin T. Adams-Watters -----Original Message----- From: David Wilson <davidwwilson@comcast.net> 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. Regarding the reachability of the position, optimally we would like the position to be reachable from the start position. However, I realize that determining this is somewhat painful, so I will settle for reasonable approximations, e.g: - The set of pieces on each side should be consistent with a legal game, (e.g, at most 9 queens per side). - Pawns should not occupy the first or eighth rank. - At most one king should be in check (though White's king being in check seems improbable anyway). - The colors of bishops should be consistent with a legal game. Regarding pending pawn promotions, each promotion counts as a distinct move, so yes, an unblocked seventh-rank pawn with two possible captures yields 12 possible moves. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun