Difficulty implementing Alpha-beta pruning to minimax algorithm

Question

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

}

seccpur · Accepted Answer · 2018-03-07T09:22:39.530

0

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

edited Mar 07 '18 at 09:22

answered Mar 06 '18 at 17:41

seccpur

4,996
2
13
21

I'm still having trouble with this (evidently I currently lack sufficient insight into AI programming!) but after a bit of debugging following your advice, I can conclude that it is my evaluation method that is failing me. My understanding is that the program should reach a final score value for a particular state based on a predefined set of heuristics unique to the game (chess, droughts etc.). Does this sound about right? – Lich Mar 08 '18 at 09:41
Examples of this might be: 1.whether the state is a winning/ losing state 2. The number of pieces for each player (such as in chess) remaining 3. Adjacency of friendly/ enemy nodes etc.... Then the challenge is programming these heuristics efficiently and effectively. – Lich Mar 08 '18 at 09:44
@Lich: For wining or losing you may allot +INF or -INF without further evaluation of the node. Your assessment in the comment is right. You can also integrate end moves and remove few unlikely moves to make your search tree slimmer. Even with simple leaf evaluation routine, it is very interesting to see the AI moves. – seccpur Mar 08 '18 at 09:56
Great, thank you for the snappy confirmation and for your assistance. It's really helped me to better understand what it is I'm trying to achieve. I'll leave this question unanswered for the time being while I take a stab at implementing it. – Lich Mar 08 '18 at 11:51

Difficulty implementing Alpha-beta pruning to minimax algorithm

1 Answers1