2

When generating attack tables for a rook, why do we consider all 2^(number of set bits on the mask) potential configurations of empty or occupied squares along the ranks and files where a rook can move?

Specifically, why are nonsensical configurations included given that they don't accurately represent legal moves a rook can make?

Take this example : X 1 1 0 1 1 and X 1 1 0 0 0 result in the same legal move for a rook. Allowing only legal combinations, the rook table could be reduced from 4096 to 144.

1
  • Not sure I understand your suggestion correctly, but how would you access the correct entry then?
    – koedem
    Aug 26, 2023 at 18:22

2 Answers 2

1

I believe you are using magic bitboards. Your suggestion can actually be done quite reasonably, and is known as PEXT bitboards. Basically, the tradeoff is between having a larger LUT or using an extra PEXT instruction to index the entry based on the least significant bit. IIRC both approaches are almost the same speed but PEXT is ever so slightly faster.

1

It takes time on the CPU to remove that extra information. Magic BitBoards are designed to do these calculations on the CPU one time when the engine is initializing so that we don't have to do them for each position being evaluated later on. If we tried to remove the extra, irrelevant blockers when computing the destinations ahead of time, we'd also need to later when attempting to retrieve the positions from the pre-computed results.

When you consider the fact that 4096 BitBoards represented in 64-bit integers constitutes about 32kb of memory, it really is not worth it to reduce this data set down. Now days, a typical home computer will have 4GB minimum. 32kb of 4GB is 0.0008192% of the available RAM. That is a perfectly reasonable amount of memory for an application to use in order to save a few CPU instructions in a method that is called thousands or millions of times per second.

1
  • While I agree that the slowdown of computing this on each node is not worth it, I have to disagree on the point that 32 KB is negligible. How much main memory you have is pretty irrelevant for something like this, it matters how much cache memory you have, you definitely want these tables in L2 cache. For that, 32 KB per square is quite a bit. However, it is just about little enough to still be ok for this.
    – koedem
    Sep 4, 2023 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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