Minimax

statistics

Definition

Minimax

Minimax is a recursive algorithm for decision making in two-or-more-games that helps to determine the optimal move by considering all possible future moves and their outcomes.

It assumes that

• one player tries to maximise their score, and
• the other players try to mimise the opponent’s score

Maximin Value

Maximin Value

The maximin value is the highest value that the player can be sure to get without knowing the actions of the other player. Equivalently, it is the lowest value of the other player to receive when they know the player’s action:

$$\underline{v_i}=\underset{a_i}{\max }\underset{a_{-i}}{\min }{v}_i(a_i,a_{-i})$$

where:

• $i$ is the player of interest
• $-i$ are all to other players except player $i$
• $a_i$ is the action taken by player $i$
• $a_{-i}$ is the action taken by all other players
• $v_i$ is the value function of player $i$

Examples

Tic-Tac-Toe

For example, the classical “minimax” solution from game theory is not correct here because it assumes a particular way of playing by the opponent. For example, a minimax player would never reach a game state from which it could lose, even if in fact it always won from that state because of incorrect play by the opponent. ¹

References

Footnotes

1. Reinforcement Learning - An Introduction ↩