实现Alpha-beta剪枝到minimax算法的困难

Question

我很难让Alpha-beta修剪正常工作。我有一个函数Minimax算法，我试着去适应，但没有用。我在维基百科上用了这个例子

目前，该算法似乎在大多数情况下都按预期运行，但不管怎样，它都会选择第一个测试节点。

这可能是因为缺乏理解，但我已经花了数小时阅读了这篇文章。让我困惑的是，在零和博弈中，算法如何知道当达到深度极限时哪个节点是最佳选择；在哪一点上，我们还不能确定哪位球员会从这样的举动中受益最大，是吗？

不管怎样，我的朋友。cpp在下面。无论是我原来的极小极大函数和任何帮助将不胜感激！

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:：Minimax Alphabeta（常数图

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

}

Answer 1

你的极小值递归调用和移动世代在逻辑上是正确的，除了你不应该用它直接在里面得出获胜者。你的叶节点评估应该是强大的，这是关键，这在你的代码中似乎是缺乏的。此外，冗长的叶节点函数会使人工智能决策太慢。

下面是递归MiniMax函数的伪代码。假设parent_graph是评估最佳移动之前的状态，leaf_graph是当前离开节点的状态。你必须在极小极大树中找到相对（不要与绝对）最好的分支。

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

评估LeafNode函数可以这样读：

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