Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

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:


Comments:

Add Comment

No comments.