Minimax

Home * Search * Minimax

Max Ernst - Little Machine Constructed by Minimax Dadamax in Person, 1919-1920

Minimax,
an algorithm used to determine the score in a zero-sum game after a certain number of moves, with best play according to an evaluation function. The algorithm can be explained like this: In a one-ply search, where only move sequences with length one are examined, the side to move (max player) can simply look at the evaluation after playing all possible moves. The move with the best evaluation is chosen. But for a two-ply search, when the opponent also moves, things become more complicated. The opponent (min player) also chooses the move that gets the best score. Therefore, the score of each move is now the score of the worst that the opponent can do.

History

Jaap van den Herik's thesis (1983) contains a detailed account of the known publications on that topic. It concludes that although John von Neumann is usually associated with that concept (1928) , primacy probably belongs to Émile Borel. Further there is a conceivable claim that the first to credit should go to Charles Babbage . The original minimax as defined by Von Neumann is based on exact values from game-terminal positions, whereas the minimax search suggested by Norbert Wiener is based on heuristic evaluations from positions a few moves distant, and far from the end of the game.

Implementation

Below the pseudo code for an indirect recursive depth-first search. For clarity move making and unmaking before and after the recursive call is omitted.

int maxi( int depth ) {
    if ( depth == 0 ) return evaluate();
    int max = -oo;
    for ( all moves) {
        score = mini( depth - 1 );
        if( score > max )
            max = score;
    }
    return max;
}

int mini( int depth ) {
    if ( depth == 0 ) return -evaluate();
    int min = +oo;
    for ( all moves) {
        score = maxi( depth - 1 );
        if( score < min )
            min = score;
    }
    return min;
}

Negamax

Usually the Negamax algorithm is used for simplicity. This means that the evaluation of a position is equivalent to the negation of the evaluation from the opponent's viewpoint. This is because of the zero-sum property of chess: one side's win is the other side's loss.

See also

Search

• Alpha-Beta
• Minimax (program)
• Negamax
• Search Pathology
• Theorem-Proving and M & N procedure
• Theorem-Proving from Five-Year Plan

People

• John von Neumann
• Claude Shannon
• Norbert Wiener

Selected Publications

1920 ...

• Émile Borel (1921). La théorie du jeu et les équations intégrales à noyau symétrique. Comptes Rendus de Académie des Sciences, Vol. 173, pp. 1304-1308, English translation by Leonard J. Savage (1953). The Theory of Play and Integral Equations with Skew Symmetric Kernels.
• John von Neumann (1928). Zur Theorie der Gesellschaftsspiele. Berlin

1940 ...

• John von Neumann, Oskar Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ.
• Norbert Wiener (1948). Cybernetics or Control and Communication in the Animal and the Machine - MIT Press, Cambridge, MA.

1950 ...

• Claude Shannon (1950). Programming a Computer for Playing Chess, Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950
• Hermann Weyl (1950). Elementary Proof of a Minimax Theorem due to von Neumann. in

Harold W. Kuhn and Albert W. Tucker (eds) (1950). Contributions to the Theory of Games I. Princeton University Press

• Émile Borel, Maurice R. Fréchet, John von Neumann (1953). Discussion of the Early History of the Theory of Games, with Special Reference to the Minimax Theorem. Econometrica, Vol. 21
• Leonard J. Savage (1953). The Theory of Play and Integral Equations with Skew Symmetric Kernels. Econometrica, Vol. 21, pp. 101-115, English translation of Émile Borel (1921). La théorie du jeu et les équations intégrales à noyau symétrique.
• David Blackwell (1956). An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, Vol. 6, No, 1
• Maurice Sion (1958). On general minimax theorems. Pacific Journal of Mathematics, Vol. 8, No. 1

1960 ...

