Minimax and Alpha–Beta Pruning

Consider a zero-sum game tree of depth 3 with 8 terminal leaves. The root node is a MAX player. Depth 1 nodes belong to the MIN player, and depth 2 nodes belong to MAX. Let the leaf scores from left to right be: 3, 5, 6, 9, 1, 2, 0, -1.

Experiment

You can try this interactive simulation at Minimax and Alpha-Beta Pruning. Use the Leaf scores input to test different scenarios.

1. Enter comma-separated integers such as -1,0,2,1,9,6,5,3 in the Leaf scores input.
2. Toggle the Pruning checkbox on or off to compare the evaluated leaves.
3. Click Finish: with pruning on this input gives root 5, seven evaluated leaves and one pruned leaf. With Pruning off, Finish gives the same root 5 from eight evaluated leaves. Reset rewinds without changing the input.
4. Use the Step button to watch the depth-first search traverse the tree, and note that when Pruning is enabled, branches are marked with an "X" once α ≥ β is met.