Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial Search & Game Playing - Coggle Diagram
Adversarial Search & Game Playing
Strategy in AI
Fully observable + deterministic: agent calculates next state (e.g., map navigation)
Partially observable / stochastic: percepts used (e.g., Wumpus World)
Need contingency plans, not just action sequences
AND-OR Search Trees
OR nodes: agent chooses action
AND nodes: environment provides possible outcomes
Goal: plan for every possibility
Game Theory
Multi-agent environments = games
Definition:
Study of conflict & cooperation between rational agents
(Interactive decision theory)
Examples: Tic-tac-toe, Chess, Checkers, Othello, Go
Zero-sum:
Perfect info
Opposing utility (win/lose/draw)
Deterministic, turn-based
Physical Games vs AI Games
AI less suited to:
Croquet, Ice-hockey
AI applied to:
Football (robotics + strategy)
Minimax Algorithm
Two players: Max and Min
Game model:
s: state
Player(s): whose move
Actions(s): legal moves
Result(s, a): new state
Terminal-Test(s): game over?
Utility(s, p): payoff for player p
Max aims to maximize utility; Min aims to minimize it
Works like depth-first AND-OR search
Alpha-Beta Pruning
Problem: Minimax searches huge trees (exponential)
Alpha: best score Max can guarantee
Beta: best score Min can guarantee
Prunes branches that cannot improve the outcome
Prisoner’s Dilemma
Decision problem: cooperate or betray?
Alliances emerge from selfish strategies
Risks of breaking alliances (trust factor)