Basically, in search strategies there is one Agent aims to find the Solution but, in some situation, more than one Agent is required. Adversarial search is a search where one Agent is trying to find the solution which is controlled by us or we are trying to find the solution but some other Agents are there working as a competitor and planning against us. This situation is basically occurring in Game playing. The Environment more than one Agent is called Multi-Agent Environment, where each Agent is opponent of other Agents and playing against each other. Each Agent needs to consider the actions of other Agent and affect of that action on their performance. So, the searches in which multiple players (Agents) are trying to explore the same search space for the solution with conflicting goals are called adversarial search often called Games.

Games:

There are 2 types of Games:

1. Deterministic Games
2. Non-Deterministic Games

• Deterministic Games: These types of Games, Agents having Perfect information about the Game rules, moves, etc. It follows a strict pattern and set of rules for games. for example, Chess, Checkers, go, Othello etc. In this types of game Agents have proper information about the game and they can see each other’s moves also.

• Non-Deterministic Games: These types of games contain imperfect information which means in a Game Agents don’t have all the information about games and no aware about what’s going on. Those Games has various unpredictable events. These Games are also called Stochastic Games. For example, Battleship, tic-tac-toe, monopoly, poker etc.

Zero-Sum Game

• • Zero-sum games are adversarial search which involves pure competition.
• • In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or gains of utility of another agent.
• • One player of the game tries to maximize one single value, while another player tries to minimize it.
• • Each move by one player in the game is called as ply.
• • Chess and tic-tac-toe are examples of a Zero-sum game.

Zero-sum game: Embedded thinking

The Zero-sum game involved embedded thinking in which one agent or player is trying to figure out:

• • What to do.
• • How to decide the move
• • Needs to think about his opponent as well
• • The opponent also thinks what to do
• • Each of the players is trying to find out the response of his opponent to their actions. This requires embedded thinking or backward reasoning to solve the game problems in AI.

Formalization of the problem:

A game can be defined as a type of search in AI which can be formalized of the following elements:

• • Initial state: It specifies how the game is set up at the start.
• • Player(s): It specifies which player has moved in the state space.
• • Action(s): It returns the set of legal moves in state space.
• • Result (s, a): It is the transition model, which specifies the result of moves in the state space.
• • Terminal-Test(s): Terminal test is true if the game is over, else it is false at any case. The state where the game ends is called terminal states.
• • Utility (s, p): A utility function gives the final numeric value for a game that ends in terminal states s for player p. It is also called payoff function. For Chess, the outcomes are a win, loss, or draw and its payoff values are +1, 0, ½. And for tic-tac-toe, utility values are +1, -1, and 0.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc