How to Learn Game-Search Algorithms: Minimax, Alpha–Beta Pruning, Evaluation Functions and Monte Carlo Tree Search

Wait, What?

Looking farther ahead is not automatically better if the game tree grows faster than your computer can search it.

Game-search algorithms study decisions in environments where another player—or chance—changes what happens next. The beginner sees a tree of possible moves. The professional sees a resource-allocation problem over an enormous state space: which branches deserve search, which can be proven irrelevant, when should search stop, how should incomplete positions be evaluated, and when is simulation better than deterministic minimax?

Quick Answer

Learn the topic through the route state → legal actions → successor state → terminal utility → game tree → minimax backup → alpha–beta bounds → move ordering → depth limit → evaluation function → iterative deepening → transposition reuse → chance/expectimax → Monte Carlo rollouts → exploration versus exploitation → MCTS. Trace tiny complete trees first, then introduce pruning and approximate evaluation only after the exact backup rule is secure.

1. Define the Game Before Searching It

A search procedure needs a precise model: the current state, the player to act, the legal actions, the state transition produced by each action, a terminal test and a utility or outcome at terminal states. If these are wrong, a perfect search algorithm optimises the wrong game.

This separates adversarial game search from the existing graph algorithms guide. Both traverse state spaces, but game search must model an opponent whose choices work against the current player’s objective.

2. Minimax Is a Backup Rule, Not a Chess-Specific Trick

In a deterministic two-player zero-sum game, one player chooses moves to maximise utility while the opponent chooses moves to minimise it. Terminal utilities are backed up through the tree: MAX nodes take the maximum child value; MIN nodes take the minimum.

MIT OpenCourseWare presents minimax as the core adversarial-search rule and then develops alpha–beta pruning and progressive deepening. See MIT 6.034: Games, Minimax and Alpha-Beta.

3. Trace a Complete Small Tree Before Pruning

Use a tree only two or three plies deep. Put utilities at every leaf. Ask learners to annotate each internal node with MAX or MIN and calculate values from leaves upward. Then ask a more important question: which child determines the parent’s value, and why?

That question prepares the learner for pruning, because alpha–beta is about proving that some unexplored child cannot change the decision already available.

4. Alpha and Beta Are Bounds on What Still Matters

During depth-first minimax, alpha records the best value MAX can already guarantee along the current path; beta records the best value MIN can already guarantee. When a branch cannot improve the relevant bound, searching deeper into that branch cannot change the final minimax choice.

Alpha–beta pruning therefore returns the same minimax result as full search when implemented correctly. It saves work by proving irrelevance, not by accepting a weaker answer.

5. Pruning Must Be Explained With a Counterfactual

For every pruned branch, ask: “Even if this unexplored subtree contained its best imaginable value, could the ancestor still choose it?” If the answer is no because an ancestor already has a better guaranteed alternative, the cut is safe.

This verbal proof is more valuable than memorising a condition such as alpha >= beta. The symbols should compress an argument the learner can already state.

6. Move Ordering Changes Cost Without Changing Correctness

Alpha–beta becomes much more effective when strong moves are examined early, because useful bounds tighten sooner. Poor move ordering may produce little pruning even though the algorithm is still correct.

This is a professional distinction: two implementations can have the same asymptotic worst-case algorithm and dramatically different practical node counts because one exposes good cutoffs earlier.

7. Real Games Force a Depth Limit

For games such as chess, Go or many planning tasks, the complete tree is too large to reach terminal positions. Search therefore stops at a chosen frontier and uses an evaluation function to estimate position quality.

At this point the algorithm becomes approximate. The quality of the move now depends on both search and evaluation. A deeper search with a poor evaluation can still make poor decisions.

8. An Evaluation Function Is a Model, Not a Terminal Utility

Terminal utility is defined by the game outcome. An evaluation function estimates nonterminal states. It may combine material, position, mobility, threats, territory or domain-specific features. These quantities are evidence about future outcome, not the outcome itself.

This boundary matters because evaluation error can be systematic. A model that rewards immediate material may miss a forced tactical loss just beyond the search horizon.

9. Horizon Effects Show Why “Depth 8” Is Not a Semantic Guarantee

A fixed-depth cutoff can stop at an unstable position where an important consequence lies one move farther away. Techniques such as quiescence search extend selected tactical positions until they become more stable to evaluate.

The professional lesson is that a search depth is a computational budget, not a guarantee that all consequences relevant to the decision have been seen.

10. Iterative Deepening Turns Time Into a Controlled Resource

Iterative deepening searches depth 1, then 2, then 3, and so on. It appears to repeat work, but it provides a usable best move after each completed iteration and supplies move-ordering information for deeper passes. This is valuable when computation has a hard time limit.

11. Transpositions Mean the Game Tree Is Often Really a Graph

