The word “Checkmate” in Chess comes from the Persian phrase “Shah Mat,” which means “the King is dead.”
While in the starting position, there are eight different ways to checkmate in two moves and 355 different ways to checkmate in three moves. Not to mention the countless other ways to be checkmated. Kind of sounds like one of those television series of “1000 terrible ways to die.”
We’ve looked before at code for making the king move, but now we want to break down how we check if the king is safe. Here’s the kingSafe commit, and we can reference several things from that code as we try to understand what I set out to accomplish.
First, let’s take a look back at the flow chart for determining available moves:
- For each piece, check for valid moves that they can make, where the spaces are empty, or where they attack an opponent’s piece.
- Add that move to the temporary list.
- Once we have a temporary list of valid moves, try each move, 1 at a time, and check if the king is safe.
- If the king is safe, add that move to the “available moves” list.
- Put the piece back, and try the other moves on the temporary list.
With that in mind, up until now, our engine has not actually checked if the king is safe. We had a isKingSafe() method that always returned true, or “yes, he is”. Now we need to flesh that out and have it really check if it is safe. For the most part, we can combine all the pieces move options into one for the king, and just ask what pieces are at the “end” of those move lines. Here’s the flow chart:
- Start with the king’s space number, and get the row/column number as well.
- Using the bishop’s move table, check the next diagonal space until it is not empty. If it is not empty, is it either a bishop or a queen? Then the king is not safe.
- Using the rook’s move table, check the up/down/left/right spaces until they are not empty. If it is not empty, is it either a rook or a queen? Then the king is not safe.
- Using the knight’s move table, check the eight “L” spaces to see if they are empty. If it is not empty, is it either a knight? Then the king is not safe.
- Using the king’s move table, check the surrounding spaces until it is not empty. If it is not empty, is it a king? Or in two cases, a pawn? Then the king is not safe.
- The king must be safe!
As you can see from the flow chart, it is checking to see if the king is “not safe”. At any juncture that the king is not safe, the rest of the checks are ignored, and a “false” boolean is returned from the isKingSafe0 method. If there are no returns of “false”, then the method returns “true”, for the king must be safe.
In my mind, there are three main ways to handle the king safe issue:
- After each piece is moved, have it flag that the king is unsafe (e.g., you check the king, so he is unsafe).
- After every move, check from all pieces to see if they are attacking the king.
- After every move, check from the king if he is threatened by any pieces.
Method one seems hard to implement, when moving you own piece may illegally threaten the king by no longer “blocking” an attacker. Conversely, method two is way more resource intensive. You would waste time checking both bishops in all directions to see if they “find” the king. Method three seems the most logical, check from the king in all directions for the enemy, rather than from all enemies for the king.
Of the method we chose, there seem to me to be two sub-methods, that of checking if the king is safe, or checking if the king is not. I like to assume the king is safe, unless we find that he is not. I think this is faster, because the moment we find he is not safe, then we quit checking. E.g., if the bishop check reveals the king is not safe, we don’t do the rook, king, knight, pawn checks, we just return “false” – not safe.
Conversely, if we were to assume the king is not safe, and prove he is, we would have to complete all of the checks every time. This would be a waste of resources. Although, with the method I chose, most of the time, the king is safe, so we end up checking them all anyways. But, since we are trying to use this engine on cell phones, we need to save on every resource that we can.
Linux – keep it simple.