Minimax: Fundamentals and Applications

By Fouad Sabry

What Is Minimax

In artificial intelligence, decision theory, game theory, statistics, and philosophy, minmax is a decision rule that is used to minimize the probable loss for a worst case scenario. When discussing profits, one may often hear the term "maximin" used, which stands for "maximizing the minimum gain." It was initially developed for the theory of several-player zero-sum games, including both the circumstances in which players take alternate movements and those in which they make simultaneous actions. Since then, however, it has been expanded to more complicated games as well as to general decision-making in the presence of uncertainty.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: Minimax

Chapter 2: Game Theory

Chapter 3: Decision Trees

Chapter 4: Alpha-Beta Pruning

Chapter 5: Expectiminimax

Chapter 6: Adversarial Search

Chapter 7: Evaluation function

Chapter 8: Monte Carlo Tree Search

Chapter 9: Negamax

Chapter 10: Artificial Intelligence

(II) Answering the public top questions about minimax.

(III) Real world examples for the usage of minimax in many fields.

(IV) 17 appendices to explain, briefly, 266 emerging technologies in each industry to have 360-degree full understanding of minimax' technologies.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of minimax.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jun 28, 2023

Book preview

Chapter 1: Minimax

Minmax is a decision rule that is used in artificial intelligence, decision theory, game theory, statistics, and philosophy with the purpose of reducing the probable loss for a worst case (maximum loss) scenario. Minmax is also referred to as Minimax or MM in certain contexts. When discussing profits, one may often hear the term maximin, which stands for maximizing the minimal gain. It was initially developed for the theory of several-player zero-sum games, covering both the cases where players take alternate moves and those where they make simultaneous moves. Since then, however, it has been extended to more complex games as well as to general decision-making in the presence of uncertainty.

The maximin value is the maximum value that a player may be guaranteed to acquire without knowing the actions of the other players; in the opposite sense, it is the lowest value that the other players can compel the player to get when they know the player's behavior. The academic definition of it is:

{\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}

Where:

i is the index of the player of interest.

-i denotes all other players except player i.

a_{i} is the action taken by player i.

a_{{-i}} denotes the actions taken by all other players.

v_{i} is the value function of player i.

The maximin value of a player is calculated using a worst-case scenario technique. This means that for each conceivable action of the player, we examine all possible actions of the other players and identify the set of actions that gives player I the lowest possible value. The next thing that we do is figure out whatever action player I can do in order to guarantee that this minimum value is the maximum that is attainable.

Consider the following game for two players as an example. The first player, referred to as the row player, has the option of selecting any one of the following three moves: T, M, or B. The second player, referred to as the column player, has the option of selecting either L or R. A payout table depicts the outcome of the game after both moves have been played:

{\displaystyle {\begin{array}{c|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}}

(the first number in each of the cells indicates the pay-out for the player who played the row, and the second number indicates the pay-out for the person who played the column).

For the sake of this illustration, we will only look at pure tactics. Perform the checks on each player in turn:

The player on the row may play the T, This ensures that they will get a payment of at least 2 (playing B is hazardous since it might result in a reward of less than 100), Playing M may result in a reward of ten dollars if you win.

Hence: {\underline {v_{row}}}=2 .

The column player can play L and secure a payoff of at least 0 (playing R puts them in the risk of getting {\displaystyle -20} ).

Hence: {\underline {v_{col}}}=0 .

If both players play their respective maximin strategies {\displaystyle (T,L)} , the payoff vector is (3,1) .

The minimax value of a player is the biggest value that the player can be guaranteed to acquire while they know the actions of the other players; alternatively, it is the minimum value that the other players can compel the player to get, without knowing the player's actions. The academic definition of it is:

{\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}

The definition is quite similar to that of the maximin value, with the exception that the order of the maximum and least operators is switched around. In the previous illustration,:

The player who plays the row has the potential to get a maximum value of either 4 (if the other player plays R) or 5 (if the other player plays L), so: {\displaystyle {\overline {v_{row}}}=4\ .}

The highest possible value that the column player may achieve is 1. (if the other player plays T), 1 (if M) or 4 (if B).

Hence: {\displaystyle {\overline {v_{col}}}=1\ .}

The maximin can never be more than the minimax for any one player i:

\underline{v_i} \leq \overline{v_i}

Intuitively, in maximin, the maximization comes after the minimization, so player I tries to maximize their value before knowing what the others will do; in minimax, the maximization comes before the minimization, so player I is in a much better position – they maximize their value knowing what the others did. In both cases, the minimization comes first.

Reading the notation from right to left is yet another method that may be used to comprehend it: While we are writing

{\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}}

