Intro to AI Ch. 3 - Adversarial Game Playing

Brief History of AI and Games

1952 - Samuel Checkers Playing Program

1997 - IBM’s Deep Blue beats reigning world champion at chess

2017 - AlphaGO beats world champion at GO

Perfect Opponent Assumption

Each player plays optimally to execute the result that is best in their favor.

Game Tree

A search tree that corresponds to a game. For example, for a board game, nodes denote board configurations and branches indicate how one board configuration can be transformed into another by a single move.

Ply

A turn taken by a player

Complete Move

Consists of 2 ply - a turn is taken by each player

Terminal Test

Goal test

Utility Function

Evaluation function

MiniMax Strategy

MAX is trying to maximize its payoff and MIN is trying to prevent this by minimizing its moves.

Uses a depth-first exploration of a complete game tree

Time and space complexity the same as DFS

Static Evaluation Approach with MiniMax

Cuts off search according to some cut-off test, usually a depth limit. Evaluate the pre-terminal leaf nodes using a static evaluation heuristic (estimates chances of winning from that node).

Static Evaluation Heuristic

Estimates chances of winning from a given node. Must agree with the payoff function at the terminal states. Must not take long to compute. Should be accurate enough.

Quiescent vs. Non-quiescent State

A quiescent state is a stable state - i.e., one in which no captures are possible.

Quiescence Search

Only apply evaluation functions in quiescent positions

Horizon Problem

In a fixed-depth search, damaging moves may be “delayed” beyond the search horizon and not seen. The program may choose moves that seem better at the time but ultimately result in more total damage.

Negative Horizon Effect - MAX may try to avoid a bad situation which is actually inevitable

Positive Horizon Effect - Max may not realize that something good is achievable and and does not make the right choices to realize this possibility

Horizon Problem Solutions

Search until quiescent - extend the normal search to look for quiescent states

Singular extension - If a single move appears considerably better than others, search its sub-tree a little deeper

Progressive Deepening

Iteratively repeat search and continue to increase the lookahead depth until time runs out. Same as Iterative Deepening Search.

Maximizes available time

Alpha-Beta Pruning

Basic idea - if you know halfway through a calculation that it will succeed/fail, you do not have to do the rest of it.

Compute the MiniMax decision without looking at every node and prune away branches that cannot possibly influence the final decision.

Keep track of:

• Alpha - the highest value seen so far on a maximizing level

• Beta - the lowest value seen so far on a minimizing level

When minimizing, do not expand any more daughter nodes once a node has been seen whose evaluation is smaller than Alpha

When maximizing, do not expand any daughter nodes once a node has been seen whose evaluation is greater than Beta

Move Ordering

Used in conjunction with progressive deepening to improve the effectiveness of pruning.

Ex. First search 1-ply deep and record the best path of moves. Then search 1-ply deeper but use the recorded path to influence move ordering

In the best case, complexity goes from O(b^d) to O(b^(d/2))

Transposition Table

A hashtable of previously seen positions, which allows faster searches.