极大极小算法

发表于 | 评论数： | 阅读次数：

Minimax算法又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。

1
2
3
4
5
6
7
8
9
10
11
12
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 α

参考链接

  1. 一张图读懂极大极小搜索和α-β剪枝,by housong_csdn.
  2. 极小化极大算法,by wikipedia.