Updated March 27, 2023
Introduction to Adversarial Search
Adversarial search has more than one entity, and each entity has conflicting goals and objectives. These entities are pitted against each other in a game like situation, and the strategy or game approach of each player varies as per the opponent’s move. A player in Adversarial Search may take a maximizer role or minimizer role depending on the game situation and the intent of the opponent. Maximizer will always try to maximize the gain, and Minimizer will try to control the damage and minimize the loss.
Whereas Normal search operation engages a single entity, in a search space, follows a set of rules, namely algorithm or heuristics based on past precedence/guesswork. The outcome is a set of actions prescribed in a sequence, and it is more accurate in case of algorithm and not so in heuristics.
Importance of Adversarial Search
This algorithm is one of the most favourites in Artificial Intelligence arena, and it provides solutions in Multiple Player Environment with complex situations like
- Each player will have to consider the movements of other players, formulate strategy dynamically and reach the end goals.
- Players introduce unforeseen turns to upset the opponent and win the game.
- Some games are co-operative in nature, and most of them are in competition.
- Each player has conflicting goals, and the opponent is unpredictable.
- A quick reaction is required to counter strategize and win the game.
- Handling all types of games with predictable, unpredictable outcomes and following transparent and blind rules and regulations.
Different Game Scenarios using Adversarial search
Below you can consider the different game scenarios:
1. Games with Perfect information
These are open and transparent games where each player has all complete information on the status of the game, and the move of the opponent is quite visible to the players. Chess, Checkers, Ethello and Go are some of such games.
2. Games with Imperfect information
In these games, players will not have any information on the status of the game, and it will have blind moves by the players assuming certain conditions and predicting the outcomes. Tic-Tac_Toe, Battleship, Blind and Bridge are some examples of this type of game.
3. Deterministic Games
These games follow pre-defined rules and pattern, and it is played in a transparent manner. Each player can see the moves of the opponents clearly. Chess, Checkers, Tic-tac-toe, Go are some of the games played in this manner.
4. Non-Deterministic Games
Luck, Chance, Probability plays a major role in these types of game. The outcome of these games is highly unpredictable, and players will have to take random shots relying on luck. Poker, Monopoly, Backgammon are few of the games played in this method.
5. Zero-Sum games
These games are purely competitive in nature, and one player’s gain is compensated by other player’s loss. The net value of gain and loss is zero, and each player will have different conflicting strategies in these games. Depending on the game environment and game situation, each player will either try to maximize the gain or minimize the loss.
The move or strategy depends not only on the game situation and environment but also on the opponent’s likely strategy and game plan. This is known as embedded thinking in problem resolution in AI, and a player backtracks and changes his strategy depends on the progress of the game, and hence it is also known as backward reasoning in AI. Chess, Tic-tac-toe is a few of the games played under this rule.
How does it work?
A game can be equated to a type of search in AI, and it will have the following constituents:
- Start of the game: This deals with the initial state of the game and configurations.
- Players: Participants in the game space.
- Action: Indicates the moves made by the players in the space.
- Result: Outcome of the moves of the players.
- Terminal Test: It indicates whether the game is over or not.
- Utility: It expresses the final outcome of the game in terms of Loss or wins or the values.
Game Tree
It has multiple nodes, and the Root node is present at the top. Each node indicates the status of the game and they contain moves of the players at its edge. Each layer in the tree has the turns for Maximizer and Minimizer alternatively. Maximizer maximizes the minimum gain and Minimizer contains the loss and minimizes the maximum loss. A player takes a maximizer role or minimizer role depending on the game environment and the opponent’s strategy.
The game contains the following steps.
- Each game has an initial state.
- There will be more than one player in a game.
- The root node may have turned for maximizer and maximizer fills “X” in any one of vacant cells in the edge of the node containing 3×3 cells. Hence there are 9 possible actions.
- Now it’s minimizer turn to assess the move by the opponent and accordingly post “0” in a vacant cell.
- Maximizer chooses the empty cell based on the earlier move by minimizer and fills it up with “X”.
- Step 4 and 5 are repeated to any depth, with optimal moves by minimizer and maximizer respectively from their standpoint, till one of the rows is filled with “X” or “0” fully.
- Once the terminal condition is reached as per step-6, the game is over.
- Using the utility, final outcome arrives, and results are declared. It could be Maximizer’s win or Minimizer’s win or draw.
Advantages/Uses of Adversarial Search
Adversarial search is used in many fields to find optimal solutions in a competitive environment and few of the applications are:
- In the legal system where two advocates argue their stand representing their party’s cases and Judges or Jury takes cues from the above-explained techniques, analyze and deliver judgment.
- These techniques are used in the business environment in sourcing suppliers and buyers for Products/services in a competitive manner.
- Wherever hard negotiations are required, these concepts help to maximize the gain who can negotiate intelligently and prudently.
- This concept is the base for further development of new technologies like Alpha-Beta pruning,
Conclusion
These searches are quite extensively in all the fields right from politics, business, economics where competition is very high, and these techniques optimize the time, effort, and cost.
Recommended Articles
This is a guide to Adversarial Search. Here we discuss the introduction, different game scenarios, game tree, and Advantages of adversarial search. You can also go through our other suggested articles to learn more –
