极小化极大算法

Minimax算法（亦稱 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值（最小化最坏情况）的算法。

概述
Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。

偽代碼
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else ( minimizing player )
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value

参考文献
外部連結
*

• [http://www.cut-the-knot.org/Curriculum/Games/MixedStrategies.shtml A visualization applet]
• [https://web.archive.org/web/20060307183023/http://www.swif.uniba.it/lei/foldop/foldoc.cgi?maximin+principle Maximin principle] at Dictionary of Philosophical Terms and Names
• [http://www.bewersdorff-online.de/quaak/rules.htm Play a betting-and-bluffing game against a mixed minimax strategy]
• [https://xlinux.nist.gov/dads/HTML/minimax.html Minimax] at Dictionary of Algorithms and Data Structures
• [http://ksquared.de/gamevisual/launch.php Minimax] (with or without alpha-beta pruning) algorithm visualization — game tree solving (Java Applet), for balance or off-balance trees.
• [http://apmonitor.com/me575/index.php/Main/MiniMax Minimax Tutorial with a Numerical Solution Platform]
• [https://github.com/ykaragol/checkersmaster/blob/master/CheckersMaster/src/checkers/algorithm/MinimaxAlgorithm.java Java implementation used in a Checkers Game]