Issue with finding the quickest mate

[ciorap0]

Hello,

I have noticed my engine has a problem when it finds checkmate, specifically after it finds a mate in n plies at depth x, it then sometimes goes on to depth x+1, where it finds mate in n+1 plies. This keeps increasing sometimes, and causes it to output a mate in 54 that it found at depth 120, instead of the mate in 3, found at depth 5.

An example of this would be:

Code: Select all

24442 >CiorapBot 0.3(0): position startpos moves d2d4 g8f6 b1c3 d7d5 c1f4 e7e6 c3b5 b8a6 g1f3 c7c6 b5c3 f6h5 f4e3 f8e7 g2g4 h5f6 g4g5 f6h5 f1h3 e7d6 h3g4 h5f4 e1g1 e8g8 d1d2 f4g6 a1d1 c8d7 h2h4 d8b6 h4h5 g6e7 h5h6 e7f5 g4f5 e6f5 f3e5 d7e6 b2b3 g7h6 g5h6 f7f6 e5c4 b6c7 c4d6 c7d6 g1h1 g8h8 f1g1 f8g8 e3f4 d6a3 g1g8 a8g8 d2e3 e6f7 h1h2 g8g4 f2f3 g4g8 d1d2 f7h5 e3e6 a3f8 e6f5 f8f7 f4e5 g8g6 f5h5 g6g2 h2g2 f7h5 e5f4 f6f5 e2e3 h5h4 d2e2 h8g8 g2g1 g8f7 a2a3 b7b5 b3b4 f7e6 c3a2 e6d7 a2c1 d7e6 c1d3 h4h5 g1g2 e6d7 d3e5 d7c8 g2f2 h5h4 f2g1 c8b7 e5d3 a6c7 d3c5 b7b6 a3a4 b5a4 c5a4 b6b7 a4c5 b7b6 g1g2 c7b5 e2f2 b5c3 c5d3 b6b5 f2f1 c3e2 f1h1 e2f4 d3f4 h4g5 g2f2 b5b4 f4e2 a7a5 f3f4 g5g6 e2g1 a5a4 g1f3 a4a3 c2c3 b4b3 f3e5 g6d6 h1b1 b3c2 b1h1 a3a2 f2g2 d6a3 e5c6 a3c3 c6e5 c3e3 h1f1 e3e2 g2g1 e2f1 g1f1 a2a1q f1f2 a1d4 f2f3 d4b6 f3g2 b6e3 e5f3 e3f4 f3g1 d5d4 g1h3 f4g4 g2h2 f5f4 h3f4 g4f4 h2g2 d4d3 g2g1 f4d4 g1h1 d3d2 h1h2
24442 >CiorapBot 0.3(0): isready
24443 <CiorapBot 0.3(0): readyok
24443 >CiorapBot 0.3(0): go wtime 620 btime 180 winc 100 binc 100 movestogo 14
24443 <CiorapBot 0.3(0): info score cp -1923 depth 1 nodes 82 time 1 nps 82000 pv d2d1q 
24443 <CiorapBot 0.3(0): info score cp -1932 depth 2 nodes 95 time 1 nps 95000 pv d4f4 h2h3 
24443 <CiorapBot 0.3(0): info score cp -1935 depth 3 nodes 842 time 1 nps 842000 pv d4e5 h2h3 d2d1q 
24443 <CiorapBot 0.3(0): info score cp -2069 depth 4 nodes 612 time 1 nps 612000 pv d2d1q h2g2 d1c1 g2f3 
24444 <CiorapBot 0.3(0): info score mate 3 depth 5 nodes 591 time 1 nps 591000 pv d2d1q h2g2 d1g1 g2f3 g1g4 
24444 <CiorapBot 0.3(0): info score mate 3 depth 6 nodes 647 time 1 nps 647000 pv d2d1q h2g2 d1g1 g2f3 g1g4 
24444 <CiorapBot 0.3(0): info score mate 4 depth 7 nodes 1817 time 1 nps 1817000 pv d4h4 h2g2 h4f4 g2g1 d2d1q g1g2 d1f1 
24444 <CiorapBot 0.3(0): info score mate 4 depth 8 nodes 127 time 1 nps 127000 pv d4h4 h2g2 h4f4 g2g1 d2d1q g1g2 d1f1 
....
24554 <CiorapBot 0.3(0): info score mate 4 depth 172 nodes 5420 time 1 nps 5420000 pv d4h4 h2g2 h4f4 g2g1 d2d1q g1g2 d1f1 
24554 <CiorapBot 0.3(0): bestmove d4h4

I have to mention that I can't really replicate the issue manually; this just happens sometimes when playing matches, using cutechess-cli. For example if I input the commands above in my engine, it correctly identifies a mate in 3 at the end.

Also, I don't use the hash score in PV nodes, so I doubt my transposition table is the problem here.

