http://chessprogramming.wikispaces.com/Magic+Bitboards
I implemented both methods in my infant engine Spandrel and measured the single-threaded performance on Core 2 Duo and Core i5.
Code: Select all
Speed advantage of fancy magic over plain magic
perft search
Core 2 2.6% 1.3%
Core i5 1.6% 0.7%
A programmer implementing fancy magic in his chess engine seems to be faced with unappealing choices: either borrowing/stealing complicated initialisation code (and perhaps the magic multipliers and other subsidiary magic numbers) from someone else's source, or working absurdly hard. By contrast, plain magic can be initialised straightforwardly (shown here for bishop attacks).
Code: Select all
const BitBoard gBMagicNum[64] = { 0xWhateverULL, ... };
BitBoard gBMagicMask[64];
int gBMagicShift[64];
BitBoard gBMagicAttacks[64][512];
BitBoard BAttacks_Init( int sq, BitBoard occupied ) {
...
return attacks;
}
void InitBMagicAttacksForSquare( int sq ) {
int index; // 0--511
BitBoard subset = 0ULL;
// iterate over all subsets of gBMagicMask[sq]
// chessprogramming.wikispaces.com/Traversing+Subsets+of+a+Set
do {
index = (subset * gBMagicNum[sq]) >> gBMagicShift[sq];
gBMagicAttacks[sq][index] = BAttacks_Init( sq, subset );
subset = (subset - gBMagicMask[sq]) & gBMagicMask[sq];
} while ( subset );
}
/*
gBMagicNum[] is already initialised.
Initialise gBMagicMask[], gBMagicShift[] and gBMagicAttacks[][].
*/
void InitBMagicAttacks() {
for ( int j = 0; j < 64; j++ ) {
// each gBMagicMask[] is 4 diagonal rays that stop short of the edge
gBMagicMask[j] = BAttacks_Init( j, 0ULL ) & gNonEdgeSquares;
gBMagicShift[j] = 64 - PopCount( gBMagicMask[j] );
InitBMagicAttacksForSquare( j );
}
}
Robert P.