7

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..

Felix
  • 357
  • 2
  • 14
  • 5
    `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
  • 4
    https://chess.stackexchange.com/questions/13871/check-for-checkmate first hit in google – Ewan Sep 15 '18 at 17:14
  • 1
    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

5 Answers5

5

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

Robbie Dee
  • 9,717
  • 2
  • 23
  • 53
Bent
  • 2,566
  • 1
  • 14
  • 18
  • 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
  • 4
    @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
  • Not sure I agree the human mind is so great at this. A player who knows the game (versus someone reading the rule book for the first time) is likely to make some sort of heuristic distinction between active and inactive pieces, and to maintain a predictive analysis over several turns. But upon check, unless the configuration conforms to a memorised checkmate arrangement (an expert capability), they are likely to brute force through the threatened squares (to see if the king can move), and brute force whether threatening piece(s) can be attacked or blocked. – Steve Jul 09 '22 at 10:45
2

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.

Aganju
  • 1,453
  • 13
  • 15
  • 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 07:25
  • Actually, that definition is not quite right: `FEN K7/B7/8/8/8/8/8/rrk5 w - - 0 1` is stalemate, as if white would move anything, the King would be unavoidably captured in the next move. – Deduplicator Jul 08 '22 at 21:33
2

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.

Simon B
  • 9,167
  • 4
  • 26
  • 33
  • 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
0

In the same boat, my game does not have an ai opponent, I had no need to find a best move yet. I can boil this down to a few scenarios, which I think you have already done. First can you move the king out of check. That is a straight forward check if you maintain indicators that indicate which squares are threatened by the opposite player. Second case is, can the king take a piece to get out of check. This may involve recalculating the threat board for several pieces. The third more complicated case is a check to see if another piece can be moved to remove the king from check. It is interesting that the solution to the third case involves iterating though moves in a similar way to finding the best move. If I end up implementing the solution then I will have done most of the work involved with building an computer opponent.

user417652
  • 1
  • Why would that involve recalculating the threat-board? If the place you want to move the king is not attacked (as long as it isn't occupied by an ally), that works. – Deduplicator Jul 08 '22 at 21:37
0

As a building-block for your code we first write a method that checks whether a king is under attack.

To see if A’s king is under attack we check if there is an opposing pawn, knight or king in the attack positions. If not then we find the first piece in every direction (up, down, left, right, diagonal) and if there is a piece in that direction, and the next piece is an opposing piece, and it is a rook or queen on the same row/column, or a bishop/queen on the diagonal, then the king is attacked. (The same rules apply for other figures, except for the en-pas sent rule for pawns, but we don’t need that here).

Moves that leave your king under attack are illegal. You find any valid move. If you have a valid move then you are not checkmate or stalemate. If there is no valid move, then you are checkmate if your king is under attack, and stalemate if your king is not under attack.

There are some special rules. Castling is not allowed while in check, and castling over a field that is attacked is not allowed.

You may be able to find faster that any move while the king is attacked leaves the king attacked, because the same attack might work after a move.

PS. It is not enough to check if the king is under attack only after the king moves. For example moving a piece that is between the king and a possible attacker can put the king under attack.

gnasher729
  • 42,090
  • 4
  • 59
  • 119