StalemateBug

Consider the following position:

Black is a queen and a pawn ahead. Black will win... unless it plays like Project Invincible's AI did.

In this position, the AI played either Ke5-f5 or Ke5-f4. Both moves result in instant stalemates.

A clue about what was wrong was that the bug triggered, and was apparently caused by, an optimization which I had made few days earlier. When the AI found a checkmate, it stopped searching and played the move leading to the checkmate. The optimization saved time and caused the AI to always pick the fastest mate. I saw that when the bug occurred, the AI never used all time it was given, so the optimization was triggered. So, the AI somehow believed that the moves will actually lead to checkmates.

Project Invincible detects checkmates both in leaf nodes...

// Check if the position is a checkmate.
if (whiteHasWon(spaceForMoves,spaceForPosition))
{
        return 100000;
}
else if (blackHasWon(spaceForMoves,spaceForPosition))
{
        return -100000;
}

...and in other nodes.

if(countMoves == 0) { // Game has ended
    if(previousPosition->_toMove == WHITE) {  // White lost or draw
        if(previousPosition->blackHasWon(spaceForMoves+MAX_MOVES, currentPosition)) {
            // White has lost
            return -100000;
        } else { // Draw
            return 0;
        }
    } else { // Black lost or draw
        if(previousPosition->whiteHasWon(spaceForMoves+MAX_MOVES, currentPosition)) {
            // Black has lost
            return 100000;
        } else { // Draw
            return 0;
        }
    }
}

Both snippets seem correct. It's the fault of the whiteHasWon() and blackHasWon() functions, right?

Wrong.

When debugging, I found what the problem was: in frontier nodes, so-called defence moves are generated. Defence moves are illegal moves where pieces capture friendly pieces. They are generated for both players, not only the one who is to move. They are used for Static Exchange Evaluation.

As a result, in frontier nodes countMoves was never zero. In the stalemate positions (which are frontier nodes in a 2-ply search) it was around 35.

So, let's see how the AI ended up thinking that the stalemate positions are actually checkmates. First, it proceeded to the main loop.

for (int i = 0 ; i < countMoves ; ++i){
            if (generateDefenceMoves && !spaceForMoves[i].isLegal())
            {
                    continue;
            }

Naturally, illegal moves are ignored because they can't be played. The algorithm ignored all moves and went to the code following the loop.

return alpha;

Alpha means the highest score that the white player can achieve regardless of how black plays. For example, it alpha is 1234, the white player will achieve a position worth at least 1234 points if he/she/it plays perfectly.

In this case, the value of alpha wasn't altered at all. The function returned the initial value of alpha. It is -100 000, meaning "no matter how well black plays, white will achieve at least a position where white is mated". That makes sense: black can't possibly achieve any better position.

So, the function returned a score of -100 000 to the main AI function. The main AI function got excited: "Wooohooo! Ke5-f4 will lead to a checkmate! :D" The checkmate optimization was triggered and the AI ended up playing Ke5-f5 or Ke5-f4.

Needless to say, this is now fixed.