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

[Pradu]

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).

It is possible. The six upper-bits of the magic number used to store the shift are either completely redundant (won't affect the index hashed to at all) or if not, it'd be redundant to most of the input keys.

For bishops the upper six bits are completely redundant for every input key possible. For rooks the upper six bits are completely redundant for every input key possible except for the first rank squares.

[jwes]

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).

Something like
__mulh: Returns the high 64 bits of the product of two 64-bit signed integers.
http://msdn.microsoft.com/en-us/library/17wa28cw.aspx

[Gerd Isenberg]

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

Looks like a good idea to me - after some thinking...
I guess the additional constrain for the max 57 left shift in the mul, might finding magics for squares 0..7 a bit harder, since they are already the heavy 12 (edges) and 11 bit squares. What about only two bits to encode the max delta of the shifts in the 52..55 range for the rooks? So we store 0..3 to perform an add cl, 52.

Code: Select all

index = (occupied * rookMagic[square]) >> ((rookMagic[square] >> 61) + 52);

The nice thing is that the additional shift right and eventually the "add" are independent from the 4 cycle latency imul and will likely improve ipc since thy are done en-passant.

Gerd

[grant]

Hi

Here is a new set of magics for the rooks. The upper most 6 bits stores the shift making the table redundant. Remember that in my engine A8=0, B8=1 ... H1=63.

Code: Select all

0    D0800280A0400072   12 bit
1    D440003000A00040   11 bit
2    D500082000304100   11 bit
3    D480080150001481   11 bit
4    D500070008001004   11 bit
5    D6000804100E000D   11 bit
6    D400242090012802   11 bit
7    D100010008802746   12 bit
8    D48080008030C001   11 bit
9    D828802002400182   10 bit
10   D8FF002000350140   10 bit
11   D901800803100080   10 bit
12   D819000800104500   10 bit
13   D808801400810200   10 bit
14   D8D2000B02003864   10 bit
15   D662000148940201   11 bit
16   D500868004304002   11 bit
17   D820018020400282   10 bit
18   D8C2260011420480   10 bit
19   D801010060689000   10 bit
20   D891050011000801   10 bit
21   D9610100028C0058   10 bit
22   D85A44000D081210   10 bit
23   D49012000400C181   11 bit
24   D701A08080004002   11 bit
25   D81008C24004A002   10 bit
26   D824F04500200104   10 bit
27   D84030010008A100   10 bit
28   DA91002D00109800   10 bit
29   DA120080800C0002   10 bit
30   D808702400414208   10 bit
31   D7010C2A00088B41   11 bit
32   D440087040800080   11 bit
33   D9B0082001400040   10 bit
34   D860002101004012   10 bit
35   D8B9891001002100   10 bit
36   D891050011000801   10 bit
37   D803044048011020   10 bit
38   D908300B14005882   10 bit
39   D4000E4102000484   11 bit
40   D4C580F040018000   11 bit
41   D810024020004000   10 bit
42   DA21412009010010   10 bit
43   D951043000090020   10 bit
44   D921001008010004   10 bit
45   D801000400790002   10 bit
46   D8000502100C0008   10 bit
47   D68182448C020007   11 bit
48   DAFFFF3DFF544600   10 bit
49   D8FFFEB5FEC78E00   9 bit
50   DCFFFF51FF67D200   9 bit
51   D8FFFED9FECC9600   9 bit
52   D819000800104500   10 bit
53   D820807401020080   10 bit
54   D8F2080A10110400   10 bit
55   DB2FFFF5F63C96A0   10 bit
56   D5FFFFA9FF9B27D2   11 bit
57   D9FFFEDDFEEDAEAE   10 bit
58   DBFFFFDDFFCF7F92   10 bit
59   DA7FFFD9FFBFD536   10 bit
60   DADFFFDDFFDBD536   10 bit
61   D412001004086942   11 bit
62   D423080092104104   11 bit
63   D775FFFECBFEA1A6   11 bit

Grant

[Pradu]

I'd like to introduce another idea, which I call a "difference key". The "difference key" will be helpful to make the detection of unpreventable collisions much faster. Assume two keys k1 and k2 in different collision groups hash to the same index given the guessed bits so far g and the unguessed bits so far u. Then the difference key d is defined as follows:

Code: Select all

/**
* This routine checks returns a bitboard of all bits that
* arn't upper redundant.  Upper redundant bits are bits
* such that (key)*(upper redundant bits)==(key). 
*
* key - input key
*/
U64 notRedundant(const U64 key) 
{
	return (U64FULL>>FirstOne(key));
}

/**
* diffKey
*
* This routine will return a "difference key" given two
* keys k1 and k2 and the unguessed bits u.
*/

U64 diffKey(U64 k1, U64 k2, U64 u)
{
	//Construct the initial difference key
	U64 d = (k1^k2);

	//If u==0, diffKey=0 - collision not preventable
	if(!u) return U64EMPTY;

	//u must have a LSB now and redundant bits in d can be removed
	return d & notRedundant(u);
}

