Minimax博弈树

skymanwu (45)in #cn • 7 years ago (edited)

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;
}

}