Definition: Generate all nodes in a game tree. Score each leaf node with its utility value. Score each minimizing node with the smallest of its children's scores, and maximizing node with the largest of its children's scores.
Generalization (I am a kind of ...)
Aggregate child (... is a part of or used in me.)
multiway tree, recursion.
Note: For most games, minimizing nodes alternate levels with maximizing nodes. This corresponds to two opponents taking turns.
Conceptually all nodes are generated first, but minimax is normally implemented as a depth-first search. Time complexity is O(bd) where b is the average branching factor and d is the depth of the move tree. Complete minimax search is impractical for most games.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 10 January 2007.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Rajiv Bakulesh Shah, "minimax", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 10 January 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/minimax.html