What is the largest possible number of plays by White from a legal chess position?
David Wilson wrote:
What is the largest possible number of plays by White from a legal chess position?
Do you count pawn promotions as one move, or as four, since there are four options for what piece the pawn promotes to? I thought I'd doodled something at least near optimal, by getting the QBBRRNN to as many squares as possible -- until I realized that a single pawn on the 7th rank could have as many as 12 possible moves, if it can advance in-line or capture in both directions, and promote to 4 possible pieces after each. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
On 8/23/06, David Wilson <davidwwilson@comcast.net> wrote:
What is the largest possible number of plays by White from a legal chess position?
By 'legal', do you mean that the position itself offends no rules, or that it was reached as a result of a series of legal moves from the starting position?
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.
You need more approximations. Consider the situation where white has all pawns on seventh rank and black has all pawns on second rank, add a few other pieces.... Helger On Wed, 23 Aug 2006, David Wilson wrote:
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
highly illegal! R. On Wed, 23 Aug 2006, Helger Lipmaa wrote:
You need more approximations. Consider the situation where white has all pawns on seventh rank and black has all pawns on second rank, add a few other pieces....
Helger
On Wed, 23 Aug 2006, David Wilson wrote:
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
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
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
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
75? I doubt that. Martin Gardner (sixth book): If eight chess pieces of one color are placed on the board as shown in Figure 39, a total of exactly 100 different moves call be made. According to T. R. Dawson, the E~lglish chess problemist, this question was first asked in 1838 by a German chess expert, h1. Bezzel. His solution, the one shown here, was publishecl the follo\ving year. In 1899 E. Lantfau, in Der Schclchfreutzd, September, 1899, proved that 100 inoves is the maximum and that Bezzel's solution is uniclue except for the trivial fact that the rook, ~,n the seventh square of the fourth row fro111 the top, could just as well be place<]. on the first square of that same row. I managed to add pawns to get up to 139 moves. .nnbbrr. PPPPPPPP ...N.... ......R. ...BBN.. .Q...... ...K...k ..R..... Ed Pegg Jr. Joshua Zucker <joshua.zucker@gmail.com> wrote: 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.
The Chess Curiosities site doesn't claim that 75 is the most possible, but rather that it's the most in any recorded actual position from a "serious and actual tournament game" between humans. --Joshua On 8/23/06, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
75? I doubt that.
Martin Gardner (sixth book): If eight chess pieces of one color are placed on the board as shown in Figure 39, a total of exactly 100 different moves call be made. According to T. R. Dawson, the E~lglish chess problemist, this question was first asked in 1838 by a German chess expert, h1. Bezzel. His solution, the one shown here, was publishecl the follo\ving year. In 1899 E. Lantfau, in Der Schclchfreutzd, September, 1899, proved that 100 inoves is the maximum and that Bezzel's solution is uniclue except for the trivial fact that the rook, ~,n the seventh square of the fourth row fro111 the top, could just as well be place<]. on the first square of that same row.
I managed to add pawns to get up to 139 moves.
.nnbbrr. PPPPPPPP ...N.... ......R. ...BBN.. .Q...... ...K...k ..R.....
Ed Pegg Jr.
Joshua Zucker <joshua.zucker@gmail.com> wrote: 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
At 04:33 PM 8/23/2006, David Wilson wrote:
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.
A note about a related problem. In the generation of optimal-play endgame tablebases, they assumed that no forced win would take more than 255 moves. Well, a few months ago they found one that took (I think) 312 moves.
Hi Jud and all, a 262 move endgame was apparently discovered about 4 years ago: http://www.chessbase.com/newsdetail.asp?newsid=239 But the longest forced win section at http://en.wikipedia.org/wiki/Endgame disagrees: it says that it was only last October that a 292 move endgame was announced, breaking an old record of 243 moves. But in May there was a 517 move endgame win discovered! One announcement of that is at http://216.25.93.108/forum/viewtopic.php?t=2860 and it's also mentioned in the wikipedia article. --Joshua Zucker On 8/23/06, Jud McCranie <j.mccranie@adelphia.net> wrote:
At 04:33 PM 8/23/2006, David Wilson wrote:
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.
A note about a related problem. In the generation of optimal-play endgame tablebases, they assumed that no forced win would take more than 255 moves. Well, a few months ago they found one that took (I think) 312 moves.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 8/23/06, David Wilson <davidwwilson@comcast.net> wrote:
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. <snip>
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.
It's clearly feasible to have three such pawns, which exhausts the byte. -- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
Oops! I was multiplying, not adding. Never mind! On 8/23/06, Mike Stay <mike@math.ucr.edu> wrote:
On 8/23/06, David Wilson <davidwwilson@comcast.net> wrote:
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. <snip>
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.
It's clearly feasible to have three such pawns, which exhausts the byte. -- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
At 04:33 PM 8/23/2006, David Wilson wrote:
The problem is to find a legal chess position with the maximal number of possible plays for White.
Using a modification of 8 queens problem by adding a 9th queen plus the two kings and two other pieces I get 197, but I can already see a better solution.
At 08:04 PM 8/23/2006, Jud McCranie wrote:
At 04:33 PM 8/23/2006, David Wilson wrote:
The problem is to find a legal chess position with the maximal number of possible plays for White.
Using a modification of 8 queens problem by adding a 9th queen plus the two kings and two other pieces I get 197, but I can already see a better solution.
I get 201 with this position, but it isn't optimal 201 _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ Q _ _ _ _ _ Q _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ K _ _ _ Q _ _ _ _ R _ _ _ _ Q _ k B _ Q _ _ _ _
At 04:33 PM 8/23/2006, David Wilson wrote:
The problem is to find a legal chess position with the maximal number of possible plays for White.
Here's a position with 206 moves, and I believe that it can arrive legally from the starting position. 206 3 169 17 11 6 B R _ _ _ _ _ Q _ _ _ Q _ _ _ _ Q _ _ _ _ _ Q _ B _ Q _ _ _ _ _ K _ _ _ _ Q _ _ _ Q _ _ _ _ _ _ _ N _ _ _ _ Q _ k N _ _ Q _ _ R
At 07:59 AM 8/23/2006, David Wilson wrote:
What is the largest possible number of plays by White from a legal chess position?
As a test, I checked the solutions of the 8-queens problem to see what the maximum moves there would be, since the queens don't block each other. The max there is 188 moves. Of course that isn't a compete position.
At 07:59 AM 8/23/2006, you wrote:
What is the largest possible number of plays by White from a legal chess position?
Someone on rec,games.chess.misc googled and found this one, said to have 218 moves for white http://www.chessup.net/result.php?fen=3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1B...
Hello math-fun members, A simple question: P is a polynomial in x + a polynomial in 1/x. For example, P=2/x^2 + 5x + 7 + 3/x^5, expecting 5x+12. What command (in Maple 7) will replace the x's from the denominator by 1 ? The following is rather cumbersome: for n from 1 to 5 do P:=subs(1/x^n=1,P) od; Thanks, Emeric
hello, I think this could work. You may use the command <map> to have the help type : ?map simon plouffe
P is a polynomial in x + a polynomial in 1/x. For example, P=2/x^2 + 5x + 7 + 3/x^5, expecting 5x+12. What command (in Maple 7) will replace the x's from the denominator by 1 ?
algsubs(1/x=1,P); 12 + 5 x I didn't test that in Maple 7 though. Alec Mihailovs
Someone on rec,games.chess.misc googled and found this one, said to have 218 moves for white
This says that 218 is the best known, and cites Dickens 1968, but no details of the reference are given. http://www.drb.insel.de/~heiner/Chess/README_LONG
participants (14)
-
Alec Mihailovs -
David Wilson -
Ed Pegg Jr -
Emeric Deutsch -
franktaw＠netscape.net -
Fred lunnon -
Helger Lipmaa -
Joshua Zucker -
Jud McCranie -
Michael Kleber -
Mike Speciner -
Mike Stay -
Richard Guy -
Simon Plouffe