Adversarial Search

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)

Game Tree (2-player, deterministic)
Game Tree (2-player, deterministic)

Leave a Comment