Konwersja minimax na przycinanie alfa beta do negamax

Napisałem aminimax algorytm zprzycinanie alfa beta dla Warcaby gry, a teraz próbuję ją przepisać za pomocąnegamax podejście. Spodziewam się, że te dwa będą równoważne, ponieważ negamax to tylko technika pisania minimaks. Ale z jakiegoś powodu moje dwa algorytmy zachowują się inaczej. Kiedy uruchamiam je oba na tym samym wejściu, wersja negamax wydaje się oceniać więcej stanów, więc myślę, że coś musi być nie tak z przycinaniem beta alfa.

Poniższy kod pokazuje oba algorytmy (minimax inegamax funkcje), a na doleplay funkcja, z której je nazywam. Theevaluate funkcja jest podstawową heurystyką, której używam do oceny stanów w obu algorytmach.

Jakakolwiek pomoc w wykryciu błędu byłaby bardzo odpowiednia.

#include "player.hpp"
#include <algorithm>
#include <limits>
#include <cstdlib>

namespace checkers
{

int evaluatedStates = 0;

int evaluate(const GameState &state)
{
    // FIXME: Improve heuristics.
    int redScore = 0;
    int whiteScore = 0;
    int piece = 0;
    for (int i = 1; i <= 32; ++i)
    {
        piece = state.at(i);
        if (piece & CELL_RED) {
            ++redScore;
            if (piece & CELL_KING)
                redScore += 2;   // King bonus.
        } else if (piece & CELL_WHITE) {
            ++whiteScore;
            if (piece & CELL_KING)
                whiteScore += 2; // King bonus.
        }
    }
    return state.getNextPlayer() == CELL_RED ? whiteScore - redScore : redScore - whiteScore;
}

int minimax(const GameState &state, int depth, int a, int b, bool max)
{
    if (depth == 0 || state.isEOG()) {
        ++evaluatedStates;
        return evaluate(state);
    }
    std::vector<GameState> possibleMoves;
    state.findPossibleMoves(possibleMoves);
    if (max) {
        for (const GameState &move : possibleMoves) {
            a = std::max(a, minimax(move, depth - 1, a, b, false));
            if (b <= a)
                return b; // β cutoff.
        }
        return a;
    } else {
        for (const GameState &move : possibleMoves) {
            b = std::min(b, minimax(move, depth - 1, a, b, true));
            if (b <= a)
                return a; // α cutoff.
        }
        return b;
    }
}

int negamax(const GameState &state, int depth, int a, int b)
{
    if (depth == 0 || state.isEOG()) {
        ++evaluatedStates;
        return evaluate(state);
    }
    std::vector<GameState> possibleMoves;
    state.findPossibleMoves(possibleMoves);
    for (const GameState &move : possibleMoves) {
        a = std::max(a, -negamax(move, depth - 1, -b, -a));
        if (b <= a)
            return b; // β cutoff.
    }
    return a;
}

GameState Player::play(const GameState &pState, const Deadline &pDue)
{
    GameState bestMove(pState, Move());

    std::vector<GameState> possibleMoves;
    pState.findPossibleMoves(possibleMoves);

    int a = -std::numeric_limits<int>::max();
    int b = std::numeric_limits<int>::max();
    for (const GameState &move : possibleMoves) {
        int v = negamax(move, 10, a, b);
        //int v = minimax(move, 10, a, b, false);
        if (v > a) {
            a = v;
            bestMove = move;
        }
    }
    std::cerr << "Evaluated states: " << evaluatedStates << std::endl;
    return bestMove;
}

/*namespace checkers*/ }

questionAnswers(1)

yourAnswerToTheQuestion