Watch a Game AI Think: Minimax and Alpha-Beta, in a Browser Tab

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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 →