Winboard Forum

New version of alfil without Tables Hash, but better alpha-beta search.
I?m trying to insert Tables Hash with Zobrist keys. My keys now are good but i have problems with the Probe and Store in alpha-beta search.

If someone can help me, thanks.

Getting the hash to work is a three part process:

(1) Your keys MUST be good. You say yours are but it is worthwhile to have debugging code to rebuild the key from scratch and compare it with every make/unmake move.

(2) When you store and probe you MUST get back exactly what you put in. This is simple in concept but errors can easily creep in.

(3) If you use the hash to cut your logic to handle the bounds, remaining depth and so on must be correct.

I pasted in below the probe and store functions from Simon. Note that none of the cut logic is included - this is done elsewhere in search. Thus these functions handle only step (2) and are easy to test - every time you do a store you can do a probe to verify that what went in comes out. Once that works you can move on to step (3) - you can download Simon from Dann Corbit's ftp site to see its cut logic.

Good Luck
Dan H.

Code: Select all

//====================================================================
//HashStore() and HashProbe() save and retrieve information from
//the hash table
//====================================================================
void HashStore(int ply, int depth, int type, int threat, int val, int move) {
  //index slot
  hash_entry *ph;
  ph = hash_table + (key_1 & hash_mask);
  //adjust for mate
  if (val > DEAD) val += ply;
  else if (val < -DEAD) val -= ply;

  if (ph->key1 != key_1) {
    //slot 1 is empty or occupied by a different position
    if ((ph->data & old_entry)||(depth >= hget_depth(ph->data))) {
      //new data looks better.  get move from slot 2 if we have none
      //and then move existing occupant (if any) to slot 2
      if (!move && (ph + 1)->key1 == key_1) move = hget_move((ph+1)->data);
      (ph+1)->key1 = ph->key1;
      (ph+1)->data = ph->data;
    } else {
      //existing data in slot 1 looks better.  leave existing occupant
      //alone and put new data in slot 2
      ph++;
    }
  } else {
    //this is our slot.  save existing move if we have no new move
    if (!move) move = hget_move(ph->data);
  }
  if (depth < 0) depth = 0;   //don't try to store negative depth!
  ph->key1 = key_1;
  ph->data = hset_type(type) | hset_threat(threat) | hset_val(val) |
    hset_depth(depth) | hset_move(move);
}

int HashProbe(int ply, int &depth, int &type, int &threat, int &val, int &move) {
  hash_entry *ph;
  ph = hash_table + (key_1 & hash_mask);
  if (ph->key1 == key_1) {
    move = hget_move(ph->data);
    type = hget_type(ph->data);
    threat = hget_threat(ph->data);
    val = hget_val(ph->data);
    if (val > DEAD) val -= ply;
    else if (val < -DEAD) val += ply;
    depth = hget_depth(ph->data);
    ph->data &= ~old_entry;
    return TRUE;
  }
  ph++;
  if (ph->key1 == key_1) {
    move = hget_move(ph->data);
    type = hget_type(ph->data);
    threat = hget_threat(ph->data);
    val = hget_val(ph->data);
    if (val > DEAD) val -= ply;
    else if (val < -DEAD) val += ply;
    depth = hget_depth(ph->data);
    ph->data &= ~old_entry;
    return TRUE;
  }
  return FALSE;
}


Many thanks to Dan Honeycutt:
My keys are good, I store and probe good, but some times on equal depth the value is diferent because alpha and beta are diferent, what could I do?.

esacosta wrote:Many thanks to Dan Honeycutt:
My keys are good, I store and probe good, but some times on equal depth the value is diferent because alpha and beta are diferent, what could I do?.

Its absolute normally that your bounds have other values, because you may reached the position from another tree.

daniel

Dan Honeycutt wrote:
(2) When you store and probe you MUST get back exactly what you put in. This is simple in concept but errors can easily creep in.

(3) If you use the hash to cut your logic to handle the bounds, remaining depth and so on must be correct.

Few comments, that might be worth mentioning:

(2) Depending how you define put in and get back, this is not the case for mate scores for typical engines. Dan's code shows, that he adjusts the mate scores by "ply". Of course, the value stored in the HT literally is the one you get back. But if you define the store/probe as the values given to tHe HashStore() and got back by HashProbe() they will differ in general for mate scores. (Long ago Miguel Ballicora showed a slightly different search scheme for mate values, were bounds get adjusted inside the search. I forgot the details, but I believe remember, that the HT scores for mates did not need any adjustment.)

(3) Also here mate scores can be an exception. Not only for the adjustment of scores, but also for cutoffs. Even when the draft would not be enough for a non mate score cutoff/bounds adjustment, a mate score (which is always a really proven score) will be enough (not for cutoffs inside the window - then you could lose the ability to find the shortest mate), but for fail high/ fail low. In some positions this can reduce the search tree by a significant amount (for fail soft searchers). But such ideas probably should only be implemented when the hash logic is well debugged. The same probably is already true for all bound adjustments. I am not sure, how much they buy, and got different results. Bob Hyatt recently mentioned, that he dumped the bounds adjustments totally.

Another subtle point in this context. Say you have a lower bound with enough draft, but not good enough to give you a cutoff (the lower bound is inside your current search window). You might want to adjust alpha to this lower bound. But it can happen, that this lower bound is really an exact score (you cannot know it at this time). When you adjusted alpha to this lower bound that actually is exact, you may end up without any best mvoe easily. This might hurt (for example you will not have a best move in the HT when you visit this node next, while with the not adjusted bound, you had such a move). Adjusting alpha = lower_bound -1 might help. I tried it, but it was not always convincing. I have many #defines to adjust the behavior.

Depending on the engine, storing negative draft may make sense. For example for qsearch nodes.

Regards,
Dieter