PVS bug?

[ciorap0]

Hello,

I was testing the correctness of my engine's PVS, TT, ID, and move sorting, against plain alpha-beta, and I discovered that PVS gives different results.

I also tested the other features, and they were consistent with the alphaBeta function, so I'm sure the problem is somewhere in the PVS code.

Code: Select all

int Search::PVS(int alpha, int beta, short depth, short ply, bool doNull) {
    nodesSearched++;

    int pvIndex = ply * (2 * MAX_DEPTH + 1 - ply) / 2;
    int pvNextIndex = pvIndex + MAX_DEPTH - ply;

    memset(pvArray + pvIndex, MoveUtils::NO_MOVE, sizeof(int) * (pvNextIndex - pvIndex));


    int hashFlag = TranspositionTable::HASH_F_ALPHA;

    bool isInCheck = board->isInCheck();

    int mateScore = MATE_EVAL - ply;


    if(alpha >= beta) return alpha;

    if(board->isDraw()) return 0;

    bool isPV = (beta - alpha > 1);

    // retrieving the hashed move and evaluation if there is any
    int hashScore = transpositionTable->probeHash(depth, alpha, beta);
    if(hashScore != TranspositionTable::VAL_UNKNOWN) {
        // we return hashed info only if it is an exact hit in pv nodes
        if(!isPV || (hashScore > alpha && hashScore < beta)) {
            return hashScore;
        }
    }

    int moves[256];
    int num = board->generateLegalMoves(moves);
    if(num == 0) {
        if(isInCheck) return -mateScore; // checkmate
        return 0; // stalemate
    }


    if(depth <= 0) {
        int q = quiescence(alpha, beta);
        return q;
    }
    int currBestMove = MoveUtils::NO_MOVE;

    int movesSearched = 0;
    
    for(int idx = 0; idx < num; idx++) {
        if(alpha >= beta) return alpha;

        board->makeMove(moves[idx]);

        // --- PRINCIPAL VARIATION SEARCH --- 
        int score;
        if(!movesSearched) {
            score = -PVS(-beta, -alpha, depth-1, ply+1, true);
        } else {
            score = -PVS(-alpha-1, -alpha, depth-1, ply+1, true);
            if(score > alpha && score < beta) {
                score = -PVS(-beta, -alpha, depth-1, ply+1, true);
            }
        }

        board->unmakeMove(moves[idx]);
        movesSearched++;
        
        if(score > alpha) {
            currBestMove = moves[idx];

            pvArray[pvIndex] = moves[idx];
            copyPv(pvArray + pvIndex + 1, pvArray + pvNextIndex, MAX_DEPTH - ply - 1);

            if(score >= beta) {
                transpositionTable->recordHash(depth, beta, TranspositionTable::HASH_F_BETA, currBestMove);

                // killers and history

                return beta;
            }
            hashFlag = TranspositionTable::HASH_F_EXACT;
            alpha = score;
        }
    }

    transpositionTable->recordHash(depth, alpha, hashFlag, currBestMove);
    return alpha;
}

Code: Select all

int Search::alphaBeta(int alpha, int beta, short depth, short ply, bool doNull) {
    nodesSearched++;

    if(alpha >= beta) return alpha;

    if(board->isDraw()) return 0;

    bool isInCheck = board->isInCheck();

    int moves[256];
    int num = board->generateLegalMoves(moves);
    if(num == 0) {
        int mateScore = MATE_EVAL - ply;
        if(isInCheck) return -mateScore; // checkmate
        return 0; // stalemate
    }

    if(depth <= 0) {
        int q = quiescence(alpha, beta);
        return q;
    }
    int currBestMove = MoveUtils::NO_MOVE;

    int movesSearched = 0;
    
    for(int idx = 0; idx < num; idx++) {
        if(alpha >= beta) return alpha;

        board->makeMove(moves[idx]);

        int score = -alphaBeta(-beta, -alpha, depth-1, ply+1, true);

        board->unmakeMove(moves[idx]);
        movesSearched++;
        
        if(score > alpha) {
            currBestMove = moves[idx];
            if(depth == currMaxDepth) bestMove = currBestMove;
            if(score >= beta) return beta;
            alpha = score;
        }
    }
    return alpha;
}

I should also mention that I also tried running PVS with move sorting enabled, but it was still different from alphaBeta.

So is there a mistake in my code, or is PVS not supposed to return the same result as alphaBeta?

Thanks!

[abulmo2]

Your PVS implementation uses a transposition table, not your alphabeta implementation. Transpositions can change the value returned.

[ciorap0]

Your PVS implementation uses a transposition table, not your alphabeta implementation. Transpositions can change the value returned.

As I said, I already tested the transposition table (alphaBeta + tt), and I got the same results as alphaBeta without tt, but the results change if I use PVS.

[ciorap0]

Your PVS implementation uses a transposition table, not your alphabeta implementation. Transpositions can change the value returned.

I also forgot to mention that I have tested PVS without TT and it still gives different results compared to alphaBeta.

[hgm]

Your PVS implementation uses a transposition table, not your alphabeta implementation. Transpositions can change the value returned.

As I said, I already tested the transposition table (alphaBeta + tt), and I got the same results as alphaBeta without tt, but the results change if I use PVS.

There is no guarantee that PVS gives the sme result of alpha-beta when you use a transistion table. You should only be worried when there is a difference between teh two without using the transposition table. Or when the move returned by the PVS is an obvious blunder.

[ciorap0]

There is no guarantee that PVS gives the sme result of alpha-beta when you use a transistion table. You should only be worried when there is a difference between teh two without using the transposition table. Or when the move returned by the PVS is an obvious blunder.

That's what I was trying to say, the 2 return different results even when not using TT.

[hgm]

And with 'different result' you mean a different score and a different root move? Or just some difference in the deeper part of the PV?

If I were in your situation I would just print the move list with the search scores of all the moves in the node where the PVs start to deviate, and then follow where these scores come from by printing the same in successively deeper nodes in the deviating branches. Then you should know what causes the difference in a matter of minutes.

[ciorap0]

And with 'different result' you mean a different score and a different root move? Or just some difference in the deeper part of the PV?

In about 1/10 games(from a sample of 1000 games), everything is different, including root move and score. Not sure about deeper parts of the PV, as I haven't checked yet.

Also the searches that I ran are only at depth 3, so it's definitely very weird.

[hgm]

Well, at such a low depth it should be very easy. Just take a position for which a different move was be played, test if this is reproducible, and then print the scores of all moves at the root.

I assume that you are playing fixed depth? If you are playing by time or nodes, then moves can be different because you happened to reach another depth.

[ciorap0]

Well, at such a low depth it should be very easy. Just take a position for which a different move was be played, test if this is reproducible, and then print the scores of all moves at the root.

I assume that you are playing fixed depth? If you are playing by time or nodes, then moves can be different because you happened to reach another depth.

It worked, thanks!

Turns out there was something wrong with my pawn evaluation TT.