Minimax

1 definition found

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

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