Artificial Intelligence
Game Playing
Game Playing State-of-the-Art
• Checkers: 1950: First computer
player. 1994: First computer
champion: Chinook ended 40-year-
reign of human champion Marion
Tinsley using complete 8-piece
endgame. 2007: Checkers solved!
• Chess: 1997: Deep Blue defeats
human champion Gary Kasparov in a
six-game match. Deep Blue
examined 200M positions per
second, used very sophisticated
evaluation and undisclosed methods
for extending some lines of search
up to 40 ply. Current programs are
even better, if less historic.
• Go: Human champions are now
starting to be challenged by
machines, though the best humans
still beat the best machines. In go, b
> 300! Classic programs use pattern
knowledge bases, but big recent
State of the art
State of the art
AI Game
• Game is primarily behavioral, since this is how
player’s perceive the intelligence
• Game is not focused on winning – it enhances
play and enjoyment
Types of Games
• Many different kinds of games!
• Axes:
– Deterministic or stochastic?
– One, two, or more players?
– Zero sum?
– Perfect information (can you see the state)?
• Want algorithms for calculating a strategy (policy)
which recommends a move from each state
Deterministic vs stochastic Games
• Deterministic is where your agent’s actions uniquely
determine the outcome.
For example in Chess, there is no randomness when
you move a piece.
• Stochastic is where your agent’s actions don’t
uniquely determine the outcome.
For example in games with dice, you can determine
your dice throwing action but not the outcome of the
dice
Zero-Sum Games
Zero-Sum Games • General Games •
Agents have opposite utilities Agents have independent utilities
(values on outcomes) (values on outcomes)
Lets us think of a single value that Cooperation, indifference,
one maximizes and the other competition, and more are all
minimizes possible
Adversarial, pure competition More later on non-zero-sum
games
Game playing
• Many similarities to search
• Most of the games studied
– have two players,
– are zero-sum: what one player wins, the other loses
– have perfect information: the entire state of the game is known to
both players at all times
• E.g., tic-tac-toe, checkers, chess, Go, backgammon, …
• Will focus on these for now
• Recently more interest in other games
– Esp. games without perfect information; e.g., poker
• Need probability theory, game theory for such games
Types of Games
Perfect Information Games
• We consider 2 players perfect information games
• Perfect Information: both players know everything
there is to know about the game position
– no hidden information
– no random events
– two players need not have same set of moves
available
– examples are Chess, Go, Checkers, O’s and X’s
11
Game Trees
• A game tree is like a search tree
– nodes are search states, with full details about a
position
– edges between nodes correspond to moves
– leaf nodes correspond to determined positions
• e.g. Win/Lose/Draw
• number of points for or against player
– at each node it is one or other player’s turn to move
12
Basis of Game Playing:
Search for best move every time
Search for Opponent
Move 1 Moves
Initial Board State Board State 2 Board State 3
Search for Opponent
Move 3 Moves
Board State 4 Board State 5
Relation of Games to Search
• Search
– Solution is (heuristic) method for finding goal
– Heuristics can find optimal solution
– Evaluation function: estimate of cost from start to goal through
given node
– Examples: path planning, scheduling activities
• Games
– 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
Coping with impossibility
• It is usually impossible to solve games completely
• This means we cannot search entire game tree
– we have to cut off search at a certain depth
• like depth bounded depth first, lose
completeness
• Instead we have to estimate cost of internal nodes
• Do so using evaluation function
15
Evaluation functions
• Evaluations how good a ‘board position’ is
– Based on static features of that board alone
• Zero-sum assumption lets us use one function to describe
goodness for both players.
– f(n)>0 if we are winning in position n
– f(n)=0 if position n is tied
– f(n)<0 if our opponent is winning in position n
16
For Trivial Games
• Draw the entire search space
• Put the scores associated with each final board
state at the ends of the paths
• Move the scores from the ends of the paths to the
starts of the paths
– Whenever there is a choice use minimax assumption
– This guarantees the scores you can get
• Choose the path with the best score at the top
– Take the first move on this path as the next move
Entire Search Space
MiniMax
• Assume that both players play perfectly
– Therefore we cannot optimistically assume player will
miss winning response to our moves
• Consider Min’s strategy
– wants lowest possible score, ideally -
– but must account for Max aiming for +
– Min’s best strategy is:
• choose the move that minimizes the score that will
result when Max chooses the maximizing move
– hence the name MiniMax
19
MINI MAX
• Restrictions:
– 2 players: MAX (computer) and MIN (opponent)
deterministic, perfect information
Select a depth-bound and evaluation function
- Construct the tree up till
MAX Select the depth-bound
3 this move
- Compute the evaluation
function for the leaves
MIN
2 1 3 - Propagate the evaluation
function upwards:
- taking minima in MIN
MAX - taking maxima in MAX
2 5 3 1 4 4 3
Modified game
• From leaves upward, analyze best decision for
player at node, give node a value
6 Player 1
0 1
Player 2 Player 2
-1 6
0 1 0 1
Player 1 -1 Player 1 4 6 Player 1 7 Player 1
0 1 0 1 0 1 0 1
-1 -2 -3 4 -5 6 7 -8
Entire Search Space
Moving the scores from
the bottom to the top
Moving a score
when there’s a choice
• Use minimax assumption
– Rational choice for the player below the number you’re moving
Choosing the best move
Minimax algorithm
Properties of minimax
• Complete? Yes (if tree is finite)
•
• Optimal? Yes (against an optimal opponent)
•
• Time complexity? O(bm)
•
• Space complexity? O(bm) (depth-first exploration)
•
• For chess, b ≈ 35, m ≈100 for "reasonable" games
exact solution completely infeasible
Multiplayer games
• Games allow more than two players
• Single minimax values become vectors
Exercise
What is value at the root?
Game Playing – Example
• Nim (a simple game)
• Start with a single pile of tokens
• At each move the player must select a pile
and divide the tokens into two non-empty,
non-equal piles
+
+
+
• The game starts with a single stack of 7tokens. At each move a
player selects one stack and divides it into two non-empty,
non-equal stacks. A player who is unable to move loses the
game.
• Draw the complete search tree for Nim.
• Assume two players, min and max, play Nim. Min plays first.
• If a terminal state in the search tree developed above is a win
for min, a utility function of zero is assigned to that state. A
utility function of 1 is assigned to a state if max wins the
game. Apply the minimax algorithm to the search tree to
assign utility functions to all states in the search tree.
• If both min and max play a perfect game, who will win?
7
6-1 5-2 4-3
5-1-1 4-2-1 3-2-2 3-3-1
4-1-1-1 3-2-1-1 2-2-2-1
3-1-1-1-1 2-2-1-1-1
2-1-1-1-1-1
Maximilian vs. Minerva
(7,Min)
(6,1,Max) (5,2,Max) (4,3,Max)
(5,1,1,Min) (4,2,1,Min) (3,2,2,Min) (3,3,1,Min)
(4,1,1,1,Max) (3,2,1,1,Max) (2,2,2,1,Max)
(3,1,1,1,1,Min) (2,2,1,1,1,Min)
(2,1,1,1,1,1,Max)
Game tree
From M. T. Jones, Artificial Intelligence: A Systems Approach
Current board:
X’s move
Minimax algorithm: Example
From M. T. Jones, Artificial Intelligence: A Systems Approach
Current board
X’s move
Problem of minimax search
• Number of games states is exponential to
the number of moves.
– Solution: Do not examine every node
– ==> Alpha-beta pruning
• Remove branches that do not influence final decision
Alpha-beta pruning
• Basic idea: “If you have an idea that is surely
bad, don't take the time to see how truly
awful it is.” -- Pat Winston
MAX >=2 • We don’t need to compute
the value at this node.
MIN =2 <=1 • No matter what it is, it can’t
affect the value of the root
MAX node.
2 7 1 ?
Example of Alpha-Beta Pruning
player 1
player 2
• Depth first search a good idea here
– See notes for explanation
Alpha-Beta Pruning for Player 1
1. Given a node N which can be chosen by player one,
then if there is another node, X, along any path, such
that (a) X can be chosen by player two (b) X is on a
higher level than N and (c) X has been shown to
guarantee a worse score for player one than N, then
the parent of N can be pruned.
2. Given a node N which can be chosen by player two,
then if there is a node X along any path such that (a)
player one can choose X (b) X is on a higher level than
N and (c) X has been shown to guarantee a better
score for player one than N, then the parent of N can
be pruned.
Modified game
• From leaves upward, analyze best decision for
player at node, give node a value
6 Player 1
0 1
Player 2 Player 2
-1 6
0 1 0 1
Player 1 -1 Player 1 4 6 Player 1 7 Player 1
0 1 0 1 0 1 0 1
-1 -2 -3 4 -5 6 7 -8
Alpha and Beta values
• Mx node has value
– the alpha value is lower bound on the exact minimax score
– with best play Mx can guarantee scoring at least
• Min node has value
– the beta value is upper bound on the exact minimax score
– with best play Min can guarantee scoring no more than
• At Max node, if an ancestor Min node has <
– Min’s best play must never let Max move to this node
• therefore this node is irrelevant
– if = , Min can do as well without letting Max get here
• so again we need not continue
41
Alpha-Beta Pruning Rule
• Two key points:
– alpha values can never decrease
– beta values can never increase
• Search can be discontinued at a node if:
– It is a Max node and
• the alpha value is the beta of any Min ancestor
• this is beta cutoff
– Or it is a Min node and
• the beta value is the alpha of any Max ancestor
• this is alpha cutoff
42
Rules for Alpha-beta Pruning
• Alpha Pruning: Search can be stopped below
any MIN node having a beta value less than or
equal to the alpha value of any of its MAX
ancestors.
• Beta Pruning: Search can be stopped below
any MAX node having a alpha value greater
than or equal to the beta value of any of its
MIN ancestors.
Alpha-Beta Pruning
Summary
• Alpha = the value of the best choice we’ve
found so far for MAX (highest)
• Beta = the value of the best choice we’ve
found so far for MIN (lowest)
• When maximizing, cut off values lower than
Alpha
• When minimizing, cut off values greater
than Beta
α-β pruning example
α-β pruning example
α-β pruning example
α-β pruning example
α-β pruning example
Alpha-beta example
MAX 3
MIN 3 2 - prune 14 1 - prune
3 12 8 2 14 1
Another α-β Pruning Example
A
B
C
D E F G
H I J K L N
M O
6 5 8 10 2 1 15 18
With alpha-beta pruning (view
presentation for animation)
Minimax with Alpha-Beta pruning
No more branches,
so this is the value
alpha=3 3
Max
My turn
0< 2<
Min beta=3 3
alpha,
so
alpha,
so
prune prune
Opp turn
5>
beta,
Max 3 so
prune
0 2
My turn
Min 2 3 5 0 2 1
Max 6 A
Min 6 B
2 C
Max 6 D >=8 E 2 F G
H I J K L M
6 5 8 2 1
Computer Move Opponent Move
Properties of α-β
• Pruning does not affect final result
•
• Good move ordering improves effectiveness of pruning
•
• With "perfect ordering," time complexity = O(bm/2)
doubles depth of search
• A simple example of the value of reasoning about which
computations are relevant (a form of metareasoning)
•
Alpha-Beta Example
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Example
1
0 1
0 2 1 2
0 2 1 -5 2
0 3 2 1 -5 2
0 -3 3 2 1 -3 -5 2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
The Game
Rules:
1. Red goes first
2. On their turn, a player must move their piece
3. They must move to a neighboring square, or if their opponent is
adjacent to them, with a blank on the far side, they can hop over
them
4. The player that makes it to the far side first wins.
Game Tree Example
MAX MIN
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Stage 1
α = -∞ β=∞
?
α = -∞ β=∞
α = -∞ β=∞
α = -∞ β = ∞
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Stage 1
?
α = 10 β=∞
10
α = -∞ β = 10 α = 10 β = ∞
10
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Stage 2 – Shallow Pruning
α = -∞ β = 10
10
α = 10 10 β = ∞ α = -∞ β = 10
9
α = 10 β = 9 α = -∞ β = 10
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Game Tree example contd.
α = 10 β=∞
10
α = -∞ 10 β = 10
14
α = 14 β = 10
14
α = -∞ β = 10
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Game Tree example contd.
α = 10 β=∞
α = 10 β=∞
α = 10 β=∞
α = 10 β = ∞
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Game Tree example contd.
α = 10 β=∞
5
α = 10 β = 5 α = 10 β = ∞
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
Game Tree example contd.
10 5
α = 10 β=5
5
α = 10 β=∞
4
α = 10 β = 4
10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21
The α-β algorithm
The α-β algorithm
The End
96