For turn-based and board games, the AI must play against a thinking opponent. Learn minimax, alpha-beta pruning, and Monte Carlo Tree Search — the algorithms behind chess, Go, and strategy AI.
In a two-player, turn-based game, minimax assumes both players play optimally: you maximize your score while the opponent minimizes it. The algorithm explores the game tree of possible moves, alternating max and min levels, and backs up the value of the best guaranteed outcome. This is the foundation of classic board-game AI — the way a chess engine reasons about "if I do this, they’ll do that."
def minimax(state, depth, maximizing):
if depth == 0 or state.is_terminal():
return state.evaluate() # heuristic score of this position
if maximizing: # OUR turn -> maximize
best = float("-inf")
for move in state.legal_moves():
best = max(best, minimax(state.apply(move), depth-1, False))
return best
else: # OPPONENT's turn -> minimize
best = float("inf")
for move in state.legal_moves():
best = min(best, minimax(state.apply(move), depth-1, True))
return best
# pick the move whose minimax value is highest -> assumes optimal opponent play.
# depth-limited: search N moves ahead, then use an evaluation heuristic.Minimax explores the whole tree, which is exponential and quickly infeasible. Alpha-beta pruning skips branches that cannot affect the result: once a move is found to be worse than one already guaranteed, its remaining branches are not explored. It returns the same answer as minimax but can search roughly twice as deep in the same time — the optimization that made minimax practical for real chess.
def alphabeta(state, depth, alpha, beta, maximizing):
if depth == 0 or state.is_terminal():
return state.evaluate()
if maximizing:
best = float("-inf")
for move in state.legal_moves():
best = max(best, alphabeta(state.apply(move), depth-1, alpha, beta, False))
alpha = max(alpha, best)
if alpha >= beta:
break # PRUNE: opponent won't allow this branch
return best
else:
best = float("inf")
for move in state.legal_moves():
best = min(best, alphabeta(state.apply(move), depth-1, alpha, beta, True))
beta = min(beta, best)
if beta <= alpha:
break # PRUNE
return best
# same result as minimax, but skips branches that can't change it -> ~2x depth.For games with enormous branching factors (Go) or no good evaluation function, minimax is hopeless. Monte Carlo Tree Search instead builds its tree by running many random playouts to the end and favoring moves that win more often, balancing exploring new moves against exploiting promising ones. MCTS needs no hand-crafted evaluation and, combined with neural networks, powered AlphaGo’s breakthrough.
MCTS — for huge trees / no good evaluation function (Go, complex strategy).
Repeat thousands of times, then play the most-visited move:
1. SELECT from the root, pick child moves (balancing "try new" vs
"exploit good", via UCB1) down to a leaf
2. EXPAND add a new child move to the tree
3. SIMULATE play RANDOM moves from there to the end of the game ("rollout")
4. BACKPROP push the win/loss result back up, updating each node's stats
-> moves that win more rollouts get visited more -> the tree grows toward
strong lines. No hand-crafted evaluation needed.
MCTS + neural networks = AlphaGo. Also used for general game-playing AI.A perfect adversarial AI is often no fun — it crushes the player. In practice you deliberately weaken it: limit search depth, add randomness, occasionally pick a sub-optimal move, or scale difficulty to the player. The goal of game AI is an enjoyable, believable opponent, not an unbeatable one — a design mindset that separates game AI from pure algorithm optimization.
Optimal != fun. A perfect minimax/MCTS opponent just crushes the player.
Tune for ENJOYMENT:
- limit search DEPTH per difficulty (easy = shallow, hard = deep)
- add randomness: sometimes pick the 2nd/3rd-best move
- occasional deliberate mistakes; slower "reaction" at low difficulty
- rubber-banding / dynamic difficulty to match the player
- telegraph intentions so the player can react (believable > invincible)
Game AI's goal is a BELIEVABLE, ENJOYABLE opponent — not an unbeatable one.
That design mindset is what separates game AI from raw algorithm optimization.