Magic Multiplier Fundamentals

[Cheney]

Hi,

I am interested in learning more about the magic multipliers. I understand, from a high level, what the end goal is - basically, to obtain an index to lookup pre-stored attacks.

Where I am stuck is with the initial math and what I see on CPW:

http://chessprogramming.wikispaces.com/Magic+Bitboards

Code: Select all

                                        any consecutive
relevant occupancy                      combination of
rook d4, 10 bits                        the masked bits
. . . . . . . .     . . . . . . . .     4 5 6 B C E F G]
. . . 6 . . . .     . . .some . . .     . . . . . .[1 2
. . . 5 . . . .     . . . . . . . .     . . . . . . . .
. . . 4 . . . .     . . .magic. . .     . . . . . . . .
. B C . E F G .  *  . . . . . . . .  =  . . garbage . .    >> (64-10)
. . . 2 . . . .     . . .bits . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

My first fundamental question is: does the magic number have to be a number which literally preserves the bit order from the occupancy bits?

Looking above, it would appear that way (e.g., the d2 occupancy bit (noted by the '1') gets mapped to the g7 index bit).

Under the assumption this is true, then what is the mapping if the occupancy was shifted left one bit (rook on c4)? I expect the "C" bit would go away and a "D" bit would replace it (thus preserving the order).

If I am correct, then I am definitely doing something wrong or have some other misunderstanding. I obtained a few magics from others' code and web sites to just perform the math up to this point and I do not get the preserved bits.

Thank you for your help

[hgm]

In general magics do not preserve bit order, or even individual bit values. They do not even provide a 1-to-1 mapping on the index; it is perfectly acceptable if two different occupancies that need the same attack set (because the difference is on a square that happens to be blocked, e.g. G when E is occupied) map to the same index value. This is why there exist sub-minimal tables, like only 2K for a corner Rook while 12 occupancies are relevant and 2^12 = 4K.

[Cheney]

OK, thanks

Although that was not the original impression I had, this is relieving to know - so maybe I am on the right track

If I am understanding this correctly, is it safe to say that the "magic" in the magic multiplier is that the index provided is more based on the first blockers encountered in the occupancy (thus why similar indexes can be provided)?

And, from what I can tell, is that why it appears that in order to generate magics one must first have the various occupancies and attack sets defined?

Thanks again.

[wgarvin]

Yes. The idea is to take the N bits of useful occupancy information, which are scattered around in the 64-bit bitboard at various places, and map them to an M-bit index where all M bits are densely packed together, with M <= N. (those M bits will be clustered together in the most significant bits after the magic multiplication... thats what the multiplication accomplishes).

You can literally generate random 64-bit numbers and then test them to see if they have this property; just test it by multiplying it against all of the 2^N permutations of the N useful bits, and make sure that the most significant M bits of the result contain a unique index for each value. If two different inputs give the same M-bit index as a result, that might still be OK (as long as the data you want to return -- the bitboard, or movecount, or whatever-- is also the same for both inputs). Thats how you can get magic multipliers with M < N : by finding magic numbers that have a lot of these "useful" collisions. The "best" ones, will have all of their used entries clustered together somehow so that you don't even need 2^M worth of storage space for them (you can overlap the beginning and/or end of the range with the table entries for a different square, and it will still work because those entries at the beginning and/or end will never be accessed).

But if it turns out that a potential magic number has a "bad" collision, then you can't use it. A "bad" collision would be, if two different input permutations of the N occupancy bits, which need to give two different results from the function, but after the magic multiply they both have the same M-bit index at the top of the result.

[wgarvin]

Usually, magics are used for move generation for sliding pieces, so the data being returned is a bitboard. Before using that result, you'll probably want to AND it with another bitboard (of either empty squares if you are generating non-captures, or of enemy pieces if you're generating captures). So you can effectively ignore the occupancy bits around the edge of the board, and only use occupancy bits that lie in the 6x6 squares in the middle of the board. You should also ignore the occupancy of the square you are starting from; it probably has a piece on it of the proper type, but you want these routines to work properly even if it doesn't. So for rooks, that means you might have an N as large as 12 (one of the four corner squares), but for 36 of the 64 squares N will only be 10. And then you try to find magics with M < N, so it can be even smaller than that. So you need a small table for each square, and to make the overall table size as small as possible, you would want to try to make each square's data as small as possible (by finding the "best" magic number you can for it) and/or overlap them in some odd way.

...If you look at Pradu Kannan's magic bitboard code, I think it has already been optimized somewhat to have the smallest tables. I don't know what the "state of the art" is for rook tables, but about 800 KB of data is typical. Bishop tables never need N > 9 and can be much smaller; IIRC they can be as small as 38 KB or something.

[Cheney]

Thanks - I am going to let that sink in a bit, but I think I follow.

I do have another question on this while I am attempting to code this.

Since the magic will be used to obtain an index to an attack set, it appears to me the attack set must be predefined and whenever it is defined/built, it must be in the same order. Is this accurate? I think it is.

What I visualize is I'll build the attack sets, for rook let's say, starting at A1 and move to H8. Then I'll generate and test magics. However, if I keep those magics and then rewrite the attack set generator to work from H8 to A1, I would expect those magics to be bad. Is this true?

[wgarvin]

