Minimax is 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.
Jaap van den Herik's thesis (1983) [2] 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) [3] , primacy probably belongs to Émile Borel. Further there is a conceivable claim that the first to credit should go to Charles Babbage[4]. 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[5] is based on heuristic evaluations from positions a few moves distant, and far from the end of the game.
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.
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[7]
^Don Beal (1999). The Nature of MINIMAX Search. Ph.D. thesis, ISBN 90-62-16-6348, pp. 2, refers Philip Morrison and Emily Morrison (1961). Charles Babbage and his Calculating Engines. Dover Publ. New York
^Alexander Reinefeld (2005). Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen. slides as pdf, Themen der Informatik im historischen Kontext Ringvorlesung an der HU Berlin, 02.06.2005 (English paper, German title)
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.
Minimax Dadamax in Person, 1919-1920 [1]
Table of Contents
History
Jaap van den Herik's thesis (1983) [2] 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) [3] , primacy probably belongs to Émile Borel. Further there is a conceivable claim that the first to credit should go to Charles Babbage [4]. 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 [5] 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.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
People
Selected Publications
1920 ...
1940 ...
1950 ...
Harold W. Kuhn and Albert W. Tucker (eds) (1950). Contributions to the Theory of Games I. Princeton University Press
1960 ...
1970 ...
1980 ...
1990 ...
2000 ...
2010 ...
Forum Posts
External Links
References
What links here?
Up one level