Connect Four: exact threat checks, and an exact solver to judge them¶
A Connect Four player that only looks one move ahead wins when it can and blocks when it must, and still loses to the oldest trick in the game: two threats at once. This page shows the library's grounded pattern (propose, check, then act or degrade) on Connect Four. A fast player proposes each move; four exact checks decide whether it is played; and an exact solver, which knows the true value of small boards and of endgames, judges the result.
This page is for anyone who wants to see what a gate can and cannot promise in a game where perfect play is known to exist but is too expensive to compute, and for engineers who want a template for a game with an exact oracle. You need no Connect Four knowledge beyond the rules below.
Try it in your browser
The board below plays this game's recorded example with no download; Play live runs this package itself in your browser, in Pyodide (about 7 MB, downloaded once), and the play page has every setting.
Connect Four runs here when JavaScript is on; the play page has it too, and the commands below run it in a terminal.
Run it¶
uv run grounded-decision examples games_connect4 # the report below
make watch-connect4 # greedy vs the same player gated, live
make play-connect4 # you (X) against the gated player
make audit-connect4 # greedy judged by the exact solver on 5 x 4
Other real commands:
grounded-decision play connect4 --agents you,search --guarded # the gate checks your moves
grounded-decision play connect4 --size 5x4 --agents solver,greedy --view history
grounded-decision play connect4 --size 4x4 --connect 3 # other sizes and line lengths
grounded-decision compare connect4 --agents random,greedy,gated,search
grounded-decision audit connect4 --agent greedy --size 5x4
Source: src/grounded_decision/examples/games/connect4.py (game, agents,
gate, report), connect4_rules.py (bitboard rules) and
connect4_search.py (the exact solver and the heuristic search). Tests:
tests/test_games_connect4.py.
The rules, exactly as implemented¶
| Rule | What the code does |
|---|---|
| Board | width columns of height cells, 7 x 6 by default (--size WxH, 1 to 16 a side). |
| Move | Drop a disc into a column that is not full; it lands on the lowest empty cell. |
| Win | The first player with connect discs in a row (4 by default, --connect K) across, up or diagonally wins at once. |
| Draw | A full board with no line. |
| Order | X moves first, then O. |
A human types a column as a letter (d) or a number (4), or the cell
it lands on (d3). Move descriptions read X drops in d (d3): the
column, then the landing cell (rows count from 1 at the bottom).
Representation. Each column takes height + 1 bits of a Python
integer: the cells from the bottom up, then one spare bit that is never
a cell. A position is two integers, the occupied cells and the cells of
the player to move. Dropping a disc is one addition (mask + bottom of
column carries up into the first empty cell), and a line of four in any
direction is three shifts and ANDs over the whole board; a line that
would leave the board runs into a spare bit or past the last column,
both always empty. This is the layout of John Tromp's and Pascal Pons's
solvers.
Checking the rules. Counting every sequence of moves from the empty board (a perft count) gives 7, 49, 343, 2,401, 16,807 and 117,649 for depths 1 to 6: no line and no full column can occur before the seventh disc, so every depth multiplies by 7. Tests also check lines in every direction, that no line wraps round an edge, full columns, the full-board draw, other line lengths, and that the fast "cells that would complete a line" function equals a cell-by-cell check on random positions of three board shapes.
The players¶
random- A uniformly random column.
greedy- Wins at once if it can, otherwise blocks a cell where the opponent would win at once, otherwise plays the column whose disc extends the most of its own open lines and closes the most of the opponent's (every window of four cells through the disc, weighted by how full it is); the seed chooses among columns within a point of the best. It looks one move ahead and no further, so it walks into double threats.
search- Negamax alpha-beta (a minimax search that skips branches that cannot change the result) with iterative deepening, a table of positions already scored, best-move-first ordering, and exact pruning of moves that lose at once. Positions at the end of a line are scored by winning cells (empty cells that would complete a line) for each player and by discs in the central column. It stops at a budget of 20,000 positions per move, counted rather than timed, so every run is identical.
gated- Greedy proposes; four exact checks decide; if one fails, the gate plays the search's best column among the columns that pass every check.
solver- Scores every column with the exact solver below and plays the best one (fastest win, slowest loss). When some column needs more than 300,000 positions it plays the search's column instead, and its note says "not proved".
alphabeta,expectimax,clairvoyant,noisy_greedy- Players for the regime table: three 3-ply searches that differ only in what they assume about the opponent, and a noisy greedy opponent.
What the gate checks¶
The four checks, each an exhaustive look at the next three plies (a ply is one player's move):
takes_win: if some column completes a line now, the move does.blocks_threat: if the opponent could complete a line on its next move, the move blocks that cell.not_under_threat: the move does not land directly below a cell where the opponent would complete a line (it would hand the opponent that cell).no_loss_in_two: after the move the opponent cannot force a win within its next two moves: no reply wins at once, and no reply leaves us without an answer, as a double threat does.
Each check applies only when it can be met. They are taken in order: start from the legal columns, and for each check keep the columns that pass it, unless none does, in which case the check is waived and the set is unchanged (a column that wins at once passes everything). A proposal passes all four exactly when it is in the final set. The fallback picks from that set, so it passes by construction. The tests confirm both statements, and every check, against a plain search on random positions of 7 x 6 and 5 x 4 boards.
Here is the gate at work, from
uv run grounded-decision play connect4 --agents random,gated --seed 2 --view history --style unicode --color never
(O is the gated player; ● is X and ○ is O):
┌──────────────┐ move 16 O (gated · worst-case): O drops in g (g3)
│· · · · · · · │ OVERRIDE proposed O drops in f (f1) -> played O drops in g (g3)
│· · · · · · · │ why: f lands directly under the opponent's winning cell
│· · · ● ○ · · │ ✓ takes_win no column wins at once
│● · · ○ ● · ○ │ ✓ blocks_threat no threat to block
│○ ○ · ○ ○ · ● │ ✗ not_under_threat f lands directly under the opponent's winning cell
│● ● · ○ ● · ● │ ✗ no_loss_in_two after f the opponent forces a win within two moves
└──────────────┘ note: fallback: best of the columns passing every check (a, b, c, d, e, g)
note: depth 5: evaluation +8
nodes_searched=2001
X owns d4, e3 and g1, so the empty cell f2 would complete X's
diagonal d4 e3 f2 g1. Nobody can play f2 while f1 is empty;
greedy's f1 would fill it and hand X the win. not_under_threat and
no_loss_in_two both fail, and the gate plays g3 instead. O goes on to
win at move 24.
Guarantee. Every move of the gated player wins at once when it can; otherwise it lets the opponent win on its next move only when every column does; and it lets the opponent force a win within its next two moves only when every column that avoids an immediate loss does.
What the gate does not guarantee
- Not perfect play. A win the opponent can force three or more of its moves ahead is invisible to the checks. The comparison below shows the cost: the 20,000-position search beats the gated player in most games.
- Not the best safe column. Among columns that pass, the gate plays greedy's proposal, and the fallback is a small search, not the solver.
The exact solver¶
connect4_search.Solver computes the exact score of a position: the
result with perfect play by both sides. Positive means the player to
move wins, 0 a draw, negative a loss; a win whose last disc is played
when \(m\) discs are already down scores \(\lfloor (\text{cells} + 1 - m)/2 \rfloor\),
so sooner wins score more (on 7 x 6 the scores run from −18 to 18). It
follows Pascal Pons's design (Solving Connect 4, 2017–2019),
generalised to any size and line length:
- negamax with alpha-beta pruning;
- moves that lose at once are never searched (playing under an opponent's winning cell, or anything but the block when the opponent has one playable winning cell; two such cells is a loss), which cannot change the value;
- bounds from the number of empty cells narrow the window before searching;
- moves that create more of the mover's own winning cells first, then central columns;
- a table of upper and lower bounds per position, used only as bounds;
- a binary search of narrow windows for the exact score, or a single window for win/draw/loss only (the weak solve, much cheaper).
A budget, never a guess. Given a node budget, the solver either
returns a proved value or raises SearchBudgetExceeded; it never returns
a value it has not proved.
Cross-checked by brute force. The tests compare the exact score with
an independent minimax written with plain lists (no bitboards, no
pruning, no table) on random positions of 4 x 4, 4 x 3 and four
three-in-a-row boards, plus the start positions, and check that the
solver player, as X on 4 x 4, never gives up the value of any position
it reaches against every possible reply.
Values of whole boards¶
The report solves six boards from the empty position every time it runs.
Five larger ones were solved once with board_value(width, height)
(connect4.board_value) on a development machine; they take too long
for every run:
| Board (columns x rows) | Result with perfect play | Positions searched | Time |
|---|---|---|---|
| 4 x 4 | draw | 9,420 | under 0.1 s |
| 5 x 4 | draw | 54,445 | 0.1 s |
| 4 x 5 | draw | 25,626 | under 0.1 s |
| 4 x 6 | draw | 269,180 | 0.6 s |
| 6 x 4 | second player wins | 545,586 | 1.2 s |
| 5 x 5 | draw | 664,205 | 1.5 s |
| 5 x 6 | draw | 2,743,046 | 7 s |
| 6 x 5 | draw | 3,772,782 | 10 s |
| 7 x 4 | draw | 5,067,037 | 14 s |
| 7 x 5 | draw | 43,029,962 | 2 min |
| 6 x 6 | second player wins | 150,480,331 | 7 min |
All eleven agree with John Tromp's published table of Connect Four values by board size. The tests re-solve the first six.
The standard 7 x 6 board is a first-player win: shown by James D. Allen and, independently, by Victor Allis in 1988 (Allis's thesis A Knowledge-based Approach of Connect-Four), and confirmed by John Tromp's database of all 8-ply positions. This library cites that result; it does not re-prove it. At about 350,000 positions a second, this Python solver cannot solve 7 x 6 from the start, and nothing here claims perfect play on that board.
What it can do on 7 x 6 is solve endgames. The report plays the search against itself from a seeded opening and solves every column once 20 (and 22) cells are empty:
A 7x6 endgame solved exactly (20 empty cells, X to move; seed 12):
. . O X . . .
. . O O . O .
. . X X . X .
. . O X . O .
. . X O X O X
. X O X X O O
a b c d e f g
exact score per column (positive: the mover wins; larger: sooner):
a +4 b +4 e -10 f +4 g +4
1,343 positions searched; greedy plays e (-10), gated plays b (+4)
A 7x6 endgame solved exactly (22 empty cells, X to move; seed 7):
. . O . O . .
. . X . X . .
. . X . X . .
O O X . O . .
X X O O O . .
X O X X O . .
a b c d e f g
exact score per column (positive: the mover wins; larger: sooner):
a +1 b -3 d +1 f -11 g +1
25,156 positions searched; greedy plays b (-3), gated plays b (-3)
In the first, X wins with any column but e; greedy picks e (a forced
loss), the gate rejects it and keeps the win. In the second, a, d and
g win for X; greedy's b loses, and so does the gated player, because
the loss is further away than its checks look. That is the honest limit
of a three-ply gate, measured exactly.
The report¶
From uv run grounded-decision examples games_connect4 (after the parts
shown above):
Each pairing: 6 seeded openings (2 random plies), both seats, on 7x6.
search = alpha-beta, 20,000 positions per move; gated = greedy checked by four exact threat checks.
pairing agent won drawn lost mean plies overrides nodes/move
gated vs greedy gated 8 0 4 17.8 9 114
greedy 4 0 8 17.8 0 0
gated vs random gated 12 0 0 8.3 0 0
random 0 0 12 8.3 0 0
search vs greedy search 12 0 0 15.3 0 13389
greedy 0 0 12 15.3 0 0
gated vs search gated 0 0 12 29.3 54 386
search 12 0 0 29.3 0 11439
Showcase: gated (X) vs search, seed 0; O connected 4.
First override, at disc 5 (X to move):
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . X . . .
. . O O . . X
a b c d e f g
greedy proposed: X drops in d (d3)
[pass] takes_win: no column wins at once
[pass] blocks_threat: no threat to block
[pass] not_under_threat: d does not land under an opponent's winning cell
[FAIL] no_loss_in_two: after d the opponent forces a win within two moves
the gate played: X drops in e (e1)
How to read it:
- Each pairing is 12 games: 6 openings of 2 random discs, each played once with each player as X. "Overrides" counts moves where the gate rejected greedy; "nodes/move" is the positions a player's search visited per move (greedy and random search none; the gate's checks are not counted).
- The gate fixes greedy's worst habit. Against plain greedy, the gated version wins 8 and loses 4 of 12, with 9 overrides; it never loses to random.
- The gate is not a strong player. Against the 20,000-position search it loses all 12 and is overridden 54 times: the search builds threats that are lost four or more plies before they land.
- The showcase is the classic open row: O has
c1 d1withb1ande1empty. Greedy plays the centre,d3; then O playsb1ore1and has two winning cells in the bottom row, and X can block only one. The checkno_loss_in_twofinds exactly that, and the gate blocks ate1.
A round robin from uv run grounded-decision compare connect4 --agents random,greedy,gated,search --seeds 5.
The empty board is the same for every seed, so compare plays the
first two discs of each game at random, drawn by the seed (the same two
for every seating; the openings are printed under the table): without
them the deterministic players would replay one game on every seed.
agent games won drawn lost cut points moves overrides win rate (95% interval)
search 30 28 0 2 0 28.0 15.1 0 0.93 [0.78, 0.99]
gated 30 20 0 10 0 20.0 15.6 32 0.67 [0.47, 0.83]
greedy 30 12 0 18 0 12.0 11.2 0 0.40 [0.23, 0.59]
random 30 0 0 30 0 0.0 8.2 0 0.00 [0.00, 0.12]
On 5 x 4, where the solver proves every move, from
uv run grounded-decision compare connect4 --size 5x4 --agents random,greedy,gated,search,solver --seeds 3:
agent games won drawn lost cut points moves overrides win rate (95% interval)
solver 24 18 6 0 0 21.0 14.9 0 0.75 [0.53, 0.90]
search 24 17 5 2 0 19.5 15.1 0 0.71 [0.49, 0.87]
gated 24 12 2 10 0 13.0 13.7 18 0.50 [0.29, 0.71]
greedy 24 6 1 17 0 6.5 12.3 0 0.25 [0.10, 0.47]
random 24 0 0 24 0 0.0 9.4 0 0.00 [0.00, 0.14]
5 x 4 is a draw with perfect play, so a perfect player never loses there from the empty board; the random opening discs can hand one side a won position, which is why the solver also wins most games, and it lost none of its 24. The gate turns greedy's 6 wins into 12.
The audit: judging moves against the exact solver¶
grounded-decision audit connect4 replays a game and asks an oracle
for the value of each move the audited player made and of the oracle's
own best move; the difference is the regret. The default oracle,
solver, values each column by its exact result (win 1, draw 0,
loss −1). From make audit-connect4 (greedy as X against the gated
player on 5 x 4, where every position is proved):
== Audit: greedy playing X in connect4, seed 0 ==
Line-up: X (greedy) vs O (gated). Result: O connected 4 (winner: O (gated)) after 16 moves.
Oracle: the exact solver on 5x4 (8/8 positions proved exactly). Regret unit: outcome under perfect play (win 1, draw 0, loss -1); where the solver ran out of budget, 1/-1 only for a result forced within 8 plies, else 0.
Decisions audited: 8
total regret 2, mean 0.25 per decision
agreed with the oracle: 6/8 (P(agrees with the oracle) ∈ [0.35, 0.97] (95%, 8 trials))
gate overrides: 0
Per decision (regret; * = the gate overrode the proposal):
1 0 0 1 0 0 0 0
Worst #1: move 1 (X): played X drops in e (e1) = -1; oracle prefers X drops in c (c1) = 0 (regret 1)
. . . . .
. . . . .
. . . . .
. . . . .
a b c d e
note: greedy: line score 3 (best 4; the seed chose among 5)
Worst #2: move 7 (X): played X drops in c (c2) = -1; oracle prefers X drops in d (d2) = 0 (regret 1)
. . . . .
. . . . .
. O . . .
O X O X X
a b c d e
note: greedy: line score 9 (best 9; the seed chose among 2)
Greedy's very first disc, e1 (the seed's choice among five columns
within a point of the best line score), already loses with perfect play:
the solver's c1 draws. Its fourth, c2, is the second mistake. Two of
its eight moves gave the game away.
On 7 x 6 the oracle is exact only where it can prove
For each position the oracle tries to solve every column within
60,000 positions. Where that fails (early in a 7 x 6 game), it falls
back to an 8-ply search and scores a column 1 or −1 only for a win or
loss forced within those plies, otherwise 0, meaning unknown. The
oracle's name says how many positions were proved exactly
(audit connect4 on 7 x 6 printed "3/10 positions proved exactly").
A regret of 0 on an unproved position means "no mistake proved", not
"agreed with perfect play". For fully exact audits, use a board up to
about 5 x 5 or --oracle alphabeta for a heuristic second opinion.
What each regime costs¶
The audit also prints a regime table: three 3-ply searches that differ
only in what they assume about the opponent's replies (the worst one,
alphabeta; a model of greedy with 20% noise, expectimax; or the
opponent's actual policy, clairvoyant, a benchmark no real player can
match), on 10 seeded openings from both seats. The measured event is a
win within 25 plies. From the same make audit-connect4 run:
agent [regime] opponent games W/D/L rate (95% interval) mean plies
alphabeta [worst-case] greedy 20 15/4/1 win in <=25 plies 0.700 [0.457, 0.881] 20.6
expectimax [probabilistic] greedy 20 11/0/9 win in <=25 plies 0.550 [0.315, 0.769] 19.1
clairvoyant [clairvoyant (benchmark)] greedy 20 20/0/0 win in <=25 plies 1.000 [0.832, 1.000] 14.3
alphabeta [worst-case] noisy_greedy 20 17/2/1 win in <=25 plies 0.850 [0.621, 0.968] 17.9
expectimax [probabilistic] noisy_greedy 20 19/0/1 win in <=25 plies 0.900 [0.683, 0.988] 13.6
clairvoyant [clairvoyant (benchmark)] noisy_greedy 20 20/0/0 win in <=25 plies 1.000 [0.832, 1.000] 10.7
Against the noisy opponent its model describes, expectimax does about
as well as alphabeta; against plain greedy, which never makes the
random moves the model expects, it loses 9 of 20 games while alphabeta
loses 1. The intervals are wide (20 games per row); the losses are the
point: a model that is wrong about the opponent costs games, and assuming
the worst reply does not.
Watching a game¶
play connect4 draws the board upright: X's discs are ● (red with
colour), O's ○ (blue), empty cells ·. The last move is highlighted;
on a gate override the rejected column flashes amber and the chosen one
green; a winning line is drawn as ✶. --coords (on by default when you
have a seat) labels the columns a–g and the rows 1–6. The panel
shows the number of winning cells each player has (X threats,
O threats).
Performance¶
From one development machine (the report prints no timings):
| Measurement | Result |
|---|---|
| Exact solver | about 350,000 positions/s |
search, per move on 7 x 6 |
at most 20,000 positions, about 0.05 s |
gated, per move |
about 0.2 ms on average (a 2,000-position fallback search when a check fails) |
| The four checks | at most 49 two-move continuations, about 0.1 ms |
Extending it¶
- Other boards and line lengths:
connect4.configure(8, 7, connect=5)or--size 8x7 --connect 5. Every agent reads the size from the game. - Another proposer:
connect4.guarded(proposer)wraps any player, including a human (--guarded), in the same checks and fallback. - A stronger fallback:
GatedConnect4Agent(proposer, fallback_nodes=…)gives the fallback search a larger budget.
Related: Checkers gates a greedy player with a depth-limited search; Games: tic-tac-toe and snake shows checks proven over a whole solved game.