hash.cpp

   1 /***************************************************************************
   2                    hash.cpp  -  Hash related implementations
   3                              -------------------
   4     begin                : Mon Sep 19 2005
   5     copyright            : (C) 2005 by Maurizio Monge
   6     email                : monge@linuz.sns.it
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include "engine.h"
  19 #include <string.h>
  20
  21 #define HSIZE (1<<22)
  22 #define HMASK (HSIZE-1)
  23 #define REHASH 3
  24
  25 void
  26 HashKey::print() const
  27 {
  28     printf("HashKey( 0x%llxLL, 0x%x )\n", (long long)check, index);
  29 }
  30
  31 void
  32 Engine::create_hash()
  33 {
  34     hash_table = new HashEntry[HSIZE];
  35 }
  36
  37 void
  38 Engine::reset_hash()
  39 {
  40     memset(hash_table, 0, sizeof(HashEntry)*HSIZE);
  41 }
  42
  43 void
  44 Engine::make_old_hash()
  45 {
  46     for(int i=0;i<HSIZE;i++)
  47         hash_table[i].is_old = 1;
  48 }
  49
  50 /* is this useful? */
  51 void
  52 Engine::prefetch_hash(const HashKey& hk)
  53 {
  54     __builtin_prefetch( &hash_table[ (hk.index) & HMASK] );
  55     __builtin_prefetch( &hash_table[ (hk.index+REHASH-1) & HMASK] );
  56 }
  57
  58 HashEntry*
  59 Engine::probe_hash(const HashKey& hk)
  60 {
  61     for(int i=0;i<REHASH;i++)
  62     {
  63         HashEntry* h = &hash_table[(hk.index + i) & HMASK];
  64         if(!h->check)
  65             return NULL;
  66         if(h->check == hk.check)
  67         {
  68             h->is_old = 0;
  69             return h;
  70         }
  71     }
  72     return NULL;
  73 }
  74
  75 void
  76 Engine::write_hash(int16_t lo, int16_t up, int depth, int best_cont)
  77 {
  78     HashEntry* h = 0;
  79
  80     /* look for an empty entry or the same entry to update */
  81     for(int i=0;i<REHASH;i++)
  82     {
  83         HashEntry* tmp = &hash_table[(board.hash.index + i) & HMASK];
  84         if(!tmp->check || tmp->check == board.hash.check)
  85         {
  86             h = tmp;
  87             break;
  88         }
  89     }
  90
  91     if(!h) /* look for an entry searched at lower depth */
  92     {
  93         int d = INF;
  94         int lowest = -1;
  95         for(int i=0;i<REHASH;i++)
  96         {
  97             HashEntry* tmp = &hash_table[(board.hash.index + i) & HMASK];
  98             if(tmp->depth < d)
  99             {
 100                 lowest = i;
 101                 d = tmp->depth;
 102             }
 103         }
 104
 105         if(d < depth)
 106             h = &hash_table[(board.hash.index + lowest) & HMASK];
 107     }
 108
 109     if(!h) /* look for an old entry and take the one searched at lowest depth */
 110     {
 111         int d = INF;
 112         int lowest = -1;
 113         for(int i=0;i<REHASH;i++)
 114         {
 115             HashEntry* tmp = &hash_table[(board.hash.index + i) & HMASK];
 116             if(tmp->depth < d && tmp->is_old == 1)
 117             {
 118                 lowest = i;
 119                 d = tmp->depth;
 120             }
 121         }
 122
 123         if(d != INF)
 124             h = &hash_table[(board.hash.index + lowest) & HMASK];
 125     }
 126
 127     if(!h)
 128         return;
 129 #if 0
 130     if(h->check == board.hash.check && h->depth>depth)
 131         return;
 132
 133     if(h->check == board.hash.check && h->depth==depth)
 134     {
 135         /* same entry, improve bounds */
 136         h->up = MIN(h->up, up);
 137         h->lo = MAX(h->lo, lo);
 138     }
 139     else
 140     {
 141         /* replace bounds */
 142         h->up = up;
 143         h->lo = lo;
 144     }
 145 #endif
 146
 147     h->up = up;
 148     h->lo = lo;
 149
 150     h->check = board.hash.check;
 151     h->depth = depth;
 152     h->best_mv = best_cont;
 153     h->is_old = 0;
 154 }