Catalogue of Artificial Intelligence Techniques
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.
- Korf, R.E., Search: A Survey of Recent Results, Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)
, ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).