Home * Board Representation * Bitboards * Sliding Piece Attacks * Magic Bitboards * Looking for Magics

Magic Bitboards is probably the fastest approach to generate sliding piece attacks on recent architectures with fast 64-bit multiplication. It performs a mask/mul/shift->lookup to gain all the attacked squares of a bishop or rook.

Trial and Error

So far the only approach to find 64-bit magic factors is trial and error. One has the idea, how many bits are needed for a perfect hashing - and about constrains of least and most significant one-bit inside the magic factor.
                                        any consecutive
relevant occupancy                      combination of
bishop b1, 5 bits                       the masked bits
. . . . . . . .     . . . . . . . .     . . .[C D E F G]
. . . . . . . .     . 1 . . . . . .     . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . . . . . . . .
. . . . E . . .  *  . 1 . . . . . .  =  . . garbage . .    >> (64- 5)
. . . D . . . .     . 1 . . . . . .     . . . . . . . .
. . C . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
bishop d4, 9 bits                       the masked bits
. . . . . . . .     . . . . . . . .     2 4 5 B C E F G]
. . . . . . G .     . . .some . . .     . . . . . . .[1
. 5 . . . F . .     . . . . . . . .     . . . . . . . .
. . 4 . E . . .     . . .magic. . .     . . . . . . . .
. . . . . . . .  *  . . . . . . . .  =  . . garbage . .    >> (64- 9)
. . C . 2 . . .     . . .bits . . .     . . . . . . . .
. B . . . 1 . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        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 . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
rook a1, 12 bits                        the masked bits
. . . . . . . .     . . . . . . . .     5 6 B C D E F G]
6 . . . . . . .     . . .some . . .     . . . .[1 2 3 4
5 . . . . . . .     . . . . . . . .     . . . . . . . .
4 . . . . . . .     . . .magic. . .     . . . . . . . .
3 . . . . . . .  *  . . . . . . . .  =  . . garbage . .    >> (64-12)
2 . . . . . . .     . . .bits . . .     . . . . . . . .
1 . . . . . . .     . . . . . . . .     . . . . . . . .
. B C D E F G .     . . . . . . . .     . . . . . . . .

Feeding in Randoms

Tord Romstad's proposal to find magics [1] :
Just trying out random numbers with a low number of nonzero bits until you find a number which works is by far the fastest and easiest way to generate the magic numbers, in my experience. On my Core Duo 2.8 GHz, it takes less than a second to find magic numbers for rooks and bishops for all squares (and I have made no attempt to optimize the code, it should be easy to make it much faster). Here is the source code:
#include <stdio.h>
#include <stdlib.h>
 
#define USE_32_BIT_MULTIPLICATIONS
 
typedef unsigned long long uint64;
 
uint64 random_uint64() {
  uint64 u1, u2, u3, u4;
  u1 = (uint64)(random()) & 0xFFFF; u2 = (uint64)(random()) & 0xFFFF;
  u3 = (uint64)(random()) & 0xFFFF; u4 = (uint64)(random()) & 0xFFFF;
  return u1 | (u2 << 16) | (u3 << 32) | (u4 << 48);
}
 
uint64 random_uint64_fewbits() {
  return random_uint64() & random_uint64() & random_uint64();
}
 
int count_1s(uint64 b) {
  int r;
  for(r = 0; b; r++, b &= b - 1);
  return r;
}
 
const int BitTable[64] = {
  63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
  51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
  26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
  58, 20, 37, 17, 36, 8
};
 
int pop_1st_bit(uint64 *bb) {
  uint64 b = *bb ^ (*bb - 1);
  unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
  *bb &= (*bb - 1);
  return BitTable[(fold * 0x783a9b23) >> 26];
}
 
uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for(i = 0; i < bits; i++) {
    j = pop_1st_bit(&m);
    if(index & (1 << i)) result |= (1ULL << j);
  }
  return result;
}
 
uint64 rmask(int sq) {
  uint64 result = 0ULL;
  int rk = sq/8, fl = sq%8, r, f;
  for(r = rk+1; r <= 6; r++) result |= (1ULL << (fl + r*8));
  for(r = rk-1; r >= 1; r--) result |= (1ULL << (fl + r*8));
  for(f = fl+1; f <= 6; f++) result |= (1ULL << (f + rk*8));
  for(f = fl-1; f >= 1; f--) result |= (1ULL << (f + rk*8));
  return result;
}
 
uint64 bmask(int sq) {
  uint64 result = 0ULL;
  int rk = sq/8, fl = sq%8, r, f;
  for(r=rk+1, f=fl+1; r<=6 && f<=6; r++, f++) result |= (1ULL << (f + r*8));
  for(r=rk+1, f=fl-1; r<=6 && f>=1; r++, f--) result |= (1ULL << (f + r*8));
  for(r=rk-1, f=fl+1; r>=1 && f<=6; r--, f++) result |= (1ULL << (f + r*8));
  for(r=rk-1, f=fl-1; r>=1 && f>=1; r--, f--) result |= (1ULL << (f + r*8));
  return result;
}
 
