Magic...what's that?

[Andrew Wagner]

So, I've been out of the chess programming community mainstream for a year or two now, getting my degree. Now I'm getting back into reading more about it, and everyone's talking about magic bitboards. Could someone give me a summary of what they are and how they work? There seem to be a number of scattered posts that talk about different aspects, but I'm pretty confused overall...

[H.G.Muller]

'magic' refers to a particular kind of table lookup, where all bits in a long (usually 64-bit) word that are relevant for the quantity to be looked up (e.g. the bits giving the occupancy state of a certain ray on a bitboard, for looking up to where a sider can move along this ray, represented as a bitboard of target squares) are collected by a single multiplication.

So usually it goes like this:

Code: Select all

u64 a;       /* bitboard containing scatterered relevant bits */
int index;

index = MAGIC_MULTIPLIER * a >> 52; /* leaves 12 bits */
result = Table[index];


That's really all. Usually the bits one wants to collect depend on the square on which a piece for which moves are calculated is positioned. Each square then needs its own MAGIC_MULTIPLIER, so there will be tables of multipliers indexed by square number, and berhaps also tables of result tables, as
Table[sqr][index].

[Andrew Wagner]

So then...all move generation just becomes static look-ups? And all these magic tables are pre-generated?

[Pradu]

So then...all move generation just becomes static look-ups? And all these magic tables are pre-generated?

Yes.