Adverserial search Flashcards
Adversarial search
In adversarial search. the algo faces an opponent that tries to achieve the oppose goal.
Example of adversarial game
Tic tac toe (zero-cross)
Hostile agent
Other agent planning against us
Classic AI games
Deterministic, turn-taking, two player, perfect information
In adversarial search, we are not dealing with __________
In adversarial search, we are not dealing with luck factor games. Ex: Dice
Different adversarial search techniques
Minimax, Alpha-beta pruning
Minimax
Terms use in Minimax game (2 important)
Max in minimax
Max is us in game. Max attempts to maximise its score.
Min in minimax
Min is opponent in the game. Min attempts to minimize Max’s score
Which search use in Minimax algo
We use DFS (Depth First Search) for expanding the tree
Properties of Minimax
Completeness: Complete if tree is finite
Optimality:Optimal against an optimal opponent (Does even better when MIN not play optimally)
Time: Depth first exploration O(bᵐ), max depth of m with b legal moves at each point (impractical for real game)
Space: Depth First Exploration O(bm)