Think of the function you are implementing (e.g. rook_attacks or bishop_attacks) as a mathematical function. It takes as input a square Sq and a bitboard Occupancy, and it returns a bitboard Result, i.e. something like

Code: Select all

  rook_attacks:  (Sq, Occupancy) --> Result

Changing the magic number for a given square Sq does not change the Result that rook_attacks is supposed to return for a given input Occupancy. However, it does change the result of the magic multiplication, that is, it changes what those top M bits are going to be after the magic multiplication (it changes the value of the index). So the actual table of size 2^M or slightly smaller, which maps those index values to the proper Result bitboard, that table does need to change when you change the magic number multiplier. First you need to find a multiplier which doesn't give any "bad" collisions for any of the 2^N occupancy permutations for that square. Then, you need to build the table using that magic multiplier. Some chess engines contain a pre-computed list of magic numbers for each square, but build their actual lookup tables (which map index to Result) each time they are started up.


About changing the square numbering of the board.. it doesn't usually affect magic bitboard stuff, and I'll try and describe why.

If you have a look at this wiki page, it talks about the mapping between square labels (e.g. A1, A2...) and numeric indexes (0, 1, ...) which are also the bit numbers of bits in a bitboard.

With magic bitboards, it usually turns out that typical reflections (H, V, D) of a bitboard of occupancy squares are commutative with whatever function the magic lookup is supposed to compute (e.g. rook_attacks or bishop_attacks, etc.) In other words, if you flip the input bitboard (Occupancy) and mirror the square number similarly) before calling rook_attacks, or flip the output bitboard (Result) after calling rook_attacks, you get the same result either way. This is also true for 90-degree rotations of the board. [Edit: this assumes the Occupancy bitboard only has bits from the set of N interesting bits, with the other 64-N bits all being zeroes... without this the magic multiply doesn't work anyway. This is usually accomplished by having a Mask bitboard for each square in the magic table, ANDing it with a bitboard of all occupied squares. Those Mask bitboards are also nice reflections of each other, i.e. square 17's Mask is a reflection of square 22's Mask across whatever axis divides square 3 and 4 in your square numbering system.]

Why is that useful, you might wonder?
Well, imagine that instead of flipping the contents of the board, you flipped instead the labels of the squares on the board. It would still be commutative, for the same reasons!

I guess what I'm trying to say, is that the symmetry of an 8x8 chess board means that the rook_attacks bitboard for square 10 with a certain occupancy bitboard, should have the same result bitboard, regardless of whether square 10 happens to be C7, or B6, or B3, or C2, or F2, or G3, or G6, or F7 in your square numbering system. As long as you number your squares in a sensible way (either the typical A1, B1, C1... numbering or one of the 7 reflections of it) then the same magic multipliers and lookup tables will work!

[Cheney]

Wiley - thanks! These are great explanations and helped me get over that initial hurdle.

At this time, I have magics implemented and working. Had to get over some odd issues to the point where I thought I had a memory leak only within the IDE debugger - what fun and what a PITA

The issue:
When in the IDE I always had perft failures at certain levels but the compiled exe did not always show the same errors. It looked like the moveDB(square,magicindex) was getting corrupted.

The fix was one of two things:
1 - I was creating new magics each time I started the engine. I changed that to preset generated magics.

2 - I generated magics for #1 with even less bits than what I was doing.

Buggy behavior gone

However, I gained no performance increase over what I was doing for generating moves. I have had other threads here about performance and I am sorry if these following thoughts/questions should go back into that thread, bu here's what I am wondering.

#1 - I am writing in C# w/ .Net 4.0 - Win 7 64-bit. Am I hitting a max based on my .NET/IDE or other system settings? I really don't think so. Another member wrote me that he achieves 50mnps. using C#. I get about 10mns where n (nodes) is actually the leaves (final perft number per depth and not actual pseudo moves played).

#2 - I use MS VS 2010 Professional. Is there something I should be changing in the compiler? I do compile: release, X64, and "optimize code", but there are no where near as many options as what C++ has.

#3 - Maybe I should be declaring my arrays differently? Currently, I do not use "jagged arrays" (ulong[][]) but I use multi-dimensional arrays (ulong[,]). Or, maybe there is an access modifier I should be using to allocate the array differently for faster access?

#4 - Of course, I wonder about the code I use for generating moves. It really should be very simple. Serialize a to/from square, set it, move it, set the board's hash keys, etc. I had an old model, 60Knps, and moved up to 10Mnps - so it was a step in the right direction

Thanks again

[wgarvin]

#3 - Maybe I should be declaring my arrays differently? Currently, I do not use "jagged arrays" (ulong[][]) but I use multi-dimensional arrays (ulong[,]). Or, maybe there is an access modifier I should be using to allocate the array differently for faster access?

I think you should probably be using "jagged arrays", because the table for each square will be a different size. Both because the number M of index bits is different, and because with a "good" magic number, you might not even need the whole 2^M entries (if none of the indexes it actually uses are at the end of that range, you could shorten it a bit). With a 2-dimensional array, you'll be wasting a bunch of space.

[Cheney]

I have migrated to jagged arrays and no performance increase. I am going to leave the magics in there and see if there is something else I can work on which might optimize the code.

Thanks again for these great explanations