Hashing based on move lists

Discussion of chess software programming and technical issues.

Moderator: Ras

Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Hashing based on move lists

Post by Daniel Shawul »

Have you checked if the distribution of keys is uniform? This is important to reduce clustering effect where only part of the TT is utilized. Btw you can measure the number of collisions relatively easily by storing two hash keys computed in a different way (one could be pre-calculated zobrist). You would be surprised how quickly that spots weak hashing algorithms. We did this while discussing 'on the fly hashing' algorithms such as ranrot,fnv hashing etc.. This is pretty much the same as those algorithms because bishop/root attacks with magic squares are done with a multiply and shift. One of the FNV variants does something like that starting with a magic 64-bit number.
Top
jdart
Posts: 4420
Joined: Fri Mar 10, 2006 5:23 am
Location: http://www.arasanchess.org

Re: A brief comment on using 128 bit Zobrist hashing

Post by jdart »

Using the least significant bits to calculate the address and storing them at the same time is somehow wasteful.
This is true, but personally, I am still doing the wasteful thing. Memory is cheap nowadays.

--Jon
Top
Gusev
Posts: 1476
Joined: Mon Jan 28, 2013 2:51 pm

Re: Hashing based on move lists

Post by Gusev »

Daniel Shawul wrote:Have you checked if the distribution of keys is uniform? This is important to reduce clustering effect where only part of the TT is utilized. Btw you can measure the number of collisions relatively easily by storing two hash keys computed in a different way (one could be pre-calculated zobrist). You would be surprised how quickly that spots weak hashing algorithms. We did this while discussing 'on the fly hashing' algorithms such as ranrot,fnv hashing etc.. This is pretty much the same as those algorithms because bishop/root attacks with magic squares are done with a multiply and shift. One of the FNV variants does something like that starting with a magic 64-bit number.
I will check, thank you! (But first I have to address the more obvious weakness of the original flawed implementation.)
Top
Gusev
Posts: 1476
Joined: Mon Jan 28, 2013 2:51 pm

Re: Hashing based on move lists

Post by Gusev »

Gerd Isenberg wrote: With all sympathies for your twiddling, don't take that too serious, but I agree more with HG, Ricardo and others, that your hashing is flawed.
I would like to emphasize the fundamental difference between the original implementation being flawed, which it is, and the underlying idea of chess-specific non-random hashing being flawed. My PowerPoint presentation mentioned that "it is easier to control and modify the technique to reduce collisions", because I had suspected that such modifications would prove necessary.
Top
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Hashing based on move lists

Post by Daniel Shawul »

Well I tested it based on my code here. It gives about 3000 coll/million which is much worse than fnv-1a which gives 60 coll/million and also much slower. Even fnv-1a was not acceptable for hashing and I was not sure if it was possible to bring it to the level of zobrist hashing. If you use smaller signature less than 64 bits say 28 collision rate sky rockets.

Code: Select all

U64 hashf(int cp,int sq) { 
   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; 
}
You can also look at the distribution by uncommenting part of the code in main below.

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

void 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*/
} 