Could this happen because of an incorrect mate distance pruning, or maybe should i make my engine stop after it finds mate the first time?

Here's the code for my search function:

Code: Select all

int Search::alphaBeta(int alpha, int beta, short depth, short ply, bool doNull) {
    assert(depth >= 0);
    assert(ply <= MAX_DEPTH);

    if(!(nodesSearched & 4095) && !infiniteTime) {
        long long currTime = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
        if(currTime >= stopTime) timeOver = true;
    }
    if(timeOver) return 0;
    nodesSearched++;

    int pvIndex = ply * (2 * MAX_DEPTH + 1 - ply) / 2;
    int pvNextIndex = pvIndex + MAX_DEPTH - ply;
    pvArray[pvIndex] = MoveUtils::NO_MOVE;

    int hashFlag = TranspositionTable::HASH_F_ALPHA;

    bool isInCheck = board->isInCheck();

    // --- MATE DISTANCE PRUNING --- 
    // if we find mate, we shouldn't look for a better move

    int matedScore = - MATE_EVAL + ply;
    int mateScore = MATE_EVAL - ply;
 
    if(ply > 0) {
        if (alpha < matedScore) alpha = matedScore;
        if(beta > mateScore - 1) beta = mateScore - 1;
        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, ply);
    if(hashScore != TranspositionTable::VAL_UNKNOWN && !isPV) return hashScore;

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

    if(depth <= 0) return quiescence(alpha, beta);

    int currBestMove = MoveUtils::NO_MOVE;

    // --- STATIC NULL MOVE PRUNING ---
    // if our position is so good that we can afford to lose some material
    // we assume this node will fail high and we prune its branch
    int staticScore = evaluate();
    if(!isInCheck && !isPV && abs(beta) < mateScore) {
        int scoreMargin = 100 * depth;
        if (staticScore - scoreMargin >= beta) {
            return staticScore - scoreMargin;
        }
    }

    // --- NULL MOVE PRUNING --- 
    // if our position is good, we can pass the turn to the opponent
    // and if that doesn't wreck our position, we don't need to search further
    const int ENDGAME_MATERIAL = 4;
    if(doNull && (!isPV) && (isInCheck == false) && ply && (depth > 3) && (gamePhase() >= ENDGAME_MATERIAL) && (staticScore >= beta)) {
        board->makeMove(MoveUtils::NO_MOVE);

        short R = 3 + depth / 6;
        int score = -alphaBeta(-beta, -beta + 1, depth - R - 1, ply + 1, false);

        board->unmakeMove(MoveUtils::NO_MOVE);

        if(timeOver) return 0;
        if(score >= beta) return beta;
    }

    // --- INTERNAL ITERATIVE DEEPENING ---
    // if we don't have a move from the tt, we do a quick search with a reduced depth
    if(depth >= 4 && isPV && transpositionTable->retrieveBestMove() == MoveUtils::NO_MOVE) {
        int score = alphaBeta(alpha, beta, depth - 2, ply + 1, doNull);

        // make sure we have a move in the tt
        if (score <= alpha) score = alphaBeta(-INF, beta, depth - 2, ply + 1, doNull);
    }


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

        board->makeMove(moves[idx]);
            
        // --- PRINCIPAL VARIATION SEARCH --- 
        // we do a full search only until we find a move that raises alpha and we consider it to be the best
        // for the rest of the moves we start with a quick null window search
        // and only if the move has potential to be the best, we do a full search
        int score;
        if(!movesSearched) {
            score = -alphaBeta(-beta, -alpha, depth-1, ply+1, true);
        } else {
            // --- LATE MOVE REDUCTION --- 
            // we do full searches only for the first moves, and then do a reduced search
            // if the move is potentially good, we do a full search instead
            if(movesSearched >= 2 && !MoveUtils::isCapture(moves[idx]) && !MoveUtils::isPromotion(moves[idx]) && !isInCheck && depth >= 3 && !board->isInCheck()) {
                int reductionDepth = int(sqrt(double(depth-1)) + sqrt(double(movesSearched-1))); 
                if(isPV) reductionDepth = (reductionDepth * 2) / 3;
                reductionDepth = (reductionDepth < depth-1 ? reductionDepth : depth-1);

                score = -alphaBeta(-alpha-1, -alpha, depth - reductionDepth - 1, ply+1, true);
            } else {
                score = alpha + 1; // hack to ensure that full-depth search is done
            }

            if(score > alpha) {
                score = -alphaBeta(-alpha-1, -alpha, depth-1, ply+1, true);
                if(score > alpha && score < beta) {
                    score = -alphaBeta(-beta, -alpha, depth-1, ply+1, true);
                }
            }
        }

        board->unmakeMove(moves[idx]);
        movesSearched++;

        if(timeOver && (ply > 0 || idx > 0)) return 0; // ensure that we at least have a move to print
        
        if(score > alpha) {
            currBestMove = moves[idx];
            if(ply == 0) bestMove = currBestMove;
            assert(currBestMove != MoveUtils::NO_MOVE);

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

                assert(pvArray[pvIndex] != MoveUtils::NO_MOVE);
            }
            assert(pvIndex < pvNextIndex);
            assert(pvNextIndex < (MAX_DEPTH * MAX_DEPTH + MAX_DEPTH) / 2);

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

                if(!MoveUtils::isCapture(moves[idx]) && !MoveUtils::isPromotion(moves[idx])) {
                    // store killer moves
                    storeKiller(ply, moves[idx]);

                    // update move history
                    updateHistory(moves[idx], depth);
                }

                return beta;
            }

            hashFlag = TranspositionTable::HASH_F_EXACT;
            alpha = score;
        }
    }
    if(timeOver) return 0;

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

