使用minimax算法时如何获取返回最优值的节点以实现最优走棋

现有代码核心问题 #

• 递归调用逻辑错误：循环遍历子节点时，minimax调用传入的仍是当前父节点node，并未向下遍历子节点，搜索逻辑完全无效
• 仅返回最优分值，未将分值与对应节点绑定存储，根节点层无法匹配到最优走法对应的子节点
• alpha-beta剪枝判断逻辑存在变量引用错误，原有判断使用的是函数入参的全局alpha/beta，而非迭代过程中更新的局部Alpha/Beta

修复方案 #

我们采用「给Node新增存储minimax计算分值的成员 + 修正minimax递归逻辑」的方案实现需求，修改后的代码如下：
首先在Node类定义中新增成员变量，存储当前节点的minimax计算分值：

// 在Node类对应的头文件中添加该成员
int minimaxScore;

之后修改GameTree类的minimax函数：

#include "gametree.h"
//Constructor
GameTree::GameTree()
{

}

/* 修正后的minimax函数，同步将计算得到的最优分值写入对应节点的minimaxScore成员 */
int GameTree::minimax(Node *node, int depth, int alpha, int beta, bool isMaxNode)
{
    int Alpha = alpha;
    int Beta = beta;
    
    if (depth == 0|| endGame ==1)
    {
        node->minimaxScore = node->score;
        return node->minimaxScore;
    }
    if (isMaxNode)
    {
        int HighScore = -1000;
        for (int i =0; i< (int)node->children.size(); i++)
        {
            // 修复递归参数：传入当前遍历的子节点，而非父节点
            int childScore = minimax(node->children[i], depth-1, Alpha, Beta, false);
            HighScore = max(HighScore, childScore);
            Alpha = max(Alpha, HighScore);
            if (Beta <= Alpha)
            {
                break;
            }
        }
        node->minimaxScore = HighScore;
        return HighScore;
    }
    else
    {
        int LowScore = 1000;
        for (int i =0; i< (int)node->children.size(); i++)
        {
            // 修复递归参数：传入当前遍历的子节点，而非父节点
            int childScore = minimax(node->children[i], depth-1, Alpha, Beta, true);
            LowScore = min(LowScore, childScore);
            Beta = min(Beta, LowScore);
            if (Beta <= Alpha)
            {
                break;
            }
        }
        node->minimaxScore = LowScore;
        return LowScore;
    }
}

最后修改GetNextMove函数，先调用minimax完成全树分值计算，再遍历根节点的子节点匹配最优走法：

void GameTree::GetNextMove()
{
    // 第一个参数为根节点，第二个参数可替换为你需要的搜索深度，根节点默认是max节点
    minimax(nodeRoot, 6, -1000, 1000, true);
    nodeNext = *nodeRoot->children.begin();
    for (Node *n : nodeRoot->children)
    {
        // 基于子节点的minimax计算分值比较，得到最优走法对应节点
        if (n->minimaxScore > nodeNext->minimaxScore)
        {
            nodeNext = n;
        }
    }
    nodeNext->UpdateDisplay(4);
    return;
}

内容的提问来源于stack exchange，提问作者Strahan and Dee Kelly