How can a check evasion move generation algorithm be done efficiently?

Question

In my chess engine, I'm attempting to create a strictly legal move generator, instead of generating pseduo-legal moves, then discarding them later in the search and evaluation phase.

So far, here is my planned approach:

• Remove pinned pieces from the board
• If the king is in check
  • Generate possible moves from the check evasion function
• Otherwise
  • Generate possible moves for pinned pieces
  • Generate possible moves for non-pinned pieces

The only part of this algorithm that I don't quite understand how to implement is the check evasion move generator. As I understand it, there are three ways of evading a check:

• Capture the checking piece
• Block the checking piece
• Move the king

Now although I understand these three cases, I'm having a hard time trying to think of a way to implement them concretely and efficiently. What strategies are usually taken in creating a check evasion function? Also note, I'm working with bitboards.

Answer 1

You generate all the legal king moves up front, regardless of whether there's a check. Then determine the number of checking pieces. There will be two scenarios relevant to the question.

If it is a double check, the only legal moves are king moves out of check, so you simply return the existing list of moves

Single check is trickier. There are multiple cases here depending on the checking piece:

• If the checker is a knight, simply generate all piece moves which capture this knight. Return the list of captures and existing king evasions

• If the checker is a pawn, you do the same thing, but you also have to check if an e.p. move works.

• For any other checking piece (the "ray" pieces: queen, bishop, rook), the most efficient way to do this for bitboard-based move generation is using masks. You generate two bitboards: one containing all the intermediate squares between the king and the checking piece, and one containing a single set bit for the location of the checking piece. If you're not storing quiet moves and captures separately, you can combine both masks. If there are no checks, this bitboard is simply the all-ones bitboard.

  Then, for every piece and pawn, you presumably generate a bitboard of target squares. You AND this with the mask(s) above, to restrict to legal check evasions. Then create the moves as usual, from this reduced bitboard.

A concrete implementation can be found in the generate_legals function in my (very optimised) chess move generator on GitHub.