Try it!
Your turn (yellow) — click a column
You Bot (Minimax + Alpha-Beta)
Visit the GitHub Repo
Description
Challenges: Writing a DFS-based minimax evaluator that's fast enough to be playable in real time. A transposition table and symmetry caching were added to avoid re-evaluating equivalent board states. I also had to build a pixel-based board reader to interface with the game running on screen, without any game API.
Result: A fully functioning Connect 4 AI that plays strong moves in real time, reading live game state from the screen via pixel detection. The minimax + transposition table combination keeps decision time under a second per move.
How the Algorithm Works
Minimax Search Tree (Connect 4) ════════════════════════════ ┌──────────────┐ │ ROOT STATE │ ← MAX turn (Bot chooses) └──────┬───────┘ ┌─────────────┼─────────────┐ ▼ ▼ ▼ [col 3] [col 4] [col 5] … all legal moves MIN MIN MIN ← Human responds / \ / \ / \ MAX MAX MAX MAX MAX MAX ← Bot replies │ │ │ │ │ │ +10 -4 +2 +8 -∞ +6 ← eval scores MIN nodes pick the lowest child (human picks worst for bot). MAX nodes pick the highest child (bot picks best for itself). Root backs up: col 3 → -4 col 4 → +2 col 5 → -∞ Bot plays: col 4 (highest backed-up value) ───────────────────────────────────────────────────── Optimisations applied in this project: Transposition table — cache board hash → score so duplicate states reached via different move orders are never re-evaluated. Symmetry cache — board mirrored horizontally is equivalent; halves the effective branching factor. Depth limit — search stops at depth N and calls the static eval function instead of expanding further. Keeps move time < 1 second. Minimax with transposition table and symmetry pruning. Bot plays MAX, human plays MIN.
Board State Reading
Pixel-Based Board Detection ════════════════════════════ ┌─────────────────────────────────────┐ │ Screen Region │ │ ┌───┬───┬───┬───┬───┬───┬───┐ │ │ │ . │ . │ R │ . │ Y │ . │ . │ row0│ │ ├───┼───┼───┼───┼───┼───┼───┤ │ │ │ . │ Y │ R │ Y │ R │ . │ . │ row1│ │ ├───┼───┼───┼───┼───┼───┼───┤ │ │ │ R │ Y │ Y │ R │ Y │ R │ Y │ row2│ │ └───┴───┴───┴───┴───┴───┴───┘ │ └─────────────────────────────────────┘ │ │ sample pixel at centre of each cell ▼ ┌─────────────────────────────────────┐ │ colour → piece map │ │ (R, G, B) near red → BOT │ │ (R, G, B) near yellow → HUMAN │ │ otherwise → EMPTY │ └─────────────────────────────────────┘ │ ▼ int board[6][7] → passed to minimax Calibration step on startup maps pixel coordinates to grid cells, fixing resolution dependence.
In Action
Real-time bot proof points
- Minimax search evaluates future board states without machine learning libraries.
- Transposition and symmetry caching keep per-move decisions fast enough for live play.
- The board state feeds directly into the same search path used for move selection.
Board detection proof points
- Startup calibration maps screen pixels to the 6-by-7 Connect 4 grid.
- Color sampling classifies each grid cell as red, yellow, or empty.
- Detection is separated from search, so either piece can be improved independently.
Dev Notes
Problems Solved
The NOAI competition requires game-playing AI built from scratch — no ML libraries. I needed a practice project that forced a real implementation of search and board evaluation, plus a way to interface with the game running on screen without any game API.
Errors & Fixes
The initial DFS was too slow for real-time play at competitive depth — adding a transposition table and symmetry caching cut per-move decision time to under a second. Pixel detection coordinates were hardcoded and broke at different screen resolutions; fixed by adding a calibration step on startup.
What I Learned
Minimax with transposition tables, board symmetry pruning, and how to profile and speed up Python search code. Also learned pixel-based game state reading — capturing screen regions, converting to a grid, and mapping colors to board positions.
Back to top