极小化极大算法:修订间差异
删除的内容 添加的内容
小 机器人: Cat:字数已超过3000字节的小作品 |
日期20220626(留言 | 贡献) →极小化极大算法: // Edit via Wikiplus |
||
第4行: | 第4行: | ||
}} |
}} |
||
'''Minimax算法'''(亦稱 '''MinMax''' or '''MM'''<ref>[http://www.fraserinstitute.org/uploadedFiles/fraser-ca/Content/research-news/research/publications/provincial-healthcare-index-2013.pdf Provincial Healthcare Index 2013] {{Wayback|url=http://www.fraserinstitute.org/uploadedFiles/fraser-ca/Content/research-news/research/publications/provincial-healthcare-index-2013.pdf |date=20150811005733 }} (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)</ref>)又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。 |
'''Minimax算法'''(亦稱 '''MinMax''' or '''MM'''<ref>[http://www.fraserinstitute.org/uploadedFiles/fraser-ca/Content/research-news/research/publications/provincial-healthcare-index-2013.pdf Provincial Healthcare Index 2013] {{Wayback|url=http://www.fraserinstitute.org/uploadedFiles/fraser-ca/Content/research-news/research/publications/provincial-healthcare-index-2013.pdf |date=20150811005733 }} (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)</ref>)又名极小化极大算法,是一种找出失败的最大可能性中的最小值(最小化最坏情况)的算法。 |
||
== 概述 == |
== 概述 == |
2024年5月13日 (一) 04:59的最新版本
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
参考文献[编辑]
- ^ 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 (页面存档备份,存于互联网档案馆)
|