uint64 ratt(int sq, uint64 block) {
  uint64 result = 0ULL;
  int rk = sq/8, fl = sq%8, r, f;
  for(r = rk+1; r <= 7; r++) {
    result |= (1ULL << (fl + r*8));
    if(block & (1ULL << (fl + r*8))) break;
  }
  for(r = rk-1; r >= 0; r--) {
    result |= (1ULL << (fl + r*8));
    if(block & (1ULL << (fl + r*8))) break;
  }
  for(f = fl+1; f <= 7; f++) {
    result |= (1ULL << (f + rk*8));
    if(block & (1ULL << (f + rk*8))) break;
  }
  for(f = fl-1; f >= 0; f--) {
    result |= (1ULL << (f + rk*8));
    if(block & (1ULL << (f + rk*8))) break;
  }
  return result;
}
 
uint64 batt(int sq, uint64 block) {
  uint64 result = 0ULL;
  int rk = sq/8, fl = sq%8, r, f;
  for(r = rk+1, f = fl+1; r <= 7 && f <= 7; r++, f++) {
    result |= (1ULL << (f + r*8));
    if(block & (1ULL << (f + r * 8))) break;
  }
  for(r = rk+1, f = fl-1; r <= 7 && f >= 0; r++, f--) {
    result |= (1ULL << (f + r*8));
    if(block & (1ULL << (f + r * 8))) break;
  }
  for(r = rk-1, f = fl+1; r >= 0 && f <= 7; r--, f++) {
    result |= (1ULL << (f + r*8));
    if(block & (1ULL << (f + r * 8))) break;
  }
  for(r = rk-1, f = fl-1; r >= 0 && f >= 0; r--, f--) {
    result |= (1ULL << (f + r*8));
    if(block & (1ULL << (f + r * 8))) break;
  }
  return result;
}
 
 
int transform(uint64 b, uint64 magic, int bits) {
#if defined(USE_32_BIT_MULTIPLICATIONS)
  return
    (unsigned)((int)b*(int)magic ^ (int)(b>>32)*(int)(magic>>32)) >> (32-bits);
#else
  return (int)((b * magic) >> (64 - bits));
#endif
}
 
uint64 find_magic(int sq, int m, int bishop) {
  uint64 mask, b[4096], a[4096], used[4096], magic;
  int i, j, k, n, fail;
 
  mask = bishop? bmask(sq) : rmask(sq);
  n = count_1s(mask);
 
  for(i = 0; i < (1 << n); i++) {
    b[i] = index_to_uint64(i, n, mask);
    a[i] = bishop? batt(sq, b[i]) : ratt(sq, b[i]);
  }
  for(k = 0; k < 100000000; k++) {
    magic = random_uint64_fewbits();
    if(count_1s((mask * magic) & 0xFF00000000000000ULL) < 6) continue;
    for(i = 0; i < 4096; i++) used[i] = 0ULL;
    for(i = 0, fail = 0; !fail && i < (1 << n); i++) {
      j = transform(b[i], magic, m);
      if(used[j] == 0ULL) used[j] = a[i];
      else if(used[j] != a[i]) fail = 1;
    }
    if(!fail) return magic;
  }
  printf("***Failed***\n");
  return 0ULL;
}
 
int RBits[64] = {
  12, 11, 11, 11, 11, 11, 11, 12,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  12, 11, 11, 11, 11, 11, 11, 12
};
 
int BBits[64] = {
  6, 5, 5, 5, 5, 5, 5, 6,
  5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 5, 5, 5, 5, 5, 5, 6
};
 
int main() {
  int square;
 
  printf("const uint64 RMagic[64] = {\n");
  for(square = 0; square < 64; square++)
    printf("  0x%llxULL,\n", find_magic(square, RBits[square], 0));
  printf("};\n\n");
 
  printf("const uint64 BMagic[64] = {\n");
  for(square = 0; square < 64; square++)
    printf("  0x%llxULL,\n", find_magic(square, BBits[square], 1));
  printf("};\n\n");
 
  return 0;
}

Fixed Shift Magics

Another application is Looking for overlapping Magics for a fixed shift approach, as recently proposed by Volker Annuss [2] .

See also


Forum Posts


External Links


References

  1. ^ Re: Magic Move Generation by Tord Romstad, CCC, February 20, 2008
  2. ^ Fixed shift magics with 800KB lookup table by Volker Annuss, Winboard Forum, September, 05, 2010

What links here