维基百科
极小化极大算法
Minimax算法（亦稱 MinMax or MM[1]）又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。
概述
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 参考文献
外部連結
- Hazewinkel, Michiel (编), Minimax principle, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- A visualization applet （页面存档备份，存于互联网档案馆）
- at Dictionary of Philosophical Terms and Names
- Play a betting-and-bluffing game against a mixed minimax strategy （页面存档备份，存于互联网档案馆）
- Minimax （页面存档备份，存于互联网档案馆） at Dictionary of Algorithms and Data Structures
- Minimax （页面存档备份，存于互联网档案馆） (with or without alpha-beta pruning) algorithm visualization — game tree solving (Java Applet), for balance or off-balance trees.
- Minimax Tutorial with a Numerical Solution Platform （页面存档备份，存于互联网档案馆）
- Java implementation used in a Checkers Game （页面存档备份，存于互联网档案馆）