Arti cial Intelligence
Adversarial Search
Dr. Junaid Younas
fi
Last lecture…..
• Informed Search
• Greedy Search
• A * Search
• Learning desired Heuristic Function
Today’s lecture
• Semester Project
• Assignment#1
• Adversarial Search
• Minimax Algorithm
• Alpha-beta pruning
Semester Project….Assign#1 —2-weeks
• Group yourself in Threes
• Ideally not with the friends you are seen most of the time
• Project topics — any of the topic implementation from the course outline
• Project report — Introduction, Problem identi cation, literature review, research gap
identi cation, contributions of each member — 2 pages max
fi
fi
Adversarial Search
• Two or more agents with con icting goals
• Multi-agent Competitive environment
• 3 stances in multi-agent environment
• Economy — ignore actions of agents
• Adversaries as part of environment —
nondeterministic
• Adversaries as agents — Adversarial
search trees
fl
Let’s play a simple game….
• You choose one of the given basket
• Adversary choose a number from basket
• Your Goal is to maximise the chosen number
A B C
50 -50 1 3 15 -5
In AI, Chess and GO are commonly analysed games
• Types
• Perfect Information
• Zero-sum game
• Move ⟹ Action
• Position ⟹ State
• Is solved?
Game tree
• Each node is decision point for the player
• Each path (root-to-leaf) is a possible outcome
of the game
• Nodes ⟹ states
• Edges ⟹ actions
A game can be de ned as space search problem…..
• Players ={agent, opp}
• Initial State S0 — starting state
• To-MOVE(s) — turn of player
• Actions(s) — possible and available actions at
state s
• Succ(s, a) — resulting state for action a in state s
• Is-END(s) — Terminal test — terminals states
• Utility(s) — agent’s utility for state s
Model a search space for chess
fi
Draw the search tree for tic-tac-toe game
MINMAX search algorithm helps to plan contingent strategy
• Deterministic zero-sum games
• Tic-tac-toe, checkers, chess
• Agent maximises the results
• Opp minimises the results
• Minimax search
• A state-space search tree
• Alternate turns for players 2 3 5 6 8
• Compute each players minimax value
UTILITY(s, max) ifIsEnd(s)
MINIMAX(s) = maxa∈Actions(s)Vminmax(Suc(s, a)) Players(s) = agent
mina∈Actions(s)Vminmax(Suc(s, a)) Players(s) = opp
Minimax Implementation
Minimax Implementation
MiniMax e ciency
• Complete DFS like exploration (exhaustive)
m
• Time complexity: O(b )
• Space complexity: O(bm)
• Infeasible for complex games
123
• B =35, m=80, 10 explorations
ffi
Is it Sensible to explore complete tree?
Properties of alpha-beta pruning
• Doesn’t alter minimax value for a root node
• Values of intermediate nodes might be wrong
• Good child ordering improves the e ectiveness of pruning
• With perfect ordering
m/2
• Time complexity drops to O(b )
• Doubles solvable depth
• Full searches for complicated scenarios is still too complex
ff
Alpha-beta pruning
• Min value
• Compute MIN-Value at node n
• Loop over n’s children
• n’s estimate of the children’s min is dropping
• Who cares about n’s value? MAX
• Let α be the best value that MAX can get at any choice point
along the current path from the root
• If n becomes worse then α, MAX will avoid it..
• MAX version is symmetric
Lets do an example…..(correction)
What about multiplayer game?
Let’s do alpha beta pruning for above tree
MINIMAX(state, α, β)
α — the value of best choice β — the value of best choice
found at any point of Path for found at any point of Path for
MAX, α = at-least MIN, β = atmost
Some examples of alpha beta pruning
10 8 4 50
f(x) = max(min(max(10,6), max(19,9)), min(max(1,2), max(20,5)))
Evaluation functions
• A function that takes in the state and outputs an estimate of the true minimax value of
that node
EVAL(s, p) ifCUT − OFF(s, d)
H − MINIMAX(s) = maxa∈Actions(s)Vminmax(Suc(s, a), d + 1) Players(s) = agent
• mina∈Actions(s)Vminmax(Suc(s, a), d + 1) Players(s) = opp
• For terminal state, EVAL(s, p) = UTILITY(s, p)
• For non-terminal states?
• UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p)
Evaluation Functions
• The most common evaluation function is linear combination
EVAL(s) = w1 f1(s) + w2 f2(s) + w3 f3(s) + . . . . . + wn fn(s)
• fi(s) corresponds to features derived from input state
• wi(s) is the weight assigned to each feature
• Possible features for checkers
• Pawns, loins/kings
• Evaluation function for checker
• Eval = 2.agentKings + agentPawans − 2.oppKings − oppPawns
What about evaluation function of CHESS?
ExpectiMAx
• Adding randomness to the decision-making
• Chance nodes — to compute the expected
utility
• Chance nodes = ∑ p(s′| s)V(s′)
• Simplest way is to add probability factor
• Expand using p=1/3


Reminder: Work on Assignment-3
Thanks … Content Inspiration CS-188
