My friend Jeff Sonas, of http://www.chessmetrics.com among other things, tells me: I don't think I've ever seen something about the most possible moves. Tim Krabbe's "Chess Curiosities" site is fascinating if you haven't seen it; he says the most in any known position was 75. http://www.xs4all.nl/~timkr/records/records.htm#Most%20possible%20moves http://www.xs4all.nl/~timkr/chess/chess.html --Joshua Zucker On 8/23/06, Mike Speciner <speciner@ll.mit.edu> wrote:
Yes, but as you add more queens to the board, they are forced away from the optimal squares and/or block each other. For example, if the first queen has 27 moves, the next can have only 25. If we look at solutions to the 8 queens problem, the total number of moves for the 8 queens is no more than 182. For the 182 case I looked at, we can add a ninth queen, but net only 10 additional moves. Each additional piece seems to net at most a few additional moves.
There is also the constraint that the black king can't already be in check. This only subtracts a few moves if it's in the corner surrounded by three black pieces.
At this point, if I had to guess, I'd say 8 bits was enough.
But it's certainly easy enough to encode all the moves with a 9-bit byte: four bits to identify the piece and 5 bits to specify its motion. I miss 36-bit machines!
--ms
franktaw@netscape.net wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun