3
\$\begingroup\$

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?

\$\endgroup\$
6
  • \$\begingroup\$ 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... \$\endgroup\$ Jun 29 at 23:03
  • \$\begingroup\$ ...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... \$\endgroup\$ Jun 29 at 23:05
  • \$\begingroup\$ @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. \$\endgroup\$
    – Sciborg
    Jun 29 at 23:34
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 29 at 23:38
  • \$\begingroup\$ 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. \$\endgroup\$
    – Sciborg
    Jun 29 at 23:42
6
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ This is a great and very helpful answer, thanks! I think you are correct about a more elegant check system being the answer. \$\endgroup\$
    – Sciborg
    Jun 30 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.