4

I currently have a function which returns the closed off squares for a piece in a particular position based on pieces blocking it. This function iterates over the rays of a piece and is sufficiently fast, but can use a lot of improvement since it accounts for most of the time taken in the move generation.

I have been recently researching on how I can optimise this function and came across this "trick": https://www.chessprogramming.org/Subtracting_a_Rook_from_a_Blocking_Piece which conveniently uses a formula to instantly get all the moves for a rook. Is there a similar "trick" to generating moves for a bishop while accounting for the blocking pieces?

If you need any clarifications regarding the question, feel free to ask.

6

Move generators in modern engines do this with lookup tables, which are indexed by the square of the slider and a bitboard representing occupied (impassable) squares that might block the movement of the piece.

There are two main ways of compressing the huge set of possible occupancy bitboards into a reasonable size. Magic Bitboards are often used, which involve multiplying the occupancy bitboard by 'magic' numbers, which are chosen because they empirically map the set of possible occupancy bitboards into a dense range.

A more modern way depends on the PEXT instruction which is available in newer x86 processors. PEXT bitboards allow for the lookup table to be mapped to an even denser range, and also improves lookup times on processors which can run PEXT quickly. However, PEXT is very slow to emulate on older processors, and also seems to be particularly slow on Ryzen processors.

| improve this answer | |
  • How does this bit board determine impassable squares, is it a fixed value or that it is computed for some instances of a blocking piece in a board position? – Crupeng Feb 15 at 13:36
  • 2
    It's precomputed (with the naive method of iterating over rays) and then stored in a table. – konsolas Feb 15 at 15:29

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.