How to reduce the "bits" used in a magic number ca

[cms271828]

Hi, isn't there a more mathematical way of finding possible magic numbers, using random numbers doesn't seem the best way of doing it when there are too many possibilities for a computer to test in a small time.

[Pradu]

Hi, isn't there a more mathematical way of finding possible magic numbers, using random numbers doesn't seem the best way of doing it when there are too many possibilities for a computer to test in a small time.

Yes, there is a deterministic way of generating magics as I outlined here. I have used this method to generate both optimal magics (both "index-optimal" and "bit-optimal") for some bishop squares and have used it to prove that no minimal-bit magic key (6-bits because there are 49 possible moves) exists for square 0 for rooks. However, the way I've been doing it right now, I use a very ad-hoc order of guessing the bits in the magic. If the following problem can be solved then the speed of this method of magic generation can be improved by many orders of magnitude and I believe that it may even be able to deterministically generate optimal magics for both rooks and bishops for all squares:

Given the input keys, the allowable collision groups, and the bits in the magic guessed so far, what is the best bit to guess next and what value should be guessed for it first (1 or 0) such that the probability of a fast collision or a cutoff can be maximized?

It is a rather difficult problem and I haven't had enough time to sit down and think over it yet, but I'm sure if I or someone else figure it out, it should be possible to generate optimal magics for both bishops and rooks.

[Gerd Isenberg]

Hi, isn't there a more mathematical way of finding possible magic numbers, using random numbers doesn't seem the best way of doing it when there are too many possibilities for a computer to test in a small time.

Yes, there is a deterministic way of generating magics as I outlined here. I have used this method to generate both optimal magics (both "index-optimal" and "bit-optimal") for some bishop squares and have used it to prove that no minimal-bit magic key (6-bits because there are 49 possible moves) exists for square 0 for rooks. However, the way I've been doing it right now, I use a very ad-hoc order of guessing the bits in the magic. If the following problem can be solved then the speed of this method of magic generation can be improved by many orders of magnitude and I believe that it may even be able to deterministically generate optimal magics for both rooks and bishops for all squares:

Given the input keys, the allowable collision groups, and the bits in the magic guessed so far, what is the best bit to guess next and what value should be guessed for it first (1 or 0) such that the probability of a fast collision or a cutoff can be maximized?

It is a rather difficult problem and I haven't had enough time to sit down and think over it yet, but I'm sure if I or someone else figure it out, it should be possible to generate optimal magics for both bishops and rooks.

So far it seems you still need trial and error and the deterministic way is about a first guess for most squares with up to four rays with length > 1. What do you mean with "index-optimal" and "bit-optimal"?

In general it is about mapping from N scattered relevant occupied bits to N (or N-1) consecutive upper bits, taking as much advantage of constructive collisions as possible, where different occupancies have common attack sets due to redundant outer occupied bits.

For instance a one-ray pattern, say bishop on a1. It is simple to find a kindergarten like fill-factor for a 1:1 mapping of all six relevant occupied bits - without any carries and collisions:

Code: Select all

idx6bitBishopA1 = ((occ & 0x0040201008040200) * 0x0002020202020200) >> (64-6)

That requires a table of 2^6 = 64 elements for the possible seven distinct attack sets. With some trial and error it is possible to half the table size with enough constructive collisions

Code: Select all

idx5bitBishopA1 = ((occ & 0x0040201008040200) * 0xffedf9fd7cfcffff) >> (64-5)

- same can be done for other edge-squares and other relevant one-ray occupancies.

How can we prove (for this bishop square a1), what the most dense index range is?

Code: Select all

idx4bitBishopA1 = ((occ & 0x0040201008040200) * magic4) >> (64-4)
idx3bitBishopA1 = ((occ & 0x0040201008040200) * magic3) >> (64-3)

To map to a three bit range, the ls1b mask with a De Bruijn factor is necessary, while other negative ray-directions require an "implicit" ms1b mask.

[Pradu]

So far it seems you still need trial and error and the deterministic way is about a first guess for most squares with up to four rays with length > 1. What do you mean with "index-optimal" and "bit-optimal"?

