Peter Norvig on Minimax Algorithm - Dictionary of Arguments
Norvig I 164
Minimax Algorithm/gaming/Norvig/Russell: The minimax value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game.
Norvig I 165
The minimax algorithm (…) computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceeds all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds. The minimax algorithm performs a complete depth-first exploration of the game tree. For real games, of course, the time cost is totally impractical, but this algorithm serves as the basis for the mathematical analysis of games and for more practical algorithms.
Norvig I 167
The problem with minimax search is that the number of game states it has to examine is exponential in the depth of the tree. Unfortunately, we can’t eliminate the exponent, but it turns out we can effectively cut it in half. The trick is that it is possible to compute the correct minimax decision without looking at every node in the game tree.
Solution: alpha–beta pruning. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
The general principle is this: consider a node n
Norvig I 168
somewhere in the tree (...), such that Player has a choice of moving to that node.
If Player has a better choice m either at the parent node of n or at any choice point further up, then n will never be reached in actual play. So once we have found out enough about n (by examining some of its descendants) to reach this conclusion, we can prune it.
Norvig I 190
The minimax algorithm is traced to a 1912 paper by Ernst Zermelo(1), the developer of modern set theory. The paper unfortunately contained several errors and did not describe minimax correctly. On the other hand, it did lay out the ideas of retrograde analysis and proposed (but did not prove) what became known as Zermelo’s theorem: that chess is determined - White can force a win or Black can or it is a draw; we just don’t know which.
Zermelo says that should we eventually know, “Chess would of course lose the character of a game at all.” A solid foundation for game theory was developed in the seminal work Theory of Games and Economic Behavior (von Neumann and Morgenstern, 1944)(2), which included an analysis showing that some games require strategies that are randomized (or otherwise unpredictable).
Norvig I 191
VsMinimax algorithms: D. F. Beal (1980)(3) and Dana Nau (1980(4), 1983(5)) studied the weaknesses of minimax applied to approximate evaluations. They showed that under certain assumptions about the distribution of leaf values in the tree, minimaxing can yield values at the root that are actually less reliable than the direct use of the evaluation function itself. >Computer Games/Norvig.
1. Zermelo, E. (1913). Über Eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In
Proc. Fifth International Congress of Mathematicians, Vol. 2, pp. 501–504
2. von Neumann, J. and Morgenstern, O. (1944). Theory of Games and Economic Behavior (first edition). Princeton University Press
3. Beal, D. F. (1980). An analysis of minimax. In Clarke, M. R. B. (Ed.), Advances in Computer
Chess 2, pp. 103–109. Edinburgh University Press
4. Nau, D. S. (1980). Pathology on game trees: A summary of results. In AAAI-80, pp. 102–104.
5. Nau, D. S. (1983). Pathology on game trees revisited, and an alternative to minimaxing. AIJ, 21(1–2),
221–244._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010