Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Longest-Chess-Game proof (5 p.)
Replies: 3   Last Post: Dec 16, 1997 5:35 AM

 Messages: [ Previous | Next ]
 Matthew van Eerde Posts: 5 Registered: 12/12/04
Longest-Chess-Game 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 50-move and repeat-position draws are
only invoked if the player wants to claim a draw.
3. The 50-move 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 triple-occurence-of-position 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" := non-pawn non-capture. (!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 h-pawns: White moves his g-pawn up to g6. Black
moves his h-pawn 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 file-pairs.
2 Pcaps/file-pair * 4 file-pairs = 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 (8-x) 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(8-x), #caps <= 30, #Pcaps = x
By the principle of inclusion and exclusion,
#big moves = #Pmoves + #caps - #Pcaps
#big moves <= (96 - 2(8-x)) + (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 small-move
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 small-move runs of size 99,
4 small-move 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.

Play-by-play: 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 h-pawns
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 99-small-move runs.
Phase 1: 4 + (4 * 99) = 400 moves.

Phase 2: White develops and abuses Black.
201. Ne4 (say) to 1350. hxg7
First, a 98-small-move run and 250. a3.
Big moves:
White moves a-, d-, f-, and g-pawns
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 99-small-move runs and one 98-small-move 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 98-small-move 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 99-small-move runs and 1 98-small-move 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 98-small-move 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 99-small-move runs and 1 98-small-move 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 98-small-move 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 99-small-move runs and 1 98-small-move 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 99-small-move runs and 4 98-small-move 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.

Date Subject Author
12/7/97 Matthew van Eerde
12/7/97 wacg@winternet.com
12/14/97 Jim Balter
12/16/97 Christian Bau