Minimax Search -- from Wolfram MathWorld

Minimax Search

A minimax search computes an optimal move in a two-player sequential game that is a finite game, has perfect information, and is a zero-sum game. The possible continuations form a rooted tree in which each position is joined to the positions reachable by one legal move. If is the set of positions reachable in one move from and is the payoff at a terminal position, the game value is determined recursively by

$V(s)={u(s) if s is terminal; max_(s^' in C(s))V(s^') if the maximizing player moves at s; min_(s^' in C(s))V(s^') if the minimizing player moves at s.$

(1)

An optimal move for the maximizing player leads to a position with the largest game value, while an optimal move for the minimizing player leads to one with the smallest game value. Unlike the minimax theorem, which is an existence theorem for optimal mixed strategies, minimax search is a recursive algorithm for exploring the possible moves.

Minimax Search

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications