You can actually catch collisions with extra 64 bits stored in TT entries. This will be another hashkey computed using a different hashing formula.
The chances of two positions colliding twice when using two different hashing formulas is almost non-existent.
I wonder if using two 64-bit zobrist hashkeys is similar to using one 128-zobrist hashkey ...
I wrote the following piece of code for testing the number of collisions per million for different methods. It was very effective at catching weak hashing formulas. I recall someone at the time suggested using attack tables as hashkeys, guess how that turned out ...
Code: Select all
#include <stdio.h>
#include <time.h>
//U64
#ifdef _MSC_VER
typedef unsigned __int64 U64;
typedef unsigned int U32;
# define U64(x) (x##ui64)
# define FMTU64 "0x%016I64x"
#else
# include <inttypes.h>
typedef uint64_t U64;
typedef uint32_t U32;
# define U64(x) (x##ull)
# define FMTU64 "0x%016llx"
#endif
#define unitBB(x) ((U64)1 << (x))
/******************************************
* PRNG
*****************************************/
#define MY_RAND_MAX 0x7fff
struct PRNG {
U32 randn;
void seed(int sd) {
randn = sd;
}
U32 rand() {
randn *= 214013;
randn += 2531011;
return ((randn >> 16) & MY_RAND_MAX);
}
U64 rand64() {
return((U64)rand()) ^
((U64)rand() << 15) ^ ((U64)rand() << 30) ^
((U64)rand() << 45) ^ ((U64)rand() << 60);
}
};
/***************************************************************
Pradu's magic tables
****************************************************************/
extern const U64 knight_magics[64];
extern const U64 king_magics[64];
extern const U64 pawn_magics[2][64];
extern const U64 magicmoves_r_magics[64];
extern const U64 magicmoves_r_mask[64];
extern const U64 magicmoves_b_magics[64];
extern const U64 magicmoves_b_mask[64];
extern const unsigned int magicmoves_b_shift[64];
extern const unsigned int magicmoves_r_shift[64];
extern const U64* magicmoves_b_indices[64];
extern const U64* magicmoves_r_indices[64];
#define king_attacks(sq) (king_magics[sq])
#define knight_attacks(sq) (knight_magics[sq])
#define pawn_attacks(sq,col) (pawn_magics[col][sq])
#define bishop_attacks(sq,occ) (*(magicmoves_b_indices[sq]+(((occ&magicmoves_b_mask[sq])*magicmoves_b_magics[sq])>>magicmoves_b_shift[sq])))
#define rook_attacks(sq,occ) (*(magicmoves_r_indices[sq]+(((occ&magicmoves_r_mask[sq])*magicmoves_r_magics[sq])>>magicmoves_r_shift[sq])))
#define queen_attacks(sq,occ) (bishop_attacks(sq,occ) | rook_attacks(sq,occ))
void initmagicmoves(void);
/***********************************************
* Hash table
************************************************/
//TT entry
struct ENTRY {
U64 key1;
U64 key2;
U32 stores;
};
//pieces
int piece[32];
int square[32];
int npieces;
U64 secondary_hkey[14][64];
U64 cp_key[14];
U64 sq_key[64];
ENTRY* table;
//gusev
U64 gusev(int cp, int sq) {
int pc = cp / 2;
int co = cp % 2;
switch(pc) {
case 0: return king_attacks(sq); break;
case 1: return knight_attacks(sq); break;
case 2: return bishop_attacks(sq,0); break;
case 3: return rook_attacks(sq,0); break;
case 4: return queen_attacks(sq,0); break;
case 5: return pawn_attacks(sq,co); break;
}
return 0;
}
//put your hash function here
U64 hashf(int cp,int sq) {
#define T 2
#if T == 0 //ROT
const U64 C1 = U64(0xeadf018b615d3be8);
const U64 C2 = U64(0x109951162821a737);
U64 h = C1;
h = (h << sq) ^ (h >> (64 - sq));
h += C2;
h = (h << cp) ^ (h >> (64 - cp));
return h;
#elif T == 1 //FNV
const U64 FNV = U64(1099511628211);
U64 h = U64(19282138887198);
h = h * FNV;
h = h ^ cp;
h = h * FNV;
h = h ^ sq;
return h;
#elif T == 2 //FNV-1a
const U64 FNV = U64(1099511628211);
U64 h = U64(19282138887198);
h = h ^ cp;
h = h * FNV;
h = h ^ sq;
h = h * FNV;
return h;
#elif T == 3 //MUL
return cp_key[cp] * sq_key[sq];
#elif T == 4 //ADD
return cp_key[cp] + sq_key[sq];
#elif T == 5 //AND
return cp_key[cp] & sq_key[sq];
#elif T == 6 //OR
return cp_key[cp] | sq_key[sq];
#elif T == 7 //GUS
return gusev(cp,sq);
#endif
}
//primary key
U64 get_key1() {
U64 key = 0;
for(int i = 0;i < npieces;i++)
key ^= hashf(piece[i],square[i]);
return key;
}
//secondary key to compare to
U64 get_key2() {
U64 key = 0;
for(int i = 0;i < npieces;i++)
key ^= secondary_hkey[piece[i]][square[i]];
return key;
}
int main() {
const int TT_SIZE = 1 << 16;
const unsigned int TT_MASK = TT_SIZE - 1;
const int PIECES_LIMIT = 32; //reduce this for faster tests ( endgame positions ).
const U64 KEY_MASK = U64(-1);//((U64)1 << 28) - 1;
//magics
initmagicmoves();
//table
table = new ENTRY[1 << 16];
//secondary hashkeys
PRNG prng;
prng.seed(0);
for(int i = 0;i < 14;i++)
for(int j = 0;j < 64;j++)
secondary_hkey[i][j] = prng.rand64();
for(int i = 0;i < 14;i++)
cp_key[i] = prng.rand64();
for(int i = 0;i < 64;i++)
sq_key[i] = prng.rand64();
//test for collisions of primary hash keys
U64 all,key1,key2,bb;
U32 index;
U32 collisions = 0;
int sq,millions = 0,j = 0;
ENTRY* pentry;
clock_t start,end;
start = clock();
while(true) {
j++;
//set up random position
all = 0;
npieces = (prng.rand() % PIECES_LIMIT) + 1;
for(int i = 0;i < npieces;i++) {
piece[i] = (prng.rand() % 12);
do {
sq = (prng.rand() % 64);
bb = unitBB(sq);
} while((all & bb));
square[i] = sq;
all |= bb;
}
//get the two keys & store them
key1 = get_key1() & KEY_MASK;
key2 = get_key2() & KEY_MASK;
index = U32(key1 & TT_MASK);
pentry = &table[index];
if(pentry->key1 == key1) {
if(pentry->key2 != key2) {
collisions++;
}
} else {
pentry->key1 = key1;
pentry->key2 = key2;
pentry->stores++;
}
//display stat
if((j % 1000000) == 0) {
end = clock();
int time = (end - start) / 1000;
printf("coll %d/%d time %ds Rate = %.2f coll/sec or %.2f coll/mil.\n",
collisions,j,time,collisions / double(time),collisions / double(millions));
millions++;
if(millions == 1000) break;
}
}
/*save distribution*/
FILE* log = fopen("test.txt","w");
for(int i = 0;i < TT_SIZE;i++) {
fprintf(log,"%d\n",table[i].stores);
}
fclose(log);
/*end*/
return 0;
}
//*/
/**********************************************************************
*Copyright (C) 2007 Pradyumna Kannan.
*
This code is directly copied from Pradu's sample code with no
modifications whatsoever. Thanks Pradu.
************************************************************************/
const unsigned int magicmoves_r_shift[64] = {
52, 53, 53, 53, 53, 53, 53, 52,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 53, 53, 53, 53, 53
};
const U64 magicmoves_r_magics[64] = {
U64(0x0080001020400080), U64(0x0040001000200040), U64(0x0080081000200080), U64(0x0080040800100080),
U64(0x0080020400080080), U64(0x0080010200040080), U64(0x0080008001000200), U64(0x0080002040800100),
U64(0x0000800020400080), U64(0x0000400020005000), U64(0x0000801000200080), U64(0x0000800800100080),
U64(0x0000800400080080), U64(0x0000800200040080), U64(0x0000800100020080), U64(0x0000800040800100),
U64(0x0000208000400080), U64(0x0000404000201000), U64(0x0000808010002000), U64(0x0000808008001000),
U64(0x0000808004000800), U64(0x0000808002000400), U64(0x0000010100020004), U64(0x0000020000408104),
U64(0x0000208080004000), U64(0x0000200040005000), U64(0x0000100080200080), U64(0x0000080080100080),
U64(0x0000040080080080), U64(0x0000020080040080), U64(0x0000010080800200), U64(0x0000800080004100),
U64(0x0000204000800080), U64(0x0000200040401000), U64(0x0000100080802000), U64(0x0000080080801000),
U64(0x0000040080800800), U64(0x0000020080800400), U64(0x0000020001010004), U64(0x0000800040800100),
U64(0x0000204000808000), U64(0x0000200040008080), U64(0x0000100020008080), U64(0x0000080010008080),
U64(0x0000040008008080), U64(0x0000020004008080), U64(0x0000010002008080), U64(0x0000004081020004),
U64(0x0000204000800080), U64(0x0000200040008080), U64(0x0000100020008080), U64(0x0000080010008080),
U64(0x0000040008008080), U64(0x0000020004008080), U64(0x0000800100020080), U64(0x0000800041000080),
U64(0x00FFFCDDFCED714A), U64(0x007FFCDDFCED714A), U64(0x003FFFCDFFD88096), U64(0x0000040810002101),
U64(0x0001000204080011), U64(0x0001000204000801), U64(0x0001000082000401), U64(0x0001FFFAABFAD1A2)
};
const U64 magicmoves_r_mask[64] = {
U64(0x000101010101017E), U64(0x000202020202027C), U64(0x000404040404047A), U64(0x0008080808080876),
U64(0x001010101010106E), U64(0x002020202020205E), U64(0x004040404040403E), U64(0x008080808080807E),
U64(0x0001010101017E00), U64(0x0002020202027C00), U64(0x0004040404047A00), U64(0x0008080808087600),
U64(0x0010101010106E00), U64(0x0020202020205E00), U64(0x0040404040403E00), U64(0x0080808080807E00),
U64(0x00010101017E0100), U64(0x00020202027C0200), U64(0x00040404047A0400), U64(0x0008080808760800),
U64(0x00101010106E1000), U64(0x00202020205E2000), U64(0x00404040403E4000), U64(0x00808080807E8000),
U64(0x000101017E010100), U64(0x000202027C020200), U64(0x000404047A040400), U64(0x0008080876080800),
U64(0x001010106E101000), U64(0x002020205E202000), U64(0x004040403E404000), U64(0x008080807E808000),
U64(0x0001017E01010100), U64(0x0002027C02020200), U64(0x0004047A04040400), U64(0x0008087608080800),
U64(0x0010106E10101000), U64(0x0020205E20202000), U64(0x0040403E40404000), U64(0x0080807E80808000),
U64(0x00017E0101010100), U64(0x00027C0202020200), U64(0x00047A0404040400), U64(0x0008760808080800),
U64(0x00106E1010101000), U64(0x00205E2020202000), U64(0x00403E4040404000), U64(0x00807E8080808000),
U64(0x007E010101010100), U64(0x007C020202020200), U64(0x007A040404040400), U64(0x0076080808080800),
U64(0x006E101010101000), U64(0x005E202020202000), U64(0x003E404040404000), U64(0x007E808080808000),
U64(0x7E01010101010100), U64(0x7C02020202020200), U64(0x7A04040404040400), U64(0x7608080808080800),
U64(0x6E10101010101000), U64(0x5E20202020202000), U64(0x3E40404040404000), U64(0x7E80808080808000)
};
const unsigned int magicmoves_b_shift[64] = {
58, 59, 59, 59, 59, 59, 59, 58,
59, 59, 59, 59, 59, 59, 59, 59,
59, 59, 57, 57, 57, 57, 59, 59,
59, 59, 57, 55, 55, 57, 59, 59,
59, 59, 57, 55, 55, 57, 59, 59,
59, 59, 57, 57, 57, 57, 59, 59,
59, 59, 59, 59, 59, 59, 59, 59,
58, 59, 59, 59, 59, 59, 59, 58
};
const U64 magicmoves_b_magics[64] = {
U64(0x0002020202020200), U64(0x0002020202020000), U64(0x0004010202000000), U64(0x0004040080000000),
U64(0x0001104000000000), U64(0x0000821040000000), U64(0x0000410410400000), U64(0x0000104104104000),
U64(0x0000040404040400), U64(0x0000020202020200), U64(0x0000040102020000), U64(0x0000040400800000),
U64(0x0000011040000000), U64(0x0000008210400000), U64(0x0000004104104000), U64(0x0000002082082000),
U64(0x0004000808080800), U64(0x0002000404040400), U64(0x0001000202020200), U64(0x0000800802004000),
U64(0x0000800400A00000), U64(0x0000200100884000), U64(0x0000400082082000), U64(0x0000200041041000),
U64(0x0002080010101000), U64(0x0001040008080800), U64(0x0000208004010400), U64(0x0000404004010200),
U64(0x0000840000802000), U64(0x0000404002011000), U64(0x0000808001041000), U64(0x0000404000820800),
U64(0x0001041000202000), U64(0x0000820800101000), U64(0x0000104400080800), U64(0x0000020080080080),
U64(0x0000404040040100), U64(0x0000808100020100), U64(0x0001010100020800), U64(0x0000808080010400),
U64(0x0000820820004000), U64(0x0000410410002000), U64(0x0000082088001000), U64(0x0000002011000800),
U64(0x0000080100400400), U64(0x0001010101000200), U64(0x0002020202000400), U64(0x0001010101000200),
U64(0x0000410410400000), U64(0x0000208208200000), U64(0x0000002084100000), U64(0x0000000020880000),
U64(0x0000001002020000), U64(0x0000040408020000), U64(0x0004040404040000), U64(0x0002020202020000),
U64(0x0000104104104000), U64(0x0000002082082000), U64(0x0000000020841000), U64(0x0000000000208800),
U64(0x0000000010020200), U64(0x0000000404080200), U64(0x0000040404040400), U64(0x0002020202020200)
};
const U64 magicmoves_b_mask[64] = {
U64(0x0040201008040200), U64(0x0000402010080400), U64(0x0000004020100A00), U64(0x0000000040221400),
U64(0x0000000002442800), U64(0x0000000204085000), U64(0x0000020408102000), U64(0x0002040810204000),
U64(0x0020100804020000), U64(0x0040201008040000), U64(0x00004020100A0000), U64(0x0000004022140000),
U64(0x0000000244280000), U64(0x0000020408500000), U64(0x0002040810200000), U64(0x0004081020400000),
U64(0x0010080402000200), U64(0x0020100804000400), U64(0x004020100A000A00), U64(0x0000402214001400),
U64(0x0000024428002800), U64(0x0002040850005000), U64(0x0004081020002000), U64(0x0008102040004000),
U64(0x0008040200020400), U64(0x0010080400040800), U64(0x0020100A000A1000), U64(0x0040221400142200),
U64(0x0002442800284400), U64(0x0004085000500800), U64(0x0008102000201000), U64(0x0010204000402000),
U64(0x0004020002040800), U64(0x0008040004081000), U64(0x00100A000A102000), U64(0x0022140014224000),
U64(0x0044280028440200), U64(0x0008500050080400), U64(0x0010200020100800), U64(0x0020400040201000),
U64(0x0002000204081000), U64(0x0004000408102000), U64(0x000A000A10204000), U64(0x0014001422400000),
U64(0x0028002844020000), U64(0x0050005008040200), U64(0x0020002010080400), U64(0x0040004020100800),
U64(0x0000020408102000), U64(0x0000040810204000), U64(0x00000A1020400000), U64(0x0000142240000000),
U64(0x0000284402000000), U64(0x0000500804020000), U64(0x0000201008040200), U64(0x0000402010080400),
U64(0x0002040810204000), U64(0x0004081020400000), U64(0x000A102040000000), U64(0x0014224000000000),
U64(0x0028440200000000), U64(0x0050080402000000), U64(0x0020100804020000), U64(0x0040201008040200)
};
U64 magicmovesbdb[5248];
const U64* magicmoves_b_indices[64] = {
magicmovesbdb+4992, magicmovesbdb+2624, magicmovesbdb+256, magicmovesbdb+896,
magicmovesbdb+1280, magicmovesbdb+1664, magicmovesbdb+4800, magicmovesbdb+5120,
magicmovesbdb+2560, magicmovesbdb+2656, magicmovesbdb+288, magicmovesbdb+928,
magicmovesbdb+1312, magicmovesbdb+1696, magicmovesbdb+4832, magicmovesbdb+4928,
magicmovesbdb+0, magicmovesbdb+128, magicmovesbdb+320, magicmovesbdb+960,
magicmovesbdb+1344, magicmovesbdb+1728, magicmovesbdb+2304, magicmovesbdb+2432,
magicmovesbdb+32, magicmovesbdb+160, magicmovesbdb+448, magicmovesbdb+2752,
magicmovesbdb+3776, magicmovesbdb+1856, magicmovesbdb+2336, magicmovesbdb+2464,
magicmovesbdb+64, magicmovesbdb+192, magicmovesbdb+576, magicmovesbdb+3264,
magicmovesbdb+4288, magicmovesbdb+1984, magicmovesbdb+2368, magicmovesbdb+2496,
magicmovesbdb+96, magicmovesbdb+224, magicmovesbdb+704, magicmovesbdb+1088,
magicmovesbdb+1472, magicmovesbdb+2112, magicmovesbdb+2400, magicmovesbdb+2528,
magicmovesbdb+2592, magicmovesbdb+2688, magicmovesbdb+832, magicmovesbdb+1216,
magicmovesbdb+1600, magicmovesbdb+2240, magicmovesbdb+4864, magicmovesbdb+4960,
magicmovesbdb+5056, magicmovesbdb+2720, magicmovesbdb+864, magicmovesbdb+1248,
magicmovesbdb+1632, magicmovesbdb+2272, magicmovesbdb+4896, magicmovesbdb+5184
};
U64 magicmovesrdb[102400];
const U64* magicmoves_r_indices[64] = {
magicmovesrdb+86016, magicmovesrdb+73728, magicmovesrdb+36864, magicmovesrdb+43008,
magicmovesrdb+47104, magicmovesrdb+51200, magicmovesrdb+77824, magicmovesrdb+94208,
magicmovesrdb+69632, magicmovesrdb+32768, magicmovesrdb+38912, magicmovesrdb+10240,
magicmovesrdb+14336, magicmovesrdb+53248, magicmovesrdb+57344, magicmovesrdb+81920,
magicmovesrdb+24576, magicmovesrdb+33792, magicmovesrdb+6144, magicmovesrdb+11264,
magicmovesrdb+15360, magicmovesrdb+18432, magicmovesrdb+58368, magicmovesrdb+61440,
magicmovesrdb+26624, magicmovesrdb+4096, magicmovesrdb+7168, magicmovesrdb+0,
magicmovesrdb+2048, magicmovesrdb+19456, magicmovesrdb+22528, magicmovesrdb+63488,
magicmovesrdb+28672, magicmovesrdb+5120, magicmovesrdb+8192, magicmovesrdb+1024,
magicmovesrdb+3072, magicmovesrdb+20480, magicmovesrdb+23552, magicmovesrdb+65536,
magicmovesrdb+30720, magicmovesrdb+34816, magicmovesrdb+9216, magicmovesrdb+12288,
magicmovesrdb+16384, magicmovesrdb+21504, magicmovesrdb+59392, magicmovesrdb+67584,
magicmovesrdb+71680, magicmovesrdb+35840, magicmovesrdb+39936, magicmovesrdb+13312,
magicmovesrdb+17408, magicmovesrdb+54272, magicmovesrdb+60416, magicmovesrdb+83968,
magicmovesrdb+90112, magicmovesrdb+75776, magicmovesrdb+40960, magicmovesrdb+45056,
magicmovesrdb+49152, magicmovesrdb+55296, magicmovesrdb+79872, magicmovesrdb+98304
};
U64 initmagicmoves_occ(const int* squares, const int numSquares, const U64 linocc) {
int i;
U64 ret=0;
for(i=0;i<numSquares;i++)
if(linocc&(((U64)(1))<<i)) ret|=(((U64)(1))<<squares[i]);
return ret;
}
U64 initmagicmoves_Rmoves(const int square, const U64 occ) {
U64 ret=0;
U64 bit;
U64 rowbits=(((U64)0xFF)<<(8*(square/8)));
bit=(((U64)(1))<<square);
do {
bit<<=8;
ret|=bit;
}while(bit && !(bit&occ));
bit=(((U64)(1))<<square);
do {
bit>>=8;
ret|=bit;
}while(bit && !(bit&occ));
bit=(((U64)(1))<<square);
do {
bit<<=1;
if(bit&rowbits) ret|=bit;
else break;
}while(!(bit&occ));
bit=(((U64)(1))<<square);
do {
bit>>=1;
if(bit&rowbits) ret|=bit;
else break;
}while(!(bit&occ));
return ret;
}
U64 initmagicmoves_Bmoves(const int square, const U64 occ) {
U64 ret=0;
U64 bit;
U64 bit2;
U64 rowbits=(((U64)0xFF)<<(8*(square/8)));
bit=(((U64)(1))<<square);
bit2=bit;
do {
bit<<=8-1;
bit2>>=1;
if(bit2&rowbits) ret|=bit;
else break;
}while(bit && !(bit&occ));
bit=(((U64)(1))<<square);
bit2=bit;
do {
bit<<=8+1;
bit2<<=1;
if(bit2&rowbits) ret|=bit;
else break;
}while(bit && !(bit&occ));
bit=(((U64)(1))<<square);
bit2=bit;
do {
bit>>=8-1;
bit2<<=1;
if(bit2&rowbits) ret|=bit;
else break;
}while(bit && !(bit&occ));
bit=(((U64)(1))<<square);
bit2=bit;
do {
bit>>=8+1;
bit2>>=1;
if(bit2&rowbits) ret|=bit;
else break;
}while(bit && !(bit&occ));
return ret;
}
#define BmagicNOMASK2(square, occupancy) *(magicmoves_b_indices2[square]+(((occupancy)*magicmoves_b_magics[square])>>magicmoves_b_shift[square]))
#define RmagicNOMASK2(square, occupancy) *(magicmoves_r_indices2[square]+(((occupancy)*magicmoves_r_magics[square])>>magicmoves_r_shift[square]))
void initmagicmoves(void) {
int i,j;
int initmagicmoves_bitpos64_database[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5
};
U64* magicmoves_b_indices2[64] = {
magicmovesbdb+4992, magicmovesbdb+2624, magicmovesbdb+256, magicmovesbdb+896,
magicmovesbdb+1280, magicmovesbdb+1664, magicmovesbdb+4800, magicmovesbdb+5120,
magicmovesbdb+2560, magicmovesbdb+2656, magicmovesbdb+288, magicmovesbdb+928,
magicmovesbdb+1312, magicmovesbdb+1696, magicmovesbdb+4832, magicmovesbdb+4928,
magicmovesbdb+0, magicmovesbdb+128, magicmovesbdb+320, magicmovesbdb+960,
magicmovesbdb+1344, magicmovesbdb+1728, magicmovesbdb+2304, magicmovesbdb+2432,
magicmovesbdb+32, magicmovesbdb+160, magicmovesbdb+448, magicmovesbdb+2752,
magicmovesbdb+3776, magicmovesbdb+1856, magicmovesbdb+2336, magicmovesbdb+2464,
magicmovesbdb+64, magicmovesbdb+192, magicmovesbdb+576, magicmovesbdb+3264,
magicmovesbdb+4288, magicmovesbdb+1984, magicmovesbdb+2368, magicmovesbdb+2496,
magicmovesbdb+96, magicmovesbdb+224, magicmovesbdb+704, magicmovesbdb+1088,
magicmovesbdb+1472, magicmovesbdb+2112, magicmovesbdb+2400, magicmovesbdb+2528,
magicmovesbdb+2592, magicmovesbdb+2688, magicmovesbdb+832, magicmovesbdb+1216,
magicmovesbdb+1600, magicmovesbdb+2240, magicmovesbdb+4864, magicmovesbdb+4960,
magicmovesbdb+5056, magicmovesbdb+2720, magicmovesbdb+864, magicmovesbdb+1248,
magicmovesbdb+1632, magicmovesbdb+2272, magicmovesbdb+4896, magicmovesbdb+5184
};
U64* magicmoves_r_indices2[64] = {
magicmovesrdb+86016, magicmovesrdb+73728, magicmovesrdb+36864, magicmovesrdb+43008,
magicmovesrdb+47104, magicmovesrdb+51200, magicmovesrdb+77824, magicmovesrdb+94208,
magicmovesrdb+69632, magicmovesrdb+32768, magicmovesrdb+38912, magicmovesrdb+10240,
magicmovesrdb+14336, magicmovesrdb+53248, magicmovesrdb+57344, magicmovesrdb+81920,
magicmovesrdb+24576, magicmovesrdb+33792, magicmovesrdb+6144, magicmovesrdb+11264,
magicmovesrdb+15360, magicmovesrdb+18432, magicmovesrdb+58368, magicmovesrdb+61440,
magicmovesrdb+26624, magicmovesrdb+4096, magicmovesrdb+7168, magicmovesrdb+0,
magicmovesrdb+2048, magicmovesrdb+19456, magicmovesrdb+22528, magicmovesrdb+63488,
magicmovesrdb+28672, magicmovesrdb+5120, magicmovesrdb+8192, magicmovesrdb+1024,
magicmovesrdb+3072, magicmovesrdb+20480, magicmovesrdb+23552, magicmovesrdb+65536,
magicmovesrdb+30720, magicmovesrdb+34816, magicmovesrdb+9216, magicmovesrdb+12288,
magicmovesrdb+16384, magicmovesrdb+21504, magicmovesrdb+59392, magicmovesrdb+67584,
magicmovesrdb+71680, magicmovesrdb+35840, magicmovesrdb+39936, magicmovesrdb+13312,
magicmovesrdb+17408, magicmovesrdb+54272, magicmovesrdb+60416, magicmovesrdb+83968,
magicmovesrdb+90112, magicmovesrdb+75776, magicmovesrdb+40960, magicmovesrdb+45056,
magicmovesrdb+49152, magicmovesrdb+55296, magicmovesrdb+79872, magicmovesrdb+98304
};
#ifdef _MSC_VER
#pragma warning (disable: 4146)
#endif
for(i=0;i<64;i++) {
int squares[64];
int numsquares=0;
U64 temp=magicmoves_b_mask[i];
while(temp) {
U64 bit=temp&-temp;
squares[numsquares++]=initmagicmoves_bitpos64_database[(bit*U64(0x07EDD5E59A4E28C2))>>58];
temp^=bit;
}
for(temp=0;temp<(((U64)(1))<<numsquares);temp++) {
U64 tempocc=initmagicmoves_occ(squares,numsquares,temp);
BmagicNOMASK2(i,tempocc)=initmagicmoves_Bmoves(i,tempocc);
}
}
for(i=0;i<64;i++) {
int squares[64];
int numsquares=0;
U64 temp=magicmoves_r_mask[i];
while(temp) {
U64 bit=temp&-temp;
squares[numsquares++]=initmagicmoves_bitpos64_database[(bit*U64(0x07EDD5E59A4E28C2))>>58];
temp^=bit;
}
for(temp=0;temp<(((U64)(1))<<numsquares);temp++) {
U64 tempocc=initmagicmoves_occ(squares,numsquares,temp);
RmagicNOMASK2(i,tempocc)=initmagicmoves_Rmoves(i,tempocc);
}
}
#ifdef _MSC_VER
#pragma warning (default: 4146)
#endif
}
const U64 knight_magics[64] = {
U64(0x0000000000020400),U64(0x0000000000050800),U64(0x00000000000a1100),U64(0x0000000000142200),
U64(0x0000000000284400),U64(0x0000000000508800),U64(0x0000000000a01000),U64(0x0000000000402000),
U64(0x0000000002040004),U64(0x0000000005080008),U64(0x000000000a110011),U64(0x0000000014220022),
U64(0x0000000028440044),U64(0x0000000050880088),U64(0x00000000a0100010),U64(0x0000000040200020),
U64(0x0000000204000402),U64(0x0000000508000805),U64(0x0000000a1100110a),U64(0x0000001422002214),
U64(0x0000002844004428),U64(0x0000005088008850),U64(0x000000a0100010a0),U64(0x0000004020002040),
U64(0x0000020400040200),U64(0x0000050800080500),U64(0x00000a1100110a00),U64(0x0000142200221400),
U64(0x0000284400442800),U64(0x0000508800885000),U64(0x0000a0100010a000),U64(0x0000402000204000),
U64(0x0002040004020000),U64(0x0005080008050000),U64(0x000a1100110a0000),U64(0x0014220022140000),
U64(0x0028440044280000),U64(0x0050880088500000),U64(0x00a0100010a00000),U64(0x0040200020400000),
U64(0x0204000402000000),U64(0x0508000805000000),U64(0x0a1100110a000000),U64(0x1422002214000000),
U64(0x2844004428000000),U64(0x5088008850000000),U64(0xa0100010a0000000),U64(0x4020002040000000),
U64(0x0400040200000000),U64(0x0800080500000000),U64(0x1100110a00000000),U64(0x2200221400000000),
U64(0x4400442800000000),U64(0x8800885000000000),U64(0x100010a000000000),U64(0x2000204000000000),
U64(0x0004020000000000),U64(0x0008050000000000),U64(0x00110a0000000000),U64(0x0022140000000000),
U64(0x0044280000000000),U64(0x0088500000000000),U64(0x0010a00000000000),U64(0x0020400000000000)
};
const U64 king_magics[64] = {
U64(0x0000000000000302),U64(0x0000000000000705),U64(0x0000000000000e0a),U64(0x0000000000001c14),
U64(0x0000000000003828),U64(0x0000000000007050),U64(0x000000000000e0a0),U64(0x000000000000c040),
U64(0x0000000000030203),U64(0x0000000000070507),U64(0x00000000000e0a0e),U64(0x00000000001c141c),
U64(0x0000000000382838),U64(0x0000000000705070),U64(0x0000000000e0a0e0),U64(0x0000000000c040c0),
U64(0x0000000003020300),U64(0x0000000007050700),U64(0x000000000e0a0e00),U64(0x000000001c141c00),
U64(0x0000000038283800),U64(0x0000000070507000),U64(0x00000000e0a0e000),U64(0x00000000c040c000),
U64(0x0000000302030000),U64(0x0000000705070000),U64(0x0000000e0a0e0000),U64(0x0000001c141c0000),
U64(0x0000003828380000),U64(0x0000007050700000),U64(0x000000e0a0e00000),U64(0x000000c040c00000),
U64(0x0000030203000000),U64(0x0000070507000000),U64(0x00000e0a0e000000),U64(0x00001c141c000000),
U64(0x0000382838000000),U64(0x0000705070000000),U64(0x0000e0a0e0000000),U64(0x0000c040c0000000),
U64(0x0003020300000000),U64(0x0007050700000000),U64(0x000e0a0e00000000),U64(0x001c141c00000000),
U64(0x0038283800000000),U64(0x0070507000000000),U64(0x00e0a0e000000000),U64(0x00c040c000000000),
U64(0x0302030000000000),U64(0x0705070000000000),U64(0x0e0a0e0000000000),U64(0x1c141c0000000000),
U64(0x3828380000000000),U64(0x7050700000000000),U64(0xe0a0e00000000000),U64(0xc040c00000000000),
U64(0x0203000000000000),U64(0x0507000000000000),U64(0x0a0e000000000000),U64(0x141c000000000000),
U64(0x2838000000000000),U64(0x5070000000000000),U64(0xa0e0000000000000),U64(0x40c0000000000000)
};
const U64 pawn_magics[2][64] = {
U64(0x0000000000000200), U64(0x0000000000000500), U64(0x0000000000000a00), U64(0x0000000000001400),
U64(0x0000000000002800), U64(0x0000000000005000), U64(0x000000000000a000), U64(0x0000000000004000),
U64(0x0000000000020000), U64(0x0000000000050000), U64(0x00000000000a0000), U64(0x0000000000140000),
U64(0x0000000000280000), U64(0x0000000000500000), U64(0x0000000000a00000), U64(0x0000000000400000),
U64(0x0000000002000000), U64(0x0000000005000000), U64(0x000000000a000000), U64(0x0000000014000000),
U64(0x0000000028000000), U64(0x0000000050000000), U64(0x00000000a0000000), U64(0x0000000040000000),
U64(0x0000000200000000), U64(0x0000000500000000), U64(0x0000000a00000000), U64(0x0000001400000000),
U64(0x0000002800000000), U64(0x0000005000000000), U64(0x000000a000000000), U64(0x0000004000000000),
U64(0x0000020000000000), U64(0x0000050000000000), U64(0x00000a0000000000), U64(0x0000140000000000),
U64(0x0000280000000000), U64(0x0000500000000000), U64(0x0000a00000000000), U64(0x0000400000000000),
U64(0x0002000000000000), U64(0x0005000000000000), U64(0x000a000000000000), U64(0x0014000000000000),
U64(0x0028000000000000), U64(0x0050000000000000), U64(0x00a0000000000000), U64(0x0040000000000000),
U64(0x0200000000000000), U64(0x0500000000000000), U64(0x0a00000000000000), U64(0x1400000000000000),
U64(0x2800000000000000), U64(0x5000000000000000), U64(0xa000000000000000), U64(0x4000000000000000),
U64(0x0000000000000002), U64(0x0000000000000005), U64(0x000000000000000a), U64(0x0000000000000014),
U64(0x0000000000000028), U64(0x0000000000000050), U64(0x00000000000000a0), U64(0x0000000000000040),
U64(0x0200000000000000), U64(0x0500000000000000), U64(0x0a00000000000000), U64(0x1400000000000000),
U64(0x2800000000000000), U64(0x5000000000000000), U64(0xa000000000000000), U64(0x4000000000000000),
U64(0x0000000000000002), U64(0x0000000000000005), U64(0x000000000000000a), U64(0x0000000000000014),
U64(0x0000000000000028), U64(0x0000000000000050), U64(0x00000000000000a0), U64(0x0000000000000040),
U64(0x0000000000000200), U64(0x0000000000000500), U64(0x0000000000000a00), U64(0x0000000000001400),
U64(0x0000000000002800), U64(0x0000000000005000), U64(0x000000000000a000), U64(0x0000000000004000),
U64(0x0000000000020000), U64(0x0000000000050000), U64(0x00000000000a0000), U64(0x0000000000140000),
U64(0x0000000000280000), U64(0x0000000000500000), U64(0x0000000000a00000), U64(0x0000000000400000),
U64(0x0000000002000000), U64(0x0000000005000000), U64(0x000000000a000000), U64(0x0000000014000000),
U64(0x0000000028000000), U64(0x0000000050000000), U64(0x00000000a0000000), U64(0x0000000040000000),
U64(0x0000000200000000), U64(0x0000000500000000), U64(0x0000000a00000000), U64(0x0000001400000000),
U64(0x0000002800000000), U64(0x0000005000000000), U64(0x000000a000000000), U64(0x0000004000000000),
U64(0x0000020000000000), U64(0x0000050000000000), U64(0x00000a0000000000), U64(0x0000140000000000),
U64(0x0000280000000000), U64(0x0000500000000000), U64(0x0000a00000000000), U64(0x0000400000000000),
U64(0x0002000000000000), U64(0x0005000000000000), U64(0x000a000000000000), U64(0x0014000000000000),
U64(0x0028000000000000), U64(0x0050000000000000), U64(0x00a0000000000000), U64(0x0040000000000000)
};