- Sometimes it is impossible to complete a search due to a large number of nodes for example games like chess.
- The only solution is to be content with a partial solution.
- Minmax is a heuristic approach and used to find move possibly better than all other moves.
- Whichever search technique we use, the awkward fact remains that for a game such as chess a complete search of the associated graph is out of the question.
- In this situation, we have to be content with a partial search around the current position.
- This is the principle underlying an important heuristic called Minimax.
- Minimax (sometimes Minmax) 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 extended to more complex games. And to general decision making in the presence of uncertainty.
A Minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game.
- A value associated with each position or state of the game. This value computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent’s possible following moves.
- Although this heuristic does not allow us to be certain of winning whenever this is possible, it finds a move that may reasonably be expected to be among the best moves available, while exploring only part of the graph starting from some given position.
- Exploration of the graph is normally stopped before the terminal positions reached, using one of several possible criteria. And the positions where exploration stopped evaluated heuristically.
- In a sense, this is merely a systematic version of the method used by some human players that consist of looking ahead a small number of moves.
Example for Minmax Principle: Tic tac toe