A special area of search methods is represented by adversarial search methods: these are involved with games (in the broad, game theory sense), i.e. problems where there is an adversary. Some of the methods can also deal with stochastic problems (stochasticity can be interpreted as a specific kind of adversary).
Cooperative and Adversarial Games
Games can be divided – based on how the goals of the players interact – to [essentials]:
- Zero-sum games: The sum of the scores of all the players is always zero (or some other constant value). That means the players are playing against each other. Given that they have to split up the score, if one receives a higher score, the other must necessarily receive a lower one.
- Common-payoff games: The players share the same score, i.e. the game is cooperative.
- Games that combine both components.
Adversarial search is, of course, primarily concerned with adversarial, i.e. zero-sum games.
Methods: Search and Deep Reinforcement Learning
There is a number of adversarial search approaches ranging from naïvely simple ones that perform complete searches (such as minimax), to very complex approaches based on advanced machine learning techniques, that are able to build up empirical heuristic functions automatically from self-play data (such as AlphaGo, AlphaZero, AlphaStar, MuZero, etc.: more in the section on deep reinforcement learning based adversarial search).