The idea of a difference key is that it possible to create an algorithm that can compute if a collision can be prevented much faster than my old naive algorithm:

Code: Select all

Old Algorithm

/**
* 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 notPreventableOLD(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;

The above big ugly function can be turned into one comparison with the help of difference keys. First you must precompute the minimum difference key required to prevent a collision given the unguessed bits u and the number of bits in the index s:

Code: Select all

/**
* minDiffKey
*
* This routine will return the minimum difference key required to
* prevent a collision given the unguessed bits u and the number of
* bits in the index s.  A collision is preventable if diffKey>=minDiffKey.
*/
U64 minDiffKey(U64 u, const int s)
{
	U64 max = &#40;C64&#40;1&#41;<<&#40;64-s&#41;);

	//routine will work correctly even if u>max
	return &#40;max/u&#41; + &#40;max%u&#41;?1&#58;0;
&#125;

So at the start of the collision prevention detection function, you compute the minimum difference key. Then all need you to do is compute diffKey>=minDiffKey for every pair of unwanted collisions!

[Rein Halbersma]

I'd like to introduce another idea, which I call a "difference key". The "difference key" will be helpful to make the detection of unpreventable collisions much faster. Assume two keys k1 and k2 in different collision groups hash to the same index given the guessed bits so far g and the unguessed bits so far u.

So at the start of the collision prevention detection function, you compute the minimum difference key. Then all need you to do is compute diffKey>=minDiffKey for every pair of unwanted collisions!

Perhaps you could update your nice article about constructing optimal magics with all your new improvements? That would really help others get the big picture!

[Pradu]

Perhaps you could update your nice article about constructing optimal magics with all your new improvements? That would really help others get the big picture!

I will most certainly update it as soon as I've finished the new implementation and will also try to make it more rigorous and easier to read. I will also post the sources to the magic-generator as well (I didn't post the sources for my old one because it was really hacked up and poorly documented).

How the above improvements fit in the existing algorithm is as follows:

1. Generate input keys (occupancies) and give each input key a group number so that two input keys with the same group number have the same set of moves.
2. Pick the number of bits in the index that you'd like to try to generate a magic for.
3. A variable magic can be represented by two 64-bit integers. All unguessed bits are '1' in u and all guessed bits are '0' in u. All unguessed bits are '0' in g and all guessed bits are either '0' or '1' in g depending on the guessed value.
4. First, all upper-redundant bits in the variable magic are set to 0 by u&=(U64FULL>>FirstOne(preMask[sq]))
5. Lets consider using a guessing order where you always guess 0 first and 1 next and you guess bits from bit 0 to bit 63 and lets start a recursive bit-guessing search using this guessing order:
   1. First you perform a 1-ply search of guessing bits to see if some bits can be determined upfront. When you find out that you can determine the value of a bit you set its value, you can repeat the 1-ply search until no bits can be determined. This is where the new improvements (the one using difference keys that tries to determine if some bad collisions are unpreventable regardless of what bits you guess) come in. After you guess a bit you can check to see if you can determine upfront if the bit guessed will lead to an unpreventable bad collision. If both values (0 and 1) will cause an unpreventable collision you can return from this node (no value of this bit can help prevent a bad collision). If only 0 causes an unpreventable collision, then the value of the bit must be guessed as 1. If only 1 causes an unpreventable collision, then the value of the bit must be guessed as 0.
   2. After the 1-ply search you can guess the next bit which is determined by your guessing order.

The recursive search will eventually guess all the bits without unwanted collisions and it will produce a magic number. Then you can return from the leaf-node and continue the search to find another magic number. And in this process you can go through them all and pick the one that produces the smallest index for the given number of bits. If there's no magic number for the number of bits that you've chosen then the recursive search will never get to a leaf node and so it'll never produce a magic number.

[Rein Halbersma]

Perhaps you could update your nice article about constructing optimal magics with all your new improvements? That would really help others get the big picture!

I will most certainly update it as soon as I've finished the new implementation and will also try to make it more rigorous and easier to read. I will also post the sources to the magic-generator as well (I didn't post the sources for my old one because it was really hacked up and poorly documented).

Great! That would be really beneficial.

How the above improvements fit in the existing algorithm is as follows:

1. Generate input keys (occupancies) and give each input key a group number so that two input keys with the same group number have the same set of moves.
2. Pick the number of bits in the index that you'd like to try to generate a magic for.
3. A variable magic can be represented by two 64-bit integers. All unguessed bits are '1' in u and all guessed bits are '0' in u. All unguessed bits are '0' in g and all guessed bits are either '0' or '1' in g depending on the guessed value.
4. First, all upper-redundant bits in the variable magic are set to 0 by u&=(U64FULL>>FirstOne(preMask[sq]))
5. Lets consider using a guessing order where you always guess 0 first and 1 next and you guess bits from bit 0 to bit 63 and lets start a recursive bit-guessing search using this guessing order:

