Game Tree and Optimization under Adversarial in AI – Analytics Insight

Game theory, in economics, considers the environment with multiple agents as a game. This is regardless of whether the agents in the game are cooperative or competitive. In AI Solutions Company, games are considered adversarial in nature. By adversarial we mean that the environment is two-player, turn-taking in which after the game, the utility values are equal and opposite.

These take place in a deterministic, full observable environment. An example of this is chess. The rules of chess can make the computer representation of the game correct in every relevant detail. However, the presence of an opponent makes solving more complicated because it introduces uncertainty.

Lets consider a game of two players, and call them MIN and MAX. These two players will compete where MAX will try to maximize the payoff. A search problem in the form of a game can be defined with the following 4 components:

In a normal search problem, the objective of MAX would be to search for a payoff value that leads to a terminal state that is a winner, thereby making its first move. However, in the presence of adversary MIN, the strategy of MAX will be to find a winning terminal state regardless of what move MIN makes.

To determine the optimal strategy for MAX, the minimax algorithm is used to determine the best first move. The 5 steps in this algorithm are:

Since the decision maximizes the payoff under the assumption that the opponent will play perfectly to minimize it, it is called the minimax decision.

Figure 1

In the two-player game tree generated in Figure 1, the A nodes indicate the moves by MAX and the V nodes indicate those of MIN. The terminal nodes show the payoff value for MAX calculated by the rules of the game, i.e. the utility function. The payoff values of the other nodes are calculated by the minimax algorithm from the payoffs of their successors. In this case, MAXS best move is A1, and MINs best reply is A11.

Read the original:

Game Tree and Optimization under Adversarial in AI - Analytics Insight

Related Posts

Comments are closed.