Adversarial Search in which we examine the problems that arise when we try to plan ahead in a world where other agents are planning against us
Problems of Adversarial Search
- Multi-agent environment:
- any given agent needs to consider the actions of other agents and how they affect its own welfare
- introduce possible contingencies into the agent’s problem-solving process
- cooperative vs. competitive
- Adversarial search problems: agents have conflicting goals — games
Games vs. Search Problems
- “Unpredictable” opponent
- specifying a move for every possible opponent reply
- Time limits
- unlikely to find goal, must approximate
Game Problem Formulation
- A game with 2 players (MAX and MIN, MAX moves first, turn-taking) can be defined as a search problem with:
- initial state: board position
- player: player to move
- successor function: a list of legal (move, state) pairs
- goal test: whether the game is over – terminal states
- utility function: gives a numeric value for the terminal states (win, loss, draw)
- Game tree = initial state + legal moves
Game Tree (2-player, deterministic)
