Artificial Intelligence

Adversarial Search

Jesus A. Gonzalez, The University of Texas at Arlington

May 6, 2016

Games

In multiagent environments each agent considers
- The actions of other agents
- How they affect its own welfare
Unpredictability of other agents introduces contingencies into agent’s problem-solving process
Competitive environments
- Agent’s goals in conflict
- Adversarial search problems, known as games
Mathematical game theory, branch of economics
- Views a multi-agent environments as a game
- Impact of each agent on others is significant, regardless of whether agents are coperative or competitive

Games

In Artificial Intelligence most common games are
- Precise rules as in chess, checkers (not as in football and other sports)
- Deterministic
- Fully observable environments
- Two agents act alternately
- Utility values at the end of the game are always equal and oposite (one agent wins and the other looses)

Games

Games are interesting, because they are too difficult to solve, such as chess
- Chess has a branching factor of about 35
- Games go for about 50 moves per player
- Search tree has about \(35^{100}\)
Agents take decisions with limited time

Games

A game is defined as
- \(S_0\): the initial state, specifying how the game is set up
- \(PLAYER(s)\): defines which player has the move in a state
- \(ACTIONS(s)\): returns the set of legal moves in a state
- \(RESULT(s, a)\): the transition model, which defines the result of a move
- \(TERMINAL-TEST(s)\): a terminal test, which is true when the game is over and false otherwise. Statates in which the game is over are terminal states
- \(UTILITY(s, p)\): a utility function, defines the final numeric value for a game that ends in terminal state \(s\) for a player \(p\)

Games

Game tree of a game, defined by the initial state, the ACTIONS function, and the RESULT function
- Nodes are game states
- Edges are moves

Games

ttt example
- Game tree with fewer than 9! = 362,880 terminal nodes (for chess it is \(10^{40}\))
- Can we build the entire game tree?
Search tree
- Tree superimposed on the full game tree
- Examines enough nodes to allow a player take a decision
  - Which move to make?

Optimal Decisions in Games

Adversarial search
- Oponents need a contingent strategy as response to the other player move
- i.e. MAX needs options for each possible response of MIN, at each step
How can we find this strategy?

Optimal Decisions in Games

Minimax decision, The decision that maximizes MAX’s move
- The optimal choice for MAX, the state with the highest minimax value
This definition of optimal play for MAX also assumes optimal play for MIN
- What happens if MIN doesn’t play optimally?

Optimal Decisions in Games

Minimax decision, The decision that maximizes MAX’s move
- The optimal choice for MAX, the state with the highest minimax value
This definition of optimal play for MAX also assumes optimal play for MIN
- What happens if MIN doesn’t play optimally?
  - MAX can do even better!

The minimax Algorithm

The minimax algorithm computes the minimax decision from the current state
Recursive computation of the minimax values of each successor state
- It first obtains the values of the leaf nodes, then uses these values to compute the values of the upper level
Complete depth-first exploration of the game tree
Time complexity: \(O(b^m)\)
- \(m\), the maximum depth of the tree
- \(b\), number of legal moves at each point
Space complexity
- \(O(bm)\), algorithm that generates all actions at once
- \(O(m)\), algorithm that generates actions one at a time

The minimax Algorithm

Optimal Decisions in Multiplayer Games

minimax can be extended for multiple players
- Replace the single value for each node with a vector of values
  - \(\langle v_A, v_B, v_C \rangle\)
  - For leaf nodes, gives utility of the state from each player’s viewpoint
  - In two-player, zero-sum games we use one value (values are always opposite)
  - UTILITY then returns a vector of utilities

Alpha-Beta Pruning

Minimax requires examining an exponential number of game states
- Exponential in the depth of the tree
We can’t eliminate the exponent but can cut it in half
- Compute correct minimax decision without looking at every node in the game tree
- We use pruning
- alpha-beta pruning

Alpha-Beta Pruning

Value of root node (minimax decision) is independent of the values of pruned leaves
Alpha-beta pruning can be applied to trees of any depth
Possible to prune entire subtrees, not only leaves
Alpha-beta pruning principle
- Consider a node \(n\) in the tree, Player has choice of moving to that node
- If Player has better choice \(m\) at parent node of \(n\) or at any point further up, then \(n\) will never be reached in actual play
- We can prune \(n\)
Remember minimax search is depth-first, at any time it considers the nodes along a single path in the tree

Alpha-Beta Pruning