//*/ 
/**********************************************************************
 *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)
};
Top
lucasart
Posts: 3243
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Hashing based on move lists

Post by lucasart »

Gusev wrote:
Gerd Isenberg wrote: With all sympathies for your twiddling, don't take that too serious, but I agree more with HG, Ricardo and others, that your hashing is flawed.
I would like to emphasize the fundamental difference between the original implementation being flawed, which it is, and the underlying idea of chess-specific non-random hashing being flawed. My PowerPoint presentation mentioned that "it is easier to control and modify the technique to reduce collisions", because I had suspected that such modifications would prove necessary.
If I were you I would not start by parading with a PowerPoint presentation. I would start with scratching my brain instead.

Your idea neither wortks, nor makes any sense. Whether in general (idea of chess specific being better than PRNG) or in particular with using attack bitboards as Zobrist keys.

Here is a completely trivial example that demonstrates hash collision with your method:

position 1: Ra1, Rh8
position 2: Rh1, Ra8

In both cases the zobrist key obtained by your method is the same:

Code: Select all

 . X X X X X X .
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 . X X X X X X .
And you are trying to solve a problem that does not exist. 64 bit Zobrist keys, if properly generated, have such an infinitesimal chance of collision, you'll probably not gonna see one in a lifetime...
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
Top
Gerd Isenberg
Posts: 2251
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Hashing based on move lists

Post by Gerd Isenberg »

lucasart wrote:Here is a completely trivial example that demonstrates hash collision with your method:

position 1: Ra1, Rh8
position 2: Rh1, Ra8

In both cases the zobrist key obtained by your method is the same:

Code: Select all

 . X X X X X X .
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 . X X X X X X .
Colission rate would be even worse in that case. As mentioned elsewhere in this thread this case is covered by including the origin square for all pieces except bishop:
http://www.talkchess.com/forum/viewtopi ... 66&t=48479
http://www.talkchess.com/forum/viewtopi ... 95&t=48479
http://www.talkchess.com/forum/viewtopi ... 03&t=48479
Top
Gusev
Posts: 1476
Joined: Mon Jan 28, 2013 2:51 pm

Re: Hashing based on move lists

Post by Gusev »

Gerd Isenberg wrote:
lucasart wrote:Here is a completely trivial example that demonstrates hash collision with your method:

position 1: Ra1, Rh8
position 2: Rh1, Ra8

In both cases the zobrist key obtained by your method is the same:

Code: Select all

 . X X X X X X .
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 X . . . . . . X
 . X X X X X X .
Colission rate would be even worse in that case. As mentioned elsewhere in this thread this case is covered by including the origin square for all pieces except bishop:
http://www.talkchess.com/forum/viewtopi ... 66&t=48479
http://www.talkchess.com/forum/viewtopi ... 95&t=48479
http://www.talkchess.com/forum/viewtopi ... 03&t=48479
Other improvements can be proposed, once we abandon the original idea of using the same table of proto-moves for hash value generation and move generation, yet stop short of going back to pseudo-random keys. Different shapes of "halos" can be designed for different piece types, allowing us, in particular, to easily distinguish white pieces from black ones.
Top
User avatar
hgm
Posts: 28451
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Hashing based on move lists

Post by hgm »

The point is that there isn't a shred of evidence that these keys, or any other one can design or hand-pick, would work any better than randomly picked keys. This seems to be nothing more than wishful thinking.

Even if for the moment we forget about the problem of the black keys, for which you have not proposed a working solution yet, you don't seem to have done even the most elementary analysis of the white set of keys to verify they are sufficiently independent. That you could not find a depence between two or three of them with pencil and paper is hardly an indication. That would also not have been possible with 64-bit random keys.
Top
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Hashing based on move lists

Post by Daniel Shawul »

This improves collision rate very slightly i.e. xoring the 'from' square for all pieces except bishops. It brought down collision rate from 3000coll/mill to 2900coll/mill. The major problem is that white and black have same keys. Fixing that in such a way that black have ~b reduces collision rate to 100coll/mill ! This is good but still no better than a simple fnv1a that gives 60coll/mill right way. It is simple and fast, OTOH generating attacks with magics is darn slow. For 28 bit key i am sure it would be much worse since attacks sets have some structure that requires all the 64 bit keys for maximum performance.

Code: Select all

U64 gusev(int cp, int sq) {
	int pc = cp / 2;
	int co = cp % 2;
	U64 b=0;
	switch(pc) {
	case 0: b=unitBB(sq) | king_attacks(sq); break;
	case 1: b=unitBB(sq) | knight_attacks(sq); break;
	case 2: b=bishop_attacks(sq,0); break;
	case 3: b=unitBB(sq) | rook_attacks(sq,0); break;
	case 4: b=unitBB(sq) | queen_attacks(sq,0); break;
	case 5: b=unitBB(sq) | pawn_attacks(sq,co); break;
	}
	if(co == 1) b=~b; //black has negation
	return b;
}
Top

Return to “Computer Chess Club: Programming and Technical Discussions”