Minimax博弈树

1. Minimax博弈树

Minimax Game Trees（简称MGT）是游戏AI中一种很重要的数据结构，用于双方轮流博弈，每次执行一步。MGT是一棵包含了所有可能的执行步骤的树，每个节点可拥有任意数目的子节点。

2. Minimax搜索

Minimax搜索算法是一种找出失败的最大可能性中的最小值的算法，一般以递归方式实现。其假定博弈双方都尽自己的最大努力获得好结果。该算法是零和算法，即一方要选择将其优势最大化的走法，另一方则选择令对手优势最小化的走法，其输赢的总和为零。

3. Alpha-Beta剪枝

预测的步数越多，生成的MGT越庞大，搜索的消耗会很大。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需要进行评估的节点的范围的优化，即Alpha-Beta剪枝，它能够快速裁剪掉不必要的搜索分支，从而提高搜索的效率。
下面是Minimax Alpha-Beta剪枝的核心代码：

int minimax(const Node &node, int depth, int min_, int max_)
{
if ( isLeaf(node) || depth == 0 )
{
return evaluate(node);
}

if ( isMaxNode(node) )
{
    int score = min_;
    for(auto it = node.children.cbegin(); it != node.children.cend(); ++it)
    {
        int newScore = minimax(*it, depth-1, score, max_);
        if(newScore > score) score = newScore;
        if(score > max_) return max_;
    }
    return score;
}

if ( isMinNode(node) )
{
    int score = max_;
    for(auto it = node.children.cbegin(); it != node.children.cend(); ++it)
    {
        int newScore = minimax(*it, depth-1, min_, score);
        if(newScore < score) score = newScore;
        if(score < min_) rturn min_;
    }
    return score;
}

}

4. 适用场合

MGT最适合完全信息博弈（games of perfect information），即博弈双方能看到博弈的全部信息，比如棋类游戏（国际象棋、五子棋、围棋等）。但是有些游戏，比如扑克，因为一方不能看另一方手上的牌，所以很难判断对手的走法，所以MGT就不怎么适用。

5. 参考文献

题图来自：AI Horizon <AI Horizon: Computer Science and Artificial Intelligence Programming Resources>
AI Horizon: Minimax Game Tree Programming, Part 1
AI Horizon: Minimax Game Tree Programming, Part 2