62 ( +1 | -1 )
On what move does the latest possible stalemate occur, when both players cooperate?
In problems like the above one, it is understood that the 50 move rule is applied automatically, i.e. without one of the players having to claim the draw. Thus the rule is NOT:
The game may be drawn if each player has made the last 50 consecutive moves without the movement of any pawn and without the capture of any piece.
Instead it is:
The game IS AUTOMATICALLY drawn if each player has made the last 50 consecutive moves without the movement of any pawn and without the capture of any piece.
Otherwise the puzzle would have no answer.
5 ( +1 | -1 )
i don't think
i don't think that's a problem that can be solved
93 ( +1 | -1 )
a math Ph.D. should be able to solve this! Theoretically, since there are 16 pawns and each pawn may move 6 times, then one would expect approximately 16*6*50 = 4800 moves due to pawns. In addition, there are 30 captures to be made, so 30*50 = 1500 moves attributed to captures, or 6350 possible moves total, including the initial 50. However, in order to stalemate, a side would need at least one piece. Therefore, 50 moves must be removed to account for one less capture. In addition, a pawn, in order to promote, must have the opposing pawn captured or make a capture. For a position to be reached in which all 16 pawns could promote, we would need at least 8 pawn captures to occur, so we remove 8*50 or 400 moves. So I would assume that the longest possible game ending in stalemate would last for 5900 moves.
If I have made any error in the above, feel free to correct me.
111 ( +1 | -1 )
Sub-games, a possible problem
While I don't really want to work out the statical possibilities of different combinations of pieces, the problem can be thought of in terms of sub-games (a portion of the board that does not affect the rest of the board, certain types of manoeuvres that do not affect the state of the position or other manoeuvres taking place on another portion of the board). The subgames can be sequenced to allow for a continuous game, without drawing by the 50-move rule, by 3-fold repitition or by stalemate.
I understand I'm probably thinking in the wrong direction but I can't help but wonder if the 3-fold repitition rule forces a capture or pawn move prior to one of the 50-move cycles. This could be for a number of reasons, a shortage of viable sub-games from which to draw moves, a manoeuvre sub-game that does not complete prior to the cycle (thus the piece making the manoeuvre starts the new cycle half-way through a manoeuvre, which may not be a good thing) .
I vaguely recall reading about sub-games in game theory a long time ago. It was a paper on solving pawn play in the endgame by applying set theory and game theory.
58 ( +1 | -1 )
..the subgame aspect, if I remember correctly, was applied to a problem of forced endgames (or endgames featuring, proven, "best play"). This would leave me to suspect if chess is a proven a draw, the formula to determine the length of the longest possible game would have to account for subgames which could force, by threat of 3-fold repetition, a 50-move cycle to reset prior to completion.
With both sides cooperating, the subgame problem is probably avoidable, there are clearly more possible sub-games than pawn moves and captures.
35 ( +1 | -1 )
i'd just like to point out that multiplication is used in your post where exponentation should be used. so the number would be many powers of ten larger than what you said.. but still. to get the exact # i'm still sure more positions would need to be forced searched than can be reasonably searched in the lifetime of the universe
8 ( +1 | -1 )
multiplication is correct. The question was regarding the search trees depth not its width.
1 ( +1 | -1 )
ahh yes. my mistake.
300 ( +1 | -1 )
The solution given by atrifix is almost correct, but there are a few finesses which have to be taken into account.
Both players make moves without moving Pawns and without capturing. On the 50th move Black must make a Pawn move (or a capture). This continues through the 100th, 150th etc. moves, until Black has no more useful moves.
It is clear that the Black Pawns can capture only the two White Knights, since all other White pieces are on the first row. The position of Black's Pawns will then look something like this:
Pawns on a4, b3, d3, d4, e3, e4, g3, h4.
If the Pawn on a4 moves any further, the solution could not be optimal, since either a Pawn would have to be captured, or the obligation to avoid the 50 move rule would have to switch sides more often.
Thus so far Black has made 28 Pawn moves, two of which were captures. 1400 moves have been completed.
Fifty moves later, it is White who will have to avoid the 50 move rule taking effect; thus he will make a Pawn move (or a capture) on move 1450, 1500, etc.
White will be able to move all his Pawns to promotion, taking 48 Pawn moves, which include 6 captures. After that White will still be able to capture 1 piece, bringing his total of "50-move rule breaking" moves to 49. This way we arrive at move # 1400 + 2450 = 3850.
Now it is Black's turn again to avoid the 50 move rule. He will do that on move 3899, 3949 etc. Black has 20 Pawn moves and 13 captures (8 promoted pieces and 5 original pieces but not the Knights which are already gone), a total of 33 moves. This brings us to move 3850 + 1650 - 1 = 5499.
Now it is White's turn and his lone King can still capture 8 remaining pieces (the promoted Pawns; all other Black pieces have been captured earlier). He captures 7 of these on his move 5549, 5599 etc., until move 5849.
Now Black remains with a Queen or a Rook (with other pieces the draw would be immediate). And finally Black will stalemate White on move 5898.
Of course the last move can be stalemate, checkmate or any other move, but the game ends there. Note that this is not the very longest game, which would have occurred when White in the previous step would have taken all the promoted pieces; then the game would have lasted until White's 5899th move.
Note: I don't think the 3-fold repetition rule comes into consideration here, since from the outset both players have sufficient moves to vary; for instance, during the first 50 moves each White Knight has 34 squares at its disposal (all the squares on the 3rd through 6th row, except d6 and f6, and the squares a1, b1, g1, h1).
28 ( +1 | -1 )
The longest game ending with stalemate or checkmate, ends on Black's 5898th move.
The longest game altogether ends in a draw on White's 5899th move, when White plays any move; whether White captures on that move or not is immaterial.
76 ( +1 | -1 )
I don't understand why Black would avoid the 50 move rule on move 3899, 3949 as opposed to move 3900, 3950, etc., and why Black does not deliver a stalemate on move 5900 (presumably this could also be considered a violation of the 50 move rule even though stalemate is on the board--this was not my interpretation; however, even if so, the game should last 5899.5 moves, ending after White's 5899th). The longest game altogether, then, should end on completion of Black's 5900th move.
Note that the exact placement of the pieces and pawns is only one solution or subgame--since it doesn't matter how often the 50 move rule "switches sides", so to speak, there are a very large number of solutions.
109 ( +1 | -1 )
Normally the avoidance of the 50 move rule taking effect, is done on the 100th half-move, but when "sides are switched" it is done after only 99 half-moves. Thus if White moved a Pawn on move 3850, and it is now Black's turn to avoid the 50 move rule, he cannot do this on move 3900, since the game would have been drawn automatically before he could make the move, 50 consecutive moves without capture or pawn move having already been played by both sides.
Thus with every switching of sides a half move is lost, and it is therefore important that there are as few side switchings as possible.
The position of Black's pawns on move 1400 (or when the side switching takes place) could be different, but it must be such that White can promote all of his pawns without switching sides.
In all the above, "switching sides" means that the opposite color takes it upon themself to ensure that the 50 move rule does not take effect.
32 ( +1 | -1 )
This is my mistake: what you would want is White to begin the chain of breaking the 50-move rule on moves 51, 101, 151, etc., giving an extra half move. So the conclusion would be either Black violating the 50-move rule and stalemating White on his 5999th, or White stalemating Black on his 5999th with no violation.
43 ( +1 | -1 )
White cannot wait until move 51 to make the first capture or pawn move, since 50 moves on both sides would already have been played and the game would be drawn by the automatic application of the 50 move rule.
Since a few half-moves are lost during the game (as explained in an earlier post), the latest possible stalemate takes place on Black's 5898th move.
42 ( +1 | -1 )
Since the FIDE website is often inaccessible, I have largely deferred to Fritz for applications of the 50 move rule. Fritz does not claim a draw by 50 moves until White makes his 51st without a pawn move or a capture; apparently, given the wording of the rule, this is a minor error in the code.
So, the latest possible stalemate takes place on the 5898th move and there is a bug in Fritz.