1

I am currently developing a Bitboard chess engine using C++. I am in the process of creating the move generator function. I have completed most of it and only the casting part is left.

I have used Magic Bitboards for sliding pieces and precalculated the attacks for other pieces. I am trying to make everything Highly efficient, by avoiding too many if-statements. The part I am stuck at is castling. The most naive method would be to use a few if-statements for checking whether the squares are empty and castling is still available. But this wouldn't be efficient at all.

What would be the fastest method to generate castle-moves?

2

Castling checks seem easy to short-circuit to be efficient. For my own implementation (not blazing fast), I did the following checks in order:

Generate pseudo-legal move:

  • Castling rights: Booleans for each castling, flipped when relevant king/rook move for the first time.
  • Intervening squares vacant: precalculated bitboards for each castling; AND it with all pieces.

Test move:

  • Check that the 3 squares the king (not the rook) passes through are not attacked. I had a general isSquareAttacked method for that.

This already suffices for orthodox chess. No need to make and unmake the move.

For Chess960, if you're interested, you do need to make and unmake the move to see if the king is in check after castling. This is because of the following type of situation: wRb1, wKe1, bRa1; a-side castling is illegal for white, although the squares the king passes through (e1, d1, c1) are not under attack in the static position. This case only arises for Chess960, though.

4

It's been a long time since I've made any efficiency mods, but this can be reduced to one if statement, but many would be easier to read.

if

!bitboard_occupied  // easy to find by ORing with f1/g1 (or queenside)

!bitboard_attacked | [square e1/f1/g1 (or queenside)  // attacked already known

!bitboard_moved | (h1 (or a1) & e1)

Updating the moved bitboards would be more costly to maintain during each move and undo than the extra if statements in the relatively rare castling routine.

3

I am not sure about the fastest way but I used pre-defined bitboards with 1:s on the bishop and knight squares (and queen if castling queen side) respectively and AND those together with the all pieces bitboard (there can't be any oppoennt pieces on the squares either). If the resulting bitboard is empty and you have castling rights, then you are allowed to make the move.

Edit: You also can't add the castling move if you are in check, which should be the first and easiest to check (since you probably already check if you are in check or not in your move gen routine).

5
  • 1
    Yes that's works except that the king can't castle if any of the squares where the king might be in between the castle are under attack, what about that :( Jan 18 at 10:32
  • Are you generating only pseudo-legal moves? If so you will do this check when you make the move to save time in your engine. If you try to make a castling move you let the make_move function check whether those squares are under attack, and if they are return that the move is False.
    – eligolf
    Jan 18 at 11:15
  • What I do is generate a set of pseudo-legal moves first, iterate through them later on to check whether the king is in check AFTER making the move. The thing is the king moves more than 1 square during casting, and none of them should be under attack, not only the one that it would be on after castling. Jan 18 at 11:48
  • So in your Negamax function you have something like 'children = get_pseudo_legal_moves()' and then when you loop through all nodes you do something like 'for child in children: if make_move(): do all the stuff, else unmake move and skip to next move'. Since most of your moves probably won't be causing the king to end up in check. In the make_move function where you check if the move ends up in check you can have a special case where 'if move_type == 'castling': also check square -1'. I hope I make myself clear, English is not my main language :)
    – eligolf
    Jan 18 at 11:56
  • Actually I haven't started the implementation of the search. I am still implementing the move generator, trying to make it as efficient. But i get what you mean, thank you. And yeah your English was comprehensible you don't have to worry. Jan 18 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.