What is adversarial search? Write the steps for game problem formulation. State and explain minimax algorithm with tic-tac-toe game.

Adversarial search is a search, where we examine the problem which arises when we try to plan ahead of the world and other agents are planning against us.


The environment with more than one agent is termed as multi-agent environment, in which each agent is an opponent of other agent and playing against each other. Each agent needs to consider the action of other agent and effect of that action on their performance.

So, Searches in which two or more players with conflicting goals are trying to explore the same search space for the solution, are called adversarial searches, often known as Games.

Chess, checkers, and tic-tac-toe are the three most popular games that can be solved via adversarial search. 

In many real-world applications, such as financial decision-making and military operations, adversarial search is used.

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.

Example: Tic-Tac-Toe game tree:
The following figure is showing part of the game-tree for tic-tac-toe game. Following are some key points of the game:

There are two players MAX and MIN.
Players have an alternate turn and start with MAX.
MAX maximizes the result of the game tree
MIN minimizes the result.

https://static.javatpoint.com/tutorial/ai/images/ai-adversarial-search.png

From the initial state, MAX has 9 possible moves as he starts first. MAX place x and MIN place o, and both player plays alternatively until we reach a leaf node where one player has three in a row or all squares are filled.
Both players will compute each node, minimax, the minimax value which is the best achievable utility against an optimal adversary.
Suppose both the players are well aware of the tic-tac-toe and playing the best play. Each player is doing his best to prevent another one from winning. MIN is acting against Max in the game.
So in the game tree, we have a layer of Max, a layer of MIN, and each layer is called as Ply. Max place x, then MIN puts o to prevent Max from winning, and this game continues until the terminal node.
In this either MIN wins, MAX wins, or it's a draw. This game-tree is the whole search space of possibilities that MIN and MAX are playing tic-tac-toe and taking turns alternately.