# Chess: Efficiently deciding whether a check mate has been made

This question addresses building a Chess engine. I've done just that, and in my humble opinion quite elegantly. But I'm missing my ending conditions.

Here are some pseudopython functions that I use.

``````# Move from position old to new
def move(old, new):
if is_legal(old, new):
# Eat and move
if is_legal(new, enemy_king) or check_in_los(enemy_king, old):
# Set check on enemy king
if piece_type == 'Pawn' and position at the end of board:
# Convert to Queen

def is_legal(old, new):
# Assure piece is moving, it's your own and new position not on another own piece
# Based on piece type, assure it's maneuvering properly
# Assure there are no pieces in between the positions if applicable

if piece_type == 'King':
is_checked(new)  # Not moving to a checked square
elif checked:
# Assure check is removed
else:
check_in_los(own_king, old)  # Moving the piece does not create a check from behind

# Determine if king is checked from line of sight
def check_in_los(king_pos, direction):
# Divide path into single-square steps
# Find next piece in direction by incrementing king position by step
if is_legal(next, king_pos):
# King is checked from direction

# Determine if king is checked
def is_checked(king_pos):
# Check if knight positions around kings contain enemy knights
# For every 8 directions around king, check_in_los(king, direction)
``````

Now on to the check mate. It would be trivial to check every position around the king if it is a legal position to be in, but that's not quite enough.

Consider the following scenario where the white king is being threatened:

``````   A    B    C    D    E    F    G    H
1  BR |    | BR |    |    |    |    |
2     |    |    |    |    |    |    |
3     |    |    |    |    |    |    |
4     |    |    |    |    |    |    |
5     |    |    |    |    |    |    |
6     |    |    |    |    |    |    |
7     |    |    |    | WN |    |    |
8     | WK | BQ |    |    |    |    |
``````

The king (B8) has no legal moves left, but the knight (E7) can save him by eating the queen. Similarly if the placement of the queen is switched and the knight is a rook instead:

``````   A    B    C    D    E    F    G    H
1  BR |    | BR |    |    |    |    |
2     |    |    |    |    |    |    |
3     |    |    |    |    |    |    |
4     | BQ |    |    |    |    |    |
5     |    |    |    |    |    |    |
6     |    |    |    |    |    |    |
7     |    |    |    | WR |    |    |
8     | WK |    |    |    |    |    |
``````

The white rook can save the king by moving to B7.

A naïve approach to checking for a mate would I guess involve checking every possibility, but that seems wasteful.

What would be a good way of achieving this? Preferably using the functions already in place. I'm also open to other approaches if needed. It crossed my mind that maybe it would be helpful to keep track of the checking pieces or even every square that is being checked and the checking pattern of each piece individually, but I'm not sure..

• `A naïve approach to checking for a mate would I guess involve checking every possibility, but that seems wasteful.` -- Probably far more efficient, though, than looking for the next ideal move. – Robert Harvey Sep 15 '18 at 16:59
• @RobertHarvey Fair enough, are you suggesting checking every move of every piece and whether that still leads to a check is a good way? – Felix Sep 15 '18 at 17:09
• chess.stackexchange.com/questions/13871/check-for-checkmate first hit in google – Ewan Sep 15 '18 at 17:14
• I don't know how your engine works, but chess engines I've looked at in the past (which was, admittedly, 20 years ago...) all needed to build a list of valid moves for each position analyzed in any case. If you're building such a list, you can trivially use it to test for check. Then expanding the position if it is check and building the list of valid moves for the next position makes a checkmake test equally trivial. Of course, you may be working on an engine that doesn't enumerate all moves in each position (I don't know whether or not such a thing is common today; it may be). – Jules Sep 17 '18 at 20:48
• @Jules I've not considered building that kind of list, that could be an option! But I found reasonable restrictions on going through every move on a check, so for now I'll pursue that. – Felix Sep 17 '18 at 21:09

This is one of those situation where the human mind have an advantage over a computer. It is fairly simple to for a human to decide if a position in chess is a check mate or not.

We can discard most moves as having no relevance to the position. Creating an algorithm that discards those moves is quite tricky.

The simple solution of just going through all possible moves (which at most can be in the region of 40-50 with many pieces on the board, often far less) is perhaps naive but it is fast and uses far less effort than trying to device an algorithm to decide if a position is check mate or not.

Imaging a position where a knight and a bishop checks the king, you can take the knight but it is still check from the bishop. Or you can take a queen checking the king, but the piece that can do that can't be moved because that would cause a check from a rook.

It really gets very complex very fast. Why not spend the same time improving other parts of the program?

That is the reason why https://chess.stackexchange.com/questions/13871/check-for-checkmate mentioned by Ewan in the comments says that stockfish tries all moves and if there aren't any legal moves then it is check mate (similar to stale mate if there is no check in the first place).

• Somewhat disappointing, but makes sense. I was hoping I and my mental capacity was the weak link. But I'll take it and get cracking. Thank you! – Felix Sep 15 '18 at 17:26
• @Felix: One of the great things about computers is their speed. This speed gives computers the ability to churn through a large number of steps that a human being would consider mundane and inefficient. But as long as the process doesn't take more than a few seconds, it's good enough. – Robert Harvey Sep 15 '18 at 18:15
• Yep, too bad a few seconds is not good enough. You see, my plan is to simulate these games, so across iterations I think this check mate condition will be the hog. But I understand it won't take that long and it's a small problem. Especially as it is only performed when a king is actually checked and not after every turn. – Felix Sep 15 '18 at 18:51
• It shouldn't be taking you seconds to evaluate a checkmate position. I had software on my ZX Spectrum (3.5 MHz) which did it in a fraction of a second in the 1980s, and earlier stuff probably existed as well. You may need to look at your algorithm, lots of stuff on the Internet about how to do that. – Philip Kendall Sep 16 '18 at 10:28
• @PhilipKendall Yeah, that's why I said `But I understand it won't take that long`. I was just responding to Robert's remark that a few seconds would be good enough. And given a human-played Chess game, I agree it would be enough. I'm always interested in nicely formulated algorithms to do things well, not just do things, but I trust that this won't break the application. – Felix Sep 16 '18 at 12:59

When you are generating all possible moves and evaluate them for the best, you are for sure taking into account the value of pieces that might be taken.

Just use the same method, and give the King a very high value; that is the usual approach.
There is no magic shortcut to recognize a checkmate - remember it is defined as 'the King will be unavoidably captured in the next move'.

Stopping a chess game one move before the capture of the King is a historic courtesy. It's fine to do the same in your program, but there is no need or gain from inventing a different mechanic.

• Yep, thanks for the additional remarks! Though I'm not looking for a best move, I'm looking for to decide whether the mate has been made or not. So I'm stopping at the first legal move that can be made. – Felix Sep 16 '18 at 7:25

Doesn't this requirement simply fall out of whatever routine determines the best move to make at each point in the game?

You aren't allowed to end your move with your king in check. That's not a valid move, so the movement routine should never pick it.

So after the opponent's move, try to determine the best move you can make as normal. If there is no move that is legal, then the game is over. If the king is currently in check, then it's checkmate, otherwise it's stalemate.

• I'm not after a routine to check the best move. I intend not to have that kind of routine at all, as I said in the comments of another answer already. I'm only building the game engine. But thanks for the input! – Felix Sep 17 '18 at 19:52