Connect Four

00Abstract

This project builds Connect Four agents step by step, from random play and a simple tactical heuristic to depth-limited minimax with alpha-beta pruning, PUCT-based Monte Carlo tree search, and a DQN implemented from scratch. I evaluate them in the same setup so I can compare playing strength alongside the extra search and latency each method requires.

The minimax experiments show how much even a small amount of lookahead matters. Against the heuristic, depth 1 wins only 14.5% of 200 games, depth 2 jumps to 57%, and depth 5 reaches 79% at about 270 ms per move. Depth 6 costs more without improving the result. In a second experiment against the same evaluator frozen at depth 1, depth 1 gives 50% as expected, while depth 2 already reaches 87%. Uniform-rollout MCTS only beats the heuristic at 800 simulations, at roughly the same latency as depth-5 minimax, while still playing worse than depth-5 minimax at that cost. The DQN reliably beats random play but not the heuristic, and increasing self-play from 3,000 to 30,000 episodes does not materially change that result. Across these experiments, a small amount of explicit lookahead proves surprisingly hard to replace with either random-rollout search or learned action values.

Connect Four is a solved game: with optimal play, the first player wins [1]. None of the agents here approaches perfect play yet. The next stage is to put a learned policy/value network inside the existing PUCT search and train it through self-play, then measure how far that AlphaZero-style loop can close the gap.

01Introduction

This project builds a sequence of Connect Four agents, with each stage adding a new idea and a new question to test.

Training and evaluation call the Python environment directly through env.step. The FastAPI + React app is only a browser interface over the same agents, not a separate implementation.

02Environment

Standard 6×7 Connect Four board. Pieces are 0 / +1 / −1. Row 0 is the top. Gravity fills the highest empty index in a column. Actions are column indices 0..6. For illegal actions, the environment raises an error rather than ignoring the move or assigning a penalty. Agents mask illegal actions with get_valid_actions().

