Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Adversarial Search?
3.
Different Game Scenarios using Adversarial Search
4.
Game Tree
5.
Need of Adversarial Search by the Agents
6.
Important Features of Adversarial Search
7.
Frequently Asked Questions
7.1.
What is an adversarial example?
7.2.
What is stemming?
7.3.
Where is adversarial search useful?
7.4.
What are the benefits and drawbacks of Artificial Intelligence?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Adversarial Search in Artificial Intelligence

Author Gaurav Gandhi
1 upvote

Introduction

The Adversarial Search in Artificial Intelligence involves more than one entity, each with competing aims and purposes. These entities are put against one another in a game-like environment and each player's strategy or game approach alters depending on the opponent's move. Depending on the game situation and the opponent's objective a player in Adversarial Search may assume a maximizer or a minimizer position.

Adversarial Search in Artificial Intelligence

Adversarial Search in Artificial Intelligence is a significant field of study in artificial intelligence, where search algorithms, heuristics and perfect or imperfect information are some of its key components. This blog will examine Adversarial Search in Artificial Intelligence, its application in many gaming contexts and its necessity in artificial intelligence.

What is Adversarial Search?

Adversarial Search in Artificial Intelligence is a type of search in artificial intelligence, deep learning, machine learning and computer vision in which one can trace the movement of an enemy or opponent. Such searches are useful in chess, business strategy tools, trade platforms and war-based games using AI agents. The user can change the current state but has no control over the future stage in an adversarial search.

The opponent has control over the next state which is unexpected. There may be instances where more than one agent is searching for a solution in the same search space which is common in gameplay. Games are treated as a Search problem and a heuristic evaluation function which are the two key components that help in the modeling and solving of games in AI.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Different Game Scenarios using Adversarial Search

Different Game Scenarios using Adversarial Search
  • Perfect Information: An example of a perfect information game is one where agents can see the entire board. Agents are able to view each other's movements and possess all of the game's information. Go, Checkers and Chess are a few examples
     
  • Imperfect Information: The term "game with imperfect information" refers to those, such as tic tac toe, battleship, blind, bridge, and others, in which agents are not fully informed about the game or aware of what is happening
     
  • Deterministic Game: Games classified as deterministic involve no element of randomness; instead, they adhere to a rigid structure and set of rules. A few examples are tic tac toe, go, checkers, chess, and so on
     
  • Non-deterministic Games: Games that involve a chance or luck element and a variety of unpredictable outcomes are said to be non-deterministic. Either dice or cards are used to introduce this element of chance or luck. Each action-reaction is not fixed; they are random. We also refer to these games as stochastic games. For instance, Monopoly, Poker, Backgammon, etc
     
  • Zero-Sum games: These are strictly competitive games where the success of one player is offset by the failure of another. Every player in these games will have a different set of opposing strategies, and the net value of gain and loss is zero. Every player aims to maximize gain or minimize loss, depending on the conditions and surroundings of the game

Game Tree

Game Tree

It has several nodes, with the Root node at the top. Each node represents the current state of the game and contains the moves of the players at its edge. Each layer in the tree contains alternate turns for Maximizer and Minimizer. Minimizer contains the loss and minimizes the maximum loss, whereas Maximizer maximizes the minimal gain. Depending on the game setting and the opponent's strategy, a player takes on a maximizer or a minimizer role.

The steps in the game are as follows:

  • Each game has a starting state
     
  • A game will have more than one person
     
  • The root node may have turned for the maximizer, and the maximizer fills "X" in any of the vacant cells on the node's edge. As a result, there are nine possible actions
     
  • It is now the minimizer's turn to evaluate the opponent's action and consequently post "0" in a vacant cell
     
  • The maximizer selects an empty cell and fills it with "X" based on the previous move by the minimizer
     
  • Steps 4 and 5 are repeated to any depth, with optimal moves by the minimizer and maximizer, respectively, until one of the rows is completely filled with "X" or "0"
     
  • The game is over whenever the terminal condition is attained in step 6
     
  • Using the utility, the ultimate result is obtained and declared. It might be a Maximizer win, a Minimizer win, or a draw

Need of Adversarial Search by the Agents

The importance of Adversarial Search in Artificial Intelligence may be seen in various games; some of the most essential elements are as follows:

  • This method can be used to observe the movement of the opposing player, and the strategy must be developed accordingly based on these observations. This strategy also addresses the end goal's path and how to reach it. So, with this technique or algorithm in place, we may modify various game situations
     
  • The games that have used such algorithms have got so clever that they may have generated unexpected types of turns that can upset the other player. As a result, the opposing players' moves are less likely to be foreseen
     
  • By incorporating adversarial searches into games, the competitiveness of the game increases significantly, attracting the user or player to play the game more frequently
     
  • By including these search predictions, unpredictable results, rules, and regulations must be revised on a frequent basis to ensure that the nature of the competition does not get rusty

Important Features of Adversarial Search

  • Adversarial games can be classified as having perfect or imperfect information. Every player in a game with perfect information is fully aware of the game's present condition; yet, in a game with imperfect information, certain information is kept hidden from the players
     
  • Search strategies such as minimax and alpha-beta pruning are used in adversarial games to discover the best move. These algorithms aid in choosing the best move for a player by weighing the possible outcomes of each move
     
  • Since the size of the game tree, it may not always be able to search it thoroughly. In these cases, heuristics are used to approximate the optimal move. Heuristics are shortcuts that allow the algorithm to quickly evaluate the possibility of a move without having to look through the entire game tree

Frequently Asked Questions

What is an adversarial example?

An adversarial example is one that is fed to the machine in order to fool it. In general it is a clean example but it fools the machine after a minor permutation. Although humans do not recognize the permutation, it is sufficient for the machine to make the incorrect judgment.

What is stemming?

Stemming is a natural language processing approach that reduces inflection in words to their root forms hence assisting in the preprocessing of text, words, and documents for text normalization.

Where is adversarial search useful?

In games adversarial search is utilized. This is due to the fact that games contain a multi-agent environment in which players attempt to achieve a goal. Legal systems also use this to examine the circumstances between the two parties and aid in the decision-making process.

What are the benefits and drawbacks of Artificial Intelligence?

Artificial intelligence benefits include conducting repetitive labor, digital assistants, eliminating human mistakes, performing risky occupations, 24x7 availability, quick decision-making and so on. Artificial intelligence disadvantages include exorbitant costs, unemployment, a lack of inventiveness, increased laziness and so on.

Conclusion

Adversarial Search in Artificial Intelligence is essential for making competitive decisions. Gamma-beta pruning, heuristics, and minimax drive efficient game tree exploration. Depth and resources must be balanced carefully. Its application to a variety of fields, including games and cybersecurity, is expanded by extensions like MCTS. In this article, we discussed what adversarial search is and different game scenarios using Adversarial Search.

To better understand the topic, you can refer to Uninformed Search Algorithms in Artificial IntelligenceAdversarial Search in NLP, and Introduction to Natural Language Processing (NLP).

For more information, refer to our Guided Path on Coding Ninjas Studio to upskill yourself in PythonData Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more! 

Head over to our practice platform, CodeStudio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!

Previous article
Agent in Artificial Intelligence
Next article
Uninformed Search Algorithms in Artificial Intelligence
Live masterclass