ADVERSARIAL SEARCH
Adversarial search are the problems that are used when it is necessary to plan ahead. Where other agents are planning against a particular agent or human. These adversarial search problems are often known as games.
Games are classified as either a single person playing or multi person playing Games like Rubik's cube, 8 tile puzzle, etc., are single person games, for these, search strategies such as Best First or A* algorithm can be used.
In a two person game like chess, checkers etc., each paly tries to smartly the opponent. Each has their own way of evaluating the situation and since each player tries to obtain the maximum benefits, best first search or A* algorithms do not serve the purpose.
The characteristics of the strategy must be look ahead in nature, i.e., explore the tree for two or more levels downwards and choose the optimal one.
The basic methods available for game playing are,
- Minimax strategy.
- Minimax strategy with alpha beta cutoffs
Two Agent Games
In AI, games are deterministic, fully observable environments in which there are two agents whose actions must alternate and in which the utility values at the end of the game are always equal and opposite.
While we are doing our best to find the solution, our opponent (i.e., adversary) is trying to beat us. Hence, the opponent not only introduces uncertainty but also wants to win (in other words defeat us). Therefore, adversial search technique is a mixture of reasoning and creativity and needs the best of human intelligence.
One must plan well ahead and guess what our opponent's moves will be. These 'moves' remain a 'guess' until we have made a move and our opponent has responded.
The steps cannot be retraced, i.e., once the choice is made there is no going back.
Therefore, they must be efficiently handled. Hence the effectiveness of a search can be improved by,
- Generating only good moves.
- The best moves (or paths) are recognized and explored first
Hence we come to the conclusion that game playing can be formally defined as a kind of search problem with the following components,
- Initial state of the game.
- Operators defining. legal moves.
- Successor function.
- Terminal state defining end of game state.
- Goal state
- Path cost/utility/pay off function.
In AI, 'game' are usually of a rather specialized kind, what game theorists call deterministic, turn-taking, two-player, zero-sum games of perfect Information.
Two Person: No third adversary and no team playing on your or adversary is assumed.
Turn Taking: The players get alternative moves as opposed to game where thy can take multiple moves, based on the speed of play.
Zero Sum: Wen one player wins, the other loses
We can represent all possible games (of a given type) by directed graph often called a game tree.
The nodes of the graph represent the states of the game. The arcs of the graph represents possible moves by the players (+ and -). Consider the start of a game.
The game starts in same "start" state, and there is a set of possible moves m1, m2, .... mN. These give rise, respectively, to states S1, S2, .... SN.
Interactive methods apply here because search space is too large for interesting games to search for a solution. Therefore, search will be done before each move in order to select the best next move to be made.
Adversary methods are needed because alternate moves are made by an opponent win is trying to win. Therefore must incorporate the idea that an adversary makes moves that are not controllable by you.
Example: Tic-Tac-Toe.
