Why consider all possible combinations of empty/occupied square a sliding piece can move to in attack table generation?

Question

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.

Answer 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.

Answer 2

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.