Every "AI" opponent in a board game — Tic-Tac-Toe, Connect 4, Checkers, Othello, Chess — tends to run the same idea: search the game tree, assume the opponent plays their best, and pick the move with the best guaranteed outcome. That idea is minimax, and alpha-beta pruning is what makes it fast enough to run in a browser tab with no backend.
I built an interactive version where you can step through minimax on a real board and toggle alpha-beta on to watch it skip work: play with it here. This post is the written companion.
Minimax in one function
Score a finished position from the AI's point of view: +1 if the AI wins, -1 if you win, 0 for a draw. Then walk the tree of possible futures. On the AI's turn it takes the max of its options; on your turn it assumes you take the min (the worst outcome for the AI). That alternation is the whole algorithm.
function minimax(node, isMax):
if node is terminal:
return score(node) # +1 / -1 / 0
if isMax:
best = -inf
for child in node.moves: # AI's turn
best = max(best, minimax(child, false))
return best
else:
best = +inf
for child in node.moves: # your turn
best = min(best, minimax(child, true))
return best
Alpha-beta: same answer, fewer nodes
Searching every branch is wasteful. Once you've found a reply that already refutes a move, you don't need to look at that move's other branches — they can't change the decision. Two running bounds carry that knowledge down the tree: alpha (the best MAX can already guarantee) and beta (the best MIN can already guarantee). When they cross, you stop.
function ab(node, alpha, beta, isMax):
if node is terminal:
return score(node)
if isMax:
best = -inf
for child in node.moves:
best = max(best, ab(child, alpha, beta, false))
alpha = max(alpha, best)
if beta <= alpha: break # prune the rest
return best
else:
best = +inf
for child in node.moves:
best = min(best, ab(child, alpha, beta, true))
beta = min(beta, best)
if beta <= alpha: break # prune the rest
return best
Pruning never changes the value at the root — only how many nodes you touch to find it. On a small Tic-Tac-Toe position with three empty squares, the full tree is 14 nodes and alpha-beta visits 10 of them. On the full-depth opening move it's dramatic: 549,945 nodes drop to 36,528 — a 93% cut — which is what lets a provably-unbeatable Tic-Tac-Toe move resolve in about 0.3 ms client-side. (The measured benchmarks are here.)
Why "just search deeper" gets expensive
A search that looks d moves ahead visits roughly b^d nodes, where b is the branching factor — how many moves you typically have. That number explodes:
- Tic-Tac-Toe: b ≈ 4
- Connect 4: b ≈ 4 (max 7 columns)
- Checkers: b ≈ 2.8
- Othello: b ≈ 10
- Chess: b ≈ 35
Looking just 8 moves ahead in chess is on the order of 35^8 ≈ 2.3 trillion positions. Alpha-beta — plus move ordering, transposition tables, quiescence and friends — is how a search reaches useful depth without visiting all of them. (Branching factors are approximate published averages, à la Allis 1994, for illustration.)
The same idea, five different games
Every opponent is this algorithm with a different board, a different way of scoring a position, and different tricks to search deeper without searching everything:
| Game | Board | Branching (approx.) | Search tricks |
|---|---|---|---|
| Tic-Tac-Toe | 3×3 | ≤ 9 (~4) | Minimax + alpha-beta, full depth on 3×3 |
| Connect 4 | 7×6 | ≤ 7 (~4) | Bitboard negamax + alpha-beta + transposition table + iterative deepening |
| Checkers | 8×8 | ~2.8 | Iterative-deepening negamax + alpha-beta + capture quiescence |
| Othello | 8×8 | ~10 | Iterative-deepening negamax + alpha-beta + exact endgame solve |
| Chess | 8×8 | ~35 | Negamax + alpha-beta + null-move + quiescence + check extensions + move ordering |
Read the real code
The pseudocode above is the shape. Here's a real, unminified engine that runs one of these opponents in the browser — iterative-deepening negamax with alpha-beta pruning and capture-aware quiescence, about 230 lines of vanilla JS: the checkers engine on GitHub Gist.
Everything runs client-side, zero dependencies. If you'd rather watch the tree animate and prune than read about it, the interactive version is here: Watch a Game AI Think →
Top comments (2)
If you want to check the 14 → 10 node counts for yourself, here's a self-contained script — no dependencies, just
node reproduce-minimax.mjs:gist.github.com/lucian-devops/8660...
It runs plain minimax and alpha-beta over the exact Tic-Tac-Toe position from the post and prints the node counts, confirming both find the same move.
Thanks for reading, everyone! If you run the reproduce script or adapt the minimax approach to another game, I'd genuinely love to hear how it goes — and feedback on the interactive tree is very welcome.