Difference between revisions of "Minimax"

From Chessprogramming wiki
Jump to: navigation, search
(5 intermediate revisions by the same user not shown)
Line 67: Line 67:
 
* <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]]''.
 
* <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
 
* [[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
 +
* [[Mathematician#MSion|Maurice Sion]] ('''1958'''). ''[https://projecteuclid.org/euclid.pjm/1103040253 On general minimax theorems]''. [https://en.wikipedia.org/wiki/Pacific_Journal_of_Mathematics Pacific Journal of Mathematics], Vol. 8, No. 1 <ref>[https://en.wikipedia.org/wiki/Sion%27s_minimax_theorem Sion's minimax theorem from Wikipedia]</ref>
 
==1960 ...==
 
==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
 
* [[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
Line 73: Line 74:
 
* [[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]
 
* [[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 ...==
 
==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.
+
* [[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
 +
* [[Mathematician#TParthasarathy|Thiruvenkatachari Parthasarathy]] ('''1970'''). ''[https://epubs.siam.org/doi/abs/10.1137/0119047?journalCode=smjmap On Games Over the Unit Square]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Applied_Mathematics SIAM Journal on Applied Mathematics], Vol. 19, No. 2 <ref>[https://en.wikipedia.org/wiki/Parthasarathy%27s_theorem Parthasarathy's theorem from Wikipedia]</ref>
 
* [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]''.
 
* [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 ...==
 
==1980 ...==
 
* [[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]]
 
* [[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]]
 +
* [[Chun-Hung Tzeng]], [[Paul W. Purdom]] ('''1983'''). ''[https://www.aaai.org/Library/AAAI/1983/aaai83-080.php A Theory of Game Trees]''. [[Conferences#AAAI-83|AAAI-83]]
 +
* [[Dana S. Nau]], [[Paul W. Purdom]], [[Chun-Hung Tzeng]] ('''1986'''). ''Experiments on Alternatives to Minimax''. [https://dblp.uni-trier.de/db/journals/ijpp/ijpp15.html#NauPT86 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, [https://arxiv.org/abs/1304.3445 arXiv:1304.3445]
 
* [[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]
 
* [[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 ...==
 
==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]
 
* [[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
 
* [[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]]
+
* [[David E. Moriarty]], [[Risto Miikkulainen]] ('''1994'''). ''[http://nn.cs.utexas.edu/?moriarty:aaai94 Evolving Neural Networks to focus Minimax Search]''. [[Conferences#AAAI-94|AAAI-94]] » [[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]
 
* [[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]]
 
* [[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]]
Line 95: Line 100:
 
==2010 ...==
 
==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
 
* [[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
 +
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Anton Scheucher]] ('''2017'''). ''[https://ieeexplore.ieee.org/document/7358032 Product Propagation: A Back-up Rule Better than Minimaxing?]'' [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 9, No. 2, [[:File:KaindlProductPropagation.pdf|pdf]]
  
 
=Forum Posts=
 
=Forum Posts=
Line 104: Line 110:
 
* [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]
 
* [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 Minimax from Wikipedia]
 +
* [https://en.wikipedia.org/wiki/Minimax_theorem Minimax theorem 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]
 
* [https://en.wikipedia.org/wiki/Minimax_estimator Minimax estimator 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/Expectiminimax_tree Expectiminimax tree from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Maxima_and_minima Maxima and minima 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]
 
* [http://www.freepatentsonline.com/5414310.html Analog voltage maximizer and minimizer circuits] from [http://www.freepatentsonline.com/ FreePatentsOnline]
* [[:Category:Kraftwerk|Kraftwerk]] - Pocket Calculator, [https://en.wikipedia.org/wiki/Minimum-Maximum Minimum-Maximum], [https://en.wikipedia.org/wiki/Moscow Moscow], [https://en.wikipedia.org/wiki/Luzhniki_Olympic_Complex Luzhniki], June 03, 2004, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category:Kraftwerk|Kraftwerk]] - Pocket Calculator, [https://en.wikipedia.org/wiki/Minimum-Maximum Minimum-Maximum], [https://en.wikipedia.org/wiki/Moscow Moscow], [https://en.wikipedia.org/wiki/Luzhniki_Olympic_Complex Luzhniki], June 03, 2004 and [https://en.wikipedia.org/wiki/Tokyo Tokyo], [https://en.wikipedia.org/wiki/Shibuya_Station Shibuya Station], March 04, 2004, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
: {{#evu:https://www.youtube.com/watch?v=naOG7CRtlHg|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=naOG7CRtlHg|alignment=left|valignment=top}}
  

Revision as of 10:10, 4 April 2021

Home * Search * Minimax

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) [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.

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

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

  1. Little Machine Constructed by Minimax Dadamax in Person from Wikipedia
  2. 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)
  3. John von Neumann (1928). Zur Theorie der Gesellschaftsspiele. Berlin
  4. 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
  5. Norbert Wiener (1948). Cybernetics or Control and Communication in the Animal and the Machine - MIT Press, Cambridge, MA.
  6. 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)
  7. Sion's minimax theorem from Wikipedia
  8. see Swap-off by Helmut Richter
  9. Parthasarathy's theorem from Wikipedia

Up one level