我在尝试将Alpha-beta剪枝正确应用到Minimax算法时遇到了困难。我已经有一个可用的Minimax算法，并尝试对其进行修改，但没有成功。我参考了维基百科上的示例

目前，算法在大部分情况下似乎运行正常，但它总是选择第一个测试的节点。

这可能是由于对算法的理解不足导致的，但我已经花了几个小时研究这个问题。让我感到困惑的是，当算法在一个零和游戏中达到其深度限制时，它如何知道哪个节点是最佳选择；在那个时候，它无法确定哪个玩家会从这样的移动中获益最多，对吗？

无论如何，我的.cpp代码如下。我的原始minimax函数和任何帮助都将不胜感激！

AIMove ComputerInputComponent::FindBestMove() {const Graph<HexNode>* graph = HexgameCore::GetInstance().GetGraph();std::vector<AIMove> possibleMoves;FindPossibleMoves(*graph, possibleMoves);AIMove bestMove = AIMove();int alpha = INT_MIN;int beta = INT_MAX;int depth = 6;Node* currentNode;for (const AIMove &move : possibleMoves) {    std::cout << move << std::endl;    graph->SetNodeOwner(move.x, move.y, (NodeOwner)aiPlayer);    int v = MiniMaxAlphaBeta(*graph, depth, alpha, beta, true);    graph->SetNodeOwner(move.x, move.y, NodeOwner::None);    if (v > alpha) {        alpha = v;        bestMove.x = move.x;        bestMove.y = move.y;    }}return bestMove;

}

template<typename T>

int ComputerInputComponent::MiniMaxAlphaBeta(const Graph& graph, int depth, int alpha, int beta, bool isMaximiser) {

std::vector<AIMove> possibleMoves;FindPossibleMoves(graph, possibleMoves);if (lastTestedNode != nullptr) {    Pathfinder pathFinder;    bool pathFound = pathFinder.SearchForPath(lastTestedNode, graph.GetMaxX(), graph.GetMaxY());    if (pathFound) {        //std::cout << "pathfound-" << std::endl;        if ((int)lastTestedNode->GetOwner() == aiPlayer) {            std::cout << "cpuWin-" << std::endl;            return 10;        }         else if ((int)lastTestedNode->GetOwner() == humanPlayer) {            std::cout << "playerWin-" << std::endl;            return -10;        }    }    else {        if (depth == 0) {                       //std::cout << "NoPath-" << std::endl;            return 0;        }    }}if (isMaximiser) {// Max    int v = -INT_MAX;    for (const AIMove &move : possibleMoves) {        graph.SetNodeOwner(move.x, move.y, (NodeOwner)aiPlayer);        graph.FindNode(move.x, move.y, lastTestedNode);        v = std::max(alpha, MiniMaxAlphaBeta(graph, depth - 1, alpha, beta, false));        alpha = std::max(alpha, v);        graph.SetNodeOwner(move.x, move.y, NodeOwner::None);        if (beta <= alpha)            break;    }    return v;}else if (!isMaximiser){ // Min    //std::cout << "Human possiblMoves size  = " << possibleMoves.size() << std::endl;    int v = INT_MAX;    for (const AIMove &move : possibleMoves) {        graph.SetNodeOwner(move.x, move.y, (NodeOwner)humanPlayer);        v = std::min(beta, MiniMaxAlphaBeta(graph, depth - 1, alpha, beta, true));        beta = std::min(beta, v);        graph.SetNodeOwner(move.x, move.y, NodeOwner::None);        if (beta <= alpha)            break;    }    return v;}

}

回答：

你的Minimax递归调用和移动生成在逻辑上是正确的，但你不应该直接在其中得出赢家的结论。你的叶节点评估应该很强，这是关键，你的代码中似乎缺乏这一点。此外，一个冗长的叶节点函数会使AI的决策变得太慢。

这里是你的递归MiniMax函数的伪代码。假设parent_graph是评估最佳移动前的状态，leaf_graph是当前叶节点的状态。你必须在minimax树中找到相对的最佳分支（不要与绝对的最佳分支混淆）。

if (depth == 0) {                   return EvaluateLeafNode(isMaximizing,parent_graph,leaf_graph);    }

EvaluateLeafNode函数可以这样写：

int EvaluateLeafNode(bool isMaximizing,Graph& parent_graph,Graph& leaf_graph){   int score = 0;   int w = find_relative_white_deads(parent_graph,leaf_graph);   int b = find_relative_black_deads(parent_graph,leaf_graph);   if(isMaximizing)      score += b;   else      score += w;   return score;}