Transposition Table Usage

[theturk1234]

Hi,

I was wondering if any of you could tell me how to use a transposition table. I already have it implemented, I just need to know when I should probe the table, when I should be saving nodes, which node types at different places in the tree, and any other advice you could give me. Your comments are greatly appreciated!

David Cimbalista

[H.G.Muller]

I normally use the TT to retore the state of the node to that where I left it on the previous visit, if the information in it is useful.

Code: Select all

Search(alpha, beta, depth)
{
  int bestScore;
  int hashMove = INVALID;
  int iterDepth = 0; // normal IID starting point
  HashEntry *tt = ProbeTT();
  if( tt != NULL &&        (tt->flags == EXACT || 
      tt->score <= alpha && tt->flags == UPPER_BOUND ||
      tt->score >= beta  && tt->flags == LOWER_BOUND)) {
    iterDepth = tt->depth;
    hashMove  = tt->move;
    bestScore = tt->score; // to make sure we return something if tt->depth >= depth
  }
  while(++iterDepth <= depth) {
    bestScore = -INF;
    PlaceInFront(hashMove);
    for(ALL_MOVES) {
      MakeMove(move);
      score = -Search(-beta, -max(alpha, bestScore), iterDepth-1);
      UnMake();
      if(score > bestScore) {
        bestScore = score;
        hashMove  = move;
        if(score >= beta) break; // beta cutoff
      }
    }
    tt = ReplaceTT();
    tt->score = bestScore;
    tt->depth = iterDepth;
    tt->move  = hashMove;
    tt->flags = (bestScore >= beta ? LOWER_BOUND : bestScore <= alpha ? UPPER_BOUND : EXACT);
  }
  return bestScore;
}

[theturk1234]

Ok, thanks for the response!

Another quick question: should I be probing and saving to the table in quiescence search? I'm doing it now and it's slowing down the engine.

Thanks,
David Cimbalista

[H.G.Muller]

You can only know that by testing. In my engines (all single-threaded) it always helped to probe in QS.

[theturk1234]

All right, thanks for the assistance!

David Cimbalista

[sandermvdb]

You can only know that by testing. In my engines (all single-threaded) it always helped to probe in QS.

Do you use a special FLAG for quiescence? Or a separate table?

[hyatt]

Just store "draft = 0" and it will work just fine...

[H.G.Muller]

No special flag. The draft stored can be 0, 1 or 2, depending on the situation, so that 1-ply or 2-ply probes can be satisfied by them. (0 for nodes that return the static evaluation, 1 for a beta cutoff, 2 for a fail low where non-captures where futile.)