maximin

1 definition found

maximin - Free On-line Dictionary of Computing (26 May 2007) :

  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)