Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial search - alpha beta pruning - Coggle Diagram
Adversarial search - alpha beta pruning
Optimizing Minimax Search
Problem:
Exponential search space in game trees becomes computationally expensive.
Alpha-Beta Pruning:
Alpha (α): Best (highest) value found so far along the path for MAX.
Beta (β): Best (lowest) value found so far along the path for MIN.
Pruning: Eliminate branches that cannot possibly influence the final decision.
Other Optimization Strategies:
Iterative Deepening: Gradually increase search depth to balance time and performance.
Killer Move Heuristics: Prioritize moves that have been successful in similar positions.
Transposition Tables: Store evaluated positions (and their values) to avoid redundant computations.
Hashing: Used for efficient lookups in transposition tables.
Stochastic Games
Definition:
Games with elements of chance or randomness (dice rolls, card draws).
Examples:
Backgammon, Poker, Monopoly.
Representing Chance:
Introduce CHANCE nodes into the game tree.
Probability:
Used to assign likelihoods to different outcomes at CHANCE nodes.
Search Algorithms:
Expectiminimax: Generalizes Minimax to handle chance nodes by calculating expected values.
Monte Carlo Tree Search (MCTS): Uses random simulations (rollouts) to estimate the value of states.
Backgammon
Stochastic Element:
Dice rolls determine possible moves.
Chance Nodes:
Represent different dice roll outcomes.
Probability Calculation (Example):
Probability of rolling a double: 6 (favorable outcomes) / 36 (total outcomes) = 1/6
Probability of rolling a 6 and a 5 (in any order): 2 (favorable outcomes) / 36 (total outcomes) = 1/18