beta pruning to minimax algorithm
I'm having some difficulty getting Alpha-beta pruning to work correctly. I've got a functional Minimax algorithm, which I've tried to adapt, but to no avail. I used the example on Wikipedia
Currently, the algorithm seems to run as expected for the most part, but then it chooses the first node tested regardless.
This could potentially be due to lack of understanding, but I've spent hours reading up on this already. What confused me is how the algorithm is supposed to know which node is the best choice when it reaches its depth limit in a zero sum game; at which point it can't be certain which player would benefit most from such a move, can it?
Anyway, my .cpp is below. Both my original minimax function and Any help whatsoever will be appreciated!
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;
}
}
Your minimax recursive call and moves generations are logically correct except that you shouldn't use it to conclude the winner directly inside. Your leaf nodes evaluation should to be strong , that's the key, which seems lacking in your code. Also a verbose leaf node function will make the AI decision making too slow.
Here's a pseudo code for your recursive MiniMax function.Say parent_graph is the state before evaluation for the best move and leaf_graph is the current leave node status. You have to find the relative ( don't mix with the absolute ) best branch among the minimax tree.
if (depth == 0) {
return EvaluateLeafNode(isMaximizing,parent_graph,leaf_graph);
}
EvaluateLeafNode function can read like this:
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;
}
下一篇: beta修剪minimax算法