Yes you still need trial and error (that's how DeBruijns are generated too) but the important thing is that technique is deterministic. "Bit-optimal" refers to a magic that reduces the number of bits in the index. "Index-optimal" refers to a magic that reduces the largest index that the function hashes to. Of course an index-optimal magic is a bit-optimal magic.

How can we prove (for this bishop square a1), what the most dense index range is?

Simply by running through the entire search-tree of viable bit-optimal magics (the same way how we did it to find the largest 64-bit DeBruijn magic, just go through them all and find the biggest one). This is indeed possible as I've already shown for rook A1 for 6-bits even with an ad-hoc bit guessing scheme which took an over night run. If running through the entire search tree does not produce a viable magic, then it is proven that such a magic does not exist. For producing index-optimal magics you may be able to use more cutoffs if you can determine up front that your magic so far will hash to an index larger than or equal to the best magic found so far. I'll try to produce an index-optimal magic for bishops for A1 as an example--however I won't be able to work on it for a few days as I'll be out of town...

You could probably find the index-optimal magics for bishops for the upper squares even without trial-error tree-searching and cutoffs. For example you could try the "easiest" bishop square D8 because it has so many upper-redundant bits and you can do this simply by trying through all the numbers from 0->2^n-1 where n=64-(number of upper-redundant bits). Similarly, you can run through the search-tree of viable magics for say Bishop on A1 and you'll pick the one that gives the smallest index.

[rjgibert]

I don't know about generating a complete set of n-bit DeBruijn numbers for a given n, but generating at least 1 for a given n can be done deterministically and efficiently.

[Pradu]

I don't know about generating a complete set of n-bit DeBruijn numbers for a given n, but generating at least 1 for a given n can be done deterministically and efficiently.

It can be generated in a maximum of 30 minutes. Gerd has a faster generator for this that employs early cutoffs and IIRC it can generate them all in 1 minute.

[Pradu]

I think I came up with a good bit guessing scheme over the weekend and also managed to come up with a better collision detection scheme:

New collision detection scheme
Let keys k0, k1, ... kn collide onto the same index given the guessed bits so far g and the unguessed bits so far u. How can it be determined if no combination of the unguessed bits can prevent the collision?

Let d = ki^kj for ki and kj being an unwanted collision. If d*u for some combination of the unguessed bits u can affect the index bits, then the collision can be prevented, otherwise it can't be prevented. The routine that will determine if no possible value of u can prevent the collision will be as follows:

Code: Select all

/**
* This routine returns a bitboard of all bits that aren't upper redundant.
* key - input key
* s   - number of bits in the index
*/
U64 notRedundant(const U64 key) 
{
	return (U64FULL>>FirstOne(key));
}

/**
* This routine returns true if collision between two keys is not preventable.
* k1 - first key
* k2 - second key
* unguessed - the unguessed bits
* s - the number of bits in the index
*/
bool notPreventable(const U64 k1, const U64 k2, U64 unguessed, const int s)
{
	U64 d = k1^k2; /* only the difference in the keys matter */
	/* max is the smallest number that gets into the index bits */
	U64 max = &#40;C64&#40;1&#41;<<&#40;64-s&#41;);
	unguessed &= notRedundant&#40;d&#41;;
	while&#40;unguessed&#41;
	&#123;
		U64 b_i = LSB&#40;unguessed&#41;;  /* For each unguessed bit */
		U64 map = d*b_i;           /* Compute the index mapping */
		if&#40;map>=max&#41; return false; /* collision may be preventable */
		max-=map;
		unguessed^=b_i;
	&#125;
	return true; /* collision is not preventable */
&#125;

New bit guessing scheme
I decided that determining the best order of guessing upfront would be too difficult. So I came up with a heuristic that uses a 1 ply search to order the bits. And here's how it works:

Code: Select all

Do
	For all unguessed bits
		Try both 0 and 1 for a bit.
		If both 0 and 1 causes a cutoff, then this node cuts off.
		If 0 causes a cutoff, then the value of this bit is determined to be 1.
		If 1 causes a cutoff, then the value of this bit is determined to be 0.
	End For
While(at least one bit caused a cutoff)

When you get through this loop, guessing a 0 of a 1 for any bit will not cause a cutoff. When trying to check for cutoffs you could at the same time count the number of unwanted collisions that occur. The next bit and value you would want to guess is the one that produces the most unwanted collisions. If two or more bits produce the same number of unwanted collisions, then pick the bit that is less significant. Less significant bits are more important than more significant bits because it is less likely that they are redundant for a certain subset of the input keys than the more significant bits.

I'll try to implement the above into my existing generator when I get the time in the next few days.

[grant]

Hi

I'm not at my home computer right now so I can't try this out, but is it possible that when we calculate the attackboard we can do away with the shift lookup table by incorporating the shift into the magic number?

So instead of

Code: Select all

index = (int)((occupied * rookMagic[square]) >> rookShift[square]);

do

Code: Select all

index = (int) ((occupied * rookMagic[square]) >> (rookMagic[square] >> 58));

This looks favourable in my 32-bit code.

Grant

[wgarvin]

I'm not at my home computer right now so I can't try this out, but is it possible that when we calculate the attackboard we can do away with the shift lookup table by incorporating the shift into the magic number?

Unlikely. The magic number causes the desired bits to be collected in the upper bits of the result (along with some stray bits elsewhere). The shift is then needed to isolate them. It is analogous to computing a fixed-point multiplication result and then rounding it to an integer. Unless you could think of some way to only compute the upper bits of the result (e.g. if using 32-bit muls to implement the 64-bit operation, or something).

[Pradu]

Hi

I'm not at my home computer right now so I can't try this out, but is it possible that when we calculate the attackboard we can do away with the shift lookup table by incorporating the shift into the magic number?

So instead of

Code: Select all

index = (int)((occupied * rookMagic[square]) >> rookShift[square]);

do

Code: Select all

index = (int) ((occupied * rookMagic[square]) >> (rookMagic[square] >> 58));

This looks favourable in my 32-bit code.

Grant

Yes it is possible.