In case of 32 bits I am able to build up all the bishop and rook magics in less then 0.3 secs !! And on my very slow Intel Core 2 at 1,5 Ghz.
The new trick is to use a sequence of PRNG optimized for each rank, so that all the squares of a given rank use a PRNG with an ad-hoc parameter optimally chosen for that rank. This trick, that I have called "magic booster" allow to greatly reduce the time to build up the magics using the "Feeding in Randoms" method:
http://chessprogramming.wikispaces.com/ ... for+Magics
Anyhow here is the code:
Code: Select all
Bitboard submask(Bitboard mask, int key) {
Bitboard subMask = 0;
int bitNum = -1;
// Extract an unique submask out of a mask according to the given key
for (Square s = SQ_A1; s <= SQ_H8; s++)
if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum)))
set_bit(&subMask, s);
return subMask;
}
Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], Bitboard excluded) {
Bitboard attacks = 0;
for (int i = 0; i < 4; i++)
{
Square s = sq + deltas[i];
while ( square_is_ok(s)
&& square_distance(s, s - deltas[i]) == 1
&& !bit_is_set(excluded, s))
{
set_bit(&attacks, s);
if (bit_is_set(occupied, s))
break;
s += deltas[i];
}
}
return attacks;
}
template<bool Is64>
Bitboard pick_magic(Bitboard mask, RKISS& rk, int booster) {
Bitboard magic;
int lsb;
if (!Is64)
lsb = first_1(mask);
// Advance PRNG state of a quantity known to be the optimal to
// quickly retrieve all the magics.
for (int i = 0; i < booster; i++)
rk.rand<Bitboard>();
while (true)
{
magic = rk.rand<Bitboard>() & rk.rand<Bitboard>();
magic &= Is64 ? rk.rand<Bitboard>() : (rk.rand<Bitboard>() | rk.rand<Bitboard>());
if ( BitCount8Bit[(mask * magic) >> 56] >= 6
&& (Is64 || BitCount8Bit[(lsb * magic) >> 56]))
return magic;
}
}
void do_magics(Bitboard magic[], Bitboard* attack[], Bitboard attTabl[],
Bitboard mask[], int shift[], Square deltas[]) {
const int MagicBoosters32[] = { 43, 53, 76, 17, 51, 65, 55, 23 };
const int MagicBoosters64[] = { 26, 21, 21, 32, 31, 9, 5, 11 };
RKISS rk;
Bitboard occupancy[4096], proofs[4096], excluded;
int key, maxKey, index, booster, offset = 0;
for (Square s = SQ_A1; s <= SQ_H8; s++)
{
excluded = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s));
attack[s] = &attTabl[offset];
mask[s] = sliding_attacks(s, EmptyBoardBB, deltas, excluded);
shift[s] = (CpuIs64Bit ? 64 : 32) - count_1s<CNT64>(mask[s]);
maxKey = 1 << count_1s<CNT32>(mask[s]);
booster = CpuIs64Bit ? MagicBoosters64[square_rank(s)] : MagicBoosters32[square_rank(s)];
// First compute occupancy and attacks for square 's'
for (key = 0; key < maxKey; key++)
{
occupancy[key] = submask(mask[s], key);
proofs[key] = sliding_attacks(s, occupancy[key], deltas, EmptyBoardBB);
}
// Then find a possible magic and corresponding attacks
do {
magic[s] = pick_magic<CpuIs64Bit>(mask[s], rk, booster);
memset(attack[s], 0, maxKey * sizeof(Bitboard));
for (key = 0; key < maxKey; key++)
{
index = CpuIs64Bit ? unsigned((occupancy[key] * magic[s]) >> shift[s])
: unsigned(occupancy[key] * magic[s] ^ (occupancy[key] >> 32) * (magic[s] >> 32)) >> shift[s];
if (!attack[s][index])
attack[s][index] = proofs[key];
else if (attack[s][index] != proofs[key])
break;
}
} while (key != maxKey);
offset += maxKey;
}
}
Code: Select all
Bitboard RMask[64];
Bitboard RMult[64];
Bitboard* RAttacks[64];
int RShift[64];
Bitboard BMask[64];
Bitboard BMult[64];
Bitboard* BAttacks[64];
int BShift[64];
Bitboard RAttacksTable[0x19000];
Bitboard BAttacksTable[0x1480];
void find_magics() {
Square RDeltas[] = { DELTA_N, DELTA_E, DELTA_S, DELTA_W };
Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
do_magics(BMult, BAttacks, BAttacksTable, BMask, BShift, BDeltas);
do_magics(RMult, RAttacks, RAttacksTable, RMask, RShift, RDeltas);
}
And finally this is how magics bitboards are supposed to be used in both 32 and 64 bits cases:
Code: Select all
/// Functions for computing sliding attack bitboards. rook_attacks_bb(),
/// bishop_attacks_bb() and queen_attacks_bb() all take a square and a
/// bitboard of occupied squares as input, and return a bitboard representing
/// all squares attacked by a rook, bishop or queen on the given square.
#if defined(IS_64BIT)
inline Bitboard rook_attacks_bb(Square s, Bitboard occ) {
return RAttacks[s][((occ & RMask[s]) * RMult[s]) >> RShift[s]];
}
inline Bitboard bishop_attacks_bb(Square s, Bitboard occ) {
return BAttacks[s][((occ & BMask[s]) * BMult[s]) >> BShift[s]];
}
#else // if !defined(IS_64BIT)
inline Bitboard rook_attacks_bb(Square s, Bitboard occ) {
Bitboard b = occ & RMask[s];
return RAttacks[s]
[unsigned(int(b) * int(RMult[s]) ^ int(b >> 32) * int(RMult[s] >> 32)) >> RShift[s]];
}
inline Bitboard bishop_attacks_bb(Square s, Bitboard occ) {
Bitboard b = occ & BMask[s];
return BAttacks[s]
[unsigned(int(b) * int(BMult[s]) ^ int(b >> 32) * int(BMult[s] >> 32)) >> BShift[s]];
}
#endif
) since it is just an optimized sequence of randoms to get a random magic quicker than usual..