A New Record in Extremal Chess Composition

Extremal Chess

Extremal combinatorics asks how far you can push something before it breaks. How many friendships can a group of people have before some three of them are all friends with each other? How many numbers can you pick from 1 to 1,000 before three of them are evenly spaced? The objects that sit right at the edge are called extremal constructions.

We have pointed Maxwell at problems like these in graph theory before. Chess is a beast of its own, and composers have been setting records in it for over a century. This time we chose one of them: a position in which every legal move gives check, with as many legal moves as possible.[2]

63 Checks

White to move. Each of White's 63 legal moves gives check, and 23 of them are mate. Position on Lichess · the 190-ply game

Searching for the Position

Finding the position and finding a game that reaches it are intertwined. Searching over all positions would be pointless, because most of them are blatantly illegal:

So Maxwell prunes as it searches.

Further filters reconstruct the history of the pawns. Pawns are predictable: they only move forward, and they change file only when they capture. For each candidate position, Maxwell checks that at least one history makes sense: some way of assigning pawns to starting files, with captures and promotions that add up. Three examples of positions with no such history:

With these filters in place, only one placement of the kings can still reach 63: Black on c6, White on d3.

Reverse-Engineering the Game

With a likely position in hand, Maxwell has to find an actual game that ends there. Off-the-shelf proof-game solvers such as Texel get stuck on crowded positions like this one: they estimate how many moves remain by assuming pieces never get in each other's way. So Maxwell combines high-level planning with backtracking search. It first decides which captures and promotions the game must contain, and roughly when. The search then only has to fill in the moves between those milestones.

The position makes strict demands:

• White still has all 16 men, so Black never captured anything.
• White has 6 queens but only 3 pawns, so 5 White pawns promoted.
• Black has 3 queens, two of them promoted on c1 and g1 without a single capture, and has lost its b-, d-, e-, f- and h-pawns. White's five captures must account for all of them.

White's five captures each do more than one job:

• axb4 removes Black's b-pawn and frees the a-file for Black's a-pawn.
• cxd5 removes the d-pawn, opens the c-file so Black's c-pawn can run to c1, and doubles White's pawns on the d-file so both can promote on d8.
• gxh5 does the same on the other wing: it removes the h-pawn, opens the g-file for Black's g-pawn, and doubles White's pawns on the h-file so both can promote on h8.
• Nxe5 and Nxf5: a knight eats the e- and f-pawns.

Maxwell wrote this plan out as the first 17 moves:

1.a3 b5 2.c4 b4 3.axb4 d5 4.cxd5 h5 5.g4 e5 6.gxh5 f5 7.Nf3 c5 8.Nxe5 c4 9.Nf3 g5 10.Nd4 c3 11.Nxf5 g4 12.d3 c2 13.Bd2 g3 14.Bc3 g2 15.e4 g1=Q 16.Nd2 Qg4 17.Be2 c1=Q

Backtracking search, guided by the plan, then fills in the remaining 160 or so plies, walking five new queens and Black's pieces into place. Full game on Lichess

Proving 64 Is Impossible

We prove the impossibility using SAT certificates. The idea is to turn the question into a giant logic puzzle, whose variables are yes/no questions:

• Is there a white queen on f3?
• Is a1 empty?
• Can the piece on f4 move to f6?

The rules of chess become conditions linking them:

• If there is a bishop on f3, then f3 is not empty.
• If there is a rook on f4 and f5 is empty, then the rook can reach f6.

On top of the rules goes the goal, "at least 64 legal moves, all of them checks", which needs many more conditions, since the solver has to count. A SAT solver then searches for an assignment satisfying all of them. We split the problem into 7,224 cases, by the squares of the two kings and whether White is in check. Every case is unsatisfiable.

For each case the solver produced an LRAT proof, which was verified by independent proof checkers. Together the proofs come to about 5 TB and took 126 core-hours to produce.

[1] Per the one-mover records register (Einzügerrekorde), maintained by Max Witte.

[2] The position must be reachable: an actual legal game from the starting position has to end there. A promotion counts as four moves, one per piece, as is standard.