hash collisions

[bob]

Several years ago Anthony Cozzie and I wrote a paper for the ICGA journal addressing this issue. My original question was "how many hash collisions per search is enough to cause a different (worse) move to be played?" I set up the experiment with Crafty and discovered that our search trees are so large, and so redundant, that we could tolerate far more collisions than I thought possible. I contacted Cozzie and explained how I had tested. He modified Zappa to try the same test and got similar numbers to mine. The bottom line was that one collision out of every 1M positions caused zero problems, which surprised me. In fact, one error every 10K nodes had very little effect, not that I would suggest using such a small hash signature to produce this error rate.

Allow me to ask? How did you recognize a collision?

Bottom line, a 32 bit key works more than good enough (I still use 64 bits myself, as one day the search speeds will reach the point where bigger is better since errors to accumulate at ultra-high NPS values.

My first TT implementation was 32 bit, it worked well in the midgame, went terribly wrong in the late endgame. Moving to a 48-bit key solved the problem.

During that period to check for collisions I created a special version that stored the full board also in the TT. Had it running for hours per position, no collisions reported with a 48-bit key. Alright, that was 1989/90, hardware allowing only 2500 NPS or so

Our methodology was simple. We did a normal hash probe, except that N% of the time, we accepted a "signature match" when the signature really did not match the hash entry. Pretty straightforward, and it pretty well represents a real collision when you think about. IE we didn't make up bogus hash entry data, we just took what was legitimately there even when the signatures didn't match. I was beyond surprised when I got the results I did. I then contacted Anthony (Cozzie) and asked him to run the same test. He got the same results. We did more testing to see exactly where we began to see trouble.

The question to ask is were you doing Zobrist hashing back then, or something else. Our paper is in the ICGA Journal, I will have to look to see exactly when.

Our test included all sorts of positions. I believe I even tried Fine #70 which I was pretty sure would be a really bad position to try with high rates of collisions, but it took a REALLY high number of collisions before the score/move began to change. Surprisingly high.

[Rebel]

Yes, I was using Zobrist.

Still the only way to catch all collisions is to store the whole board in the TT.

[Henk]

Yes I'm storing whole boards using bb. Don't know how much it cost. But Skipper playing weak and that is probably not the cause.

[Daniel Shawul]

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)
};

[bob]

Yes, I was using Zobrist.

Still the only way to catch all collisions is to store the whole board in the TT.

Yes to the last. And it happens a surprisingly small number of times. One day when the depths pass 100, it will get more interesting since the greater number of XOR's will add to the probability of two positions mapping to the same key. When I tested a long while back on the Cray, I just used 32 byte positions (4 bits per square) to give me an exact board representation. If two signatures matched, I then compared the 32 bytes for each. If they failed to match. I don't remember how we factored in white to move, but we did. Just too long ago to remember.

In any case, rare collisions are almost impossible to detect just by looking at PV/score changes. The only issue is to be sure a collision won't cause a crash. If that is guaranteed, then a few hash collisions are totally harmless. Our trees are so large it takes a LOT of error to begin to influence the root move selection...

[chrisw]

Yes, I was using Zobrist.

Still the only way to catch all collisions is to store the whole board in the TT.

Yes to the last. And it happens a surprisingly small number of times.

Why surprisingly small? Doesn’t one just apply the birthday paradox to get the probability, all known stuff:

The birthday problem in this more generic sense applies to hash functions: the expected number of N-bit hashes that can be generated before getting a collision is not 2N, but rather only 2​N⁄2.

It seems fairly trivial to experimentally find the collision probability for various N, and plot these against birthday paradox theoretical predictions. Any reason why these should differ?

One day when the depths pass 100, it will get more interesting since the greater number of XOR's will add to the probability of two positions mapping to the same key. When I tested a long while back on the Cray, I just used 32 byte positions (4 bits per square) to give me an exact board representation. If two signatures matched, I then compared the 32 bytes for each. If they failed to match. I don't remember how we factored in white to move, but we did. Just too long ago to remember.

In any case, rare collisions are almost impossible to detect just by looking at PV/score changes. The only issue is to be sure a collision won't cause a crash. If that is guaranteed, then a few hash collisions are totally harmless.

Whoa! Totally?! That maybe be a little premature and/or subjective. Incorrect PV prediction is time/performance degrading, and incorrect score/bounds information degrades the search tree in a quite unpredictable manner. It’s an incorrect assumption that random evaluation fails are always neutralised by robustness of a search tree, sometimes they will be and sometimes they won’t.
Did anybody perform the experiment of randomly inserting random (or even fixed mate) evals and random bounds coming back from the hash lookup? Probably quite an easy experiment for, let’s say, someone able to compile, let’s say, Stockfish and carry out some 60,000 games matches. Elo against various hash eval trashers. I wouldn’t bank on the totally harmless hypothesis.

Our trees are so large it takes a LOT of error to begin to influence the root move selection...

I think you mean error rate here. Errors per number of lookups.

[syzygy]

I think lockless hashing was pretty safe at modest number of threads most people have removed the need for legality checking of the hash move. Now it may be necessary to bring that back in.

So it looks like the SF devs were right when they decided not to store the full hash key in the TT (currently, only the first 16 bits are stored if I'm not mistaken), making the storage more economical (a 3-entry struct in 32 bytes), but to check the TT move for legality instead. I see that it was discussed 8 years ago: Stockfish hash implementation.

SF has always checked the TT move for legality. The TT move should be checked for legality whatever the hashing method.

[syzygy]

It is just too easy to implement this and solve the problem until you reach the search speeds where 64 bits fails to provide reasonable hash signatures. We are a LONG way from that point today.

64 bits are not a lot nowadays at all.
With 16 bytes per entry and a 64 GB hash, you need 32 bits to index the entry. You are left with just 64-32=32 bits to distinguish positions mapping to the same entry. This leads to several errors per minute of searching (assuming all SMP errors are caught by lockless hashing).

So it is very much necessary to check the validity of the TT move (or at least to ensure that an invalid move cannot corrupt the data structures).

[syzygy]

I don't see how ANY parallel search program can avoid choosing lockless or (1) or (2) above, otherwise you need to be completely immune to corrupted hash entries.

Stockfish avoids lockless hashing. The TT move is checked (which is necessary even without SMP) and there is nothing else that can go wrong.

[hgm]

So it is very much necessary to check the validity of the TT move (or at least to ensure that an invalid move cannot corrupt the data structures).

Only the latter. The hash move can be as illegal as you want. You just need a robust MakeMove / UnMake. E.g. take care to restore both what is captured by the King and by the Rook, after a castling, and put back what you actually moved, rather than assuming it was a King and a Rook.