Minimax (sometimes MinMax or MM) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. Originally formulated for two-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.

The algorithm reviews all possibilities for a limited number of step and assign a value that takes into account the benefits for the player and for his opponent. Then the best choice is the one that minimizes the loss of any player assuming the adversary seeks instead to maximize (the game is zero-sum).

There are various algorithms based on MinMax to optimize the search for the best shot by limiting the number of nodes visited in the game tree, the best known is pruning alpha-beta. In practice, the tree is often too large to be fully explored (like chess or go). Only a fraction of the tree is explored.

Source: Wikipedia (license)

External resources

Online Participants