Tic-Tac-Toe Game Tree Lab

Tap a square to play. After each AI move the whole search tree (3 plies) grows outward from the board: cyan = good for X, orange = good for O, gold = draw, dark red = pruned away, violet = skipped as a symmetric duplicate.

Presets

Players

X (cyan, moves first)

O (orange)

AI search algorithm

Move ordering: centre, corners, edges first Skip symmetric duplicate moves (8 symmetries) Prefer faster wins (score = 10 - plies) Pick randomly among equally good moves

Display

Nodes per search (log scale)

nodes visited, log₁₀

Last searches

#	Algorithm	Nodes	Cuts	ms

Position

Play a move to see the analysis.

Square markers show what perfect play gives the side to move from each empty square: green = forced win, amber = draw, red = loses. They come from an exact solver over all 5,478 reachable positions, independent of the search being measured.

1 - How big is the game tree?

Search the empty board with every algorithm and count the nodes. Published values: 549,946 nodes for minimax, 5,478 distinct legal positions, 765 up to symmetry.

2 - Random play: exact probability vs measured

If both players pick uniformly random legal moves, the outcome probabilities can be computed exactly by walking the tree. 20,000 simulated games should land within sampling error of them.

3 - How deep must the AI look?

An alpha-beta AI limited to d plies is scored on every reachable position (does it pick a move that keeps the perfect-play result?) and plays 300 games as X against a random O. We also count the nodes it needs for the opening move.

The science

Game tree. Each position is a node and each legal move an edge. From the empty board there are 9 × 8 × 7 × ... move sequences, but games end early when someone completes a line, so the full tree has exactly 549,946 nodes (255,168 complete games).

Minimax. X picks the child with the largest value, O the smallest: V(s) = max V(child) on X's turn, min on O's, and +1 / 0 / -1 for a win / draw / loss at a terminal. The opening value is 0: with best play, tic-tac-toe is a draw.

Alpha-beta. Keep a window [α, β] of values that still matter. As soon as α ≥ β the rest of that node's moves cannot change the result and are skipped. It returns the same value as minimax. The saving depends on move order: in the best case it needs about b^d/2 nodes instead of b^d, so it can search twice as deep in the same time.

Symmetry. The square has 8 symmetries (4 rotations x mirror). Positions related by one have the same value, so only one move per symmetry class is expanded: 5,478 legal positions collapse to 765.

Random play. The exact probabilities are a weighted average over the tree: each of the n legal moves has weight 1/n. This gives X wins 58.49 %, draw 12.70 %, O wins 28.81 %: moving first matters when nobody thinks.

Depth-limited search. At the depth limit a non-terminal position is scored with a heuristic (weighted count of open lines for X minus O, scaled below 1). Shallow search plays plausibly but can miss forks that need 4-5 plies to see.

Simplifications. Node counts include every call to the recursive function (terminals too). Timings are from your browser's JavaScript and only indicative. The 3-ply picture shows the search actually performed; deeper levels are counted but not drawn.