# In a chess simulator, how to efficiently determine checkmate?

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?

• Just brainstorming here. Another possible implementation of check would be to keep track of which squares are attacked by which pieces each time a move is made. The complication with this is the notion of discovered attacks; a piece can move and expand the reach of another. However, the only pieces that can be "discovered" like this are the bishop, rook, and queen. So, maybe we could keep track of which squares are attacked, updating after each move by updating the moved piece and the queens, rooks, and bishops... Commented Jun 29, 2021 at 23:03
• ...and then, when we want to check for checkmate, we would first check to see if the king and his surrounding spaces are attacked and by whom. If the king is attacked and surrounded, but only one piece is attacking the king, we can see if that piece can be captured, as well as if an interposition can be made in the case of a non-knight/non-pawn. Otherwise, the king must be mated. I think... Commented Jun 29, 2021 at 23:05
• @FluffytheTogekiss This is a very interesting idea for an approach! I think I understand what you're saying in that this involves keeping a list of each color's "attacked squares," and updating the list on each move. Then, if the king is attacked, you check each attacker for possible captures or blocks by friendly pieces, and if none exist, it's checkmate. Keeping track of all attacked squares by all pieces seems like it would require a big array structure and looping, and I'm not sure it's strictly better than brute-force "check every legal move," but this is a great option. Commented Jun 29, 2021 at 23:34
• The implementation I was thinking of would be a per-board-space data structure, so you would have a constant number of them (64), but there are probably a number of ways to do it. Commented Jun 29, 2021 at 23:38
• Possibly, to build on your idea of keeping track of attackers, you could "radiate" rays out from each enemy piece after their move depending on their moving rules, and if one or more of the enemy rays intersects the king, it's check. If there is no way to 1) capture attacking pieces with friendly pieces, 2) move the king out of the attacking rays, or 3) block the attacking ray(s) by the opponent using friendly pieces - then it's checkmate. But again I feel like this wouldn't be computationally much better than the brute-force solution. Commented Jun 29, 2021 at 23:42

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:
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)