极小化极大算法 目录 概述 伪代码 註釋 外部連結 导航菜单Provincial Healthcare Index...
检测论游戏人工智能图算法优化算法与方法搜尋演算法博弈论数理与定量方法 (经济学)离散数学定理决策论不动点
零总和井字棋
Minimax算法(亦稱 MinMax or MM[1])又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。
目录
1 概述
2 伪代码
3 註釋
4 外部連結
概述
Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法,例如井字棋(tic-tac-toe)。
伪代码
function minimax(node, depth)
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
let α := +∞
foreach child of node
α := min(α, minimax(child, depth-1))
else {we are to play at node}
let α := -∞
foreach child of node
α := max(α, minimax(child, depth-1))
return α
註釋
^ Provincial Healthcare Index 2013 (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)
外部連結
Hazewinkel, Michiel (编), Minimax principle, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- A visualization applet
Maximin principle 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
|