CHAPTER 12 — GAME PLAYING

12.1 OVERVIEW
Games have fascinated humans for centuries. The idea that a machine could play games has existed
almost as long as computers themselves. Charles Babbage (1791–1871) thought about programming his
Analytical Engine to play chess.

Why Games Are a Good Domain for AI

• They provide a structured task with easy measurement of success or failure.
• They do NOT require large amounts of general knowledge — just rules and search.

The Search Problem in Chess — Why Simple Search Fails

Chess illustrates why brute-force search is impossible:
Factor Value
Average Branching Factor ~35 legal moves per turn
Average Game Length ~50 moves per player (100 plies total)
Total Positions to Examine 35¹⁰⁰ — astronomically large

📌 Key Takeaway
A program that does a straightforward search of the game tree CANNOT even select its first
move within the lifetime of its opponent.
→ A HEURISTIC SEARCH PROCEDURE is necessary.

Two Ways to Improve a Search-Based System

• Improve the GENERATE procedure — generate only good (plausible) moves, not all legal moves.
• Improve the TEST procedure — recognize and explore the best moves first.

Plausible-Move Generator vs Legal-Move Generator

Legal-Move Generates ALL legal moves at each turn. The test procedure must then
Generator evaluate each of them — too slow.

Plausible-Move Generates only a SMALL SET of promising moves. The test procedure can
Generator spend more time evaluating each, producing more reliable results.
Static Evaluation Function
A heuristic function that estimates the value (goodness) of a board position.
Static Evaluation
Large values indicate positions favourable for us; small/negative values
Function
indicate positions favorable for the opponent. Like h' in the A* algorithm.

The static evaluation function is applied at leaf nodes (terminal positions in the search tree). It estimates
how likely a position is to lead to a win.
A very simple evaluation for chess (proposed by Turing): Compute W/B, where W = sum of white's piece
values and B = sum of black's piece values.
Samuel's more sophisticated approach used a linear combination of several features:
c₁ × pieceadvantage + c₂ × advancement + c₃ × centercontrol + ...

The Credit Assignment Problem

Deciding which moves in a game are actually responsible for the final outcome
Credit Assignment
(win or loss). It is hard because a bad move followed by an opponent mistake
Problem
might still lead to a win — should the bad move get credit?

Two Key Components of a Game-Playing Program

1. A good PLAUSIBLE-MOVE GENERATOR — limits the moves considered to only promising ones.
2. A good STATIC EVALUATION FUNCTION — estimates the value of positions without searching
further.
Both must incorporate a great deal of knowledge about the specific game being played.

📌 Important Note on Search Strategy

For a one-person puzzle, the A* algorithm works well — it searches forward and uses h' to estimate the
best position.
For a TWO-PERSON game, A* alone is NOT adequate — the opponent also gets to choose moves at
alternating levels, and we cannot assume they will help us.
→ The MINIMAX procedure is used instead.

12.2 THE MINIMAX SEARCH PROCEDURE

