Transposition Table Usage

Code, algorithms, languages, construction...
Post Reply
theturk1234
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm
Real Name: David Simalista

Transposition Table Usage

Post by theturk1234 » Tue Jul 12, 2016 4:35 am

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
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Transposition Table Usage

Post by H.G.Muller » Tue Jul 12, 2016 7:33 am

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
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm
Real Name: David Simalista

Re: Transposition Table Usage

Post by theturk1234 » Wed Jul 13, 2016 5:19 pm

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
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Transposition Table Usage

Post by H.G.Muller » Wed Jul 13, 2016 10:18 pm

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

theturk1234
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm
Real Name: David Simalista

Re: Transposition Table Usage

Post by theturk1234 » Sat Jul 16, 2016 9:33 pm

All right, thanks for the assistance!

David Cimbalista

sandermvdb
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Transposition Table Usage

Post by sandermvdb » Sun Jul 24, 2016 3:33 pm

H.G.Muller wrote: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
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Transposition Table Usage

Post by hyatt » Sun Jul 24, 2016 3:44 pm

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

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Transposition Table Usage

Post by H.G.Muller » Sun Jul 24, 2016 7:04 pm

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.)

Post Reply