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
* Optimality
* TC
* SC
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)
Alpha Beta pruning
Modified version of minimax
Ignore portions of search tree that make no difference to final choice
Initial value of alpha and beta
Alpha: Initially set to -∞ at maximising nodes. This represents the worst possible score for the maximising player, so any value will improve it
Beta: Initially set to +∞ at minimising nodes. This represents the worst possible score for the minimising player, so any value will improve it.
Main algo point of alpha beta pruning
In both min and max node, we return when alpha>=beta which compares with its parent node only.
Alpha beta pruning
* Time complexity (best case and worst case)
* Space complexity
* Completeness
* Optimality
Alpha beta pruning
- Time complexity
Best case: O(b^(d/2)) In best case it reduces the branching factor from b to sqrt(b), effectively allowing us t o explore only half the depth of the tree compared to mini max algo
Worst case: O(b^d) In worst case, it is equivalent to minimax if no pruning occurs. This happens when moves are poorly ordered (worst moves exlored first) - Space complexity : O(d) Alpha beta pruning uses DFS, requiring space proportional to the depth of the tree d
- Completeness: complete if the tree is finite. alpha-beta pruning will exlpore all necessary branches in a finite game tree to ensure a decision is made.
- Optimality: optimal if the evaluation function is perfect. If the evaluation function represents the utility of a node, alpha beta pruning guarantees the same optimal decision as minimax.
