So far we’ve talked about uninformed and informed search algorithms. That should be it, right? Both of them combined should cover the space of all search algorithms, no? Well, unfortunately not. We’ve made some strong assumptions in everything discussed so far. We had assumed that search problems had following properties:
- Single agent: There is only one agent (player).
- Deterministic actions: There is no randomness i.e., an action in a given state has the same effect every time.
- Fully observed state: The agent has perfect information about the world.
- Discrete state space: States evolve only in response to the actions taken by the agent and not as a function of time.
Let’s relax one of these constraints and allow multiple agents instead of only one. A major class of multiple-agent search problems is the space of fixed-sum games, which are necessarily adversarial (since the total utility is fixed, the players must compete with each-other to maximize their utilities). An important special case of adversarial games is two-player, zero-sum, deterministic, perfect-information games, e.g., chess, checkers, tic-tac-toe etc.