beta修剪minimax算法
我在使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 :: 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;
}