In the "fancy" magic scheme the rook table contains about 100k 64-bit entries (around 800 kB), but in reality there are only 4900 different attacking bitboards possible for a rook, so there is an important redundancy.
One can easily construct the look-up table of 4900 different attacking bitboards (about 40 kB), and then replace the 100 k rook table entries with a 16-bit index in the look-up table. This leads to a memory footprint of 40 kB + 2 * 100 kB or about 240 kB instead of the initial 800 kB.
The next step is to realize that there are maximum 144 rook attacking bitboards for a given square. This means that one can replace the 16-bit index with an 8-bit index combined with a fixed offset per square. This leads to a memory footprint of 40 kB + 100 kB or about 140 kB instead of the initial 800 kB.
In the "plain" magic scheme the savings would be even more important. The 2048 kB rook table becomes 40 kB + 256 kB or about 300 kB.
The plain magic code shown above would simply become:
Code: Select all
byte mBishopAttacks[64] [512]; // 32 K
byte mRookAttacks [64][4096]; // 256 K
U64 mRookLookup[4900]; // 39 K
U64 mBishopLookup[1428]; // 11 K
struct SMagic {
U64 mask; // to mask relevant squares of both lines (no outer squares)
U64 magic; // magic 64-bit factor
int offset; // offset into lookup table
};
SMagic mBishopTbl[64];
SMagic mRookTbl [64];
U64 bishopAttacks(U64 occ, enumSquare sq) {
occ &= mBishopTbl[sq].mask;
occ *= mBishopTbl[sq].magic;
occ >>= 64-9;
return mBishopLookup[mBishopTbl[sq].offset + mBishopAttack[sq][occ]];
}For the bishop table there are 1428 attacking bitboards, so the 40 kB (fancy) bishop table compacts to a 11 kB look-up table and a 5 kB index table = 16 kB. Probably less useful.
I've tested this compacting scheme successfully in Houdini, but I'm still not sure whether it's really beneficial or not.