Minimax & Alpha-Beta Pruning Simulator

Visualise minimax game tree evaluation for two-player games and see which branches alpha-beta pruning skips during the search.

Loading minimax simulator...

About This Simulation

The minimax mode of this simulator evaluates a game tree for a two-player game. You can see each MAX and MIN node receive its value as the search backs values up from the leaves to the root.

The alpha-beta mode of this simulator runs minimax with pruning. It tracks α and β at every node and shows which branches are cut off because they cannot change the final decision.

Features

Build or load a game tree with leaf utilities
MAX and MIN levels clearly marked
Values backed up from the leaves step by step
Best move at the root highlighted
α and β values updated at each node
Pruned branches marked on the tree
Same result as plain minimax with fewer nodes visited
Node visit order shown step by step

Topics covered

Minimax Algorithm
Game Trees
Adversarial Search
MAX and MIN Players
Utility Values
Alpha-Beta Pruning
Minimax Optimisation
Alpha and Beta Values
Move Ordering
Game Tree Search

Explanation

Minimax is a decision rule for two-player, zero-sum games such as tic-tac-toe and chess. MAX tries to maximise the score and MIN tries to minimise it, and each assumes the other plays perfectly.

Alpha-beta pruning speeds up minimax by skipping branches that cannot affect the final decision. α is the best value MAX can already guarantee and β is the best value MIN can already guarantee; when α ≥ β, the rest of that node's children are pruned.

How it works

Build the game tree: the root is the current position, and each level alternates between MAX's moves and MIN's moves.
Give every leaf (end position) a utility value, for example +1 for a win, 0 for a draw and −1 for a loss.
At a MIN node, take the minimum value of its children.
At a MAX node, take the maximum value of its children.
The value at the root is the best guaranteed outcome, and the child that produced it is the best move.
Start at the root with α = −∞ and β = +∞, and search the tree depth first.
At a MAX node, update α = max(α, child value) after each child.
At a MIN node, update β = min(β, child value) after each child.
Whenever α ≥ β, stop examining the remaining children of that node: they are pruned.
Pass the current α and β down to each child, and return the node's value up to its parent.

Why it matters

Minimax is the foundation of game-playing AI, from tic-tac-toe programs to chess engines (combined with alpha-beta pruning and evaluation functions). It is a core topic of AI courses such as CSE440, CSE420 and CSE427.

Alpha-beta pruning lets game engines search roughly twice as deep in the same time, which is why it is used in chess and checkers programs. Tracing α and β by hand is a classic exam question in CSE440, CSE420 and CSE427.

Frequently Asked Questions

What is the time complexity of minimax?

O(b^d), where b is the branching factor (moves per position) and d is the depth of the search, because it visits every node in the game tree.

What is the difference between MAX and MIN nodes?

At a MAX node it is the maximising player's turn, so the node takes the largest child value. At a MIN node it is the opponent's turn, so it takes the smallest.

What is a zero-sum game?

A game where one player's gain is exactly the other player's loss, so the total utility is constant. Chess, checkers and tic-tac-toe are zero-sum games.

Does alpha-beta pruning change the result of minimax?

No. It returns exactly the same value and best move as minimax; it only avoids exploring branches that cannot change the answer.

What is the best-case complexity of alpha-beta pruning?

With perfect move ordering it examines O(b^(d/2)) nodes instead of O(b^d), which means it can search about twice as deep in the same time. With the worst ordering, nothing is pruned.

What do alpha and beta represent?

α is the highest value MAX is already guaranteed along the current path, and β is the lowest value MIN is already guaranteed. A branch is pruned when α ≥ β.

Why does move ordering matter in alpha-beta pruning?

If the best moves are searched first, α and β tighten quickly and many more branches are pruned. Engines use heuristics to try promising moves first.

Related Simulations

Artificial Intelligence