Home/Game AI
Search algorithmsCTRL K

Game AI

· 5 algorithms · game tree
Start with Minimax
// gameai

Game AI picks the best move by imagining the opponent’s best reply, and their reply to that. The game tree grows fast; the art is in not exploring all of it.

Five algorithms go from plain minimax to alpha-beta pruning, iterative deepening, expectimax for dice, and Monte Carlo tree search.

START HERE1Minimax
O(b^d)2Alpha-beta pruning
O(b^(d/2))3Iterative deepening
O(b^d)4Expectimax
O(b^d)
Minimax
alpha-beta · b=3 d=4
exploredprunedchosen

All algorithms

5
Each card runs its own algorithm
Minimax
PLAY →

Assume the opponent plays perfectly; pick the move with the best worst case.

AVGO(b^d)
WORSTO(b^d)
SPACEO(d)
Alpha-beta pruning
PLAY →

Minimax that skips branches which cannot change the answer.

AVGO(b^(d/2))
WORSTO(b^d)
SPACEO(d)
Iterative deepening
PLAY →

Search depth 1, 2, 3… until time runs out.

AVGO(b^d)
WORSTO(b^d)
SPACEO(d)
Expectimax
PLAY →

Minimax with chance nodes for dice and cards.

AVGO(b^d)
WORSTO(b^d)
SPACEO(d)
Monte Carlo tree search
PLAY →

Random playouts guide which branches to grow.

AVG—
WORST—
SPACEO(n)