If anyone has encountered this issue before, some help would be highly appreciated. Thanks!

[Ras]

If anyone has encountered this issue before, some help would be highly appreciated.

Do you convert mate scores in the hash table between root and node relative? If you don't, that could explain why you only see that in games where the game move counter changes, but not in position analysis. I've seen similar issues before I fixed that in my engine.

[ciorap0]

If anyone has encountered this issue before, some help would be highly appreciated.

Do you convert mate scores in the hash table between root and node relative? If you don't, that could explain why you only see that in games where the game move counter changes, but not in position analysis. I've seen similar issues before I fixed that in my engine.

Yes, that was my initial thought as well, but I fixed that and it still happens (even though it's more rare than before).

Code: Select all

int TranspositionTable::probeHash(short depth, int alpha, int beta, int ply) {
    ...
    if(score > Search::MATE_THRESHOLD) score -= ply;
    else if(score < -Search::MATE_THRESHOLD) score += ply;
    ...
}

void TranspositionTable::recordHash(short depth, int score, int hashF, int best, int ply) {
    ...
    if(score > Search::MATE_THRESHOLD) score += ply;
    if(score < -Search::MATE_THRESHOLD) score -= ply;
    ...
}

[Ras]

Yes, that was my initial thought as well, but I fixed that and it still happens (even though it's more rare than before).

Ok, then does your move sorting ensure that the leftmost path you search is the PV from the iteration before?

[ciorap0]

Yes, that was my initial thought as well, but I fixed that and it still happens (even though it's more rare than before).

Ok, then does your move sorting ensure that the leftmost path you search is the PV from the iteration before?

Well, the hash moves are put first in move sorting. I don't explicitly get the move from the pv array, because I guess it can't be different from the hash move? (I have a depth-preferred entry that I sort first, and then an always-replace one)

[Ras]

I guess it can't be different from the hash move?

Yes, should be the same. Looking a bit closer at the mate distance pruning, I have a different logic here:

Code: Select all

const int mate_score = INFINITY_ - (mv_stack_p - Starting_Mv);
if (alpha >= mate_score) return alpha;
if (beta <= -mate_score) return beta;

My INFINITY_ corresponds to your MATE_EVAL, and (mv_stack_p - Starting_Mv) should be your ply. The idea isn't to adjust alpha and beta, but actually return from the function if possible. The alpha-if means, if my alpha from other nodes is already so high that even if I can deliver mate in this node (or its children), it would still not be worth searching. The beta-if means that the other side has already secured a mate so that even if I get mated in this node, the other side still won't change mind.

You could also outcomment your mate distance pruning and see whether the issue is still there - if not, then it is probably the problem.

[ciorap0]

You could also outcomment your mate distance pruning and see whether the issue is still there - if not, then it is probably the problem.

I copied the mate-distance pruning from stockfish, so it would be weird for it to be wrong. Maybe I'm just not using it right?

Regardless, I'll try that and come back with the results.

[ciorap0]

I copied the mate-distance pruning from stockfish, so it would be weird for it to be wrong. Maybe I'm just not using it right?

Regardless, I'll try that and come back with the results.

It seems like it's fixed now. I ran 1k games and it hasn't happened again.

Thanks for the help!

[Ciekce]

The real issue is here:

Code: Select all

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

In order to prioritise faster mates, you should subtract the distance from root (ply) from the mate score - in this case, you should be returning `-mateScore + ply` (or, if you prefer, `-(mateScore - ply)`):

Code: Select all

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

This has the effect of giving shorter mates higher scores and vice versa, and is the normal technique for achieving this.

As a side note, some parts of your search (particularly LMR) are very strange, and feel like they're influenced by extremely outdated info from the chess programming wiki - feel free to join one of the active engine development discord servers and ask questions there if you want more info :)

Stockfish: https://discord.gg/GWDRS3kU6R
Engine Programming: https://discord.gg/YctB2p4