Game-Playing Programs and Lookahead Search

Heuristic search decides how much of the possible game tree to examine.

Programming

From Board to Search Tree

A game-playing program does not need to inspect every possible continuation before choosing a move. Samuel's checkers programs began with the current board position, searched outward through selected possible moves, and used the results to choose a move. The central control problem was deciding how the game tree should grow and when the search should stop.

How do possible moves become the positions examined by a lookahead search?

Controlling Expansion and Stopping

Heuristic search decides how much of the possible game tree to examine. It determines which positions are expanded into further possible moves and where expansion ends. The search therefore examines a selected part of the tree rather than treating every possible continuation as equally necessary.

Which game-tree branches are expanded, and where does heuristic search stop examining possible moves?

Scoring the Search Endpoints

When the search reaches terminal board positions, a value function supplies numerical scores for them. Samuel's programs used a value function also described as a scoring polynomial. The source describes this evaluation as using linear function approximation. The search produces positions to assess; the value function supplies the scores used in the later decision process.

How is a terminal board position transformed into a numerical value representing its desirability?

Worked example

Assigning Endpoint Scores

Suppose a selected search reaches four terminal positions. The value function gives them the scores 6, 2, 5, and 4.

1
Reach endpoints
The lookahead search produces terminal board positions at the ends of the examined branches.
2
Apply the value function
Each terminal position receives a numerical score from the value function.
3
Prepare for backup
These endpoint scores become the information that minimax carries backward through the earlier positions.

Result

The endpoint scores are 6, 2, 5, and 4. They are starting values for backward minimax reasoning, not necessarily the final scores of the candidate moves.

Backing Values Through Minimax

Minimax works backward from the scored endpoints. At an opponent decision, the program assumes that the opponent chooses the lower score from the machine's perspective. At a machine decision, it chooses the higher score. The procedure therefore alternates between minimizing and maximizing rather than selecting the highest number at every level.

How do evaluated terminal positions propagate backward through alternating maximizing and minimizing turns to determine the best move?

Worked example

A Two-Move Minimax Trace

The current position has two candidate moves. Candidate A allows endpoint scores 6 and 2 after possible opponent responses. Candidate B allows endpoint scores 5 and 4.

1
Evaluate Candidate A
The opponent is assumed to choose the lower score from the machine's perspective. Between 6 and 2, the backed-up score for Candidate A is 2.
2
Evaluate Candidate B
Between 5 and 4, the opponent's assumed choice gives Candidate B a backed-up score of 4.
3
Choose at the root
The machine compares the candidate scores 2 and 4 and selects the higher backed-up score.

Result

Candidate B is selected under this generated illustration because its backed-up score is 4, which is higher than Candidate A's score of 2.

What does a score mean as it moves from a lower board position to the parent positions and eventually to the candidate move?

Definition

A backed-up score is the best assumed result carried backward from searched endpoints to an earlier position, using minimization at the opponent's choices and maximization at the machine's choices.

How do the two players' different choices at successive levels determine which child value is selected?

Avoiding Irrelevant Exploration

Some branches do not need to be explored once earlier information shows that their outcome cannot affect the decision. Some versions of Samuel's programs used sophisticated search-control methods analogous to alpha-beta cutoffs. Their purpose was to optimize the search by avoiding certain unnecessary explorations while preserving the decision supported by the search.

How can the search stop exploring a branch once its value cannot affect the final move choice?

Common mistake
Assuming that the program must inspect every possible continuation
What it looks like
Treating the entire game tree as something the program must fully enumerate before moving
Why it fails
Samuel's programs performed lookahead over a selected part of the possible game tree, with heuristic search controlling expansion and stopping.
Do this instead
Ask which part of the tree the heuristic search examines and where it stops.
Common mistake
Choosing the highest score at every tree level
What it looks like
Selecting 6 instead of 2 when the opponent can choose between endpoint scores 6 and 2
Why it fails
At an opponent decision, minimax assumes the lower score from the machine's perspective.
Do this instead
Alternate minimization at opponent choices with maximization at machine choices.
Common mistake
Treating an endpoint score as the final score of its candidate move
What it looks like
Calling the endpoint score 6 the score of Candidate A without considering the opponent's other response
Why it fails
The useful score of an earlier position is obtained by backing up results from the endpoints according to the assumed player choices.
Do this instead
Trace the score backward through each intervening decision before comparing candidate moves.
Common mistake
Thinking a cutoff means that the ignored branch has been fully evaluated
What it looks like
Claiming that a skipped branch has a precisely known final score
Why it fails
A cutoff avoids exploration because the branch cannot affect the decision under the information already available.
Do this instead
Describe the cutoff as eliminating unnecessary search, not as producing an additional endpoint evaluation.

Practice the Trace

MEDIUM

A machine has two candidate moves. After the opponent's possible responses, the first candidate reaches endpoint scores 8 and 3. The second reaches endpoint scores 7 and 6. Using the minimax viewpoint described in this article, determine the backed-up score for each candidate and identify which candidate the machine selects.

Hints

At each opponent decision, select the lower score from the machine's perspective.
At the current machine decision, compare the candidate scores and select the higher one.

Your attempt (not saved)

Worked example

Practice Answer

The first candidate reaches endpoint scores 8 and 3. The second reaches endpoint scores 7 and 6.

1
Back up the first candidate
The opponent is assumed to select the lower score, so the first candidate receives a backed-up score of 3.
2
Back up the second candidate
The lower of 7 and 6 is 6, so the second candidate receives a backed-up score of 6.
3
Choose at the machine turn
The machine selects the higher of the candidate scores 3 and 6.

Result

The second candidate is selected, with a backed-up score of 6.

Search Pipeline

1
Begin with the current board position as the root of the game tree.
2
Use heuristic search to decide which positions to expand and where to stop.
3
Apply a value function to the terminal board positions reached by the search.
4
Work backward through the tree with minimax: minimize at opponent choices and maximize at machine choices.
5
Carry the best assumed result to earlier positions as a backed-up score.
6
Use alpha-beta-like search control in some versions to avoid explorations that cannot affect the supported decision.

Key point

The final move is not chosen directly from the first endpoint score encountered. It is chosen after heuristic search selects a portion of the tree, a value function scores the endpoints, and minimax backs those scores up through alternating machine and opponent decisions.

Key Takeaways

Heuristic search controls both how a game tree expands and where the search stops.
A value function supplies numerical scores for terminal board positions reached by the search.
Minimax works backward, minimizing at opponent choices and maximizing at machine choices.
A backed-up score is the best assumed result carried from searched endpoints toward the current position.
Alpha-beta-like cutoffs can avoid unnecessary branch exploration while preserving the decision supported by the search.

More concepts starting with G