Back Up Next

Checkmate/Stalemate Scoring

Checkmate and stalemate can be handled by an evaluation function, but it's more typical to handle them in the search.

Alpha-beta search collects checkmate/stalemate information about every node it traverses for free.

If it turns out that there are no successors of the node being processed, the result is either checkmate or stalemate.  It's easy to tell them apart -- if there are no legal moves here, and the side to move is in check, it's checkmate.  Otherwise, it's stalemate.

Now that the simple stuff is out of the way, the question is what score to return when one of these conditions is detected.

Stalemate is typically handled via the contempt factor.  I don't feel the need to discuss this further, and the only reason I'm discussing it here at all is that it's detected at the same time as checkmate is detected.  Checkmate is the important issue here.

Checkmate is more complicated.  It is easy to suggest that you should return some very large constant negative number if the side to move is checkmated, but this overlooks an important consideration.

It is desirable that the fastest mate be chosen, if there are several to choose from, as there often are.  If all mates are scored the same, whether or not the quickest one is chosen is left to random chance, and Murphy's Law being what it is, often you'll watch a program with this "feature" repeatedly threaten mate in one, but never actually give mate.

This is very embarrassing if you are the programmer, and a laugh riot if you aren't.

The way to solve this is to give a larger negative score if the side to move is mated closer to the root of the tree.  This will cause the winning side to try to checkmate faster, and the losing side to stay alive as long as possible, which is usually considered better play.

It can be a little complicated to implement this, because you end up having to keep track of how far you are from the root of the search.  This is not normally an interesting or necessary thing to keep track of -- you are usually much more interested in the amount of depth under this node, not the length of the line above this node.

You have to handle this somehow.  Here is an obvious, but not terribly efficient, means of handling this, in the context of a normal alpha-beta search:

int AlphaBeta(int depth, int alpha, int beta, int mate)
{

    int legal = 0;


    if (depth == 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha,

            mate - 1);
        UnmakeMove();
        if (val >= beta)
            return beta;
        if (val > alpha)
            alpha = val;

        legal++;
    }

    if (!legal) {

        if (!InCheck())               // Stalemate.

            return Contempt();

        return -mate;                 // Checkmate.

    }
    return alpha;
}

You'd call this routine with, for instance:

val = AlphaBeta(8, -INFINITY, INFINITY, MATE);

"MATE" is in this case a constant with a large positive value, larger than any score created by summing material and positional factors could be.

In order to make sense out of mate scores returned by this, you have to do some math on the return value in order to figure out if it's mate in 2 or whatever.  An example based on the above:

if (val >= MATE - 1000) // Handle up to mate in 500 or so.

    printf("Mate in %d\n", (MATE - val + 1) / 2);

else if (val <= -MATE + 1000)

    printf("Mated in %d\n", (MATE + val) / 2);

That's a little tricky because it assumes integer division.  The code will print "Mate in 1" if the side to move can checkmate on its first move, and "Mated in 0" if the side to move is checkmated now.
 

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 12/27/02