A depth-first, depth-limited search procedure for two-player games.
The idea: generate positions forward to some depth, apply the static evaluation
Minimax Procedure function to the resulting positions, and back up values to the root. At each level,
the current player either MAXIMIZES (our turn) or MINIMIZES (opponent's turn)
the value.

The Core Idea

3. Start at the current position.
4. Use the plausible-move generator to generate successor positions.
5. Apply the static evaluation function to the leaf positions.
 6. Back up values: at OUR levels, choose the MAXIMUM; at the OPPONENT'S levels, choose the
MINIMUM.
7. The best move is the one that leads to the backed-up value at the root.

One-Ply Search
A is the current position. B, C, D are the possible next positions with evaluation values 8, 3, and −2
respectively. Since we want to MAXIMIZE, we choose B (value 8).
Position Evaluation Action
A (root) — We choose the MAXIMUM of children
B 8 ← BEST (we choose this)
C 3

D -2

Two-Ply Search
We look TWO levels ahead: first our move, then the opponent's response. The opponent will MINIMIZE
the evaluation function.

Children of B: E(9), F(−6), G(0). Opponent minimizes → picks F(−6). So B's backed-up value = −6.
Children of C: H(0), I(−2). Opponent minimizes → picks I(−2). So C's backed-up value = −2.
Children of D: J(−4), K(−3). Opponent minimizes → picks J(−4). So D's backed-up value = −4.
At root A: we MAXIMIZE over {−6, −2, −4} → choose C (value −2). Best move is C.

Level Player Rule

MAXIMIZE — pick highest value among
Root (Ply 0) US
children
MINIMIZE — pick lowest value among
Ply 1 OPPONENT
children
Ply 2 US MAXIMIZE again
Ply 3 OPPONENT MINIMIZE again
 📌 The Name 'Minimax' Explained
The name comes from alternating between MAXIMIZING (our moves) and MINIMIZING (opponent's
moves).
The alternation corresponds to the opposing strategies of the two players.

The MINIMAX Algorithm — Formal Description

The algorithm relies on two auxiliary procedures:
8. MOVEGEN(Position, Player) — Returns a list of successor positions (the plausible-move
generator).
9. STATIC(Position, Player) — Returns a number representing the goodness of Position from
Player's point of view.

The algorithm also uses DEEP-ENOUGH(Position, Depth) which returns TRUE if the search should stop
here, and FALSE otherwise. In a simple implementation, it simply checks if Depth exceeds a cutoff value.

MINIMAX returns TWO results:

• VALUE — the backed-up value of the path it chooses.
• PATH — the path it chooses (the first element is the best next move).

Algorithm: MINIMAX(Position, Depth, Player)

📌 MINIMAX Algorithm Steps

Step 1: If DEEP-ENOUGH(Position, Depth), return VALUE = STATIC(Position, Player),
PATH = nil.
Step 2: Otherwise, call MOVEGEN(Position, Player) to generate SUCCESSORS.
Step 3: If SUCCESSORS is empty (no moves), return the same structure as step 1.
Step 4: For each SUCC in SUCCESSORS:
(a) Set RESULT-SUCC = MINIMAX(SUCC, Depth+1, OPPOSITE(Player))
(b) Set NEW-VALUE = −VALUE(RESULT-SUCC) [negate, to flip perspective]
(c) If NEW-VALUE > BEST-SCORE, update BEST-SCORE and BEST-PATH.
(d) If BEST-SCORE >= USE-THRESH, cut off (alpha-beta, discussed later).
Step 5: Return VALUE = BEST-SCORE, PATH = BEST-PATH.

Initial call (if PLAYER-ONE is to move): MINIMAX(CURRENT, 0, PLAYER-ONE)

The best move is the first element of the returned PATH.

12.3 ADDING ALPHA-BETA CUTOFFS

An optimization of the minimax procedure that eliminates branches that cannot
Alpha-Beta Pruning
possibly affect the final decision. It maintains two threshold values — ALPHA
 (lower bound for the maximizing player) and BETA (upper bound for the
minimizing player) — and prunes branches that go outside these bounds.

Why Alpha-Beta?
Minimax is a depth-first process. Like branch-and-bound in other search problems, we can abandon partial
solutions that are clearly worse than already-known solutions.

Alpha and Beta Values

Value Maintained by Meaning Triggers cutoff when...

A minimizing node finds a

Lower bound — best score the
ALPHA (α) Maximizing player value LESS THAN alpha →
maximizer is guaranteed so far
prune

A maximizing node finds a

Upper bound — best score the
BETA (β) Minimizing player value GREATER THAN beta
minimizer is guaranteed so far
→ prune

Alpha Cutoff Example

After examining node F, we know the opponent is guaranteed a score of −5 or less at C (C is a minimizing
node). But we are already guaranteed a score of 3 if we move to B. So ANY move to C can only make
things worse for us — we prune node G without examining it.

📌 Rule: Alpha Cutoff

Search at a MINIMIZING level is terminated when a value LESS THAN ALPHA (the best score the
maximizer can guarantee from elsewhere) is discovered.
→ The maximizer will NEVER choose to go through this minimizing node, so further children are
irrelevant.

Beta Cutoff Example

At a maximizing level, if we discover a value GREATER THAN BETA (the best score the minimizer can
guarantee from elsewhere), the minimizer will never allow us to reach this node. So we can prune
immediately.

📌 Rule: Beta Cutoff

Search at a MAXIMIZING level is terminated when a value GREATER THAN BETA is
found.
 → The minimizer will NEVER choose to go through this maximizing node.

USE-THRESH and PASS-THRESH

To write a single procedure (not two separate ones for maximizing and minimizing levels), MINIMAX uses:
Variable Purpose
The threshold used at the CURRENT level to decide cutoffs. At maximizing
USE-THRESH
levels, this is alpha; at minimizing levels, this is beta.
Passed to the NEXT level as its USE-THRESH. Both are NEGATED each time
PASS-THRESH
they cross a level (because STATIC values are negated when passed up).

Algorithm: MINIMAX-A-B(Position, Depth, Player, Use-Thresh, Pass-Thresh)

📌 MINIMAX-A-B Algorithm Steps

Step 1: If DEEP-ENOUGH, return STATIC(Position, Player), PATH = nil.
Step 2: Generate SUCCESSORS via MOVE-GEN(Position, Player).
Step 3: If SUCCESSORS empty, return same as Step 1.
Step 4: For each SUCC in SUCCESSORS:
(a) RESULT-SUCC = MINIMAX-A-B(SUCC, Depth+1, OPPOSITE(Player), -Pass-Thresh, -Use-
Thresh)
(b) NEW-VALUE = -VALUE(RESULT-SUCC)
(c) If NEW-VALUE > Pass-Thresh: update Pass-Thresh, update BEST-PATH.
(d) If Pass-Thresh >= Use-Thresh: PRUNE — return immediately with Pass-Thresh.
Step 5: Return VALUE = Pass-Thresh, PATH = BEST-PATH.

Initial call: MINIMAX-A-B(CURRENT, 0, PLAYER-ONE, max_STATIC_value, min_STATIC_value)

Effectiveness of Alpha-Beta
The effectiveness depends heavily on the ORDER in which paths are examined.
• WORST CASE (worst paths examined first): No cutoffs occur at all — same as plain minimax.
 • BEST CASE (best paths examined first): The number of terminal nodes examined at depth d
equals approximately twice the nodes examined by minimax at depth d/2.
• Practical implication: Alpha-beta effectively DOUBLES the search depth achievable in the same
time compared to plain minimax!

Futility Cutoff
Terminating the exploration of a subtree that offers only marginal improvement
over already-known paths. For example, if exploring subtree C can give at most
Futility Cutoff
3.2, and we already have a guaranteed score of 3 from subtree B, the tiny gain
from C does not justify further exploration.

12.4 ADDITIONAL REFINEMENTS

Several more techniques further improve game-playing programs beyond alpha-beta pruning:

12.4.1 Waiting for Quiescence

A stable state of the game where no drastic changes occur from one ply to the
Quiescence next. The search should continue until quiescence is reached before applying
the static evaluation function.

The Problem: In the middle of a piece exchange in chess, if we stop the search after our capture but before
the opponent's recapture, the static evaluation function will overestimate our position dramatically. This
misleads the search.

The Solution: Continue searching until the board position is 'calm' — no major exchanges or threats are
pending. This is called waiting for quiescence.

Horizon Effect
An inevitable bad event (like losing a piece) can sometimes be delayed by tactics
Horizon Effect until it goes beyond the depth of the minimax search — making a bad position
look good to the algorithm.

Waiting for quiescence HELPS reduce the horizon effect but does not eliminate it completely. All fixed-
depth search programs are still subject to subtle horizon effects.

12.4.2 Secondary Search

After the main minimax search selects the best move, a deeper search is
Secondary Search conducted specifically on that move's branch to verify there is no hidden pitfall
lurking beyond the original search depth.

Example: If the main search goes 6 ply deep, the secondary search explores the best single branch an
additional 2 levels (to 8 ply), which is much cheaper than searching ALL branches to 8 ply.
Singular Extensions
A form of secondary search where, if a leaf node is judged far superior to all its
siblings, the node is expanded one extra ply. This allows the search to
Singular Extensions
concentrate on tactically interesting, forcing lines of play without needing
additional domain knowledge.

Used effectively by the DEEP THOUGHT chess computer (Anantharaman et al., 1990) to find mating
combinations up to 37 moves deep — impossible for fixed-depth minimax.

12.4.3 Using Book Moves

Precomputed lists of optimal opening and endgame moves stored in a
database (a 'book'). The program looks up the current position in the book
Book Moves
instead of searching, dramatically improving performance in highly stylized
game phases.

In chess, both opening sequences and endgame sequences are highly stylized and well-studied. Using
book moves for these phases, combined with minimax search for the middle game, combines the best of
both knowledge-based and search-based approaches.

12.4.4 Alternatives to Minimax

Minimax has some weaknesses:
• It assumes the opponent ALWAYS plays optimally. In a losing situation, it might be better to
choose a move that leads to a worse guaranteed outcome but gives the opponent more chances
to make a mistake.
• It cannot distinguish between a move that is slightly better assuming perfect play, and a move that
could be much better if the opponent makes a single error.

To make optimal decisions, we would need a model of the specific opponent's playing style — very hard
to obtain in practice.

📌 Theoretical Problem with Minimax

Nau (1980) and Pearl (1983) showed that for certain game trees (uniform trees with random terminal
values), the DEEPER the search, the WORSE the result from minimax.
However, this 'pathological' behavior has NOT been observed in actual game-playing programs, which
use non-random heuristic estimates and non-uniform tree structures.

12.5 ITERATIVE DEEPENING

A search strategy that repeatedly performs depth-first searches with increasing
Iterative Deepening depth limits: first to depth 1, then depth 2, then depth 3, and so on, until time runs
out. The best move from the previous iteration guides move ordering in the next.
Why Not Just Search to the Final Depth?
• Game-playing programs have TIME CONSTRAINTS (e.g., 2 hours for an entire chess game).
• With a fixed-depth search, it is impossible to predict in advance how long it will take due to
variations in pruning efficiency.
• With iterative deepening, the search can be ABORTED AT ANY TIME and the best move found
by the PREVIOUS iteration can be played.

Why Isn't Iterative Deepening Wasteful?

It might seem that redoing shallow searches is wasteful. But consider: in a complete tree of branching
factor b, the number of nodes at level n is approximately equal to the number of nodes at ALL previous
levels combined. So the last iteration dominates the total work, making earlier iterations negligible.

📌 Efficiency of Iterative Deepening

DFID is only slower than pure depth-first search by a CONSTANT FACTOR.
The benefit of better move ordering (from previous iterations enabling better alpha-beta pruning) MORE
than compensates for this overhead.

Move Ordering Benefit

If a move was judged superior to its siblings in iteration N, it is searched FIRST in iteration N+1. With
effective ordering, alpha-beta can prune many more branches, drastically reducing total search time and
allowing deeper searches.

Depth-First Iterative Deepening (DFID) Algorithm

📌 DFID Algorithm
Step 1: Set SEARCH-DEPTH = 1.
Step 2: Conduct a depth-first search to depth SEARCH-DEPTH. If a solution is found, return it.
Step 3: Otherwise, increment SEARCH-DEPTH by 1 and go to Step 2.

DFID finds the shortest solution path. The maximum memory used is proportional to the number of nodes
in the solution path (not the entire tree).

Iterative Deepening A* (IDA*)

Combines iterative deepening with the A* heuristic. Instead of a depth limit, it
uses a COST THRESHOLD (g + h'). If the cost of a path exceeds the threshold,
IDA*
the path is pruned. On each iteration, the threshold is increased to the minimum
excess found in the previous iteration.

• IDA* is GUARANTEED to find an optimal solution (like A*) if h' is admissible.

• IDA* is very MEMORY EFFICIENT because it uses depth-first search internally.
• IDA* was the first algorithm to solve the 15-puzzle (a 4×4 version of the 8-puzzle) optimally within
reasonable time and space.
•
 12.6 REFERENCES ON SPECIFIC GAMES
Different games require different balances of search and knowledge:

Game Key Challenge Approach Notable Programs

Huge branching factor Deep search + opening/endgame

Chess HITECH, DEEP THOUGHT
(~35), but structured books + singular extensions

Simpler than chess; Search + machine learning to

Checkers Samuel's program (1963)
learning is key improve evaluation
Enormous branching
Heavy knowledge-based; brute Knowledge-intensive
Go factor; pattern
force fails programs
recognition critical

Incomplete info (dice); Mostly knowledge-intensive; BKG (Berliner),

Backgammon
large alternatives per ply neural networks NEUROGAMMON

8×8 grid; computers

Various champion-level
Othello exceed human Brute-force search + table lookup
programs
performance

Chess — Key Points

• Research on computer chess predates AI as a field. Shannon (1950) was the first to propose
automating the game.
• Trade-off: More knowledge → less searching needed. More searching → less knowledge needed.
• Human chess players use a great deal of knowledge but examine very few branches (~100).
• Computers examine millions of branches but have limited knowledge (mainly in the static
evaluation function).
• Recent trend: Away from knowledge, toward faster brute-force search (full-width search with
pruning).
• HITECH and DEEP THOUGHT use custom-built parallel hardware to speed up move generation
and heuristic evaluation, and have beaten human grandmasters.

Backgammon — Key Points

• Unlike chess, a backgammon program must choose moves with INCOMPLETE INFORMATION
(dice rolls introduce randomness).
• With all possible dice rolls, the number of alternatives at each level is huge — cannot search
many ply ahead.
• BKG (Berliner, 1980) does NO searching at all — relies entirely on positional understanding and
knowledge.
• NEUROGAMMON (Tesauro & Sejnowski, 1989) uses a neural network that learns from
experience — one of the few competitive game programs relying on automatic learning.

Othello — Key Points

 • Computer programs have achieved world-championship level play (Rosenbloom, 1982; Lee and
Mahajan, 1990).
• Computers are NOT permitted to compete in international tournaments.
• High-performance Othello programs rely on fast brute-force search and table lookup.

CHAPTER SUMMARY — QUICK REVISION TABLE

Concept Key Idea Section
Games provide structured tasks with easy success/failure
Game Playing in AI 12.1
measurement. Search + knowledge both required.
Chess: branching factor 35, 100 plies → 35¹⁰⁰ positions. Impossible to
Why not brute force? 12.1
search completely.
Static Evaluation Function Heuristic that estimates board position value. Applied at leaf nodes. 12.1
Credit Assignment Hard to decide which moves caused a win or loss in a sequence of
12.1
Problem moves.
Depth-first search alternating MAX (our turn) and MIN (opponent's
Minimax 12.2
turn) at each level.
Alpha Cutoff Prune minimizing subtrees where value < current best for maximizer. 12.3
Beta Cutoff Prune maximizing subtrees where value > current best for minimizer. 12.3
Prune subtrees that offer only marginal improvement over known
Futility Cutoff 12.3
paths.
Quiescence Continue search until board is stable before applying static evaluation. 12.4.1
Bad event delayed past search horizon makes a position appear
Horizon Effect 12.4.1
better than it is.
Secondary Search Extra search on the chosen branch to verify no hidden pitfall exists. 12.4.2
Singular Extensions Expand leaf nodes that are far superior to siblings by one extra ply. 12.4.2
Precomputed opening/endgame move databases to avoid searching
Book Moves 12.4.3
highly stylized positions.
Repeat depth-first searches at increasing depths; abort anytime and
Iterative Deepening 12.5
use last result.
DFID Optimal and space-efficient uninformed iterative deepening. 12.5
Iterative deepening with A* cost threshold. Finds optimal path with
IDA* 12.5
minimal memory.
 QUESTION BANK WITH ANSWERS
SHORT ANSWER QUESTIONS (2–4 marks)

Q: Why is game playing considered a good domain for exploring machine intelligence?
A: Game playing provides structured tasks with very easy measurement of success or failure
(win/lose/draw). Initially it was also thought they could be solved without large amounts of knowledge
using straightforward search.

Q: Why can't a chess program simply search the entire game tree?
A: With an average branching factor of 35 and each player making ~50 moves, the game tree has
approximately 35¹⁰⁰ positions. This is astronomically large, so a program doing a complete search could
not even select its first move within the lifetime of its opponent.

Q: What is a static evaluation function? Give an example.

A: A static evaluation function estimates the goodness of a board position by returning a numerical value
— large positive values favor us, large negative values favor the opponent. A simple example for chess:
compute W/B, where W = sum of white's piece values and B = sum of black's piece values.

Q: What is the credit assignment problem?

A: The credit assignment problem is the difficulty of deciding which moves in a series of actions are
actually responsible for a final outcome (win or loss). For example, a bad move might be followed by an
opponent mistake that leads to a win — should the bad move get credit for the win? This problem makes
it hard to build effective learning mechanisms.

Q: What is the difference between a legal-move generator and a plausible-move generator?

A: A legal-move generator produces ALL legal moves at each turn. A plausible-move generator
produces only a small set of PROMISING moves. The plausible-move generator is better because the
test procedure can spend more time evaluating fewer moves, producing more reliable results.

Q: What are the two important knowledge-based components of a game-playing program?

A: 1) A good plausible-move generator — restricts moves to only promising ones. 2) A good static
evaluation function — estimates position quality without searching further. Both must incorporate deep
knowledge of the specific game.

