minimax

minimax
maximin

   <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)