Winboard Forum

I'm creating a chess engine using bitboards and I have a question about legal move generation. Here is what I came up with so far:

- Check if the king is in check
------- If not, then generate all possible moves for all pieces
-------------Check each king move/en-passant/castling/absolute pin (if they result in check after the move is made, remove from list of legal moves)
-------------If no legal moves, then stalemate
-------If in check, generate king moves, captures of piece giving check, or blocks
--------------Check each move (if they result in check after the move is made, remove from the list of legal moves)
--------------If no legal moves, then checkmate

I have 2 questions:
1) Is this an efficient way to generate a list of legal moves, or is there a better way?
2) Right now I plan to see if the white king is in check by computing the attacks of all black pieces and seeing if the result of (white_king & black_attacks) is 0 or not. Is there a more efficient way to do this?

Thanks!

Well, for one, generating legal moves is never efficient, (compared to the alternative of postponing the test to the point where you decide to search them), except perhaps in positions where you are in-check. As for the most efficient way to do it:

Testing after every move whether your King happens to be in check is quite expensive. I never did bitboards, but identifying pinned pieces in advance seems a lot cheaper even with bitboards. (E.g. generate Rook attacks from King square; intersect with own pieces to get potentially pinnend pieces. (You could intersect with opponent R+Q here to make sure you are not in check, if you did not know that already.) Delete those from the occupied set, and generate Rook moves again, and intersect with the R+Q bitboard to get possible pinners (usually an empty set), loop over the pinners to generate Rook-attacks from their position, intersect each of those with the set of potentially pinned pieces, done.

Then you can generate the moves of the pinned pieces as soon as you identified them, and intersect their move set with the Rook attacks from the pinner to get non-captures, and with the pinner itself to get its capture by the pinned piece. Then you can take a measure that causes this piece to be skipped for the normal move generation of unpinnend pieces (depending on how you loop through those).

Then repreat the entire process for diagonals.

This way you will only have to test King moves for blundering into check, and the bulk of the moves can be generated without worrying about putting yourself in check at all.

When you are in check it depends on what kind of check; on a contact check capture of the checker is the only alternative to moving the King (and on double check not even that), and you could just generate Rook and Bishop attacks intersected with R+Q and B+Q own bitboards to find possible capturers. For distant checks it is not so clear, because there are also interpositions possible. If there is only a single interposition square it might be fastest to look for moves to that square the same way as you looked for captures of the checker. If there are many interposition squares, and few pieces on the board, it might be faster to generate move sets for all the pieces, and intersect those with the set of interposition squares (which again is the R or B attacks through King intersected with R or B attacks through checker). Because you typically only have few check evasions, it is better to test each evasion individually for not putting your King in check. Identifying pinners in advance might be wasted effort if the pinned piece cannot interpose or capture the checker at all, and when it has only a single move to cure the check (the next common case) determining if that move was legal is probably still not more work than identifying pinners.

To determine whether you are in check, I would always work from the King: generate the attack sets for all piece types radiating out from the King square, and intersect them with the bitboard of opponent pieces of that type to get the checkers. That is way faster than generating all moves of all opponent pieces (except, perhaps, when he has a bare King...)

Thanks for your detailed reply!