难以对 minimax 算法实施 Alpha-beta 剪枝

Question

我在让 Alpha-beta p运行ing 正常工作时遇到一些困难。我有一个功能性的 Minimax 算法，我试图对其进行调整，但无济于事。我在 Wikipedia

上使用了示例

目前，该算法似乎运行大多数情况下都符合预期，但随后它无论如何都会选择第一个测试的节点。

这可能是由于缺乏理解，但我已经花了几个小时阅读它。令我困惑的是，当算法在零和博弈中达到深度限制时，该算法如何知道哪个节点是最佳选择；在这一点上不能确定哪个球员会从这样的举动中获益最多，不是吗？

无论如何，我的.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;
}

}

Answer 1

您的 minimax 递归调用和移动生成在逻辑上是正确的，只是您不应该使用它来直接在内部得出获胜者。您的叶节点评估应该是 strong ，这是您的代码中似乎缺少的关键。此外，冗长的叶节点函数会使 AI 决策速度太慢。

这是您的递归 MiniMax 的伪代码 function.Say 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;
}

难以对 minimax 算法实施 Alpha-beta 剪枝

Difficulty implementing Alpha-beta pruning to minimax algorithm

artificial-intelligence

minimax

alpha-beta-pruning