25,161
edits
Changes
Created page with "'''Home * Search * Minimax''' FILE:ConstructedbyMinimaxDadamax.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Min..."
'''[[Main Page|Home]] * [[Search]] * Minimax'''
[[FILE:ConstructedbyMinimaxDadamax.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person
| [[Arts#Ernst|Max Ernst]], [https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person Little Machine Constructed] by [https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person Minimax Dadamax in Person], 1919-1920 <ref>[https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person Little Machine Constructed by Minimax Dadamax in Person from Wikipedia]</ref> ]]
'''Minimax''',<br/>
an algorithm used to determine the [[Score|score]] in a [https://en.wikipedia.org/wiki/Zero-sum 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 [[Ply|one-ply]] search, where only move sequences with length one are examined, the side to move (max player) can simply look at the [[Evaluation|evaluation]] after playing all possible [[Moves|moves]]. The move with the best evaluation is chosen. But for a two-[[Ply|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.
<span id="History"></span>
=History=
[[Jaap van den Herik|Jaap van den Herik's]] thesis (1983) <ref>[[Jaap van den Herik]] ('''1983'''). ''Computerschaak, Schaakwereld en Kunstmatige Intelligentie''. Ph.D. thesis, [[Delft University of Technology]]. Academic Service, The Hague. ISBN 90 62 33 093 2 (Dutch)</ref> contains a detailed account of the known publications on that topic. It concludes that although [[John von Neumann]] is usually associated with that concept ([[Timeline#1928|1928]]) <ref>[[John von Neumann]] ('''1928'''). ''[http://gdz.sub.uni-goettingen.de/dms/load/img/?IDDOC=29357 Zur Theorie der Gesellschaftsspiele]''. Berlin</ref> , [https://en.wikipedia.org/wiki/Primacy_of_mind primacy] probably belongs to [[Mathematician#Borel|Émile Borel]]. Further there is a conceivable claim that the first to credit should go to [[Mathematician#Babbage|Charles Babbage]] <ref>[[Don Beal]] ('''1999'''). ''The Nature of MINIMAX Search''. Ph.D. thesis, ISBN 90-62-16-6348, pp. 2, refers [[Mathematician#PhilipMorrison|Philip Morrison]] and Emily Morrison ('''1961'''). ''Charles Babbage and his Calculating Engines''. Dover Publ. New York</ref>. The original minimax as defined by Von Neumann is based on exact values from [[Terminal Node|game-terminal positions]], whereas the minimax search suggested by [[Norbert Wiener]] <ref>[[Norbert Wiener]] ('''1948'''). ''[http://www.amazon.com/gp/reader/026273009X/ref=sib_dp_pt#reader-link Cybernetics or Control and Communication in the Animal and the Machine]'' - MIT Press, Cambridge, MA.</ref> is based on [[Evaluation|heuristic evaluations]] from positions a few moves distant, and far from the end of the game.
=Implementation=
Below the pseudo code for an indirect [[Recursion|recursive]] [[Depth-First|depth-first search]]. For clarity [[Make Move|move making]] and [[Unmake Move|unmaking]] before and after the recursive call is omitted.
<pre>
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;
}
</pre>
=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]]
* [[James R. Slagle#TheoremProving|Theorem-Proving and M & N procedure]]
* [[Jack Good#TheoremProving|Theorem-Proving from Five-Year Plan]]
==People==
* [[John von Neumann]]
* [[Claude Shannon]]
* [[Norbert Wiener]]
=Selected Publications=
==1920 ...==
* <span id="Borel"></span>[[Mathematician#Borel|É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 [[Mathematician#LJSavage|Leonard J. Savage]] ('''1953'''). ''[[Minimax#Savage|The Theory of Play and Integral Equations with Skew Symmetric Kernels]]''.
* [[John von Neumann]] ('''1928'''). ''[http://gdz.sub.uni-goettingen.de/dms/load/img/?IDDOC=29357 Zur Theorie der Gesellschaftsspiele]''. Berlin <ref>[[Alexander Reinefeld]] ('''2005'''). ''Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen''. [http://www.informatik.hu-berlin.de/studium/ringvorlesung/ss05/slides/05-06-02.pdf slides as pdf], Themen der Informatik im historischen Kontext Ringvorlesung an der [https://en.wikipedia.org/wiki/Humboldt_University_of_Berlin HU Berlin], 02.06.2005 (English paper, German title)</ref>
==1940 ...==
* [[John von Neumann]], [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] ('''1944'''). ''[https://en.wikipedia.org/wiki/Theory_of_Games_and_Economic_Behavior Theory of Games and Economic Behavior]''. Princeton University Press, Princeton, NJ.
* [[Norbert Wiener]] ('''1948'''). ''[http://www.amazon.com/gp/reader/026273009X/ref=sib_dp_pt#reader-link Cybernetics or Control and Communication in the Animal and the Machine]'' - MIT Press, Cambridge, MA.
==1950 ...==
* [[Claude Shannon]] ('''1950'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]'', Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950
* [[Mathematician#Weyl|Hermann Weyl]] ('''1950'''). ''Elementary Proof of a Minimax Theorem due to von Neumann''. in
: [[Mathematician#HWKuhn|Harold W. Kuhn]] and [[Mathematician#AWTucker|Albert W. Tucker]] (eds) ('''1950'''). ''[http://books.google.com/books?id=TpbbVU4tA58C&printsec=frontcover&dq=isbn:9780691079349&hl=de&ei=r2i1TabJL8_usgaW-rj7Cw&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCoQ6AEwAA#v=onepage&q&f=false Contributions to the Theory of Games I]''. [https://en.wikipedia.org/wiki/Princeton_University_Press Princeton University Press]
* [[Mathematician#Borel|Émile Borel]], [[Mathematician#MRFrechet|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''. [https://en.wikipedia.org/wiki/Econometrica Econometrica], Vol. 21
* <span id="Savage"></span>[[Mathematician#LJSavage|Leonard J. Savage]] ('''1953'''). ''The Theory of Play and Integral Equations with Skew Symmetric Kernels''. [https://en.wikipedia.org/wiki/Econometrica Econometrica], Vol. 21, pp. 101-115, English translation of [[Mathematician#Borel|Émile Borel]] ('''1921'''). ''[[Minimax#Borel|La théorie du jeu et les équations intégrales à noyau symétrique]]''.
* [[Mathematician#DHBlackwell|David Blackwell]] ('''1956'''). ''[http://projecteuclid.org/euclid.pjm/1103044235 An analog of the minimax theorem for vector payoffs]''. [https://en.wikipedia.org/wiki/Pacific_Journal_of_Mathematics Pacific Journal of Mathematics], Vol. 6, 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, [https://en.wikipedia.org/wiki/Leslie_Fox Leslie Fox] (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix: ''Rules of SOMAC'' by [[John Maynard Smith]], introduces [https://en.wikipedia.org/wiki/Expectiminimax_tree Expectiminimax tree] <ref>see [[Helmut Richter#Swapoff|Swap-off]] by [[Helmut Richter]]</ref>
* [[James R. Slagle]], [[Philip Bursky]] ('''1968'''). ''[http://portal.acm.org/citation.cfm?id=321444 Experiments With a Multipurpose, Theorem-Proving Heuristic Program]''. [[ACM#Journal|Journal of the ACM]], Vol. 15, No. 1
* [[James R. Slagle]], [[John K. Dixon]] ('''1969'''). ''Experiments With Some Programs That Search Game Trees''. [[ACM#Journal|Journal of the ACM]], Vol 16, No. 2, [http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf pdf]
==1970 ...==
* [[James R. Slagle]], [[John K. Dixon]] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362052.362054 Experiments with the M & N Tree-Searching Program]''. [[ACM#Communications|Communications of the ACM]], Vol. 13, No. 3, pp. 147-154.
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p004.htm#index54 Minimax] in [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''.
==1980 ...==
* [[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]]
* [[Ronald L. Rivest]] ('''1987'''). ''Game Tree Searching by Min/Max Approximation''. Artificial Intelligence Vol. 34, 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]
==1990 ...==
* [[Liwu Li]], [[Tony Marsland]] ('''1990'''). ''On Minimax Game Tree Search Pathology and Node-value Dependence''. TR90-24, [[University of Alberta]], [https://webdocs.cs.ualberta.ca/~tony/TechnicalReports/TR90-24.pdf pdf]
* [[Claude G. Diderich]] ('''1993'''). ''[http://portal.acm.org/citation.cfm?id=165007 A Bibliography on Minimax Trees]''. [[ACM#SIG|ACM SIGACT News]], Vol. 24, No. 4
* [[David E. Moriarty]], [[Risto Miikkulainen]] ('''1994'''). ''Evolving Neural Networks to focus Minimax Search''. [[AAAI|AAAI-94]], [http://www.cs.utexas.edu/~ai-lab/pubs/moriarty.focus.pdf pdf] » [[Othello]]
* [[Claude G. Diderich]], [[Marc Gengler]] ('''1995'''). ''[http://link.springer.com/chapter/10.1007/978-1-4613-3557-3_2 A Survey on Minimax Trees and Associated Algorithms]''. ''[http://link.springer.com/book/10.1007/978-1-4613-3557-3 Minimax and Its Applications]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers]
* [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-first minimax search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, Nos 1-2 » [[Best-First]]
* [[Yoav Freund]], [[Robert Schapire]] ('''1996'''). ''Game Theory, On-line Prediction and Boosting''. [http://dblp.uni-trier.de/db/conf/colt/colt1996.html#FreundS96 COLT 1996], [http://www.cs.princeton.edu/~schapire/papers/FreundSc96b.pdf pdf]
* [[Don Beal]] ('''1999'''). ''The Nature of MINIMAX Search''. Ph.D. thesis
==2000 ...==
* [[Claude G. Diderich]], [[Marc Gengler]] ('''2001'''). ''[http://link.springer.com/referenceworkentry/10.1007%2F0-306-48332-7_280 Minimax Game Tree Searching]''. [http://link.springer.com/book/10.1007/0-306-48332-7 Encyclopedia of Optimization], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [http://milne.ruc.dk/~thk/ Tinne Hoff Kjeldsen] ('''2001'''). ''John von Neumann’s Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts''. [https://en.wikipedia.org/wiki/Archive_for_History_of_Exact_Sciences Archive for History of Exact Sciences], Vol. 56, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Thomas Hauk]], [[Michael Buro]], [[Jonathan Schaeffer]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_3 Rediscovering *-Minimax Search]''. [[CG 2004]], [http://skatgame.net/mburo/ps/STAR-A.pdf pdf]
* [[Mitja Luštrek]], [[Matjaž Gams]], [[Ivan Bratko]] ('''2005'''). ''[http://dl.acm.org/citation.cfm?id=1642327 Why Minimax Works: An Alternative Explanation]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2005.html#LustrekGB05 IJCAI 2005] » [[Search Pathology]]
* [[Claude G. Diderich]], [[Marc Gengler]] ('''2009'''). ''[http://link.springer.com/referenceworkentry/10.1007%2F978-0-387-74759-0_370 Minimax Game Tree Searching]''. [http://link.springer.com/book/10.1007/978-0-387-74759-0 Encyclopedia of Optimization], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
==2010 ...==
* [[Jeff Rollason]] ('''2014'''). ''[http://www.aifactory.co.uk/newsletter/2014_01_interest_minimax.htm Interest Search - Another way to do Minimax]''. [[AI Factory]], Summer 2014
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=13433 beyond minimax] by [[Harm Geert Muller]], [[CCC]], April 27, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=42806 The evaluation value and value returned by minimax search] by [[Ma Chao]], [[CCC]], March 09, 2012 » [[Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54295 Why minimax is fundamentally flawed] by [[Harm Geert Muller]], [[CCC]], November 09, 2014 » [[KRK]]
=External Links=
* [http://web.archive.org/web/20070820195815/www.seanet.com/%7Ebrucemo/topics/minmax.htm Min-Max Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [https://en.wikipedia.org/wiki/Minimax Minimax from Wikipedia]
* [https://en.wikipedia.org/wiki/Minimax_estimator Minimax estimator from Wikipedia]
* [https://en.wikipedia.org/wiki/Expectiminimax_tree Expectiminimax tree from Wikipedia]
* [https://en.wikipedia.org/wiki/Maxima_and_minima Maxima and minima from Wikipedia]
* [https://en.wikipedia.org/wiki/Nash_equilibrium Nash equilibrium from Wikipedia]
* [https://en.wikipedia.org/wiki/Parthasarathy%27s_theorem Parthasarathy's theorem from Wikipedia]
* [https://en.wikipedia.org/wiki/Sion%27s_minimax_theorem Sion's minimax theorem from Wikipedia]
* [http://www.freepatentsonline.com/5414310.html Analog voltage maximizer and minimizer circuits] from [http://www.freepatentsonline.com/ FreePatentsOnline]
=References=
<references />
'''[[Search|Up one level]]'''
[[FILE:ConstructedbyMinimaxDadamax.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person
| [[Arts#Ernst|Max Ernst]], [https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person Little Machine Constructed] by [https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person Minimax Dadamax in Person], 1919-1920 <ref>[https://en.wikipedia.org/wiki/Little_Machine_Constructed_by_Minimax_Dadamax_in_Person Little Machine Constructed by Minimax Dadamax in Person from Wikipedia]</ref> ]]
'''Minimax''',<br/>
an algorithm used to determine the [[Score|score]] in a [https://en.wikipedia.org/wiki/Zero-sum 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 [[Ply|one-ply]] search, where only move sequences with length one are examined, the side to move (max player) can simply look at the [[Evaluation|evaluation]] after playing all possible [[Moves|moves]]. The move with the best evaluation is chosen. But for a two-[[Ply|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.
<span id="History"></span>
=History=
[[Jaap van den Herik|Jaap van den Herik's]] thesis (1983) <ref>[[Jaap van den Herik]] ('''1983'''). ''Computerschaak, Schaakwereld en Kunstmatige Intelligentie''. Ph.D. thesis, [[Delft University of Technology]]. Academic Service, The Hague. ISBN 90 62 33 093 2 (Dutch)</ref> contains a detailed account of the known publications on that topic. It concludes that although [[John von Neumann]] is usually associated with that concept ([[Timeline#1928|1928]]) <ref>[[John von Neumann]] ('''1928'''). ''[http://gdz.sub.uni-goettingen.de/dms/load/img/?IDDOC=29357 Zur Theorie der Gesellschaftsspiele]''. Berlin</ref> , [https://en.wikipedia.org/wiki/Primacy_of_mind primacy] probably belongs to [[Mathematician#Borel|Émile Borel]]. Further there is a conceivable claim that the first to credit should go to [[Mathematician#Babbage|Charles Babbage]] <ref>[[Don Beal]] ('''1999'''). ''The Nature of MINIMAX Search''. Ph.D. thesis, ISBN 90-62-16-6348, pp. 2, refers [[Mathematician#PhilipMorrison|Philip Morrison]] and Emily Morrison ('''1961'''). ''Charles Babbage and his Calculating Engines''. Dover Publ. New York</ref>. The original minimax as defined by Von Neumann is based on exact values from [[Terminal Node|game-terminal positions]], whereas the minimax search suggested by [[Norbert Wiener]] <ref>[[Norbert Wiener]] ('''1948'''). ''[http://www.amazon.com/gp/reader/026273009X/ref=sib_dp_pt#reader-link Cybernetics or Control and Communication in the Animal and the Machine]'' - MIT Press, Cambridge, MA.</ref> is based on [[Evaluation|heuristic evaluations]] from positions a few moves distant, and far from the end of the game.
=Implementation=
Below the pseudo code for an indirect [[Recursion|recursive]] [[Depth-First|depth-first search]]. For clarity [[Make Move|move making]] and [[Unmake Move|unmaking]] before and after the recursive call is omitted.
<pre>
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;
}
</pre>
=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]]
* [[James R. Slagle#TheoremProving|Theorem-Proving and M & N procedure]]
* [[Jack Good#TheoremProving|Theorem-Proving from Five-Year Plan]]
==People==
* [[John von Neumann]]
* [[Claude Shannon]]
* [[Norbert Wiener]]
=Selected Publications=
==1920 ...==
* <span id="Borel"></span>[[Mathematician#Borel|É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 [[Mathematician#LJSavage|Leonard J. Savage]] ('''1953'''). ''[[Minimax#Savage|The Theory of Play and Integral Equations with Skew Symmetric Kernels]]''.
* [[John von Neumann]] ('''1928'''). ''[http://gdz.sub.uni-goettingen.de/dms/load/img/?IDDOC=29357 Zur Theorie der Gesellschaftsspiele]''. Berlin <ref>[[Alexander Reinefeld]] ('''2005'''). ''Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen''. [http://www.informatik.hu-berlin.de/studium/ringvorlesung/ss05/slides/05-06-02.pdf slides as pdf], Themen der Informatik im historischen Kontext Ringvorlesung an der [https://en.wikipedia.org/wiki/Humboldt_University_of_Berlin HU Berlin], 02.06.2005 (English paper, German title)</ref>
==1940 ...==
* [[John von Neumann]], [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] ('''1944'''). ''[https://en.wikipedia.org/wiki/Theory_of_Games_and_Economic_Behavior Theory of Games and Economic Behavior]''. Princeton University Press, Princeton, NJ.
* [[Norbert Wiener]] ('''1948'''). ''[http://www.amazon.com/gp/reader/026273009X/ref=sib_dp_pt#reader-link Cybernetics or Control and Communication in the Animal and the Machine]'' - MIT Press, Cambridge, MA.
==1950 ...==
* [[Claude Shannon]] ('''1950'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]'', Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950
* [[Mathematician#Weyl|Hermann Weyl]] ('''1950'''). ''Elementary Proof of a Minimax Theorem due to von Neumann''. in
: [[Mathematician#HWKuhn|Harold W. Kuhn]] and [[Mathematician#AWTucker|Albert W. Tucker]] (eds) ('''1950'''). ''[http://books.google.com/books?id=TpbbVU4tA58C&printsec=frontcover&dq=isbn:9780691079349&hl=de&ei=r2i1TabJL8_usgaW-rj7Cw&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCoQ6AEwAA#v=onepage&q&f=false Contributions to the Theory of Games I]''. [https://en.wikipedia.org/wiki/Princeton_University_Press Princeton University Press]
* [[Mathematician#Borel|Émile Borel]], [[Mathematician#MRFrechet|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''. [https://en.wikipedia.org/wiki/Econometrica Econometrica], Vol. 21
* <span id="Savage"></span>[[Mathematician#LJSavage|Leonard J. Savage]] ('''1953'''). ''The Theory of Play and Integral Equations with Skew Symmetric Kernels''. [https://en.wikipedia.org/wiki/Econometrica Econometrica], Vol. 21, pp. 101-115, English translation of [[Mathematician#Borel|Émile Borel]] ('''1921'''). ''[[Minimax#Borel|La théorie du jeu et les équations intégrales à noyau symétrique]]''.
* [[Mathematician#DHBlackwell|David Blackwell]] ('''1956'''). ''[http://projecteuclid.org/euclid.pjm/1103044235 An analog of the minimax theorem for vector payoffs]''. [https://en.wikipedia.org/wiki/Pacific_Journal_of_Mathematics Pacific Journal of Mathematics], Vol. 6, 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, [https://en.wikipedia.org/wiki/Leslie_Fox Leslie Fox] (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix: ''Rules of SOMAC'' by [[John Maynard Smith]], introduces [https://en.wikipedia.org/wiki/Expectiminimax_tree Expectiminimax tree] <ref>see [[Helmut Richter#Swapoff|Swap-off]] by [[Helmut Richter]]</ref>
* [[James R. Slagle]], [[Philip Bursky]] ('''1968'''). ''[http://portal.acm.org/citation.cfm?id=321444 Experiments With a Multipurpose, Theorem-Proving Heuristic Program]''. [[ACM#Journal|Journal of the ACM]], Vol. 15, No. 1
* [[James R. Slagle]], [[John K. Dixon]] ('''1969'''). ''Experiments With Some Programs That Search Game Trees''. [[ACM#Journal|Journal of the ACM]], Vol 16, No. 2, [http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf pdf]
==1970 ...==
* [[James R. Slagle]], [[John K. Dixon]] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362052.362054 Experiments with the M & N Tree-Searching Program]''. [[ACM#Communications|Communications of the ACM]], Vol. 13, No. 3, pp. 147-154.
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p004.htm#index54 Minimax] in [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''.
==1980 ...==
* [[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]]
* [[Ronald L. Rivest]] ('''1987'''). ''Game Tree Searching by Min/Max Approximation''. Artificial Intelligence Vol. 34, 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]
==1990 ...==
* [[Liwu Li]], [[Tony Marsland]] ('''1990'''). ''On Minimax Game Tree Search Pathology and Node-value Dependence''. TR90-24, [[University of Alberta]], [https://webdocs.cs.ualberta.ca/~tony/TechnicalReports/TR90-24.pdf pdf]
* [[Claude G. Diderich]] ('''1993'''). ''[http://portal.acm.org/citation.cfm?id=165007 A Bibliography on Minimax Trees]''. [[ACM#SIG|ACM SIGACT News]], Vol. 24, No. 4
* [[David E. Moriarty]], [[Risto Miikkulainen]] ('''1994'''). ''Evolving Neural Networks to focus Minimax Search''. [[AAAI|AAAI-94]], [http://www.cs.utexas.edu/~ai-lab/pubs/moriarty.focus.pdf pdf] » [[Othello]]
* [[Claude G. Diderich]], [[Marc Gengler]] ('''1995'''). ''[http://link.springer.com/chapter/10.1007/978-1-4613-3557-3_2 A Survey on Minimax Trees and Associated Algorithms]''. ''[http://link.springer.com/book/10.1007/978-1-4613-3557-3 Minimax and Its Applications]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers]
* [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-first minimax search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, Nos 1-2 » [[Best-First]]
* [[Yoav Freund]], [[Robert Schapire]] ('''1996'''). ''Game Theory, On-line Prediction and Boosting''. [http://dblp.uni-trier.de/db/conf/colt/colt1996.html#FreundS96 COLT 1996], [http://www.cs.princeton.edu/~schapire/papers/FreundSc96b.pdf pdf]
* [[Don Beal]] ('''1999'''). ''The Nature of MINIMAX Search''. Ph.D. thesis
==2000 ...==
* [[Claude G. Diderich]], [[Marc Gengler]] ('''2001'''). ''[http://link.springer.com/referenceworkentry/10.1007%2F0-306-48332-7_280 Minimax Game Tree Searching]''. [http://link.springer.com/book/10.1007/0-306-48332-7 Encyclopedia of Optimization], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [http://milne.ruc.dk/~thk/ Tinne Hoff Kjeldsen] ('''2001'''). ''John von Neumann’s Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts''. [https://en.wikipedia.org/wiki/Archive_for_History_of_Exact_Sciences Archive for History of Exact Sciences], Vol. 56, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Thomas Hauk]], [[Michael Buro]], [[Jonathan Schaeffer]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_3 Rediscovering *-Minimax Search]''. [[CG 2004]], [http://skatgame.net/mburo/ps/STAR-A.pdf pdf]
* [[Mitja Luštrek]], [[Matjaž Gams]], [[Ivan Bratko]] ('''2005'''). ''[http://dl.acm.org/citation.cfm?id=1642327 Why Minimax Works: An Alternative Explanation]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2005.html#LustrekGB05 IJCAI 2005] » [[Search Pathology]]
* [[Claude G. Diderich]], [[Marc Gengler]] ('''2009'''). ''[http://link.springer.com/referenceworkentry/10.1007%2F978-0-387-74759-0_370 Minimax Game Tree Searching]''. [http://link.springer.com/book/10.1007/978-0-387-74759-0 Encyclopedia of Optimization], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
==2010 ...==
* [[Jeff Rollason]] ('''2014'''). ''[http://www.aifactory.co.uk/newsletter/2014_01_interest_minimax.htm Interest Search - Another way to do Minimax]''. [[AI Factory]], Summer 2014
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=13433 beyond minimax] by [[Harm Geert Muller]], [[CCC]], April 27, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=42806 The evaluation value and value returned by minimax search] by [[Ma Chao]], [[CCC]], March 09, 2012 » [[Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54295 Why minimax is fundamentally flawed] by [[Harm Geert Muller]], [[CCC]], November 09, 2014 » [[KRK]]
=External Links=
* [http://web.archive.org/web/20070820195815/www.seanet.com/%7Ebrucemo/topics/minmax.htm Min-Max Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [https://en.wikipedia.org/wiki/Minimax Minimax from Wikipedia]
* [https://en.wikipedia.org/wiki/Minimax_estimator Minimax estimator from Wikipedia]
* [https://en.wikipedia.org/wiki/Expectiminimax_tree Expectiminimax tree from Wikipedia]
* [https://en.wikipedia.org/wiki/Maxima_and_minima Maxima and minima from Wikipedia]
* [https://en.wikipedia.org/wiki/Nash_equilibrium Nash equilibrium from Wikipedia]
* [https://en.wikipedia.org/wiki/Parthasarathy%27s_theorem Parthasarathy's theorem from Wikipedia]
* [https://en.wikipedia.org/wiki/Sion%27s_minimax_theorem Sion's minimax theorem from Wikipedia]
* [http://www.freepatentsonline.com/5414310.html Analog voltage maximizer and minimizer circuits] from [http://www.freepatentsonline.com/ FreePatentsOnline]
=References=
<references />
'''[[Search|Up one level]]'''
