In a chess simulator, how to efficiently determine checkmate?

Question

I'm working on a small C++ chess simulator game for the first time, and I have a bit of a programming dilemma. I have searched for similar questions on this site and StackOverflow, but can't find a consensus on what to do here, so hopefully this is an appropriate question for this site.

I'm currently working on implementing check, through a function that starts at the king's position and checks all knight moves, verticals, horizontals, and diagonals for threatening pieces. If it finds a threatening piece that isn't blocked by another piece, then the king is considered to be in check and the player must make their next move in a way that gets them out of check. That seems to be the most efficient solution for determining check from the chess-related posts I've seen.

However, I'm stuck on how to efficiently implement checkmate. The only logical way I can think of is that once the check flag has been raised, run the check function on every legal follow-up move to see if it results in non-check, and if none of them do, it is checkmate.

Or, to express this in C++ pseudocode:

bool checkForCheckmate() {
  for (allLegalMoves)
  {
    doMoveTemporarily();
    if (!inCheck) {
      return false; // The player can get out of check, so it's not checkmate.
    }
  }
  return true; // If we got here, none of the player's legal moves can get them out of check, so it's checkmate.
}

While it makes sense to me and is logical, that seems extremely inefficient, and this is supposed to be a fairly simple and lightweight application. However, this seems to be the approach suggested by most sources when I look up "how to implement checkmate in a chess game."

Is there another, potentially more efficient chess algorithm to check if a given arbitrary board arrangement is a checkmate?

Answer 1

A move which results in the own king being in check is already an illegal move. So allLegalMoves would already excludes any moves which end up with the own king in check by definition. If fact the FIDE Laws of Chess section 1.2 define checkmate as:

The objective of each player is to place the opponent’s king ‘under attack’ in such a way that the opponent has no legal move. The player who achieves this goal is said to have ‘checkmated’ the opponent’s king and to have won the game. Leaving one’s own king under attack, exposing one’s own king to attack and also ’capturing’ the opponent’s king are not allowed.

That means the checkmate can be defined as ownKingIsInCheck && allLegalMoves.size() == 0. (By the way, this can be easily combined with checking for stalemate: allLegalMoves.size() == 0 without the king being in check)

OK, but doesn't that just move the problem from the mate-check routine to the move enumeration routine instead of solving it? Well, you need to move it there anyway. When you determine all the legal moves, you have to exclude those moves which put the own king in check, regardless of whether or not the king is already in check.

So if you feel the need to optimize (do you, though?), then you need to optimize your check-checking routine. One possible approach can be to cache the squares threatened by each piece (this data can also be useful for your rating function, by the way). Keep in mind that when a piece moves, then any pieces which threatened its old square might now threaten new squares. So their threat area needs to be recalculated. (see Pin and Discovered Check for two test-cases your routine needs to be able to cover)