Two questions: 1) during this search, for each bit that you want to determine, do you loop over all possible keys to check for collissions? and 2) your old paper mentions to guess from 0...63 for bits that direct influence the index mapping, and from 63...0 for bits that only have carry influence. Do you now always guess from 0...63 for all bits?

1. First you perform a 1-ply search of guessing bits to see if some bits can be determined upfront. When you find out that you can determine the value of a bit you set its value, you can repeat the 1-ply search until no bits can be determined. This is where the new improvements (the one using difference keys that tries to determine if some bad collisions are unpreventable regardless of what bits you guess) come in. After you guess a bit you can check to see if you can determine upfront if the bit guessed will lead to an unpreventable bad collision. If both values (0 and 1) will cause an unpreventable collision you can return from this node (no value of this bit can help prevent a bad collision). If only 0 causes an unpreventable collision, then the value of the bit must be guessed as 1. If only 1 causes an unpreventable collision, then the value of the bit must be guessed as 0.
2. After the 1-ply search you can guess the next bit which is determined by your guessing order.

[/list]The recursive search will eventually guess all the bits without unwanted collisions and it will produce a magic number. Then you can return from the leaf-node and continue the search to find another magic number. And in this process you can go through them all and pick the one that produces the smallest index for the given number of bits. If there's no magic number for the number of bits that you've chosen then the recursive search will never get to a leaf node and so it'll never produce a magic number.

If there are no collision groups (so every key maps to a unique index), you can stop after the first magic you have found, right?

BTW, how many recursive calls for the bit guessing does your algorithm typically take before before it terminates? Say, for a 10-bit magic? (I guess anywhere between 64 and 2^64, but I am interested in average case behaviour).

Rein

[Pradu]

Two questions: 1) during this search, for each bit that you want to determine, do you loop over all possible keys to check for collissions?

No. Only the ones that are in different groups that hash to the particular index. So first you'd have to hash all the input keys into their respective indices then calculate difference keys for every combination of two input keys in different groups.

2) your old paper mentions to guess from 0...63 for bits that direct influence the index mapping, and from 63...0 for bits that only have carry influence. Do you now always guess from 0...63 for all bits?

I don't know the answer to the best order of guessing. I just mentioned the above as a reasonable guess for the order of guessing. The reasoning I used behind these guessing schemes is shaky. I considered that less significant bits are more important than more significant bits simply because more significant bits are redundant to more of the input keys and less significant bits affect the input keys more. I considered guessing from MSB to LSB for the direct influence because it'll be more likely to have groups collide into each other. Perhaps with the new one-ply search to try to determine bits up front, the guessing from direct influence is not necessary.

If there are no collision groups (so every key maps to a unique index)

By collision group I meant that if two input keys are in the same collision group, they will produce the same move bitboards. That means that if two input keys in the same collision group hash to the same index, it'd be ok. However if two input keys in different collision groups hash to the same index, that'd be a bad unwanted collision. I guess what you meant was: If you have guessed all bits without unwanted collisions, ...

you can stop after the first magic you have found, right?

Yes, but if you continue you may find a better magic that hashes to a better range of indices. Hypothetically, say some 10-bit magic hashes from 0..1023. But if you find another 10-bit magic which hashes from 0..600, you'd rather use that.

BTW, how many recursive calls for the bit guessing does your algorithm typically take before before it terminates? Say, for a 10-bit magic? (I guess anywhere between 64 and 2^64, but I am interested in average case behaviour).

I haven't counted it and it varies considerably depending on what square and piece you are trying to do, the number of bits in the index you choose, and what guessing order you choose. I'll perform some experiments after I get my new code up and running.

[Pradu]

I guess this would probably be better in the case where (k1^k2)&notRedundant(u) is just slightly larger than minDiffKey:

Code: Select all

/**
* diffKey
*
* This routine will return a "difference key" given two
* keys k1 and k2 and the unguessed bits u.
*/
U64 diffKey(U64 k1, U64 k2, U64 u)
{
	//k1^k2 are the bits that matter
	//1 bits that are the same in both k1 and k2 don't matter
	U64 d = (k1^k2);

	//If u==0, diffKey=0 - collision not preventable
	if(!u) return U64EMPTY;

	//u must have a LSB now and redundant bits in d can be removed
	d&=notRedundant(u);

	{
		U64 diff1 = k1&d;
		U64 diff2 = k2&d;
		if(diff1>diff2) return diff1;
		else return diff2;
	}
}

/**
* minDiffKey
*
* This routine will return the minimum difference key required to
* prevent a collision given the unguessed bits u and the number of
* bits in the index s.  A collision is preventable if diffKey>=minDiffKey.
*/
U64 minDiffKey(U64 u, const int s)
{
	U64 max = &#40;C64&#40;1&#41;<<&#40;64-s&#41;);

	//routine will work correctly even if u>max
	return &#40;max/u&#41; + (&#40;max%u&#41;?C64&#40;1&#41;&#58;C64&#40;0&#41;);
&#125;