Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial search and decision trees - Coggle Diagram
Adversarial search and decision trees
AND - OR Search Trees
Used when outcomes are not fully under agent control
OR node
- agent chooses action
AND node
- environment/opponent chooses outcome
Solution Requirements
- must handle all outcomes at AND nodes and choose actions at OR nodes
Example: Vacuum World
- vacuum doesn't know dirt location - must plan for both clean and dirty possibilities
Minimax Algorithm
Optimal decision-making assuming both players play perfectly to maximize their own utility
Game Representation
Two mathematical ways to model strategic interactions between players
Decision Trees
- shows sequential decision-making over time with complete knowledge tracking
Sequential Moves
Matrix/Payoff Table
- assumes simultaneous moves or players don't observe opponent's actions
Simultaneous Decisions
What is Adversarial Search
Game theory approach where one agent's gain is another's loss (competitive environment)
Zero-Sum Games
- perfect information games where utilities are equal and opposite
Perfect information
- all players can see the complete game state
Utility Opposition
- my win +1, your loss -1
Game Tree Representation
Initial State
- starting configuration of the game board or environment
Players
- function determining whose turn it is at each state
Actions
- set of legal moves available in each state
Results
- resulting state after taking action x in state y
End condition
- function checks if the game has ended (win/lose/draw)
Utility
- numerical value representing how desirable an outcome is for a player
Models games as search problems with states and actions
Alpha-Beta Pruning
Optimization technique that eliminates branches that can't influence the final decision