# Catalogue of Artificial Intelligence Techniques

## Minimax

**Keywords:**
games

### Categories: Game Theory , Search

Author(s): **Hans Berliner**

Consider a (partial) Game Tree between
two players. If the leaf nodes
are labelled with payoffs such that the larger the value the
more favourable the outcome for one of the players, then this
player will naturally prefer the play to finish at a leaf node
with as high a payoff as possible. We will refer to this player as Max, and
to his opponent (who tries to direct the play to minimise Max's payoff)
as Min.
The Minimax value of such a tree is
derived by starting at the leaf nodes and *backing up* values in
the following manner. If the parent of a set of sibling nodes
whose values, p
, are all known is a Max node, then the value, P, of
that node is given by P=max(p
). If the parent is a Min node,
then P=min(p
).
This procedure is recursive and
results in eventually labelling the root node with a value. The
optimal path through the tree from the point of view of both
adversaries is known as the Maximin path.

### References:

- Korf, R.E.,
*Search: A Survey of Recent Results*,*Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)*(Shrobe, H.E. , ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).

### Comments:

No comments.