Cs 171 07a Games MiniMax

Game-Playing & Adversarial Search
MiniMax, Search Cut-off, Heuristic Evaluation

This lecture topic:
(MiniMax, Search Cut-off, Heuristic Evaluation)
Read Chapter 5.1-5.2, 5.4.1-2, (5.4.3-4, 5.8)
Next lecture topic:
(Alpha-Beta Pruning, [Stochastic Games])
Read Chapter 5.3, (5.5)
(Please read lecture topic material before
and after each lecture on that topic)
You Will Be Expected to Know

Basic definitions (section 5.1)
Minimax optimal game search (5.2)
Evaluation functions (5.4.1)
Cutting off search (5.4.2)
Optional: Sections 5.4.3-4; 5.8
Types of Games
battleship
Kriegspiel
Not Considered:
Physical games like tennis, croquet, ice hockey, etc.
(but see robot soccer http://www.robocup.org/)
Typical assumptions
Two agents whose actions alternate
Utility values for each agent are the opposite of the other
This creates the adversarial situation
Fully observable environments
In game theory terms:
Deterministic, turn-taking, zero-sum, perfect information
Generalizes: stochastic, multiple players, non zero-sum, etc.
Compare to, e.g., Prisoners Dilemma (p. 666-668, R&N)
NON-turn-taking, NON-zero-sum, IMperfect information
Game tree (2-player, deterministic, turns)
How do we search this tree to find the optimal move?
Search versus Games

Search no adversary
Solution is (heuristic) method for finding goal
Heuristics and CSP techniques can find optimal solution
Evaluation function: estimate of cost from start to goal through given
node
Examples: path planning, scheduling activities
Games adversary
Solution is strategy
strategy specifies move for every possible opponent reply.
Time limits force an approximate solution
Evaluation function: evaluate goodness of game position
Examples: chess, checkers, Othello, backgammon
Games as Search
Two players: MAX and MIN
MAX moves first and they take turns until the game is over
Winner gets reward, loser gets penalty.
Zero sum means the sum of the reward and the penalty is a constant.
Formal definition as a search problem:
Initial state: Set-up specified by the rules, e.g., initial board set-up of chess.
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): Transition model defines the result of a move.
Terminal-Test(s): Is the game finished? True if finished, false otherwise.
Utility function(s,p): Gives numerical value of terminal state s for player p.
E.g., win (+1), lose (-1), and draw (0) in tic-tac-toe.
E.g., win (+1), lose (0), and draw (1/2) in chess.
MAX uses search tree to determine best next move.
An optimal procedure:
The Min-Max method
Will find the optimal strategy and best next move for Max:
1. Generate the whole game tree, down to the leaves.
2. Apply utility (payoff) function to each leaf.
3. Back-up values from leaves through branch nodes:
a Max node computes the Max of its child values
a Min node computes the Min of its child values
4. At root: Choose move leading to the child of highest value.
Two-ply Game Tree
Two-Ply Game Tree
Two-Ply Game Tree
Two-Ply Game Tree

Minimax maximizes the utility of
the worst-case outcome for Max
The minimax decision
Pseudocode for Minimax Algorithm

function MINIMAX-DECISION(state) returns an action
inputs: state, current state in game
return arg maxaACTIONS(state) MIN-VALUE(Result(state,a))
function MAX-VALUE(state) returns a utility value
if TERMINAL-TEST(state) then return UTILITY(state)
v
for a in ACTIONS(state) do
v MAX(v,MIN-VALUE(Result(state,a)))
return v
function MIN-VALUE(state) returns a utility value
if TERMINAL-TEST(state) then return UTILITY(state)
v +
for a in ACTIONS(state) do
v MIN(v,MAX-VALUE(Result(state,a)))
return v
Properties of minimax
Complete?
Yes (if tree is finite).
Optimal?
Yes (against an optimal opponent).
Can it be beaten by an opponent playing sub-optimally?
No. (Why not?)
Time complexity?
O(bm)
Space complexity?
O(bm) (depth-first search, generate all actions at once)
O(m) (backtracking search, generate actions one at a time)
Game Tree Size
Tic-Tac-Toe
b 5 legal actions per state on average, total of 9 plies in game.
ply = one action by one player, move = two plies.
59 = 1,953,125
9! = 362,880 (Computer goes first)
8! = 40,320 (Computer goes second)
exact solution quite reasonable
Chess
b 35 (approximate average branching factor)
d 100 (depth of game tree for typical game)
bd 35100 10154 nodes!!
exact solution completely infeasible
It is usually impossible to develop the whole search tree.
(Static) Heuristic Evaluation Functions

An Evaluation Function:
Estimates how good the current board configuration is for a player.
Typically, evaluate how good it is for the player, how good it is for
the opponent, then subtract the opponents score from the players.
Often called static because it is called on a static board position.
Othello: Number of white pieces - Number of black pieces
Chess: Value of all white pieces - Value of all black pieces
Typical values :
-infinity (loss) to +infinity (win) or [-1, +1] or [0, +1].
Board evaluation X for player is -X for opponent
Zero-sum game (i.e., scores sum to a constant)
Applying MiniMax to tic-tac-toe

The static heuristic evaluation function:
Minimax Values (two ply)
Iterative (Progressive) Deepening

In real games, there is usually a time limit T to make a move
How do we take this into account?
Using MiniMax we cannot use partial results with any
confidence unless the full tree has been searched
So, we could be conservative and set a conservative depthlimit which guarantees that we will find a move in time < T
Disadvantage: we may finish early, could do more search
In practice, Iterative Deepening Search (IDS) is used
IDS runs depth-first search with an increasing depth-limit
When the clock runs out we use the solution found at the
previous depth limit
With alpha-beta pruning (next lecture), we can sort the nodes
based on values found in previous depth limit to maximize
pruning during the next depth limit => search deeper
Heuristics and Game Tree Search:

Limited horizon
The Horizon Effect

Sometimes theres a major effect (e.g., a piece is captured) which
is just below the depth to which the tree has been expanded
The computer cannot see that this major event could happen
because it has a limited horizon --- i.e., when search stops
There are heuristics to try to follow certain branches more deeply to
detect such important events, and so avoid stupid play
This helps to avoid catastrophic losses due to short-sightedness
Heuristics for Tree Exploration
Often better to explore some branches more deeply in allotted time

Various heuristics exist to identify promising branches
Stop at quiescent positions --- all battles are over, things are quiet
Continue when things are in violent flux --- the middle of a battle
Selectively Deeper Game Trees
Eliminate Redundant Nodes
On average, each board position appears in the search tree

approximately ~10150 / ~1040 10100 times.
=> Vastly redundant search effort.
Cant remember all nodes (too many).

=> Cant eliminate all redundant nodes.
However, some short move sequences provably lead to a

redundant position.
These can be deleted dynamically with no memory cost
Example:
1. P-QR4 P-QR4; 2. P-KR4 P-KR4
leads to the same position as
1. P-QR4 P-KR4; 2. P-KR4 P-QR4
Summary
Game playing is best modeled as a search problem
Game trees represent alternate computer/opponent moves
Minimax is a procedure which chooses moves by assuming that the

opponent will always choose the move which is best for them
Basically, it avoids all worst-case outcomes for Max, to find the best.
If the opponent makes an error, Minimax will take optimal advantage
of that error and make the best possible play that exploits the error.
Cutting off search

In general, it is infeasible to search the entire game tree.
In practice, Cutoff-Test decides when to stop searching further.
Prefer to stop at quiescent positions.
Prefer to keep searching in positions that are still violently in flux.
Static heuristic evaluation function

Estimate quality of a given board configuration for the Max player.
Called when search is cut off, to determine value of position found.

Cs 171 07a Games MiniMax

Uploaded by

Copyright:

Available Formats

Cs 171 07a Games MiniMax

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Cs 171 07a Games MiniMax

Uploaded by

Copyright:

Available Formats

Game-Playing & Adversarial Search

MiniMax, Search Cut-off, Heuristic Evaluation

You Will Be Expected to Know

Game tree (2-player, deterministic, turns)

How do we search this tree to find the optimal move?

Search versus Games

Two players: MAX and MIN

Formal definition as a search problem:

MAX uses search tree to determine best next move.

Two-ply Game Tree

Two-Ply Game Tree

Two-Ply Game Tree

Two-Ply Game Tree

The minimax decision

Pseudocode for Minimax Algorithm

Game Tree Size

It is usually impossible to develop the whole search tree.

(Static) Heuristic Evaluation Functions

Applying MiniMax to tic-tac-toe

Minimax Values (two ply)

Iterative (Progressive) Deepening

Heuristics and Game Tree Search:

The Horizon Effect

Heuristics for Tree Exploration

Often better to explore some branches more deeply in allotted time

Selectively Deeper Game Trees

Eliminate Redundant Nodes

On average, each board position appears in the search tree

Cant remember all nodes (too many).

However, some short move sequences provably lead to a

Game playing is best modeled as a search problem

Game trees represent alternate computer/opponent moves

Minimax is a procedure which chooses moves by assuming that the

Cutting off search

Static heuristic evaluation function

You might also like