Minimax

Minimax is a strategic decision rule used to manage risk and uncertainty. It is a core concept in artificial intelligence, decision theory, and statistics. Scientists and philosophers use it to minimize possible losses during a worst-case scenario. A worst-case scenario is the most unfavorable outcome possible. When the goal is to increase gains instead of reducing losses, the rule is called maximin. This approach helps agents make logical choices when they cannot predict exactly what will happen next.

To understand the mechanism, imagine a player trying to find the safest path. This is known as the maximin approach. First, the player considers every possible action they can take. For each specific action, the player looks at all possible responses from other players. The player identifies the smallest possible value they would receive for each action. This represents the worst outcome for that specific choice. Finally, the player selects the action that makes this minimum value as large as possible. This process is often described as maximizing the minimum gain.

Minimax is a related but distinct concept where the order of operations is reversed. In minimax, the player assumes they know the actions of the other players. They first find the maximum value they can achieve for every possible response from their opponents. Then, they look for the response from the opponent that results in the smallest of these maximum values. This is the smallest value that other players can force the player to receive. Because the player acts with knowledge of the opponent's moves, the minimax value is usually higher. Mathematically, the maximin value for a player is always less than or equal to their minimax value.

We can see these rules in action through a mathematical payoff table. Imagine a game with two players: a row player and a column player. The row player has three choices: T, M, or B. The column player has two choices: L or R. The table shows the results for both players in each scenario. For example, if the row player chooses T and the column player chooses R, the row player gets 2 and the column player gets -20.

Let us calculate the maximin value for the row player in this specific game. If the row player chooses T, their lowest possible payoff is 2. If they choose M, they might receive -10. If they choose B, they could lose 100 points. To stay safe, the row player follows the maximin rule and chooses T. This guarantees them a value of 2. Similarly, the column player looks for their own safe move. If the column player chooses L, they are guaranteed at least 0. If they choose R, they risk receiving -20. Therefore, the column player's maximin value is 0.

Now, let us calculate the minimax value for these same players. For the row player, we look at the maximum they can get for each of the column player's moves. If the column player plays L, the row player can get a maximum of 5. If the column player plays R, the row player can get a maximum of 4. The minimax value is the minimum of these two maximums, which is 4. For the column player, the maximum payoffs they can get are 1, 1, or 4. The minimum of these values is 1. This shows how the minimax perspective changes the expected outcome.

Historically, these ideas were originally formulated for several-player zero-sum games. In a zero-sum game, one player's gain is exactly balanced by the losses of the other players. These rules covered games where players take turns or make moves at the same time. Over time, mathematicians have extended these concepts to much more complex games. They are also used in general decision-making when there is high uncertainty. Today, these principles allow computers to navigate complex environments by preparing for the most difficult challenges.