Players alternate. Player one sits first on an empty board. step is deterministic for legal actions. On a win, current_player is left as the winner (it doesn't flip).

Rewards are sparse and defined from the perspective of the player who just moved: +1 for a winning move and 0 otherwise, including draws. The losing player never receives -1 directly from step, because the game ends immediately after the winning move. Search agents ignore this reward signal. For DQN, the trainer handles the sign change explicitly so that value targets stay consistent when turns alternate.

get_canonical_state() multiplies the grid by current_player, so +1 is the side to move. DQN uses this representation. clone() copies board, turn, and terminal flags. Minimax and MCTS clone at every node.

Win detection scans four cells from every occupied square in four directions. Opposite directions are covered by starting at the other end of the line.

03Methods

Every policy implements the same contract (connect4/agents/base.py):

select_action(state, valid_actions) → AgentDecision(action, probabilities, value, metadata)

state is the absolute board. valid_actions is computed by the environment. Search agents are not passed an env, they rebuild one from the grid and infer the seat from piece count (even number of discs ⇒ player one).

probabilities is a length-7 vector for the demo. Heuristic and minimax are deterministic: the bars are a softmax of scores, not a sampling policy. MCTS fills them from visit counts. DQN fills them from a softmax over masked Q-values, play is still argmax.

The CLI, the HTTP session layer, and the match harness all call select_action then step.

3.1 Random

Uniform sample over legal columns. Illegal columns get probability 0.

3.2 Heuristic

A 1-ply tactician (no game tree). Priority:

1. Win immediately if a legal drop makes four in a row (center on ties).
2. Block any opponent immediate win. Two or more such columns means the position is already lost against perfect reply (fork). The agent still takes the most central block.
3. Otherwise score each legal drop and take the max, center on ties.

The four positions below are the unit tests.

Immediate win

Block

Self-fork

Hanging move

After a candidate drop, we score the move:

• Immediate loss: −10^6 if the move gives the opponent a direct win.
• Open windows: +100 for an uncontested three-in-a-row window, +10 for two.
• Center: bonus (1, 2, 3, 4, 3, 2, 1) according to the played column.
• Self-fork: +10^5 if the move creates at least two immediate wins next turn.
• Opponent fork: −800 if the opponent can create a double threat on the reply.

Scoring counts my windows after the drop, so the heuristic is not zero-sum.

3.3 Minimax and alpha-beta

The minimax agent performs depth-limited adversarial search with alpha-beta pruning. The default depth used in the demo is 5. Terminal positions are scored separately, while non-terminal leaves are evaluated with a zero-sum function that is deliberately simpler than the standalone heuristic agent:

Here, $n_3$ and $n_2$ count uncontested four-cell windows containing three or two pieces respectively. The center term uses the same column weights as the heuristic agent. Unlike the heuristic, however, the minimax leaf evaluation is explicitly zero-sum. A position evaluated from one player’s perspective receives the opposite score when evaluated from the other:

The fork bonuses, HARD_LOSS, and the explicit win and block rules used by the heuristic are not part of this leaf function. Wins and losses are instead handled by the search itself through terminal scores.

This distinction matters most at shallow depth. A depth-1 search can see whether its own move ends the game because the resulting child is terminal. It cannot yet see the opponent’s reply, so it doesn't systematically block an immediate threat. Depth 2 is the first setting that can do so. This is why the largest improvement in both minimax experiments appears between depths 1 and 2.

Terminal positions receive a score of approximately $\pm \mathrm{WIN\_SCORE}$, with a small adjustment for search depth so that the agent prefers faster wins and delays losses when possible. Legal moves are explored from the center outward. This ordering doesn't change the minimax result, but it improves alpha-beta pruning by searching promising moves earlier.

For validation, I also keep an unpruned reference implementation, reference_minimax, with the same terminal scoring, leaf evaluation, and move order. I compared the alpha-beta implementation against this reference on 80 randomly generated positions at depths 1 to 3, using the score assigned to every legal column, and on one fixed mid-game position at depths 2 to 4 using the final selected action. These checks are useful for catching implementation errors, although they are only finite tests and do not constitute a proof of equivalence at deeper search depths. The benchmark sweeps use only the alpha-beta implementation.

At each search node, the environment is cloned and advanced with step. There is currently no transposition table, so identical positions reached through different move sequences are searched independently.

3.4 Monte Carlo tree search

The MCTS agent uses PUCT for tree selection, with a uniform prior over legal actions and random rollouts for leaf evaluation [6],[7]. For a child action $a$, selection is based on

where $Q(s,a)$ is the current mean value of the child, $P(s,a)$ is its prior probability, $N(s)$ is the visit count of the parent, and $N(s,a)$ is the visit count of the child. In the current implementation, $P(s,a)$ is uniform across legal actions. The search therefore still follows the PUCT rule, even though the prior doesn't yet come from a neural network.

A new search tree is built for every move. Values are stored from the perspective of the player to move at each node. When a child value is viewed from its parent, the sign is reversed, and the same alternation is applied during backup. This keeps the tree consistent with the zero-sum nature of the game.

Terminal positions use the exact game outcome rather than a rollout estimate. As a result, an immediate win or loss is handled exactly whenever the search reaches it. Random rollouts are only used for non-terminal leaves. At the end of the search, visit counts at the root are normalized to produce the probability vector shown by the interface, and the most visited action is selected.

The agent also reports the number of simulations and the number of expanded tree nodes. The latter counts created children, including nodes that may not yet have been visited, so it shouldn't be compared directly with the node counts reported for minimax.

When two actions receive the same PUCT score, or the same final visit count, ties are broken in favor of the more central column. This is the same small amount of Connect Four-specific prior knowledge used for move ordering in minimax.

3.5 DQN

The DQN is implemented from scratch in PyTorch following the standard setup of Mnih et al. [4]. The board is represented by two $6\times7$ canonical planes, one for the player to move and one for the opponent. After flattening, the network is a small MLP:

with one Q-value per column. Illegal actions are masked both when selecting moves and when computing the Bellman target. Training uses $\varepsilon$-greedy exploration over legal actions, while evaluation is greedy.

Because the next state is represented from the opponent’s perspective, the Bellman target uses a negamax sign flip:

Training uses Huber loss, Adam, a replay buffer of 50k transitions, batches of 64, $\gamma=0.99$, gradient clipping at 10, and a hard target-network update every 500 environment steps. Exploration decays from $\varepsilon=1$ to $0.05$ over 30k environment steps.

No Double DQN, dueling network, or prioritized replay is used.

04Evaluation protocol

Code: connect4/evaluation/match.py, connect4/training/evaluate.py, evaluate_mcts.py.

Heuristic and minimax are deterministic. From the empty board, a matchup is two games (one per seat), not a sample. Headline tables therefore use paired random openings.

For $n$ games (even), draw $n/2$ openings. Opening $i$ is four uniform legal moves from Random(seed + i). The shortest Connect Four win is seven plies, so four random plies never terminate. Each opening is played twice, labelled agent as P1 then as P2. The same opening list is reused at every depth or simulation budget.

This measures strength over a distribution of random 4-ply positions, then play to the end. It is the wrong protocol for the game-theoretic question “who wins from move 1?” That question is the two-game empty-board table in Section 5.3.

We report wins, draws, and losses from the labelled agent’s perspective, along with separate win rates as P1 and P2. For that same agent, we also record the average number of searched nodes per move and the mean and median move latency. The opponent is not instrumented, even when both agents use minimax.

Node counts are averaged over the positions that actually occurred in the games. This matters because stronger agents may finish games earlier, and late-game positions usually have fewer legal moves to search. The reported node counts therefore reflect the cost of the games that were played, rather than the complexity of a fixed set of board positions.

Each experiment saves its results as JSON, together with a Markdown summary and generated plots under experiments/results/. The JSON file is treated as the raw result used to produce the tables and figures in this report. Unit tests such as “minimax beats random as P1 in 20 games” are only sanity checks and are not used as experimental results.

05Experiments

5.1 Minimax versus the heuristic

Question. Can extra search depth beat a 1-ply tactician when the searcher doesn't have that tactician’s fork and block rules in the leaf?

Setup. 200 games per depth (100 openings × 2 seats), 4 opening plies, seed 0, depths 1–6.

Depth 1 loses because it can't see a block. Depth 2 is the jump (14.5% → 57%): one extra ply takes wins and answers hanging threats. Depth 2→3 is almost flat. Depths 4 and 5 keep climbing: against an opponent who already knows the cheap tactics, further lookahead still helps. Depth 5 is the strongest cell: 79% overall, 85% as P1, 73% as P2.

Depth 6 is much more expensive than depth 5. It searches about 3.7 times as many nodes and takes roughly one second per move, yet its win rate is 77% compared with 79% at depth 5. With only 200 games, that two-point difference is too small to interpret as a real loss in strength. The safer conclusion is simply that depth 6 doesn't improve enough on depth 5 to justify the extra search cost. If the small dip is real, one possible explanation is an odd/even horizon effect, since an even search depth evaluates leaves after the opponent’s move [3]. Experiment 5.2 provides a cleaner comparison of depth itself.

Draws remain uncommon, between 0.5% and 6.5%. With 200 games per depth, differences of only a few percentage points in win rate are also within the uncertainty of the experiment. For example, the 58.5% result at depth 3 should not be treated as meaningfully better than the 57% at depth 2. The confidence estimates here are only approximate because the games come in pairs that share the same random opening. Their main purpose is to prevent over-interpreting small differences, not to provide a formal statistical comparison between depths.

5.2 Same evaluator, only depth changes

Question. Holding evaluate(), the search code, the rules, the openings, and seat balance fixed, what does increasing the depth buy?

Setup. Opponent is MinimaxAgent(depth=1). 100 games per depth (50 openings × 2 seats), 4 opening plies, seed 0, depths 1–5.

Depth 1 against itself serves as a control. Since both agents are deterministic and identical, each paired opening gives the labelled agent one game in each seat. Any first-player advantage therefore should cancel across the pair, yielding an expected 50% overall win rate.

The control behaves as expected, with depth 1 against itself giving a 50% win rate. The largest gain comes from increasing the search depth from 1 to 2, where the win rate jumps from 50% to 87%. This is the same tactical threshold seen in Table 1: depth 2 is the first setting that can explicitly account for the opponent’s reply. Going deeper helps much less against a fixed depth-1 opponent. Depths 3 to 5 improve the win rate only from 88% to 91%, while the average search cost grows from 187 to 2,666 nodes per move. Given the 100-game sample, these small differences should not be over-interpreted. The main result is the sharp improvement from depth 1 to 2, followed by much smaller returns from additional search.

5.3 Empty board and horizon effect

Question. What happens when minimax starts from the standard empty board rather than from random 4-ply openings? Can these games also help explain the odd/even behavior seen in the depth sweep?

Setup. Minimax plays against the heuristic from the empty board at depths 1–7. Each depth is evaluated in exactly two games, once as P1 and once as P2. Both agents are deterministic, so these are fixed outcomes rather than samples. Perfect Connect Four is a first-player win [1]. Here, a win as P2 only means beating the heuristic from the second seat.

python -m connect4.training.evaluate --empty-board --opponent heuristic

Depth 5 is the first setting that beats the heuristic from both seats. Depths 6 and 7 produce the same two outcomes while becoming much more expensive. Depth 7 for example takes roughly 9 times as long per move as depth 5. This makes depth 5 the natural operating point among the depths tested here.

The more interesting behavior appears between depths 3 and 4. Depth 3 loses as P1 but wins as P2, while depth 4 does the opposite. Inspecting the games shows that the two depths make different choices at the first position where minimax is not forced by a terminal win or loss. The difference comes from where the search horizon falls relative to the players' turns.

As P1, depths 3 and 4 share the opening moves $3,3$. At the next decision, depth 3 gives columns 2 and 4 a score of $+92$ and chooses column 2. That move creates several favorable two-piece windows, and because the depth 3 search ends after P1's own move, the static evaluator sees the resulting shape before P2 can respond. At depth 4, the search includes one additional opponent reply. The same candidate moves then receive a score of $-1$, and the agent instead continues in the center. In this game, the deeper choice eventually wins.

The effect reverses when minimax plays as P2. After the heuristic opens in the center, depth 3 also stacks the center and eventually wins. Depth 4 sees one reply further, assigns that line a worse value, and instead chooses column 1. That alternative eventually loses. Searching one additional ply therefore changes the decision in both games, but it doesn't improve both outcomes.

This is a useful example of the horizon effect in depth-limited search. The leaf evaluator is only an approximation of the true game value, so moving the horizon by one ply can change which board patterns it rewards. Odd depths tend to evaluate positions after the searching player's move, while even depths allow one more opponent response before evaluation. The empty-board games show that this interaction is real in the current agent, although two deterministic games are not enough to explain the small depth-5 to depth-6 difference observed in the larger experiment.

5.4 MCTS simulation budget

Question. How much does MCTS improve as the simulation budget increases, and how does its cost compare with the search-based agents?

Setup. MCTS is evaluated with 50, 200, and 800 simulations per move using the same paired-opening protocol as the previous experiments. The prior over legal actions is uniform and non-terminal leaves are evaluated by random rollout. Each budget is tested over 100 games.

A small latency probe is used only to give context when comparing MCTS with minimax. It is not intended as an exact latency match between the two methods.

MCTS vs heuristic

Increasing the simulation budget produces a clear improvement against the heuristic. At 50 simulations, MCTS wins only 9% of games. This rises to 36% at 200 simulations and 64% at 800. The increase comes with an almost proportional rise in search cost, from 278 to 3,126 tree nodes per move and from 16 to 265 ms of latency.

At the largest budget, MCTS is strong enough to beat the heuristic overall, but it remains weaker than depth-5 minimax, which reaches 79% against the same opponent. The comparison isn't perfectly latency-matched, but it shows that random-rollout MCTS needs a substantial simulation budget before it becomes competitive with the stronger deterministic search agent.

MCTS vs Minimax(depth=3)

The same pattern appears against Minimax(depth=3). With 50 or 200 simulations, MCTS loses the matchup overall. At 800 simulations it reaches a 66% win rate, but this requires several times the latency of the depth-3 opponent.

These results suggest that simply increasing the number of random rollouts has diminishing value. The current MCTS has no informed prior and no learned value function, so much of its budget is spent exploring and evaluating positions without guidance. The next step is therefore to improve the information used by the search, which is the role of the policy and value network in the AlphaZero stage.

5.5 DQN

Question. Does the DQN learn a useful policy through self-play, and does substantially more training close the gap to the search-based agents?

Setup. The DQN is trained through self-play and evaluated greedily using the same paired-opening protocol as the previous experiments. Each opponent is tested over 40 games, using 20 openings played from both seats. I compare two checkpoints, after 3,000 episodes (about 53k environment steps) and 30,000 episodes (about 563k steps).

After 3,000 episodes, the DQN already beats Random reliably, with a 90% win rate, but performs poorly against the stronger baselines. It wins 10% against Minimax(depth=1), 2.5% against the heuristic, and doesn't beat Minimax(depth=2).

Training for 10 times as many episodes doesn't change that conclusion. The 30k checkpoint still beats Random, but remains weak against even shallow search and loses every game against the heuristic. With only 40 games per opponent, differences such as 90% versus 80% against Random shouldn't be interpreted as meaningful changes in strength.

The important result is therefore qualitative rather than the exact percentages. The DQN learns enough from self-play to move well beyond random play, but the current architecture and training setup do not recover the tactical behavior that the heuristic and minimax obtain explicitly through rules or lookahead. More training alone doesn't close that gap.

06Discussion

The two minimax experiments tell a consistent story. The largest gain comes from going from depth 1 to depth 2, when the search first includes the opponent’s reply. Against Minimax(depth=1), almost all of the improvement happens at that point. Against the stronger heuristic, deeper search continues to help through depth 5 because the agent begins to reason beyond the one-move tactics that the heuristic encodes explicitly.

For the interactive demo, depth 5 is the best trade-off among the settings tested. It reaches 79% against the heuristic at about 270 ms per move. Depth 6 is much more expensive and doesn't improve the result, while depth 4 remains a reasonable lower-latency option at about 90 ms per move.

The heuristic remains an important baseline because it captures immediate wins, blocks, and forks without search. Depth-1 minimax doesn't reliably recover those behaviors, while depths 2 and above beat the heuristic overall in the paired-opening benchmark. The comparison shows the difference between encoding short tactical knowledge directly and recovering it through lookahead.

MCTS improves steadily as the simulation budget increases, but random rollouts are expensive. At roughly 265 ms per move, 800-simulation MCTS reaches 64% against the heuristic, compared with 79% for depth-5 minimax. This does not say that PUCT is inherently weaker. In the current agent, the prior is uniform and non-terminal leaves are evaluated by random rollout. The AlphaZero stage changes both by introducing a learned policy and value function.

The DQN learns a useful policy from self-play, but its limitations are clear. It reliably beats Random, yet remains weak against the heuristic and shallow minimax. Increasing training from 3,000 to 30,000 episodes does not materially change that picture. I therefore treat DQN as a value-based RL baseline rather than as the route to the strongest Connect Four agent in this project. The next step is to combine learning with search, using a policy/value network to guide the existing PUCT tree.

07Software

connect4/env            MDP
connect4/agents         Random, Heuristic, Minimax, MCTS, DQN
connect4/evaluation     match harness and metrics
connect4/training       evaluate, evaluate_mcts, train_dqn
backend/               FastAPI sessions
frontend/               React demo
tests/                  engine, agents, API, harness
experiments/results/    sweeps (JSON / Markdown / PNG)

The browser demo uses a FastAPI backend over the same environment and agent implementations used for training and evaluation. /game/new creates a session, while /move and /ai-move advance the game. AI moves go through the common select_action interface before calling step, so the web app doesn't maintain a separate implementation of the agents. Minimax depth is configurable from 3 to 7, with depth 5 as the default.

08Limitations

The search experiments use 100 to 200 games per configuration, while the DQN evaluation uses 40. These sample sizes are enough to support the large differences reported in the experiments, but not small changes of only a few percentage points.

The paired-opening protocol reduces seat bias, but the openings are randomly generated four-ply positions rather than a curated opening set. Confidence intervals are also computed at the game level, even though paired games share the same opening.

Search cost is measured over the positions actually encountered during play. Different agents therefore see different game lengths and board states, so node counts and latency are useful empirical costs rather than controlled complexity measurements on a fixed position set.

The MCTS and minimax comparisons are not strictly equal-compute experiments. All timings were collected on one machine, and the methods were not constrained to identical wall-clock budgets.

Finally, none of the agents is evaluated against a perfect solver. Win rate against the chosen baselines measures relative playing strength, not distance from optimal Connect Four play.

09Reproducibility

pip install -e ".[eval,rl]"
python -m connect4.training.evaluate --opponent heuristic --games 200 --depths 1,2,3,4,5,6 --seed 0 --opening-plies 4
python -m connect4.training.evaluate --opponent d1 --games 100 --depths 1,2,3,4,5 --seed 0 --opening-plies 4
python -m connect4.training.evaluate --empty-board --opponent heuristic
python -m connect4.training.evaluate_mcts --opponent heuristic --games 100 --sims 50,200,800
python -m connect4.training.train_dqn --episodes 30000 --eval-games 40
python -m connect4.training.train_dqn --eval-only --checkpoint models/dqn/dqn.pt
pytest

The commands above reproduce the main minimax, MCTS, and DQN experiments reported in this document. Seeds and opening lengths match the saved experiment configurations. Empty-board evaluation is deterministic and doesn't use the paired-opening protocol.

The repository also includes tests for the environment, minimax and alpha-beta equivalence, evaluation logic, MCTS, and DQN. In particular, the evaluation tests check the paired-seat control used in Section 5.2, while the minimax tests compare alpha-beta against the unpruned reference implementation.

10Conclusion

The experiments show a clear progression in what each additional idea contributes. A 1-ply heuristic is enough to beat shallow minimax when the search cannot yet see the opponent’s reply. Moving from depth 1 to depth 2 produces the largest gain, and deeper search continues to help against the stronger heuristic, reaching 79% at depth 5. Beyond that, the computational cost grows much faster than the measured improvement.

MCTS also becomes stronger as the simulation budget increases, but random rollouts use that compute less efficiently than alpha-beta search in these experiments. The DQN learns well enough to beat random play, but even substantially more self-play does not close the gap to the tactical and search-based agents.

What matters most to me in these results is that the answer depends on the comparison being made. Depth 2 is almost sufficient against a depth-1 copy of the same evaluator, while additional lookahead still matters against the heuristic. More MCTS simulations help, but not enough to compensate for an uninformed prior and random leaf evaluation. These differences are exactly what the shared environment and evaluation protocol were meant to expose.

The next step is to combine search and learning directly: a policy/value network guiding the existing PUCT tree and trained through self-play.

11References

1. [1]L. V. Allis, A Knowledge-based Approach of Connect-Four, M.Sc. thesis, Vrije Universiteit Amsterdam, 1988. The game is solved; first player wins.
2. [2]D. E. Knuth and R. W. Moore, “An analysis of alpha-beta pruning,” Artificial Intelligence, 1975.
3. [3]D. S. Nau, “An investigation of the causes of pathology in games,” Artificial Intelligence, 1982; J. Pearl, Heuristics, 1983.
4. [4]V. Mnih et al., “Human-level control through deep reinforcement learning,” Nature, 2015.
5. [5]L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning,” ECML, 2006.
6. [6]C. D. Rosin, “Multi-armed bandits with episode context,” Annals of Mathematics and Artificial Intelligence, 2011. PUCT.
7. [7]D. Silver et al., “Mastering the game of Go without human knowledge,” Nature, 2017; “A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play,” Science, 2018.