Explain like I'm five - what is the 'n' in right shift 64-n?

[Bayowulf]

I need help understanding magics. I hope you all tolerate beginners with niave questions. Let me give you some background about what I understand so you can adjust your explanations accordingly. First of all I am not a C programmer, but I can comprehend small doses. I am begining to write a chess program in Python as a personal challange. I have lots of questions but I will focus on only one here now - and that is what exactly is the 'n' in: 'Right shift the index mapping by 64-n bits to create an index' (from http://chessprogramming.wikispaces.com/Magic+Bitboards)

I am sudying Fritz Reul's paper http://www.personeel.unimaas.nl/uiterwi ... thesis.pdf - but it is making my brain burn : ) Eventually I hope to be able to extract what I need from it.

I (mostly) understand from the following code that this is used to generate an index to look up the sliding_move in a hash table and I get the gist of Mask --> Multiply --> Shift --> Lookup.

Code: Select all

Minimal Array Access Implementation
uint64 get_sliding_direction (const int square , const uint64
blockers) {
uint64 bitboard = blockers & sliding_mask[square];
int offset_index = sliding_offset_index[square];
int magic_index = bitboard * sliding_magic[square] >>
sliding_shift[square];
return sliding_move_hash_table[offset_index + magic_index];
}

The big question I have here is what is the 'sliding_shift'? There are 12 positions to acount for with Ra1 - so is the sliding_shift[square] = 12? On the other hand magics are often listed with a 'number of bits' column e.g.: magic_multiplier_rook[a1] = 0x0080004000802010; // 5 bits - what is this? Do I subtract 5 or 12?

Also the number bitboard * sliding_magic[square] is often huge and if it is longer than binary 64 digits I just chop off any digits greater than 64. Is that correct?


I did some tests with the above Rook A1 magic and a 64-12 shift - an excerpt:

Code: Select all

Mask #  2                 
........
X.......
X.......
X.......
........
X.......
........
.X......

magic index:  2591
________________

Mask #  126
........
X.......
X.......
X.......
........
X.......
........
.XXXXXX.

magic index:  3583
________________

The magic indexes differ from one to the next by 16: (2591 + 16*62 = 3583). Is this type of pattern to be expected?

If I use 64 - 5 I get:

Code: Select all

Mask #  2
........
X.......
X.......
X.......
........
X.......
........
.X......

magic index:  20

Mask #  126
........
X.......
X.......
X.......
........
X.......
........
.XXXXXX.

magic index:  27
________________

Here the pattern is every eight in a row are the same number, proceeding in sets of eight from 20 to 27. This seems unlikely to be correct. - Thanks

[micron]

I need help understanding magics.
[snip]
what exactly is the 'n' in: 'Right shift the index mapping by 64-n bits to create an index' (from http://chessprogramming.wikispaces.com/Magic+Bitboards)

Magic multiplication 'herds' the relevant and interesting bits to the most significant end of the product (bitboard * sliding_magic[square]). Irrelevant rubbish bits are either lost by overflow, or end up occupying the low order (bits 64 - n - 1 to 0).

The next consideration is that the product is a huge number, completely unsuitable as an index into an array. We need to derive or construct a small integer from the product, using only its most significant n bits.

Right shifting by 64 - n does exactly that.

If you are learning about magic attack generation, I suggest looking first at a simple form in which n is fixed (at 9 for bishops and 12 for rooks), instead of being yet another precomputed array.
http://chessprogramming.wikispaces.com/ ... ions-Plain

Robert P.

[Desperado]

1: background of n
====================

a: "n"

*
imagine an empty board with a rook on d4.

*
Now, if you want to lookup the bitboard target pattern in a table,
you have to know how many occupancy states can occur with a rook on d4.

first there are 7 empty squares along the file (a4,b4,c4,e4,f4,g4,h4)
+ 7 empty squares along the rank (d1,d2,d3,d5,d6,d7,d8)

These squares can be occupied (1) or can be empty (0).
Therefore you first have 2^14 (n=14) occupancy states.

But the occupancy state of the border squares is not relevant, they
do not obstruct anything. That is the reason why you are only interested
in the occupancy state of the "inner" bits.

eg: (b4,c4,e4,f4,g4) + (d2,d3,d5,d6,d7) : 2^10 bits

So, with a rook on d4 and a table which holds these 2^10 occupancy states,
you can lookup for each of these occupancy states the target bitboards.

"Basically" you are able to adress with n = 10 bits every occupancy state
in a table. You never will need more than these 10 bits.

In an advanced scheme you may reduce the 10, because some of the occupancy
states are holding an identical target bitboard...

b: "64-n"
====================

*
number64 = maskedOccupancy (file+Rank of d4) * magicNumberRook[d4];

In the given example you need 10 bits for adressing the table.

So you just pick the 10 most significant bits of the "number64".

number64 = number64 >> 54 (so 10 bits are left).

In that case 64-10, because n is fixed to 10.

In advanced schemes you can optimize as stated above, so n could be 9 for example.

which would lead to 64-9 == 55 bits right shift.

Finally in a "basic scheme" you can just make a table with the minimum requirements
like 10 in the given example, and calculate the numbers for each other square.

Hope it helps...

regards Michael

[Bayowulf]

Thanks for the clear explanations. So, n is a function of the scheme I used to index the attack table. I'd like to clear up one other aspect of the calculation.

micron: The next consideration is that the product is a huge number,

Desperado: number64 = maskedOccupancy (file+Rank of d4) * magicNumberRook[d4];

In the given example you need 10 bits for adressing the table.

So you just pick the 10 most significant bits of the "number64".

number64 = number64 >> 54 (so 10 bits are left).

Do I handle the number maskedOccupancy (file+Rank of d4) * magicNumberRook[d4] as is? What if it has more than 64 bits such that number64 >> (64-n) is still also a very large number?


//deleted and reposted to include the following//:

So, taking the large number as is I get the following:

Code: Select all

Mask #  2
........
X.......
X.......
X.......
........
X.......
........
.X......

magic index:  2260647514737183

Mask #  126
........
X.......
X.......
X.......
........
X.......
........
.XXXXXX.

magic index:  2260647514738175

The right most 12 digits are the same. So can they be disregarded?

Thanks, Jim

[/quote]

[Desperado]

Sorry I am in hurry, but just a hint...

The overflow bits of the product (maskOccupancy * magicNumber) are
lost (if you mean that). The "right shifted" number, so the final index
has to be in the range between (0,2^n). In my above given example
0...1023.

must leave, maybe tonight i will have a closer look what you mean exactly...

cheers Michael

[hgm]

You are doing this in 64-bits precision, so the result can never be more than 64 bit. That is the reason you use '64' in '64-n'. If you had been doing thisin 80-bit arithmetic, you would have to use '80-n' (and possibly larger magic multipliers to make sure all occupany bits are carried to the high end of the 80-bit result). So the whole basis of the method is that the shift is guaranteed to clear the 64-n high-order bits of the word.

[Bayowulf]

I'm not sure I follow. If big = 0xf000000000000000 and bigsq = big * big then bigsq >> 64-12 will be greater than 64 bits. (At least it is in Python, perhaps not so in C).

I am really just trying to calculate the magic index correctly. I don't yet have a feeling for what is a reasonable index number versus one that is outrageously incorrect.

If I make no attempt to reduce the number of digits, I could possibly end up with really big numbers greater than 64 digits. So, should I trim LSB's on all multiplication results to stay within 64 digits?

[hgm]

Indeed, in C the product of two 64-bit ints will be a 64-bit int, and bits that do not fit will be clipped. If that is not the case in Python, you wouldhave to clip the leading bits by hand, through ANDing with 0xFFFFFFFFFFFFFFFF (or with (1<<12)-1 after the shift).

[bob]

Indeed, in C the product of two 64-bit ints will be a 64-bit int, and bits that do not fit will be clipped. If that is not the case in Python, you wouldhave to clip the leading bits by hand, through ANDing with 0xFFFFFFFFFFFFFFFF (or with (1<<12)-1 after the shift).

Actually, you can get 128 bits when you mult two q-words. A bit dicey to use, but if you want the high-order 64 bits, just peek in edx and use the one-operand multiply instruction.

edit: oops. Make that "rdx" for 64 x 64 multiply, of course. edx is for 32 x 32 multiply.

[micron]

I don't yet have a feeling for what is a reasonable index number versus one that is outrageously incorrect.

For the plain fixed-shift magic mention earlier, the bishop index has 9 bits, so its range is 0..512. The rook index is 0..4095.

So, should I trim LSB's on all multiplication results to stay within 64 digits?

LSBs don't make a number huge. MSBs do. That's why you right-shift the 64-bit product.

110010011000...0000000000000 // huge
000000000000...0000110010011 // small, after shift right

Robert P.