minimaxalpha-beta-pruningnegamax

Is there something wrong with my quiescence search?


I keep getting weird behavior in my negamax-based AI when I try to implement QuiesenceSearch. I based it on the pseudo-code from here:

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;

    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();

        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

And this is my code:

    private double QuiescenceSearch(GameBoard gameBoard, double alpha, double beta, int color)
    {
        double standPat = color * CalculateBoardScore(gameBoard);

        if (standPat >= beta)
        {
            return beta;
        }
        else if (alpha < standPat)
        {
            alpha = standPat;
        }

        foreach (Move move in GetNoisyMoves(gameBoard))
        {
            gameBoard.TrustedPlay(move);
            double score = -1.0 * QuiescenceSearch(gameBoard, -beta, -alpha, -color);
            gameBoard.UndoLastMove();

            if (score >= beta)
            {
                return beta;
            }
            else if (score > alpha)
            {
                alpha = score;
            }
        }

        return alpha;
    }

Namely, the AI seems to behave as-if making the absolute worst move (killing it self) is the way to go.

CalculateBoardScore always returns from the color == 1 side, hence the multiply by color.


Solution

  • I refactored my code and now this works properly:

    private double QuiescenceSearch(GameBoard gameBoard, double alpha, double beta, int color)
    {
        double bestValue = color * CalculateBoardScore(gameBoard);
    
        alpha = Math.Max(alpha, bestValue);
    
        if (alpha >= beta)
        {
            return bestValue;
        }
    
        foreach (Move move in GetNoisyMoves(gameBoard))
        {
            gameBoard.TrustedPlay(move);
            double value = -1 * QuiescenceSearch(gameBoard, -beta, -alpha, -color);
            gameBoard.UndoLastMove();
    
            bestValue = Math.Max(bestValue, value);
    
            alpha = Math.Max(alpha, bestValue);
    
            if (alpha >= beta)
            {
                break;
            }
        }
    
        return bestValue;
    }
    

    The problem with the pseudo code is that it should return the stand_pat/score if it's greater than beta, not beta:

    int Quiesce( int alpha, int beta ) {
        int stand_pat = Evaluate();
        if( stand_pat >= beta )
            return stand_pat;
        if( alpha < stand_pat )
            alpha = stand_pat;
    
        until( every_capture_has_been_examined )  {
            MakeCapture();
            score = -Quiesce( -beta, -alpha );
            TakeBackMove();
    
            if( score >= beta )
                return score;
            if( score > alpha )
               alpha = score;
        }
        return alpha;
    }