Transposition table replacement strategies

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Transposition table replacement strategies

Post by zd3nik » Sun Mar 06, 2016 1:10 am

Here is how I handle TT probes/stores in my main search routine. If anyone can spot potential problem(s) I would appreciate feedback.

Code: Select all

    pv = EMPTY
    bestScore = MATED_AT(ply);

    ttGets++;
    ttMove = NONE;
    ttEntry = TT.GetEntryAt(positionKey);
    if (ttEntry.Matches(positionKey)) {
      ttHits++;
      ttMove = ttEntry.BestMove();
      if (ttEntry.Depth() >= depth) {
        switch (ttEntry.Type()) {
        case UpperBound:
          if &#40;ttEntry.Score&#40;) <= alpha&#41; &#123;
            pv = ttMove;
            return ttEntry.Score&#40;);
          &#125;
          break;
        case LowerBound&#58;
          if &#40;ttEntry.Score&#40;) >= beta&#41; &#123;
            pv = ttMove;
            return ttEntry.Score&#40;);
          &#125;
          break;
        case ExactScore&#58;
          if (&#40;ttEntry.Score&#40;) <= alpha&#41; OR &#40;ttEntry.Score&#40;) >= beta&#41; OR &#40;not pvNode&#41;) &#123;
            pv = ttMove;
            return ttEntry.Score&#40;);
          &#125;
          break;
        &#125;
      &#125;
      Exec&#40;ttMove&#41;;
      bestScore = -child.Search&#40;-beta, -alpha&#41;
      Undo&#40;ttMove&#41;;
      pv = ttMove + child.pv;
      if &#40;bestScore >= beta&#41; &#123;
        ttEntry.Set&#40;bestScore, LowerBound, ttMove&#41;;
        return bestScore;
      &#125;
    &#125;

    GenerateMoves&#40;);
    if &#40;no legal moves&#41; &#123;
      if &#40;in check&#41; return MATED_AT&#40;ply&#41; else return DRAW;
    &#125;

    foreach&#40;move&#41; &#123;
      if &#40;move != ttMove&#41; &#123;
        Exec&#40;move&#41;;
        score = -child.Search&#40;-beta, -alpha&#41;;
        Undo&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
          pv = move + child.pv;
          bestScore = score
        &#125;
        if &#40;score >= beta&#41; &#123;
          ttEntry.Set&#40;score, LowerBound, move&#41;;
          return score;
        &#125;
        alpha = max&#40;score, alpha&#41;;
      &#125;
    &#125;

    if &#40;bestScore > original_alpha&#41; &#123;
      ttEntry.Set&#40;bestScore, ExactScore, pv.FirstMove&#40;));
    &#125;
    else &#123;
      ttEntry.Set&#40;bestScore, UpperBound, pv.FirstMove&#40;));
    &#125;

    return bestScore;
Of course I've simplified things a lot in this psuedo-code. For example the real code implements null move pruning, PVS, LMR, etc...

QSearch does the TT lookup and returns ttEntry.Score() where appropriate. But QSearch does not store results (never calls ttEntry.Set)

Post Reply