Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial Search - Coggle Diagram
Adversarial Search
-
Alpha-Beta Pruning
When to use
in deterministic, perfect-information, two-player games. When Minimax is used to minimize computation
How to works
The highest value that the maximizer (MAX) can currently ensure is a (Alpha). The best value that the minimizer (MN) can now guarantee is B (Beta).
The remaining branches are cut off (skipped) if a z B since they have no bearing on the outcome.
Benefits
makes deep search feasible, expedites search, and lowers time complexity from O(b m) to O(b*(m/2)) in the best scenario.
Example
If an MN node potentially lead to a value of 3 and a MAX node already has a value of 5, the MAX node will not take that path into consideration any further because it will never select it if it is pruned.
Definition
An optimization method for the Minimax algorithm that reduces the number of nodes assessed by removing branches from the game tree that have no bearing on the outcome.
MIN-MAX Algorithm
-
Used for two-player, zero-sum games
-
-
-
Application in Games
-
Go
Complex board game with huge branching factor Combines adversarial search with deep reinforcement learning. Used in AlphaGo by DeepMind.
Checkers
Another deterministic, perfect-information game Solved using advanced search algorithms. Used in Chinook, the first program to win against a human world champion.
Chess
Classic two-player, zero-sum game Deep game tree search using Minimax and Alpha-Beta Pruning Used by programs like Stockfish and Deep Bl
Assumption & Aims
Assumptions in Adversarial Search
Turn-Bared Play: Players alternate turns to tale moves Perfect information All players know the full state of the game (eg, chess).
Deterministic Environment: The outcome of an action is predictable and has no randomness.
Zero Sum Game: One plaver & gain is exactly the othor's loss.
Aims of Adversarial Search
Determine Optimal Strategy: Choose the best possible move assuming the opponent also plays optimally.
Predict Opponent Moves Simulate and evaluate all possible future moves and countermoves
Maximize Minimum Gain: Ensure the best outcome considering the worst case response from the opponent (Minimax principle)
-