minimax
<games> An algorithm for choosing the next move in a two player game. A
player moves so as to maximise the minimum value of his opponent's possible
following moves. If it is my turn to move, I give a value to each legal move I
might make. If the result of a move is an immediate win for me I give it
positive infinity and, if it is an immediate win for you, negative infinity. The
value to me of any other move is the minimum of the values resulting from each
of your possible replies.
The above algorithm will give every move a value of positive or negative
infinity since the value of every move will be the value of some final winning
or losing move. This can be extended if we can supply a heuristic evaluation
function which gives values to non-final game states without considering all
possible following complete sequences. We can then limit the minimax algorithm
to look only a certain number of moves ahead. This number is called the
"look-ahead" or "ply".
See also alpha/beta pruning.
[Is "maximin" used? Is it significantly different?]
(2000-12-07)
Nearby terms:
Mini Disc « minifloppy « minimal automaton « minimax
» Mini-ML » minimum seek time » Mini PL/I
