Reinforcement Learning · Search · PyTorch
Connect Four
From classical search to AlphaZero
I wanted to understand planning and reinforcement learning by implementing the pieces myself rather than wrapping a library.
01Why this project
Connect Four with perfect play is a first-player win. None of these agents is a solver. I use the same environment and evaluation harness for every agent, then change only the decision-making method. That makes it possible to compare playing strength, search cost, and latency without changing the rest of the system.
02The progression
Each agent implements the same contract: select_action(state, valid_actions). The CLI, FastAPI demo, and evaluation harness all call that, then env.step.
Minimax. Searches future states with alpha-beta pruning.
03Classical search
Minimax with alpha-beta and center-first move ordering. Leaves use window and center features — not the full heuristic, which still gets win, block, and fork. Depth 1 loses because it cannot see a block. Depth 2 is the first ply that can.
Experiment A — vs heuristic
Paired random openings, both seats, 4 opening plies, 200 games per depth. The heuristic still gets win / block / fork; Minimax’s leaf does not. Depth 1 loses because it cannot see blocks. Depth 2 is the jump. Depth 5 is the practical agent; depth 6 is slower and not stronger.
| Depth | Win | Draw | Nodes / move | Latency |
|---|---|---|---|---|
| 1 | 14.5% | 0.5% | 7 | 1.3 ms |
| 2 | 57.0% | 6.5% | 41 | 6.6 ms |
| 3 | 58.5% | 2.5% | 159 | 23 ms |
| 4 | 68.5% | 6.5% | 601 | 88 ms |
| 5 | 79.0% | 2.5% | 2,022 | 268 ms |
| 6 | 77.0% | 4.5% | 7,456 | 1029 ms |
A second run holds the evaluator fixed and only changes depth, against Minimax depth 1. Search-cost numbers in Experiment B (8 → 2,666 nodes/move) are not from Experiment A.
Experiment B — vs Minimax d1
Same evaluator, only depth changes. 100 games per depth. Depth 1 versus itself is the 50% control. Almost all of the lift is depth 1 → 2. Extra depth barely helps against a shallower copy of the same evaluator; it still helps against the tactician.
| Depth | Win | Nodes / move | Latency |
|---|---|---|---|
| 1 | 50% | 8 | 1.3 ms |
| 2 | 87% | 47 | 7.3 ms |
| 3 | 88% | 187 | 26 ms |
| 4 | 90% | 748 | 108 ms |
| 5 | 91% | 2,666 | 356 ms |
04MCTS / PUCT
Selection by PUCT, expansion of legal children, evaluation by random rollout, backup of visit counts and values. The prior is uniform. Visit counts are the policy. There is no policy/value network in this agent — that is the AlphaZero stage.
100 games per simulation budget. PUCT, uniform prior, random rollouts. 800 simulations beat both opponents at about the same wall time as Minimax depth 5 (79% vs heuristic). Extra rollouts help; a better leaf is the next lever.
Node b
- N visits
- 210
- Q value
- 0.57
- P prior
- 0.34
- U bonus
- 1.04
Select
Walk the tree by PUCT until a leaf.
Expand
Add the legal children of that leaf.
Evaluate
Current leaf evaluation: random rollout. Policy/value evaluation is introduced in the AlphaZero stage.
Backup
Push N and Q up the path.
Illustrative counts for the diagram, not a dumped search from a match.
| Sims | vs heuristic | vs Minimax d3 | Latency |
|---|---|---|---|
| 50 | 9% | 9% | ~16 ms |
| 200 | 36% | 26% | ~64 ms |
| 800 | 64% | 66% | ~270 ms |
05DQN
A compact value-based agent in PyTorch, not through Stable-Baselines. Canonical 2×6×7 board planes. Network: MLP 84 → 128 → 128 → 7.
- Replay buffer
- Online + target network
- ε-greedy over legal actions only
- Illegal-action masking
- Huber loss, Adam, gradient clipping
- Hard target synchronization
- Mover-centric / negamax Bellman target
Training: 3,000 self-play episodes, about 52,600 environment steps. Greedy evaluation against frozen opponents. The agent reliably beats Random but still fails against tactical search. The point of this stage is the comparison, not the 90% number.
- Random90%
- Minimax d110%
- Heuristic2.5%
- Minimax d20%
A later 30,000-episode run did not change the conclusion: more self-play of this architecture still fails against search.
06Toward AlphaZero
The next stage is a policy/value network guiding PUCT, with self-play producing improved targets, then training, then repeat. It is being implemented. MCTS and DQN stay frozen except for the hooks that work needs.
- 01State
- 02Policy / Value net
- 03PUCT search
- 04Improved policy
- 05Self-play
- 06Training↺
Same environment and eval protocol. This loop is the current milestone — still being implemented.
07Evaluation methodology
- Frozen opponents — not a moving target during a reported run.
- Paired openings and both seats, so first-player advantage is not mistaken for strength.
- The same match harness for CLI, HTTP demo, and benchmarks: select_action → env.step.
- Latency and nodes/move reported next to win rate. Strength without cost is incomplete.
Technical report
Algorithms, protocol, plots, and caveats that did not fit here.