Game Playing Algorithms
Dr B Radhika Selvamani
Introduction
• Game theory is the study of strategic decision
making between two or more intelligent and
rational parties.
Penalty for copying in assignment
• All confess
-2.5 for those who copied and -1 for who did by own
• All deny
-2 for all
• One confesses to me by message and others deny
– The one who confesses gets full mark irrespective for
whether he copied or not
– Others get -3 each
Rules for Team Participation Marks for
Project
• If all are putting equal effort
– Add 5 for each for team participation
• If one person is just copying
– I add only 3 for team participation
• If only one person is doing the whole project
– I give only 0 for team participation
Rules for Real time competition
component
• If two teams participate in a competition
– The team who wins get 5
– Others get 0
• If three teams participate in the competition
– The team who comes first gets 3
– The team who comes second gets 2
– Others get 0
Can you make a rational decision
without knowing the other person’s
choice ?
• If your friend has confessed then it is better for
you to confess too
• If your friend has not confessed then it is better
that you do not confess
• Your decision is a function of the other person’s
decision.
Can you make a rational decision
without knowing the other person’s
choice ?
• If your friend has confessed then it is better for you to
confess too
Nash Equilibrium defined by John Nash
• If your friend has not confessed then it is better that
you do not confess
This is called Pareto Optimal state as
defined by Vilfredo Pareto
• Your decision is a function of the other person’s
decision.
Prisoner’s Dilemma
You Confess You deny
He Confess -100/-100 -200/-10
He Denies -10/-200 -50/-50
Nash Equilibrium
Pareto Optimal
Characteristics of Most Board Games
• Two Person Games
• Zero Sum Games
• Complete Information Games
• Alternate Move Games
• Deterministic Games
Game Tree – You Move
Win Loss
for Draw for
you for you
you
Game Tree – Max Move
Win for
you
Win Loss
for Draw for
you for you
you
Game Tree – When Opponent moves
Loss for Win for
you you
Draw
for you
Game Tree – Min Move
Loss
for
you
Loss for Win for
you you
Draw
for you
Game Tree
D
D W L
W D
L
L L
D
W
L D
Constructing a Strategy
• Strategies are subtrees that show the choices
of one player from a given state.
• Traverse the tree starting at the root
• If level is MAX
– Then choose one branch below it
• Else if level is MIN
– Then choose all the branches below it
A Strategy
D
D W L
W D
L
L L
D
W
L D
Strategy 2
D
D W L
W D
L
L L
D
W
L D
Game Tree
D
D W L
W D
L
L L
D
W L
L D
Game Tree
D
D W L
L W D
L
W
L L
D
W L
L D
Game Tree
L
L
D
D
D W L
L W D
L
W
L L
D
W L
L D
Game Tree
D
L
L
D
D
D W L
L W D
L
W
L L
D
W L
L D
TicTacToe
• Evaluation function to be defined for each board position.
• All board positions for both players should be covered by the evaluation function.
• The evaluation function defines the favorability of MAX
Rows, column, diagonals available to MAX
x Rows available =2 Columns available =2
o
x x x x x x
o o x x
x x x x x
Diagonals available =2
x x
o x
Evaluation function
Favorability of MAX x x
= (rows, column, diagonals available to MAX) – (rows, column, diagonals available to MIN)
Rows, column, diagonals available to MIN
Rows available =2 Columns available =2
x x x o o
o o o o o o o
o o o o o
Diagonals available =1
x o
o o
Evaluation function
Favorability of MAX o
= (rows, column, diagonals available to MAX) – (rows, column, diagonals available to MIN)
Evaluation function value = 6-5 = 1
Game Tree for Tic Tac Toe
A
C
B
x
x x
Game Tree for Tic Tac Toe
A
C
B
x
x x
x
o
6-5=1
Game Tree for Tic Tac Toe
A
C
B
x
x x
x x
o
o
6-5=1 5-5=0
Game Tree for Tic Tac Toe
A
C
B
x
x x
x x
o
o
6-5=1 5-5=0
1 0 1 0 -1
α - β score
• α – the upper bound of scores of MAX nodes
• Β – the lower bound of scores of MIN nodes
• All MAX nodes maintain the α score
• All MIN nodes maintains the β score
Propagating a α bound
α >= -1
β = -1
1 0 1 0 -1
α bound created
α > = -1
-1 If β <= the α bound
then the sub tree can
be pruned
α cutoff
1 0 1 0 -1 -1
α bound created
α > = -1
β <= -1
-1
α cutoff
1 0 1 0 -1 -1
α bound increased
α>=0
0 0
-1 β <= -1
α cutoff
1 0 1 0 -1 -1
α bound crossing a β bound
β <= -1 If α >= the β bound
-1 then the sub tree
β cutoff can be pruned
α>=0
α =-1
-1
0 0
-1 β <= -1
-1
α cutoff
1 0 1 0 -1 -1
SSS*
• Start search with a set of nodes covering all
strategies
• Refine the MAX node with the highest upper
bound
• If a fully refined strategy has highest value
than other partial refined strategy we stop.
Game Strategy 1
D W
W D
L L
D
W
L D
Game strategy 2
D
D W L
W D
L
L L
D
W
L D
Game strategy 3
D W
L
L D
L L
D
W
L D
Nodes covering all Strategies in a partial tree
where MIN nodes are only partially explored
D
L
L
L L
D
W
L D
A Partial game tree
L L
D
W
L
Reference
• Artificial Intelligence by Russel Norvig
Or
• A first course in AI by Dr. Deepak Khemani