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:
where:
is the player of interest are all to other players except player is the action taken by player is the action taken by all other players is the value function of player
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. 1