Draw detection

[Look]

Hi,

I wanted to know what is the draw detection algorithm in strong chess engines, in particular Stockfish ? I do not mean draw by repetition (that has already happened) but foreseeing the draw in future. Specially draw by perpetual check.

[Ajedrecista]

Hello:

There was a thread discussing perpetual check a month ago. I wrote there, saying that FIDE had not got a perpetual check rule and that the correct draw claim is by threefold repetition or fifty-move rule in such cases. I recall this now to point out that there is a high chance that SF simply has a general draw detection algorithm because perpetual check falls in 3-fold and/or 50-move with enough moves played. Other insights are welcome because I am not a programmer.

Then, I found some lines of code under position.cpp file. Currently:

Code: Select all

[...]

// Tests whether the position is drawn by 50-move rule
// or by repetition. It does not detect stalemates.
bool Position::is_draw(int ply) const {

    if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
        return true;

    return is_repetition(ply);
}

// Return a draw score if a position repeats once earlier but strictly
// after the root, or repeats twice before or at the root.
bool Position::is_repetition(int ply) const { return st->repetition && st->repetition < ply; }

// Tests whether there has been at least one repetition
// of positions since the last capture or pawn move.
bool Position::has_repeated() const {

    StateInfo* stc = st;
    int        end = std::min(st->rule50, st->pliesFromNull);
    while (end-- >= 4)
    {
        if (stc->repetition)
            return true;

        stc = stc->previous;
    }
    return false;
}


// Tests if the position has a move which draws by repetition.
// This function accurately matches the outcome of is_draw() over all legal moves.
bool Position::upcoming_repetition(int ply) const {

    int j;

    int end = std::min(st->rule50, st->pliesFromNull);

    if (end < 3)
        return false;

    Key        originalKey = st->key;
    StateInfo* stp         = st->previous;
    Key        other       = originalKey ^ stp->key ^ Zobrist::side;

    for (int i = 3; i <= end; i += 2)
    {
        stp = stp->previous;
        other ^= stp->key ^ stp->previous->key ^ Zobrist::side;
        stp = stp->previous;

        if (other != 0)
            continue;

        Key moveKey = originalKey ^ stp->key;
        if ((j = H1(moveKey), cuckoo[j] == moveKey) || (j = H2(moveKey), cuckoo[j] == moveKey))
        {
            Move   move = cuckooMove[j];
            Square s1   = move.from_sq();
            Square s2   = move.to_sq();

            if (!((between_bb(s1, s2) ^ s2) & pieces()))
            {
                if (ply > i)
                    return true;

                // For nodes before or at the root, check that the move is a
                // repetition rather than a move to the current position.
                if (stp->repetition)
                    return true;
            }
        }
    }
    return false;
}

[...]

This piece of code does not detect draws by stalemate, as stated in the first comment.

Regards from Spain.

Ajedrecista.

[mar]

well, a perpetual will be detected simply as a repetition by the engine

what might be interesting, however, would be for the GUI to give hints (guesses) about what type of draw the engine sees, might be useful for analysis:

the GUI knows the game history, engine PV and engine score, so:

if engine score is within a threshold of a draw, walk the PV to see how it ends, then you could distinguish:
- stalemates
- draws by insufficient material
- draws by 50 move rule (possibly)
- draws by repetition
- presumed perpetual (say it's a repetition but ends with a queen check/king evasion having a couple of extra queen checks before that)
- draws by tablebases

won't work well for engines doing TT cutoffs in PV nodes, but if the GUI avoids aspiration window fails it might be somewhat insightful

not perfect, but definitely doable and I'm not aware of any GUI doing that