Are these magics wrong?

Question

I am working on my chess engine and wanted to finally implement magic bitboards to get a huge increase in performance.

Basically I was writing a method to check if a number can be used as a magic for a given attack mask. I took a look at this table: best magics and tried to verify if these can actually be used.

I tested it with the index 48 (rook on a7). I should probably say that I am working in Java and there are no unsigned values but this is not a problem because all shift-operations still work the same and the given magic for a7 is positive anyway.

So I took the mask and populated it with some random blockers.

mask:                     random blockers:

00000000                  00000000
01111110                  00110010
10000000                  10000000
10000000                  10000000
10000000                  10000000
10000000                  00000000
10000000                  00000000
00000000                  00000000

I then took the magic number (0x48FFFE99FECFAA00) and took the random blockers bitboard and multiplied them. the result and the shifted result looks like this:

result                    shifted

00000111                  00000000                           
00011110                  00000000
10011110                  00000000
01010101                  00000000
00000000                  00000000
00000000                  00000000
00000000                  11100000
00000000                  11000000

The problem here is that the amount of bits does not equal the one of the random blockers which is a problem because the bits in shifted result must be the same as the amount of bits in the random blockers bitboard. Also different random blockers inputs resulted in the same output.

Can somebody verify this? Where did I go wrong?

---

Also I was wondering how long it takes to generate the magic numbers. My code was running for a few seconds and did not find a single one (I checked about one thousand). What is the density of valid magics? 1/1000 ? 1/10000000?

---

My last question is: Why are people trying to reduce their tables sizes of magics? I keep seeing this and people seem to have a real battle about who can go below x kByte. Is there a specific reason for this?

EDIT:

I found the problem with the magics. I compared the shifted result and they were the same for some blockers. but these had the same actual attack set. I am very happy for any kind of help!

Answer 1

I think you're misunderstanding something here based on the way you formulated your question. Multiplying the blockers by the magic and the shifting does not give you the attack set. What it gives you is an index by which you can lookup the attack set in a pre-computed array. The shifted product is a key, not a bitboard as you displayed it

It is possible (and desireable) for multiple blocker sets to result in the same index and therefore have the same attack map. Consider a rook on A1. The attack set will be the same if there is a blocker on B1, blockers on B1 and C1, blockers on B1 and C1 and D1.

As for how long it takes to generate the magics themselves, that depends on your hardware and on the speed of your algorithm. I would say that only being able to test a thousand in a few seconds indicates a serious performance issue in your code. I feel like stockfish claims to be able to generate them all in a second or so.

Finally, the benefit of findind a "better" magic is what you said. It reduces the size of the pre-computed array. Lowering the memory footprint of an engine makes it more efficient in terms of cpu cache hits vs memory lookups.