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?

Assigning Endpoint Scores

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

Reach endpoints: The lookahead search produces terminal board positions at the ends of the examined branches.

Apply the value function: Each terminal position receives a numerical score from the value function.

Prepare for backup: These endpoint scores become the information that minimax carries backward through the earlier positions.

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?

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.

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.

Evaluate Candidate B: Between 5 and 4, the opponent's assumed choice gives Candidate B a backed-up score of 4.

Choose at the root: The machine compares the candidate scores 2 and 4 and selects the higher backed-up score.

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?

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?

Assuming that the program must inspect every possible continuation
Samuel's programs performed lookahead over a selected part of the possible game tree, with heuristic search controlling expansion and stopping.
Fix: Ask which part of the tree the heuristic search examines and where it stops.
Choosing the highest score at every tree level
At an opponent decision, minimax assumes the lower score from the machine's perspective.
Fix: Alternate minimization at opponent choices with maximization at machine choices.
Treating an endpoint score as the final score of its candidate move
The useful score of an earlier position is obtained by backing up results from the endpoints according to the assumed player choices.
Fix: Trace the score backward through each intervening decision before comparing candidate moves.
Thinking a cutoff means that the ignored branch has been fully evaluated
A cutoff avoids exploration because the branch cannot affect the decision under the information already available.
Fix: 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)

Practice Answer

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

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.

Back up the second candidate: The lower of 7 and 6 is 6, so the second candidate receives a backed-up score of 6.

Choose at the machine turn: The machine selects the higher of the candidate scores 3 and 6.

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

Search Pipeline

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

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.