Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



LongestChessGame proof (5 p.)
Posted:
Dec 7, 1997 8:43 PM


This is my lengthy attemptedly rigorous proof (?) of the exact depth of Chess. I would appreciate any criticism anyone would care to give about details, spirit, style, correctness, relevance (keeping in mind that this is about as irrelevant, worldly speaking, as it is possible to get,) possible improvements, futility, etc. This proof generalizes easily (?) to any starting position. Matthew van Eerde
Claim: The complete chess tree is exactly 11796 levels deep.
In other words, there is a legal (but silly) chess game with 11796 moves, 5898 by each player, and no legal game has more, unless a player misses a draw claim.
Proof: Assumptions (4): 1. Players will cooperate to create a long game. The longest one player can force a game to be against his opponent's efforts is a different, much harder, problem. 2. Even so, each player will claim a draw if possible. Otherwise, infinite play is possible. Consider the trivial game: 1. Nf3 Nf6 2. Ng1 Ng8 3. Nf3 Nf6 4. Ng1 Ng8 5. Nf3 ÃÂÃÂ note: the 50move and repeatposition draws are only invoked if the player wants to claim a draw. 3. The 50move rule is in effect. US Chess Federation Official Rules of Chess 14F1: "The game is drawn when the player on the move claims a draw and demonstrates that the last 50 consecutive moves have been made by each side without any capture or pawn moveÃÂÃÂ"
4. The tripleoccurenceofposition rule is in effect. USCF Official Rules of Chess 14C: "The game is drawn upon a claim by the player on the move when the same position is about to appear for at least the third time or has just appeared for at least the third time, the same player being on the move each time. In both cases, the position is considered the same if pieces of the same kind and color occupy the same squares and if the possible moves of all the pieces are the same, including the right to castle or to capture en passant."
Definitions (5): 1. "Pmove" := move by a pawn, whether capturing or not. 2. "cap" := capture, whether by a pawn or not. 3. "Pcap" := capture by a pawn. (Pmove && cap.) 4. "big move" := Pmove or cap or Pcap. (Pmove  cap.) 5. "small move" := nonpawn noncapture. (!big move.)
Lemmas (3):
Lemma 1. If 100 consecutive small moves occur the game ends. Proof: Assumptions 2 and 3. Corollary 1: If two consecutive big moves in a game (possibly with small moves in between) are made by the same player, the number of small moves between them is an odd number <= 99. Corollary 2: If two consecutive big moves in a game (possibly with small moves in between) are made by different players, the number of small moves between them is an even number <= 98.
Lemma 2a. To promote all 16 pawns, >= 8 Pcaps are necessary. Proof: there are eight files. One or the other of the pawns on this file at the start of the game needs to get out of the way. This can only be accomplished by a Pcap. 1 Pcap/file * 8 files = 8 Pcaps Lemma 2b. To promote all 16 pawns, 8 Pcaps are sufficient. Proof: consider the following series of moves by the 4 g and hpawns: White moves his gpawn up to g6. Black moves his hpawn down to h3. White Pcaps a Black piece on h7: gxh7. Black Pcaps a White piece on g2: hxg2. White now has a pawn on h7 and a pawn on h2. Black has a pawn on g7 and one on g2. All four can promote freely. Repeat on other 4 filepairs. 2 Pcaps/filepair * 4 filepairs = 8 Pcaps. Lemma 2c. At most 30 caps can occur. Proof: there are 32 pieces. Kings cannot be captured. Lemma 2d. At most 96 Pmoves can occur. Proof: there are 16 pawns. Each can move at most six times before it promotes and becomes a piece. 16 * 6 = 96. Lemma 2. No more than 118 big moves can occur in any game. Proof: Suppose a game has more than 8 Pcaps. In this game, #Pmoves <= 96, #caps <= 30, #Pcaps = x > 8 By the principle of inclusion and exclusion, #big moves = #Pmoves + #caps  #Pcaps #big moves < 96 + 30  8 = 118.
Suppose, on the other hand, a game has x <= 8 Pcaps. At least (8x) of the 8 files must have the property that neither pawn starting on that file executed a Pcap. These two pawns can together make a maximum of 10 moves, (if one of them is captured by a piece after moving 4 times,) which is 2 less than the 12 they could have made had one of them executed a Pcap. In this game, #Pmoves <= 96  2(8x), #caps <= 30, #Pcaps = x By the principle of inclusion and exclusion, #big moves = #Pmoves + #caps  #Pcaps #big moves <= (96  2(8x)) + (30)  (x) #big moves <= 96  16 + 2x + 30  x = 110 + x. Since x <= 8, #big moves <= 118. Corollary: The maximum number of big moves, 118, can occur only if exactly 96 Pmoves, exactly 30 caps, and exactly 8 Pcaps can occur.
Lemma 3. At most moves 11796 moves, 5898 by each player, can occur in any legal game with no missed draw claims. Proof: If the same player could make all the big moves, the game would look like 99 small moves, big move, 99 small moves, big move, etc. for a theoretical maximum of 118 + (118 * 99) = 11800 moves. Unfortunately, this is impossible. Black needs to pass the big move privilege to White. Further, in order to allow: (0) Black to move his pawns; (1) White to move his pawns and get out of the way; (2) Black to get out of the way, promote, and capture; (3) White to promote and capture pieces; and (4) Black to capture promoted White pieces; the buck needs to pass not once but four times. Thus, a game can have at most 118 big moves, with 118 smallmove runs: at most 114 of size 99 and at least 4 of size 98, to allow the opposite side to start making big moves.
Theorem: A game exists with the maximal 118 big moves and the maximal 11796 moves, 5898 by each player. Proof: Existence: Game A, outlined below. Maximality: Lemmas 3 and 4
Game A Outline:
Move Classification: 96 Pmoves + 30 caps  8 Pcaps = 118 big moves, 114 smallmove runs of size 99, 4 smallmove runs of size 98: Total: 118 + (114 * 99) + (4 * 98) = 11796 moves, 5898 by each player. Even #moves implies Black makes the last move.
Game A has five phases: 1. Black develops. 2. White develops and abuses Black. 3. Black strikes back and gets reinforcements. 4. White gets reinforcements too and demolishes Black. 5. Black's king becomes Rambo.
Playbyplay: It may help to have a board in front of you.
Phase 1: Black develops. 1. Nf3 (say) to 200. ÃÂÃÂ h6 Big moves: Black moves his b, c, e, and hpawns down to b6, c6, e6, and h6. 4 Pmoves. 0 caps. 0 Pcaps. Small moves: White moves his knights out. White moves his rooks back and forth. Black moves all of his pieces. Black's king moves out in front of his pawns. Move Classification: 4 Pmoves + 0 caps  0 Pcaps = 4 big moves. 4 99smallmove runs. Phase 1: 4 + (4 * 99) = 400 moves.
Phase 2: White develops and abuses Black. 201. Ne4 (say) to 1350. hxg7 First, a 98smallmove run and 250. a3. Big moves: White moves a, d, f, and gpawns up to a6, d6, f6, and g6. 4 + 4 + 4 + 4 = 16 Pmoves. 0 caps. 0 Pcaps. White captures Black's queen and bishops with pieces. 0 Pmoves. 3 caps. 0 Pcaps. White Pcaps Black's knights and rooks on b7, c7, e7, and h7. 4 Pmoves. 4 caps. 4 Pcaps. Small moves: White's pieces move out on the board. White's king moves in front of his pawns. Move Classification: 20 Pmoves + 7 caps  4 Pcaps = 23 big moves, 22 99smallmove runs and one 98smallmove run: Phase 2: 23 + (22 * 99) + 98 = 2299 moves.
Phase 3: Black strikes back and gets reinforcements. 1350. ÃÂÃÂ Ke4 (say) to 3549. ÃÂÃÂ h1=N First, a 98smallmove run and 1399. ÃÂÃÂ bxa5. Big moves: Black Pcaps on a5, d5, e5, and h5. 4 Pmoves. 4 caps. 4 Pcaps. Black promotes all 8 pawns. 4 * (4 + 6) = 40 Pmoves. 0 caps. 0 Pcaps. Move Classification: 44 Pmoves + 4 caps  4 Pcaps = 44 big moves, 43 99smallmove runs and 1 98smallmove run: Phase 3: 44 + (43 * 99) + 98 = 4399 moves.
Phase 4: White gets reinforcements too and demolishes Black. 3550. Ng5 (say) to 5349. NxR First, a 98smallmove run and 3599. b8=N. Big moves: White promotes all 8 pawns. 4 * (1 + 6) = 28 Pmoves. 0 caps. 0 Pcaps. White captures remaining 8 Black pieces with pieces. 0 Pmoves. 8 caps. 0 Pcaps. Move Classification: 28 Pmoves + 8 caps  0 Pcaps = 36 big moves, 35 99smallmove runs and 1 98smallmove run: Phase 4: 36 + (35 * 99) + 98 = 3599 moves.
Phase 5: Black's king becomes Rambo. 5349. ÃÂÃÂ Ke4 (say) to 5898. ÃÂÃÂ KxR draw First, a 98smallmove run and 5399. ÃÂÃÂ KxN Big moves: Black king takes remaining 11 White pieces. 0 Pmoves. 11 caps. 0 Pcaps. Move Classification: 0 Pmoves + 11 caps  0 Pcaps = 11 big moves, 10 99smallmove runs and 1 98smallmove run: Phase 5: 11 + (10 * 99) + 98 = 1099 moves.
Game Over! Draw, due to lack of mating material. USCF Official Rules of Chess 14D1: King vs. king. Overall Move Classification: 96 Pmoves + 30 caps  8 Pcaps = 118 big moves, 114 99smallmove runs and 4 98smallmove runs: Total: 118 + (114 * 99) + (4 * 98) = 11796 moves By Phase: 400 + 2299 + 4399 + 3599 + 1099 = 11796 moves 11796 moves overall, 5898 by each player.
QED
Corollary 1: The longest game Black wins is the same length. White leaves Black a rook in phase 4. Black's king captures White's rook on move 5848., and 99 moves later Black mates White. 5848. ÃÂÃÂ KxR ÃÂÃÂ (99 moves) ÃÂÃÂ 5898. ÃÂÃÂ Rh4 mate. Corollary 2: The longest game White wins is one move shorter. Rather than letting Black capture the White rook on move 5898. ÃÂÃÂ KxR, White gets the drop on Black: 5898. Ra1 mate.



