I have a stupid idea

[Mike Sherwin]

Are magic modulo bitboards a thing? I don't remember reading anything about them. Considering just the bishops it might work like so.
1. get the blockers
2. put some magic bits in for the 8th rank (and maybe also among the rest of the blockers)
3. magic blockers % magic divisor = magic index

Is that possible or is modulo too slow?

[Sesse]

Modulo by constant can be done fairly efficiently by multiplication, but some CPUs have pretty fast div/mod these days anyway. E.g. Zen 4 has 9–17 cycles latency for DIV r64 (compare this to Haswell's 31—94).

I have no idea whether your idea is useful in itself, though.

[Mike Sherwin]

That is really good timing for modulo compared to what it used to be! Now if magic modulo bitboards work then due the the relatively low number of instructions and no dependency chain it looks to be darn fast.

And I think it will work. Since modulo returns a remainder it automatically returns an index without a need for a right shift. I do not know how many bytes the magics would be but 65,536 is quite a few combinations to try. That means the required amount of memory would be quite low. But if we had to use 16 bit magics the number of combinations would be quite enormous, 4,294,967,296. The magic divisor would have to be within a range to return a remainder with the required number of bits and wala it should work!

[thomasahle]

Did you test how big the divisor needs to be to not get collisions?

Is the idea that nothing else uses division/modulo, so those circuits are lying around free?

[Mike Sherwin]

Did you test how big the divisor needs to be to not get collisions?

Is the idea that nothing else uses division/modulo, so those circuits are lying around free?

I just came up with the idea tonight so I have not tested anything! The fact that it might gain an advantage by using unused resources never crossed my mind. What did cross my mind was that using two magics together means 'a * b' combinations instead of just 'a' by itself. That should mean much smaller tables.

Edit: on second thought I might not be thinking correctly about smaller tables. Maybe just smaller magics.

[thomasahle]

I don't know if you remember his is well appreciated here, but one thing about the "ax>>b" method is that it's a universal hash function (known as multiply shift in the hashing literature) which guarantees you can always easily find an "a" magic constant to spread out some given set of keys without collisions.

Basically, for a random "a", two given keys will collide with probability 1/m, where "m = 2^(64-b)" is the number of distinct hash values. If you take m ~= n^2 then with constant probability no two keys will collide. So trying a few different "a"s will quickly find you a good one.

For modulo we can do a similar analysis. If we pick a random modulo, the probability that two keys, x and y, will collide depends on the number of divisors of (x-y). However there can't be more than log|x-y| many, si it shouldn't make things too bad. You probably need "m" in the order of "n^2 logn", unless you are lucky.

[dangi12012]

mod is a valid hash function.
It will be slower then the other universal hash function of "(a*b >> x)" so for performance reason its out (on pretty much all hardware I know of)

Fun fact. Mod by power of two:

Code: Select all

A % B == A & (B -1) 

Which is faster than above function - but its just taking N bits. - can be used quite effectively if you shift beforehand by "square" lets say.