Two parameters that describe bounds on the backed-up values that appear anywhere along the path
- \(\alpha\), is the maximum lower bound of possible solutions
- \(\beta\), is the minimum upper bound of possible solutions
- We consider a node as a possible path to the solution if \(\alpha \leq N \leq \beta\), where \(N\) is the current estimate of the value of the node
- Prune when \(\alpha \geq \beta\)
Updates values of \(\alpha\) and \(\beta\) and prunes branches of a node
- When the value of current node is known to be worse than current \(\alpha\) or \(\beta\) value for MAX or MIN

Move Ordering

Alpha-beta pruning dependent on order in which states are examined
- In case worst successors are generated first
- Minimax: \(O(b^m)\)
- Alpha-beta pruning \(O(b^{m/2})\), with optimal ordering to increase pruning
  - Effective branching factor becomes \(\sqrt(b)\) instead of \(b\)
  - Alpha-beta solves a tree twice as deep as minimax in the same amount of time

Move Ordering

Examine first successors more likely to be best?
- Use heuristics and increase how much we prune
- Trying first moves that were best in the past
- Iterative deepening search to gain information
- Best moves called killer moves, become heuristic

Move Ordering

Repeated states in search tree
- Cause exponential increase in search cost
- Caused by transpositions
  - Reaching the same state from different moves
- Only store evaluation of resulting position in hash table the first time
  - Transposition table

Imperfect Real-Time Decisions

Proposed by Claude Shannon - Programming a Computer for Playing Chess, 1950
- Cut off search earlier
- Apply evaluation function, turn nonterminal nodes into terminal leaves
A change to minimax or alpha-beta
- Replace utility function by heuristic evaluation function EVAL
  - Estimates the position’s utility
- Replace terminal test by a cutoff test
  - Decides when to apply EVAL

Imperfect Real-Time Decisions

Heuristic minimax

Imperfect Real-Time Decisions

Evaluation Function
- Returns an estimate of the expected utility of game from given position
- Performance of game-playing program
- Strongly depends on quality of its evaluation function

Imperfect Real-Time Decisions

Designing Evaluation Functions
- Order terminal states in same way as true utility function
  - Win states better evaluated than drawns, dranws better evaluated than losses
- Computation must not take too long
- Evaluation function of nonterminal states should be correlated with chances of winning
  - Uncertainty because we don’t see the whole search tree
  - We guess about the final outcome

Imperfect Real-Time Decisions

Evaluation functions
- Compute features of the state
  - i.e. Chess: # of white pawns, black pawns, etc.
  - Features together define categories or equivalence classes of states
  - i.e. category of all two-pawn vs. one-pawn end games
  - Some states in caterory will lead to win, drawn, or losses

Imperfect Real-Time Decisions

Evaluation functions
- Compute features of the state (continues…)
  - Evaluation function may return proportion of wins, drawns, and losses
  - i.e. 72% lead to win (1), 20% lead to loss (0), and 8% to drawn (0.5)
  - Expected value: \((0.72 * 1) + (0.20 * 0) + (0.8 * 0.5) = 0.76\)

Imperfect Real-Time Decisions

Cutting off Search
- Modify Alpha-Beta-Search with iterative pruning
  - Call EVAL heuristic when cutting off search:
  - if CUTOFF-TEST(state, depth) then return EVAL(state)
  - Could do with iterative deepening search
  - When time runs out, return move selected by deepest completed search, iterative deepening also helps with move ordering (to know which states evaluated best in the past and increase pruning)
- Apply evaluation function only quiescent positions
  - Unlikely to exhibit wild changes in near future

Stochastic Games

Stochastic games involve unpredictability by including a random element during the game
- Throwing a dice
- Backgammon combines luck and skill

Stochastic Games

We know what the legal moves are
We don’t know what the oponent will roll
Then, we cannot construct a standard game tree (i.e. chess or ttt)
We need chance nodes* plus our MAX and MIN nodes

Stochastic Games

Positions don’t have definite minimax values anymore
Now we need minimax nodes with expected value
- average over all possible outcomes of the chance nodes
Generalize minimax value for deterministic games to an expectiminimax value for games with chance nodes

Stochastic Games

Terminal, MAX and MIN nodes work as before
For chance nodes we compute expected value: sum of value over all outcomes weighted by probability of each chance action
- r represents a possible dice roll
- RESULT(s,r) is the same state as s considering that the result of the dice roll is r

State-of-the-Art Game Programs

Chess: IBM’s Deep Blue
Checkers: CHINOOK, Jonathan Schaeffer
Othello: LOGISTELLO, Buro, 2002
Backgammon: TD-GAMMON, Gerry Tesauro, 1992
Go: MoGo
Bridge: Bridge Baron, Smith et al., 1998; GIB, Ginsberg, 1999
Scrabble, Gordon, 1994; QUACKLE, 2006
Jeopardy: IBM’s Watson