• James R. Slagle (1963). Game Trees, M & N Minimaxing, and the M & N alpha-beta procedure. Artificial Intelligence Group Report 3, UCRL-4671, University of California
• Donald Michie (1966). Game Playing and Game Learning Automata. Advances in Programming and Non-Numerical Computation, Leslie Fox (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix: Rules of SOMAC by John Maynard Smith, introduces Expectiminimax tree
• James R. Slagle, Philip Bursky (1968). Experiments With a Multipurpose, Theorem-Proving Heuristic Program. Journal of the ACM, Vol. 15, No. 1
• James R. Slagle, John K. Dixon (1969). Experiments With Some Programs That Search Game Trees. Journal of the ACM, Vol 16, No. 2, pdf

1970 ...

• James R. Slagle, John K. Dixon (1970). Experiments with the M & N Tree-Searching Program. Communications of the ACM, Vol. 13, No. 3
• Thiruvenkatachari Parthasarathy (1970). On Games Over the Unit Square. SIAM Journal on Applied Mathematics, Vol. 19, No. 2
• Minimax in Alex Bell (1972). Games Playing with Computers.

1980 ...

• Ivan Bratko, Matjaž Gams (1982). Error Analysis of the Minimax Principle. Advances in Computer Chess 3
• Chun-Hung Tzeng, Paul W. Purdom (1983). A Theory of Game Trees. AAAI-83
• Dana S. Nau, Paul W. Purdom, Chun-Hung Tzeng (1986). Experiments on Alternatives to Minimax. International Journal of Parallel Programming, Vol. 15, No. 2
• Dana S. Nau, Paul W. Purdom, Chun-Hung Tzeng (1986, 2013). An Evaluation of Two Alternatives to Minimax. Machine Intelligence and Pattern Recognition, Vol. 4, arXiv:1304.3445
• Ronald L. Rivest (1987). Game Tree Searching by Min/Max Approximation. Artificial Intelligence Vol. 34, 1, pdf 1995

1990 ...

• Liwu Li, Tony Marsland (1990). On Minimax Game Tree Search Pathology and Node-value Dependence. TR90-24, University of Alberta, pdf
• Claude G. Diderich (1993). A Bibliography on Minimax Trees. ACM SIGACT News, Vol. 24, No. 4
• David E. Moriarty, Risto Miikkulainen (1994). Evolving Neural Networks to focus Minimax Search. AAAI-94 » Othello
• Claude G. Diderich, Marc Gengler (1995). A Survey on Minimax Trees and Associated Algorithms. Minimax and Its Applications. Kluwer Academic Publishers
• Richard Korf, Max Chickering (1996). Best-first minimax search. Artificial Intelligence, Vol. 84, Nos 1-2 » Best-First
• Yoav Freund, Robert Schapire (1996). Game Theory, On-line Prediction and Boosting. COLT 1996, pdf
• Don Beal (1999). The Nature of MINIMAX Search. Ph.D. thesis

2000 ...

• Claude G. Diderich, Marc Gengler (2001). Minimax Game Tree Searching. Encyclopedia of Optimization, Springer
• Tinne Hoff Kjeldsen (2001). John von Neumann’s Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts. Archive for History of Exact Sciences, Vol. 56, Springer
• Thomas Hauk, Michael Buro, Jonathan Schaeffer (2004). Rediscovering *-Minimax Search. CG 2004, pdf
• Mitja Luštrek, Matjaž Gams, Ivan Bratko (2005). Why Minimax Works: An Alternative Explanation. IJCAI 2005, pdf » Search Pathology
• Mitja Luštrek, Matjaž Gams, Ivan Bratko (2006). Is Real-Valued Minimax Pathological? Artificial Intelligence, Vol. 170, pdf
• Claude G. Diderich, Marc Gengler (2009). Minimax Game Tree Searching. Encyclopedia of Optimization, Springer

2010 ...

• Jeff Rollason (2014). Interest Search - Another way to do Minimax. AI Factory, Summer 2014
• Hermann Kaindl, Helmut Horacek, Anton Scheucher (2017). Product Propagation: A Back-up Rule Better than Minimaxing? IEEE Transactions on Computational Intelligence and AI in Games, Vol. 9, No. 2, pdf

2020 ...

• Quentin Cohen-Solal, Tristan Cazenave (2020). Minimax Strikes Back. arXiv:2012.10700 » Reinforcement Learning

Forum Posts

• beyond minimax by Harm Geert Muller, CCC, April 27, 2007
• The evaluation value and value returned by minimax search by Chao Ma, CCC, March 09, 2012 » Evaluation
• Why minimax is fundamentally flawed by Harm Geert Muller, CCC, November 09, 2014 » KRK

External Links

• Min-Max Search from Bruce Moreland's Programming Topics
• Minimax from Wikipedia
• Minimax theorem from Wikipedia
• Parthasarathy's theorem from Wikipedia
• Sion's minimax theorem from Wikipedia
• Minimax estimator from Wikipedia
• Expectiminimax tree from Wikipedia
• Maxima and minima from Wikipedia
• Analog voltage maximizer and minimizer circuits from FreePatentsOnline
• Kraftwerk - Pocket Calculator, Minimum-Maximum, Moscow, Luzhniki, June 03, 2004 and Tokyo, Shibuya Station, March 04, 2004, YouTube Video

References

Up one level