Q: What is meant by 'ply' in game playing?

A: A 'ply' refers to one move by one player. So a two-ply search means we look ahead one move by us
and one move by the opponent. The term comes from the game-playing literature.
MEDIUM ANSWER QUESTIONS (5–8 marks)

Q: Explain the minimax procedure with an example.

A: The minimax procedure is a depth-first, depth-limited search for two-player games. It alternates
between MAXIMIZING (our turn) and MINIMIZING (opponent's turn) at each level. Values are
computed at leaf nodes using the static evaluation function and backed up the tree. At maximizing
levels, the maximum child value is chosen; at minimizing levels, the minimum is chosen. Example: At
depth 2, suppose leaf values are E=9, F=−6, G=0 (under B) and H=0, I=−2 (under C). The opponent
minimizes: B gets −6, C gets −2. We maximize: choose C (−2 is better than −6). So our best move is
C.

Q: Explain the concept of alpha-beta pruning. How does it improve minimax?

A: Alpha-beta pruning eliminates branches from the minimax tree that cannot affect the final decision.
Two threshold values are maintained: ALPHA (lower bound for the maximizing player, updated at
maximizing levels) and BETA (upper bound for the minimizing player, updated at minimizing levels).
Alpha cutoff: At a minimizing level, if a value less than alpha is found, prune — the maximizer will
never choose this path. Beta cutoff: At a maximizing level, if a value greater than beta is found, prune
— the minimizer will never allow us here. Benefit: In the best case (perfect ordering), alpha-beta
effectively doubles the search depth achievable in the same time compared to plain minimax, since it
examines roughly the square root of the nodes minimax would examine.

Q: What is the horizon effect and how does quiescence help?

A: The horizon effect occurs when a program delays an inevitable bad event (like losing a piece)
through tactics until the event falls beyond the depth of the search tree. The program then evaluates
the position as if the bad event will never happen, leading to poor decisions. Quiescence search
addresses this by continuing the search beyond the normal depth limit until the board reaches a
stable ('quiescent') state — no major exchanges or threats pending. This ensures the static
evaluation function is applied only to calm positions, reducing misleading evaluations.

Q: Explain iterative deepening. Why is it not as wasteful as it first appears?

A: Iterative deepening performs a series of depth-first searches with increasing depth limits (1, 2, 3,
...) until time runs out. The best move from each iteration guides move ordering in the next. It seems
wasteful because earlier iterations are redone. However, in a tree with branching factor b, the number
of nodes at level n approximately equals all nodes at levels 1 through n−1 combined. So the final
iteration dominates total work, and earlier iterations add only a small constant overhead. The benefit
— always having a best move available to play at any moment, plus better move ordering enabling
better alpha-beta pruning — more than compensates.

Q: What is IDA* and how does it differ from iterative deepening?

A: IDA* (Iterative Deepening A*) combines iterative deepening with the A* heuristic. Instead of a
depth cutoff, it uses a COST THRESHOLD based on g + h' (cost so far + heuristic estimate).
Branches are pruned when their cost exceeds the threshold. Each iteration, the threshold is
increased by the minimum amount it was exceeded previously. IDA* differs from DFID: DFID is
uninformed (uses only depth); IDA* is informed (uses a heuristic h'). IDA* guarantees an optimal
 solution (like A*) if h' is admissible, while being very memory-efficient (uses depth-first search
internally).

LONG ANSWER (10–15 marks)

Q: Describe the complete MINIMAX algorithm in detail. Explain how it handles two-player
games differently from single-player search.
A: The MINIMAX algorithm is a depth-first, depth-limited recursive procedure. It relies on two auxiliary
procedures: MOVEGEN(Position, Player) which generates successor positions, and
STATIC(Position, Player) which evaluates a position. The recursion stops when DEEP-
ENOUGH(Position, Depth) returns TRUE. At that point, VALUE = STATIC(Position, Player) and
PATH = nil. Otherwise, MOVEGEN is called to get SUCCESSORS. If SUCCESSORS is empty, the
same leaf value is returned. Otherwise, for each successor, MINIMAX is called recursively with the
OPPOSITE player and depth+1. The returned value is NEGATED to reflect the switch in perspective.
The best result (highest negated value) is recorded along with the path. The key difference from
single-player search: In single-player search (like A*), we always choose the best move. In two-player
search, the opponent chooses moves at alternating levels, and the opponent's goal is opposite to
ours. MINIMAX accounts for this by alternating MAX and MIN decisions at each level, always
assuming the opponent plays optimally.

Q: Explain with diagrams all the refinements to minimax: alpha-beta cutoffs, quiescence,
secondary search, book moves, and iterative deepening. How do they collectively improve
game-playing performance?
A: Alpha-Beta Cutoffs: Maintains ALPHA (best guaranteed score for maximizer) and BETA (best
guaranteed score for minimizer). Prunes branches where: (a) at a minimizing level, value < alpha —
maximizer will never choose this, OR (b) at a maximizing level, value > beta — minimizer will never
allow this. Benefit: Best case doubles search depth. Quiescence: Extends search beyond normal
depth limit until board position is stable (no major exchanges pending). Prevents the static evaluation
function from being applied during unstable tactical sequences. Reduces horizon effect. Secondary
Search / Singular Extensions: After main search, the best-move branch is searched an additional few
plies to confirm no hidden pitfall. Singular extensions expand nodes that are far superior to siblings by
one extra ply, allowing the search to find deep tactical combinations. Book Moves: Precomputed
opening and endgame move databases bypass the need to search these highly stylized phases
entirely. Combined with minimax for the middle game, this gives the best of both knowledge and
search. Iterative Deepening: Repeats depth-first searches at increasing depths. The program always
has a valid best move to play (from the last completed iteration), and move ordering information from
previous iterations dramatically improves alpha-beta pruning. Together, these refinements transform
a simple minimax into a powerful, practical game-playing engine.

Q: Compare the game-playing approaches for Chess, Go, Backgammon, and Othello. What
makes each game unique from an AI perspective?
A: Chess: Deterministic, perfect information game. Branching factor ~35. Computers can search
millions of branches. Key challenge: combining deep search with good evaluation functions. Recent
trend: full-width brute-force search (HITECH, DEEP THOUGHT). Computers have beaten
grandmasters. Go: Deterministic, perfect information, but enormous branching factor (hundreds of
moves per turn). Brute-force search is ineffective. Human players use pattern recognition and deep
positional knowledge. AI programs must also be heavily knowledge-based. Backgammon: Non-
deterministic (dice rolls), so incomplete information about what will happen. The huge number of
alternatives makes deep search impossible. Programs like BKG use no search at all, relying entirely
on positional understanding. NEUROGAMMON uses neural networks and automatic learning — one
of the few examples. Othello: Played on 8×8 grid. Computers have surpassed human world
champions. Programs rely on fast brute-force search and table lookup. This suggests that in games
where computers are strongest, knowledge matters less and raw search power dominates. Key
insight: The balance between search and knowledge varies dramatically by game. More knowledge
→ less search needed; more search power → less knowledge needed.

GLOSSARY OF KEY TERMS

An optimization of minimax that prunes branches using two threshold values
Alpha-Beta Pruning
(alpha and beta) to eliminate moves that cannot affect the final decision.

The lower bound maintained by the maximizing player. Any minimizing node
Alpha (α)
yielding a value below alpha is pruned.

The upper bound maintained by the minimizing player. Any maximizing node
Beta (β)
yielding a value above beta is pruned.

Precomputed optimal moves for opening and endgame phases of a game,

Book Moves
stored in a database and used to bypass search.

Credit Assignment The difficulty of determining which actions in a sequence caused a particular
Problem outcome.

Depth-First Iterative Deepening. Combines depth-first efficiency with breadth-

DFID
first optimality guarantees. Optimal for uninformed search.

A function used in MINIMAX to decide when to stop recursing and apply the
Deep-Enough
static evaluation function.

Pruning a subtree that offers only marginal improvement over an already-

Futility Cutoff
known path.

The illusion that a bad event will not happen because it lies beyond the search's
Horizon Effect
depth limit.
 Iterative Deepening A*. Uses an increasing cost threshold (g + h') instead of
IDA*
depth, guaranteeing optimal solutions with low memory use.

Repeated depth-first searches with increasing depth limits, always having a

Iterative Deepening
best move available if time runs out.

Legal-Move Generates all legally valid moves from a position.

Generator

A depth-first search for two-player games that alternates maximizing (our turn)
Minimax Procedure
and minimizing (opponent's turn) at each level.

Plausible-Move Generates only a small set of promising moves, allowing the evaluator to spend
Generator more time on each.

Ply One move by one player in game-playing terminology.

A stable board state with no major pending exchanges or threats. The static
Quiescence
evaluation function should only be applied at quiescent positions.

A deeper search on the selected best-move branch after the main search, to
Secondary Search
verify there is no hidden pitfall.

A form of secondary search that expands nodes that are far superior to their
Singular Extensions
siblings by one extra ply.

Static Evaluation A heuristic function that estimates the goodness of a board position without
Function further searching.