Tic-Tac-Toe Game Tree Map (2D)

Tap a square to play. After every AI move the first two plies of the search tree are drawn: cyan = good for X, orange = good for O, gold = draw, dark red = pruned by alpha-beta, violet = skipped symmetric duplicate.

The science

Game tree. Positions are nodes, legal moves are edges. Counting every call, the full tree has exactly 549,946 nodes (255,168 finished games); there are only 5,478 distinct legal positions.

Minimax. V(s)=max V(child) for X, min for O, and +1/0/-1 at terminals. The opening value is 0: tic-tac-toe is a draw with best play.

Alpha-beta. Keep a window [alpha, beta]; once alpha >= beta the remaining moves cannot change the result and are skipped. Same value as minimax, far fewer nodes - the saving depends strongly on move order.

Symmetry. The square has 8 symmetries, so positions collapse to 765 classes; only one move per class needs expanding.

Check. The self-test compares the measured counts with exact enumeration (5,478 / 765) and the published 549,946, and the exact random-play probabilities (X 58.49 %, draw 12.70 %, O 28.81 %) with 20,000 simulated games.

Simplifications. Only two plies are drawn; deeper levels are counted but not shown. Timings come from your browser and are indicative only. Canvas-only 2D companion of the 3D table version.