Optimal Strategy for Connect 4

ELI5 / TLDR

Someone figured out how to play perfect Connect 4 using a recipe book instead of a supercomputer. Instead of searching millions of positions mid-game, they compressed the entire winning strategy into about 10,000 patterns that fit in 150 kilobytes — smaller than a low-res photo. The trick: every possible endgame position turns out to contain a simple tactical pattern that can be described in a tiny custom language, so the computer just looks up what to do instead of thinking.

The Full Story

The Old Way: Brute Force Everything

Connect 4 was “solved” back in 1988 by Victor Allis — meaning someone proved that the first player (Red) can always win with perfect play. But “solved” and “understood” are different things. Allis’s solution needed around 500,000 nodes. John Tromp’s Fhourstones and Pascal Pons’s solvers take the search approach: given any board position, crunch through a tree of future moves until you find the right one. It works, but it’s like answering “what’s 2+2?” by counting every number from zero.

The New Way: A Phrasebook for Endgames

WeakC4 flips the approach. Instead of searching during play, it pre-computes an opening tree — about 10,000 nodes total, roughly two-thirds of which are leaves. Each leaf node is an endgame position that contains what the author calls a “steady state”: a simple tactical pattern expressible in a custom language.

Think of it like chess opening theory taken to its logical extreme. You memorize the first several moves from a book, and when the book runs out, every position you could possibly land in has an obvious, mechanical continuation. No thinking required from that point forward.

The Steady State Language

The language itself is elegant. It annotates board diagrams with a priority list of symbols telling Red exactly what to do:

Win if you can (obviously)
Block if your opponent can win (also obviously)
Play on ! — urgent squares that must be claimed now
Play on @ — miai squares, but only if exactly one is available (miai is a Go term: two equally good options where you only need one)
Play on | or blanks — these exploit “claimeven” and “claimodd,” the foundational insight from Allis

The claimeven idea is the backbone. Imagine a column with an odd number of empty spaces. If Red simply mirrors whatever Yellow does in that column, Red ends up owning the even rows. Since gravity means pieces stack from the bottom, controlling even rows in the right columns lets you set up forced wins your opponent can’t prevent. It’s like always taking the escalator while your opponent takes the stairs — you end up on the floors that matter.

How They Built It

Finding these steady states wasn’t done by hand. The project used genetic algorithms to guess candidate patterns, then verified each one by brute-force checking that it actually works against all possible opponent responses. A depth-limited search (about 8 moves ahead) optimized which branches of the opening tree to keep.

The visualization is striking too — a force-directed 3D graph where the opening tree’s structure becomes visible, with mirror symmetry (since Connect 4 is symmetric about the center column) guiding the layout. Community players helped prune nodes, testing whether human-readable patterns held up.

The Numbers

The full solution compresses to roughly 150 kilobytes. Move selection runs in O(wh) time — that’s O(42) for the standard 7x6 board, which is essentially instant. The author reports it’s faster than Fhourstones’ direct solving on the same machine, which is notable since Fhourstones is already considered fast.

The Deeper Point

The most interesting claim is philosophical. The author argues this solution represents “multi-resolutional understanding” — endgames resolve into simple tactical patterns, but the opening tree reveals emergent macrostructures that start looking like named variations (similar to chess openings). The compression from 500,000 nodes to 10,000 isn’t just an engineering win. It suggests that Connect 4, despite being a “toy” game, has genuine strategic structure at multiple levels — not just a giant lookup table, but something closer to understanding.

Claude’s Take

This is genuinely impressive work. Compressing a solved game’s strategy by roughly 50x while making it faster to execute is a rare combination — usually you trade space for time or vice versa. The fact that every reachable endgame contains a describable tactical pattern is a real insight, not just a computational stunt.

The claimeven/claimodd foundation is the kind of idea that makes you slap your forehead. Gravity in Connect 4 means parity matters enormously, and once you see it, you can’t unsee it. The steady state language built on top of it is a clean piece of design.

The philosophical framing about “multi-resolutional understanding” is a bit grandiose for a Connect 4 project, but the underlying point is sound: the difference between solving a game and understanding it is real, and compression is one way to measure understanding. A 150KB strategy that a human could theoretically follow is qualitatively different from a terabyte database.

Score: 8/10. Strong technical work with a genuine conceptual contribution. Loses points only because it’s a solved game (the hard theoretical work was done decades ago) and the writing occasionally oversells the philosophical implications. But as an example of finding structure in combinatorial objects, it’s excellent.