the initial set of outcomes {\displaystyle \ v_{i}(a_{i},a_{-i})\ } depends on both {\displaystyle \ {a_{i}}\ } and {\displaystyle \ {a_{-i}}\ .} We first marginalize away {\displaystyle {a_{i}}} from {\displaystyle v_{i}(a_{i},a_{-i})} , by maximizing over {\displaystyle \ {a_{i}}\ } (for every possible value of {\displaystyle {a_{-i}}} ) to yield a set of marginal outcomes {\displaystyle \ v'_{i}(a_{-i})\,,} which depends only on {\displaystyle \ {a_{-i}}\ .} We then minimize over {\displaystyle \ {a_{-i}}\ } over these outcomes.

(The opposite is true for maximin.)

Although it is always the case that {\displaystyle \ {\underline {v_{row}}}\leq {\overline {v_{row}}}\ } and {\displaystyle \ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,} the payoff vector resulting from both players playing their minimax strategies, {\displaystyle \ (2,-20)\ } in the case of {\displaystyle \ (T,R)\ } or {\displaystyle (-10,1)} in the case of {\displaystyle \ (M,R)\,,} cannot similarly be ranked against the payoff vector {\displaystyle \ (3,1)\ } resulting from both players playing their maximin strategy.

When there are two players involved in a game with no winner, the minimax solution and the Nash equilibrium are identical.

The minimax theorem may be rephrased as the equivalent of in the setting of zero-sum games:

There is a value V and a mixed strategy that may be chosen by each player in any two-player, zero-sum game with a finitely large number of possible tactics, such that

(a) Taking into consideration the tactics of Player 2, the optimum feasible reward for Player 1 is V, and

(a) Taking into account the tactic used by Player 1, the best possible payoff for Player 2 is V.

Equally, the strategy chosen by Player 1 ensures that they will get a payment of V regardless of the approach chosen by Player 2, and Player 2 has the ability to ensure that they will receive a reward of V for themselves. Because each player strives to ensure that the other receives the smallest possible maximum payment, the game is known as minimax. However, because it is a zero-sum competition, players must also work to ensure that they suffer the smallest possible maximum loss (i.e. maximize their minimum payoff). See also: an illustration of a game that doesn't have any utility here.

Maximin solutions are shown by the following example of a zero-sum game, in which both A and B make their moves at the same time. Let's say that each player has three options, and let's look at the reward matrix that's presented for option A on the table (Payoff matrix for player A). Consider that the payout matrix for B is the same matrix, but with the signs switched around (i.e. if the choices are A1 and B1 then B pays 3 to A). Therefore, the simple maximin option for B is B2, given that the worst possible outcome for B is then having to pay nothing, whereas the maximin choice for A is A2 since the worst possible result for B is then having to pay 1. However, this solution is not stable because if B believes A will choose A2, then B will choose B1 to gain 1; then if A believes B will choose B1, then A will choose A1 to gain 3; and then B will choose B2; and eventually, both players will realize how difficult it is to decide which option to go with. Therefore, a technique that is more reliable is required.

Certain options are overshadowed by others and may be crossed from the list: A will not choose option A3 since either option A1 or A2 will yield a better outcome regardless of the option B selects; Because certain combinations of B1 and B2 will yield a superior outcome regardless of whatever option A selects, B will not go with option B3 in this scenario.

Player A can avoid having to make an expected payment of more than 1/

 3 

by choosing A1 with probability 1/

 6 

and A2 with probability 5/

 6 

: The expected payoff for A would be   3 × 1/

 6 

− 1 × 5/

 6 

= −+1/

 3 

  in case B chose B1 and   −2 × 1/

6 

+ 0 × 5/

 6 

= −+1/

 3 

  in case B chose B2.

Similarly, B can ensure an expected gain of at least 1/

 3 

, regardless of the option that A picks, by using a randomized strategy of choosing B1 with probability 1/

 3 

and B2 with probability 2/

 3 

.

These mixed minimax techniques can no longer be made more effective and have reached a stable state.

In game theory, the terms maximin and minimax are distinguished from one another often. In games with no winners and no losers, the term minimax refers to reducing the maximum reward that an opponent may get. This is the same thing as maximizing one's own minimum gain while minimizing one's own maximum loss in a game with a zero-sum outcome, which is a zero-sum game.

The word maximin is often used in the context of non-zero-sum games to refer to the approach that maximizes an individual's personal minimal payout. In non-zero-sum games, this is neither the same thing as reducing the opponent's potential for the greatest possible gain, nor is it the same as following the Nash equilibrium approach.

In the theory of repeated games, the values of the minimax are of the utmost significance. The minimax values are the basis for the folk theorem, which is one of the most important theorems in this subject.

There is an algorithm called minimax that is used for game solutions in combinatorial game theory.

A straightforward implementation of the minimax algorithm is described in the following paragraphs. This implementation focuses on games like tic-tac-toe, in which each player has an equal chance of winning, losing, or drawing. If player A can win with only one move, then the winning move is player A's best option. If player B is aware that one move will lead to a circumstance in which player A can win in one move, while another move will lead to a situation in which player A can, at most, draw, then player B should make the move that would lead to a draw in order to maximize his or her chances of winning. As the game progresses, it becomes quite clearer what the best