Alpha beta pruning search count

Question

I am trying to play with the alpha beta pruning algorithm; I got the program working. I need to figure out the number of searches was done before alpha or beta value got selected. I am counting the value but I am not sure if the count value is right.

int alpha_beta(const int level, const bool player, const Board &board, int alpha, int beta, Move &move) {
**static int count = 0;**

if (board.isGameOver() || level == 0) {
    if (!board.isGameOver()) move = (board.legalMoves())[0];
    return (getScore(board));
}

vector<Move> children = board.legalMoves();

tempBoard = board;
permutator(children.begin(), children.end());
//cout << count;
//getchar();
if (player == MAX) {
    for (vector<Move>::iterator it = children.begin(); it != children.end(); it++) {
        Board child = board.doMove(*it);
        Move temp;
        int score = alpha_beta(level - 1, !player, child, alpha, beta, temp);
        if (score > alpha) {
            alpha = score; // We have found a better best move
            move = *it;
        }
        if (alpha >= beta) {
            move = *it;
            cout << alpha;
            return alpha; // Beta Cut Off
            cout << alpha;
        }
        count++;
    }

    **cout << "alpha count ="<<count;**
    std::getchar();
    return alpha; // This is our best move

}
else {
    for (vector<Move>::iterator it = children.begin(); it != children.end(); it++) {
        Board child = board.doMove(*it);
        Move temp;
        int score = alpha_beta(level - 1, !player, child, alpha, beta, temp);
        if (score < beta) {
            beta = score; // Opponent has found a better worse move
            move = *it;
        }
        if (alpha >= beta) {
            move = *it;
            cout << beta;
            return beta; // Alpha Cut Off
        }


        count++;
    }
    **cout <<" beta count ="<<count;**
    std::getchar();
    return beta; // This is the opponent's best move
}}

Any suggestion would be helpful on the search count.

Answer 1

Just a simple thought that may be you should implement the Minimax algorithm first because basically, alpha beta pruning is an optimization of Minimax so that if you want to get the total number of leaves searched before alpha or beta is selected, Minimax is maybe a good choice.

In that case, you should add a counter whenever your tree reaches leave node

if (board.isGameOver() || level == 0) {
    count ++;
    if (!board.isGameOver()) move = (board.legalMoves())[0];
    return (getScore(board)); 
}