(algorithm)
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 ...)
depth-first search.
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.
Author: RS
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 10 January 2007.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Rajiv Bakulesh Shah, "minimax", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 January 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/minimax.html