Minimax

Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

Game theory

In general games

The maximin value is the highest value that the player can be sure to get without knowing the actions of the other players; equivalently, it is the lowest value the other players can force the player to receive when they know the player's action. Its formal definition is:

v

i

_

=

max

a

i

min

a

−

i

v

i

(

a

i

,

a

−

i

)

{\displaystyle {\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

{\displaystyle -i}

denotes all other players except player i.

a

i

{\displaystyle a_{i}}

is the action taken by player i.

a

−

i

{\displaystyle a_{-i}}

denotes the actions taken by all other players.

v

i

{\displaystyle v_{i}}

is the value function of player i.

Calculating the maximin value of a player is done in a worst-case approach: for each possible action of the player, we check all possible actions of the other players and determine the worst possible combination of actions – the one that gives player i the smallest value.