(1) Since multiple bits are potentially set, a magic number for rook/bishop lookups is not necessarily a De-Bruijn number. It needs to be sparsely populated though (i.e. only a few bits is set). Is this correct?

Not as far as I am aware. I think sparsely populated numbers are more likely to avoid problems, but I don't see that a large number of ones will not work, it is just much less likely. If you want to create a magic number to effectively coalesce some sparsely distributed bits a,b,c,d,e,... then you might want to shift bit a to bit 63, bit b to bit 62, bit c to bit 61, etc.

So the number of ones required in the magic can be similar to the number of bits of interest {a,b,c,d,e,...}. However, if some of the bits are close, e.g. 1 bit apart, then shifting bit b to bit 62 might also simultaneously shift bit c to bit 61, and one bit less is required in the magic number. For pieces like a rook, there will be a string of consecutive bits and the magics are likely quite small (in terms of number of ones).

Although it might be nice to collect the bits 00000a00000b00000c00000d00e0f000g0000 or something like that together nicely in the form

abcdefg, I didn't create a real example there, just an arbitrary pattern, but see how the e and f bits are two bits apart?

So if I shift the e bit to where I want it, look where the f bit goes ...

****e*f

So when I find a magic number, it might not be possible to order the bits how I want them, and I might have to accept something like this as a result

abcdegf

Note the f and g bits are reversed.

Since the order the bits are packed into an index isn't known when we start looking for magics, some trial and error is involved in finding them.

I can think of about 4 ways then of finding magics. This amounts to 4 different ways of generating the guesses.

1. I have hand crafted some magics, where the packing was awkward.

2. SNOOB. (Same number of one bits)

3. repeated trial with random numbers

4. recursive software trying to pack the pits in different orders.

1. There is an example of this somewhere in the forum.

2. I have not used snoob to find magics, but have heard of it being used. This can find minimal magics, and I believe multiplication with less ones can be quicker

on some hardware - though I don't know for sure.

3, This is what I use. I do a search using a table of magics already found as first guesses, and limit the number of guesses per square and go onto another square if I don't find a magic. Then I start again with a deeper search for the missing ones. That way the program doesn't hang on an obstinate square and I can get an overview of whether what I am looking for is easy, difficult, very challenging, or maybe impossible. For example 14 bit magics for rooks didn't seem possible without a little trick (also described elsewhere on here).

4. This should be posssible, attempting to shift the bits into various orders, eg for a rook there might be 14 bits of interest and so there are 14! (factorial) ways you might try to pack them. Some of the bits are consecutive in the original data (due to the way a rook moves) and these will land together in the index after tha magic multiplication has been applied and they cannot be separated, but that just reduces the number of possibilities. I tried method 4 with no success. My coding skills and patience were not up to the task.

With a large number of bits in a magic, you are likely to start getting problems.

Suppose your product after the magic multiplication starts looking like this

abcdefgXYZ.....

Those bits XYZ are close to producing a carry that will start corrupting the bit g.

There is also a likelyhood that instead of getting a single copy of each bit you want in the index, you will start getting multiple copies, corrupting each other.

That is the reason that small numbers of one bits work best. But it doesn't mean -- as far as I can see -- that a large number will never work.

Some collisions you can get away with, but that's another story.

(2) From what I've read, a rook on A1, requires a database of size 1024 (10 bits) to hash without collisions using the currently best known magic of 0x1234567890123456. Given an ample amount of time, would it be possible to find a magic for say, a 9-bit database? Since a rook on A1 has 12 possible blockers or none at all (giving 14), the absolute minimum would be 49, i.e. pick 1 from 7 horizontally, or not at all and 1 from 7 vertically, or not at all. This gives a total of 49. Am I talking nonsense here? Of course, finding a magic number that hashes all those boards (2^7^2=16384, i think) to 42 would be a pipe dream. However, is there a proof of some sorts to give the absolute minimum database size required? I don't think there is, or whether it is even possible.

I have not got to grips really with what are the best magics found and what are the optimal ones in some sense. I just found ones that work for my application.

But I have doubts about your calculations. a rook on a1 could be blocked by a piece on b1, c1, d1, e1 or f1, or not at all. That is 6 values. That makes a total of 36 combinations if the application is "what blocks the rook". A rook on a1 can move to b1, c1, d1, e1, f1, g1, h1. That is 7 values. So there might be 49 possiblilties if the application is something like "where might the rook capture". A rook on a1 can capture on b1, c1, d1, e1, f1, g1, h1 or maybe not at all. That is 8 values. So there might be 64 possibilities if the application is something like "what can the rook capture".

If you ignore the exact application when you create magics, then you can use the same magics to create indexes into multiple different tables. You do however possibly lose the chance of some compression. My example is the classic "it is safe to eat oysters when there is an R in the month". There is probably a magic number that multiplies some ASCII month name and gives a single bit saying whether it is safe to eat oysters. However it is generally more useful if you can find a magic that converts a month number into a 4 bit value. Better still would be to covert a month name to an integer 0-11. And the super magic number would map January to 0, feb to 1, march to 2, etc. To me, crunching the months down to 4 bits would be enough and I'd have a 16 entry "safe to eat oysters table". Crunching it down to a single bit using a magic number would mean I'd need new magics next time I needed to use months for something else.