I'm just starting to learn about magics, and had a general question:
Do valid magics depend on which direction you define your bitboards (e.g A1 as MSB or LSB), or do they work with any reasonable ordering because of symmetry?
Super Fast 'Looking for magics' 1.0
Moderators: hgm, Rebel, chrisw
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Super Fast 'Looking for magics' 1.0
A given set of valid magics depends on a given board orientation. I think this is related to bit shifting as well as to the fact that any occupancy bitboard involved in the "magic multiplication" depends on a board orientation, too.Robert Pope wrote:I'm just starting to learn about magics, and had a general question:
Do valid magics depend on which direction you define your bitboards (e.g A1 as MSB or LSB), or do they work with any reasonable ordering because of symmetry?
The underlying principle of magic bitboards works for all reasonable board orientations but first you define your square numbering (e.g. A1=0, H8=63) and then you implement your magic bitboard generation code and your code to initialize related data structures. It is certainly possible to write such code in a generic way suitable for all possible board orientations but I never tried that and I don't know whether such code will be easy to understand. Furthermore, all the other code in the engine that accesses bitboards would need to be fully independent of the board orientation as well (which may be the easier part, though).
-
Robert Pope
- Posts: 558
- Joined: Sat Mar 25, 2006 8:27 pm
Re: Super Fast 'Looking for magics' 1.0
Good to know - thanks!Sven Schüle wrote:A given set of valid magics depends on a given board orientation. I think this is related to bit shifting as well as to the fact that any occupancy bitboard involved in the "magic multiplication" depends on a board orientation, too.Robert Pope wrote:I'm just starting to learn about magics, and had a general question:
Do valid magics depend on which direction you define your bitboards (e.g A1 as MSB or LSB), or do they work with any reasonable ordering because of symmetry?
The underlying principle of magic bitboards works for all reasonable board orientations but first you define your square numbering (e.g. A1=0, H8=63) and then you implement your magic bitboard generation code and your code to initialize related data structures. It is certainly possible to write such code in a generic way suitable for all possible board orientations but I never tried that and I don't know whether such code will be easy to understand. Furthermore, all the other code in the engine that accesses bitboards would need to be fully independent of the board orientation as well (which may be the easier part, though).
-
Robert Pope
- Posts: 558
- Joined: Sat Mar 25, 2006 8:27 pm
Re: Super Fast 'Looking for magics' 1.0
Where do the numbers in BitTable come from?
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Super Fast 'Looking for magics' 1.0
What do you mean by "BitTable", to which source code do you refer?Robert Pope wrote:Where do the numbers in BitTable come from?
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Super Fast 'Looking for magics' 1.0
I see, you refer to chessprogramming wiki and to Tord's magic generator code. I don't know where Tord got these numbers from. They are not directly related to magic bitboards but to general bitboard operations (pop_1st_bit).Sven Schüle wrote:What do you mean by "BitTable", to which source code do you refer?Robert Pope wrote:Where do the numbers in BitTable come from?
-
wgarvin
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Super Fast 'Looking for magics' 1.0
I assume this is the table being asked about?
It looks like some sort of De Bruijn sequence for a minimal perfect hash of the 64 bitboard values with exactly 1 bit set.
Some similar examples can be found on this page, and there are many related threads linked at the bottom of that page. (thanks Gerd!)
I don't know where this specific BitTable sequence comes from, but I guess there are many possible sequences that will work and you only need one of them.
(Edit: the expression *bb ^ (*bb - 1) will return a bitboard containing all zeros in the top part and all ones in the bottom part, where "bottom part" means all bits below the lowest set bit in the original *bb. So assuming *bb was not empty to begin with, b can take only 64 different values here, which then get multiplied by something and "folded" onto the 64-entry BitTable by throwing away all but the top 6 bits of the multiplication result. This kind of "multiply and shift" is used to remap a sparse set of input values onto a dense range of table entries; this is basically the same trick as magics use.)
(Edit: my description of the xor expression sucks and might be wrong. I need coffee.. search for "With separated LS1B" on the BitScan page for a better description. Or this one.)
Code: Select all
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];
}Some similar examples can be found on this page, and there are many related threads linked at the bottom of that page. (thanks Gerd!)
I don't know where this specific BitTable sequence comes from, but I guess there are many possible sequences that will work and you only need one of them.
(Edit: the expression *bb ^ (*bb - 1) will return a bitboard containing all zeros in the top part and all ones in the bottom part, where "bottom part" means all bits below the lowest set bit in the original *bb. So assuming *bb was not empty to begin with, b can take only 64 different values here, which then get multiplied by something and "folded" onto the 64-entry BitTable by throwing away all but the top 6 bits of the multiplication result. This kind of "multiply and shift" is used to remap a sparse set of input values onto a dense range of table entries; this is basically the same trick as magics use.)
(Edit: my description of the xor expression sucks and might be wrong. I need coffee.. search for "With separated LS1B" on the BitScan page for a better description. Or this one.)
-
wgarvin
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Super Fast 'Looking for magics' 1.0
It looks basically the same as this folding trick by Matt Taylor, although the multiplication constant and BitTable sequence are not quite the same as what is listed on that page.
Also, in Stockfish you can find this snippet which I suppose is derived from Tord's original code:
Also, in Stockfish you can find this snippet which I suppose is derived from Tord's original code:
Code: Select all
// De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan
const uint64_t DeBruijn_64 = 0x3F79D71B4CB0A89ULL;
const uint32_t DeBruijn_32 = 0x783A9B23;
...
// Matt Taylor's folding for 32 bit systems, extended to 64 bits by Kim Walisch
b ^= (b - 1);
return Is64Bit ? (b * DeBruijn_64) >> 58
: ((unsigned(b) ^ unsigned(b >> 32)) * DeBruijn_32) >> 26;-
vittyvirus
- Posts: 646
- Joined: Wed Jun 18, 2014 2:30 pm
- Full name: Fahad Syed
Re: Super Fast 'Looking for magics' 1.0
Here's the version 1.1 of this program. It takes much, much less time than 1.1 on my poor Android (0.2 sec) and should be instantaneous on a normal PC:
Did I tell you it records the time taken too?
Code: Select all
/* Super Fast 'Looking for Magics' by Tord Romstad * Made 'Super-Fast' by Syed
Fahad, and Matthew Brades * * Description: This program is an improvement
over Tord Romstad's Feeding in Randoms to generate magics. I (Syed Fahad)
started this working on this program when I ran Tord's program on my
andriod and it couldn't generate the numbers. It would always fail. So, I
began to speedup his program. Then, when I was stuck fighting a bug that
freezed the computation somewhere when generating Bishop Magics, I showed
my code to my close friend, Matthew Brades, who fixed the code and and then
further speeded up the code by Hardware Instructions. * * Results: *
BEFORE: This program took 2 seconds for generating all magics on Core Duo
2.8 GHz. * AFTER: This program generates all magics almost instantly w/o
compiler optimization on my 1 GHz Micromax Canvas Doodle 3 with 512 MB of
RAM using GCC on C4Driod. * Huge improvement, you see. * * There are a lot
of possible speed ups still, so... * Version: 1.1 */
#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#define USE_32_BIT_MULTIPLICATIONS
typedef unsigned long long uint64;
const uint64 BitMask[64] = {
0x1ULL, 0x2ULL, 0x4ULL, 0x8ULL, 0x10ULL, 0x20ULL, 0x40ULL, 0x80ULL,
0x100ULL, 0x200ULL, 0x400ULL, 0x800ULL, 0x1000ULL, 0x2000ULL,
0x4000ULL, 0x8000ULL, 0x10000ULL, 0x20000ULL, 0x40000ULL, 0x80000ULL,
0x100000ULL, 0x200000ULL, 0x400000ULL, 0x800000ULL, 0x1000000ULL,
0x2000000ULL, 0x4000000ULL, 0x8000000ULL, 0x10000000ULL, 0x20000000ULL,
0x40000000ULL, 0x80000000ULL, 0x100000000ULL, 0x200000000ULL,
0x400000000ULL, 0x800000000ULL, 0x1000000000ULL, 0x2000000000ULL,
0x4000000000ULL, 0x8000000000ULL, 0x10000000000ULL, 0x20000000000ULL,
0x40000000000ULL, 0x80000000000ULL, 0x100000000000ULL,
0x200000000000ULL, 0x400000000000ULL, 0x800000000000ULL,
0x1000000000000ULL, 0x2000000000000ULL, 0x4000000000000ULL,
0x8000000000000ULL, 0x10000000000000ULL, 0x20000000000000ULL,
0x40000000000000ULL, 0x80000000000000ULL, 0x100000000000000ULL,
0x200000000000000ULL, 0x400000000000000ULL, 0x800000000000000ULL,
0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL,
0x8000000000000000ULL
};
uint64 RMask[64];
uint64 BMask[64];
// #define u1 ((uint64) ((unsigned short) (rand())))
// #define u2 ((uint64) ((unsigned short) (rand())))
// #define u3 ((uint64) ((unsigned short) (rand())))
// #define u4 ((uint64) ((unsigned short) (rand())))
// #define random_uint64() (u1 | (u2 << 16) | (u3 << 32) | (u4 << 48))
uint64 a, b, c, d;
#define ROTATE_L(x, k) ((x << k) | (x >> (64 - k)))
uint64 random_uint64()
{
uint64 e = a - ROTATE_L(b, 7);
a = b ^ ROTATE_L(c, 13);
b = c + ROTATE_L(d, 37);
c = d + e;
return d = e + a;
}
/*
uint64 random_uint64_fewbits() { return random_uint64() & random_uint64() &
random_uint64(); } */
#define random_uint64_fewbits() (random_uint64() & random_uint64() & random_uint64())
int count_1s(uint64 b)
{
// Original
// int r;
// for (r = 0; b; r++, b &= b - 1);
// Non-GCC users
/* unsigned w = (unsigned)b >> 32, v = (unsigned)b; v -= (v >> 1) &
0x55555555; // 0-2 in 2 bits w -= (w >> 1) & 0x55555555; v = ((v >> 2)
& 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits w = ((w >> 2) &
0x33333333) + (w & 0x33333333); v = ((v >> 4) + v + (w >> 4) + w) &
0x0F0F0F0F; return (int)((v * 0x01010101) >> 24); */
return __builtin_popcountll(b);
}
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]; */
int lsb = __builtin_ctz(*bb);
*bb &= *bb - 1;
return lsb;
}
uint64 index_to_uint64(int index, int bits, uint64 m)
{
int i, j, k;
uint64 result = 0ULL;
for (i = 0; i < bits; i++)
{
j = pop_1st_bit(&m);
if ((index & (BitMask[i])) != 0)
result |= (BitMask[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 |= (BitMask[(fl + r * 8)]); for (r = rk - 1; r
>= 1; r--) result |= (BitMask[(fl + r * 8)]); for (f = fl + 1; f <= 6;
f++) result |= (BitMask[(f + rk * 8)]); for (f = fl - 1; f >= 1; f--)
result |= (BitMask[(f + rk * 8)]); return result; */
return RMask[sq];
}
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 |= (BitMask[(f + r *
8)]); for (r = rk + 1, f = fl - 1; r <= 6 && f >= 1; r++, f--) result
|= (BitMask[(f + r * 8)]); for (r = rk - 1, f = fl + 1; r >= 1 && f <=
6; r--, f++) result |= (BitMask[(f + r * 8)]); for (r = rk - 1, f = fl
- 1; r >= 1 && f >= 1; r--, f--) result |= (BitMask[(f + r * 8)]);
return result; */
return BMask[sq];
}
uint64 rmask_gen(int sq)
{
uint64 result = 0ULL;
int rk = sq / 8, fl = sq % 8, r, f;
for (r = rk + 1; r <= 6; r++)
result |= (BitMask[(fl + r * 8)]);
for (r = rk - 1; r >= 1; r--)
result |= (BitMask[(fl + r * 8)]);
for (f = fl + 1; f <= 6; f++)
result |= (BitMask[(f + rk * 8)]);
for (f = fl - 1; f >= 1; f--)
result |= (BitMask[(f + rk * 8)]);
return result;
}
uint64 bmask_gen(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 |= (BitMask[(f + r * 8)]);
for (r = rk + 1, f = fl - 1; r <= 6 && f >= 1; r++, f--)
result |= (BitMask[(f + r * 8)]);
for (r = rk - 1, f = fl + 1; r >= 1 && f <= 6; r--, f++)
result |= (BitMask[(f + r * 8)]);
for (r = rk - 1, f = fl - 1; r >= 1 && f >= 1; r--, f--)
result |= (BitMask[(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 |= (BitMask[(fl + r * 8)]);
if ((block & (BitMask[(fl + r * 8)])) != 0)
break;
}
for (r = rk - 1; r >= 0; r--)
{
result |= (BitMask[(fl + r * 8)]);
if ((block & (BitMask[(fl + r * 8)])) != 0)
break;
}
for (f = fl + 1; f <= 7; f++)
{
result |= (BitMask[(fl + r * 8)]);
if ((block & (BitMask[(fl + r * 8)])) != 0)
break;
}
for (f = fl - 1; f >= 0; f--)
{
result |= (BitMask[(fl + r * 8)]);
if ((block & (BitMask[(fl + r * 8)])) != 0)
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 |= (BitMask[(f + r * 8)]);
if ((block & (BitMask[(f + r * 8)])) != 0)
break;
}
for (r = rk + 1, f = fl - 1; r <= 7 && f >= 0; r++, f--)
{
result |= (BitMask[(f + r * 8)]);
if ((block & (BitMask[(f + r * 8)])) != 0)
break;
}
for (r = rk - 1, f = fl + 1; r >= 0 && f <= 7; r--, f++)
{
result |= (BitMask[(f + r * 8)]);
if ((block & (BitMask[(f + r * 8)])) != 0)
break;
}
for (r = rk - 1, f = fl - 1; r >= 0 && f >= 0; r--, f--)
{
result |= (BitMask[(f + r * 8)]);
if ((block & (BitMask[(f + r * 8)])) != 0)
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, mbits, fail;
int c = 0;
mask = bishop ? bmask(sq) : rmask(sq);
n = count_1s(mask);
for (i = 0; i < (BitMask[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 == 0) && i < (BitMask[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 == 0)
return magic;
}
printf("***Failed***\n");
return 0ULL;
}
const 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
};
const 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()
{
a = 0xF1EA5EED, b = c = d = 0xD4E12C77;
int square;
uint64 magic;
uint64 RookMagics[64];
uint64 BishMagics[64];
for (square = 0; square < 64; ++square)
{
RMask[square] = rmask_gen(square);
BMask[square] = bmask_gen(square);
}
double startTime, endTime;
startTime = clock();
for (square = 0; square < 64; square++)
{
RookMagics[square] = find_magic(square, RBits[square], 0);
BishMagics[square] = find_magic(square, BBits[square], 1);
}
endTime = clock();
printf("const uint64 RMagic[64] = {\n");
for (square = 0; square < 64; square++)
printf(" 0x%llxULL,\n", RookMagics[square]);
printf("};\n\n");
printf("const uint64 BMagic[64] = {\n");
for (square = 0; square < 64; square++)
printf(" 0x%llxULL,\n", BishMagics[square]);
printf("};\n\n");
printf("Took %f seconds", (endTime - startTime) / (double)CLOCKS_PER_SEC);
// fflush(stdout);
return 0;
}