Why should magic bitboards be sparse?

[ajp]

The chess programming wiki mentions that "[a] better magic number will have less bits required in the index" without explaining why. What is the advantage of having magic bitboards be sparse? Or am I misreading the comment?

[AndrewGrant]

Currently for rooks, you need ~100000 indexes of boards. If we could reduce the number of bits needed we could reduce the size of the database. For example, I believe we need 4096 boards for A1. A8, H1, H8 for rooks. If we could find a magic number that works that requires one less bit (2048 boards) we could save on some cache space and array size.

[ajp]

Currently for rooks, you need ~100000 indexes of boards. If we could reduce the number of bits needed we could reduce the size of the database. For example, I believe we need 4096 boards for A1. A8, H1, H8 for rooks. If we could find a magic number that works that requires one less bit (2048 boards) we could save on some cache space and array size.

Maybe I'm missing something, but isn't the number of indices fixed by the number of bits set in the bitboard of potential blockers? For a rook on a1, blockers can be found on squares a2 to a7 and b2 to g2. That's 12 bits that can possibly be set, so we have 2^12 = 4096 elements in the attack table for a rook on a1.

[kbhearn]

You're misreading it - magic numbers that satisfy that comment are usually not sparse at all.

the index is the number of bits you extract after the multiplation (less bits = a larger shift value). for example a R not on any edge has 10 potential occlusion bits. If the R is on d4 say, this maps to only 3*3*4*4 = 144 possible result states which could be mapped in 8 bits if an appropriate number can be found (or even exists). Often there'll be a sparse magic number that maps all the squares of interest to 10 bits, but to get it to 9 or 8 bits you need a dense magic number with lots of potential for constructive interference and need to find it by trial and error.

The main difference being that in your final lookup table the 10 bit number takes 1024 64 bit entries while the 8 bit number takes 256 entries and wastes less space. Now many squares are very hard to find magic numbers for that perform anywhere close to their result space so instead of reducing the number of bits an alternative way to reach the same idea is to overlap your result tables - that is instead of trying to find a better magic number for a R in a corner (one of the harder ones with 12 potential occlusion bits and only 49 output states - the 6 contiguous potenital blockers with few bits that can be used to make them constructively interfere creates difficulties) you accept a large index key but overlap it with other squares such that you have as many unused indices for your extra large Ra1 as you can and overlap other squares into the same range of the table.

[ajp]

Thanks Kevin, very well explained.

[Gerd Isenberg]

What is the advantage of having magic bitboards be sparse? Or am I misreading the comment?

In trying to find magics with the usual 2^n-bit sized individual square tables of Pradu's fancy magics in a few milliseconds, sparse randoms have higher probability to be a contradiction free magic factor. Six bits are usually enough to squash the relevant occupancy to the upper n-bits used as index. See Tord's code where candidates are intersection of three 64-bit random integers. If you are looking for magics for denser 2^n-1 sized tables you'll need to waste more time, trying also high populated numbers, see Best Magics so far.