Different move sequences may reach the same position. A transposition table caches evaluated states so the same position does not need to be solved repeatedly. That creates new engineering questions: how is a state hashed, what depth was searched, was the stored value exact or only a bound, and what happens when the cache fills?

This is a natural bridge to the existing hash-table learning guide.

12. Chance Nodes Require Expected Values, Not Minimax

If outcomes include randomness—dice, card draws or uncertain transitions—the next state may be selected by a probability distribution rather than an adversarial player. Expectimax-style search backs up expected values at chance nodes.

Do not use MIN to represent randomness. “The worst outcome occurs” and “outcomes occur according to probabilities” are different world models and produce different decisions.

13. Monte Carlo Tree Search Samples Instead of Expanding Everything

When the branching factor is enormous, Monte Carlo Tree Search (MCTS) selectively grows the tree using repeated simulations. A typical cycle performs selection, expansion, simulation or rollout, then backpropagates the observed result.

Berkeley’s CS188 text explains MCTS as combining rollout-based evaluation with selective search for games where exhaustive minimax-style expansion is impractical. See UC Berkeley CS188: Monte Carlo Tree Search. Berkeley’s Fall 2026 CS188 course continues to list game playing among its core AI topics. See CS188 course description and schedule.

14. MCTS Balances Exploitation and Exploration

A search policy should revisit moves that have performed well while still testing moves whose value is uncertain. UCT-style selection formalises this exploration–exploitation balance. Too much exploitation can lock onto an early lucky estimate; too much exploration wastes simulation budget on persistently poor branches.

This differs from randomized algorithms in a useful way: MCTS uses randomness inside an adaptive search process where previous samples change where future samples are spent.

15. Choose the Search Family From the Game Structure

• Full minimax: small deterministic perfect-information trees.
• Alpha–beta: deterministic adversarial trees where useful bounds and move ordering permit pruning.
• Expectimax: models with explicit stochastic outcomes.
• MCTS: very large branching spaces where simulation is meaningful and exhaustive expansion is infeasible.
• Hybrid systems: combine search, domain heuristics, learned evaluation and caching when the workload justifies the complexity.

16. Common Learning Failure States

• Putting MAX or MIN on the wrong player-to-move level.
• Backing values down from the root instead of up from evaluated leaves.
• Pruning because a branch “looks bad” rather than because bounds prove it cannot matter.
• Assuming alpha–beta changes the minimax answer.
• Calling an evaluation score a guaranteed outcome.
• Ignoring transpositions and counting repeated states as unrelated worlds.
• Using MIN to model chance.
• Comparing MCTS agents without controlling simulation budget, rollout policy or randomness.

17. A Scaffold-Fade Learning Ladder

• Level 1: identify states, actions and terminal outcomes in a tiny game.
• Level 2: compute complete minimax values on a two-ply tree.
• Level 3: add alpha and beta annotations without pruning.
• Level 4: justify each safe cutoff verbally.
• Level 5: compare good and poor move ordering by node count.
• Level 6: introduce depth limits and critique an evaluation function.
• Level 7: add iterative deepening and a transposition table.
• Level 8: implement MCTS and analyse how simulation budget changes decision stability.

PRIMM—Predict, Run, Investigate, Modify, Make—is particularly suitable here because learners can predict backed-up values or pruned nodes before running an implementation. The Raspberry Pi Foundation’s current computing pedagogy guidance recommends code reading, tracing and explanation before code writing. See Computing pedagogy at the Raspberry Pi Foundation.

18. Immediate, Delayed and Transfer Checks

• Immediate: compute the minimax value of a small tree.
• Pruning: explain why one subtree can no longer affect the root choice.
• Evaluation: identify a position where a shallow heuristic may be misleading.
• Delayed: reconstruct alpha–beta from the meanings of alpha and beta rather than memorised pseudocode.
• Transfer: decide whether a new environment needs minimax, expectimax, MCTS, ordinary shortest-path search or an online-decision model.

19. AI Assistance Boundary

AI can generate toy game trees, check minimax backups, propose evaluation features and run controlled MCTS experiments. The learner must still define the state and utility correctly, distinguish proof-based pruning from heuristic omission, and validate comparisons under equal computational budgets.

Professional Direction

Advanced study includes aspiration windows, principal-variation search, quiescence, transposition-table replacement policies, endgame databases, expectiminimax, imperfect-information games, information-set MCTS, reinforcement learning, learned policies and value functions, and large-scale parallel search. When benchmarking agents, use the discipline in How Professionals Evaluate Algorithms: control hardware, time, randomness, opponent strength and test positions before claiming superiority.

Algorithm-learning rule: game search is not about seeing every future. It is about spending limited computation where it can still change the decision, while keeping the model of the opponent, chance and evaluation explicit.