transposition table pseudocode

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.
zenpawn
Posts: 299
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

transposition table pseudocode

Post by zenpawn » Mon Aug 22, 2016 11:51 pm

I've been experiencing a strange TT-related bug lately (doesn't happen when it's disabled). My engine will play an OK game for a while before going bonkers and just ditching its queen for no reason. It might have been there before to a lesser degree, but I'm really noticing it now that I'm using the transposition table in quiescence search (both saving and retrieving).

Below is the basic structure of my alpha-beta search. My question is a sanity check: Does the use of the transposition table look correct? (Notes: zobrist is updated incrementally in make/undoMove, and addTransposition takes the zobrist, depth, eval, and type.).

Thanks,
-Erin

Code: Select all

function absearch(int a, int b, int depth, bool quiesce)
{
  entry = getTransposition(zobrist);
  if (entry && entry.depth >= (quiesce ? 0 : depth))
  {
    if &#40;entry.type == Type.Exact && entry.eval > a && entry.eval < b&#41;
    &#123;
      return entry.eval;
    &#125;
    else if &#40;entry.type == Type.Beta && entry.eval >= b&#41;
    &#123;
      return b;
    &#125;
    else if &#40;entry.eval <= a&#41;
    &#123;
      return a;
    &#125;
  &#125;
  if &#40;quiesce&#41;
  &#123;
    eval = evaluate&#40;);
    if &#40;eval > a&#41;
    &#123;
      if &#40;eval >= b&#41;
      &#123;
        addTransposition&#40;zobrist, 0, b, Type.Beta&#41;;
        return b;
      &#125;
      a = eval;
    &#125;
  &#125;
  if &#40;null_move_allowed&#41;
  &#123;
    makeMove&#40;null&#41;;
    eval = -absearch&#40;-b, -b + 1, depth - R - 1&#41;;
    undoMove&#40;null&#41;;
    if &#40;eval >= b&#41;
    &#123;
      addTransposition&#40;zobrist, max&#40;0, depth - R&#41;, b, Type.Beta&#41;;
      return b;
    &#125;
  &#125;
  localBest = -inf;
  movelist = getMoves&#40;quiesce&#41;;
  foreach move in movelist
  &#123;
    makeMove&#40;move&#41;;
    eval = -absearch&#40;-b, -a, depth - 1&#41;;
    undoMove&#40;move&#41;;
    if &#40;eval > a&#41;
    &#123;
      if &#40;eval >= b&#41;
      &#123;
        addTransposition&#40;zobrist, quiesce ? 0 &#58; depth, b, Type.Beta, move&#41;;
        return b;
      &#125;
      addTransposition&#40;zobrist, quiesce ? 0 &#58; depth, eval, Type.Exact, move&#41;;
      localBest = eval;
      a = eval;
    &#125;
  &#125;
  if &#40;localBest < a&#41;
  &#123;
    addTransposition&#40;zobrist, quiesce ? 0 &#58; depth, a, Type.Alpha&#41;;
  &#125;
  return a;
&#125;

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: transposition table pseudocode

Post by kbhearn » Tue Aug 23, 2016 4:34 am

your code to take cutoffs appears to have some problems at first glance

exact entries of sufficient depth can always be returned, they don't have to be inside the bounds - if you want to clamp to alpha/beta before returning that's fine (fail hard) or you can return it as is (fail soft)

on the other hand an entry type qualifier is necessary for returning a fail low based on TT entry - if you have a beta entry that says >= -2 and your alpha in current node is -1, you can't fail low based on that, it's possible that it'd also be > -1, you've gotta search :) If your logic was that a type beta can't reach that point - note that type beta that aren't sufficient to fail high DO reach that point.

Your stores look fine though at first glance to me.

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: transposition table pseudocode

Post by jwes » Tue Aug 23, 2016 4:54 am

kbhearn wrote:your code to take cutoffs appears to have some problems at first glance

exact entries of sufficient depth can always be returned, they don't have to be inside the bounds - if you want to clamp to alpha/beta before returning that's fine (fail hard) or you can return it as is (fail soft)

on the other hand an entry type qualifier is necessary for returning a fail low based on TT entry - if you have a beta entry that says >= -2 and your alpha in current node is -1, you can't fail low based on that, it's possible that it'd also be > -1, you've gotta search :) If your logic was that a type beta can't reach that point - note that type beta that aren't sufficient to fail high DO reach that point.

Your stores look fine though at first glance to me.
This leads to another question: if you have a beta entry that says >= -2 with a depth of 9 and your alpha in current node is -1 with a depth remaining of 7, you have to search. When the search returns, do you overwrite the deeper search with the shallower one, overwrite another entry, or not save the current entry? Does it matter if it fails low or high?

User avatar
Evert
Posts: 2924
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: transposition table pseudocode

Post by Evert » Tue Aug 23, 2016 5:44 am

You always save what you just searched, so yes: overweite any existing enty. If it were any good you would not have searched the position again.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: transposition table pseudocode

Post by ZirconiumX » Tue Aug 23, 2016 6:40 am

Though I have fairly limited experience, your stores do actually have issues.

- Null move should store at original depth, not at depth - R or zero. This maximises cutoff potential, saving even a nullmove search.
- Don't store evaluations in the hash table, you'll pollute what could be useful searches with information useful only to the qsearch. Instead, use a separate eval hash table.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

zenpawn
Posts: 299
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: transposition table pseudocode

Post by zenpawn » Tue Aug 23, 2016 10:16 am

kbhearn wrote: exact entries of sufficient depth can always be returned, they don't have to be inside the bounds - if you want to clamp to alpha/beta before returning that's fine (fail hard) or you can return it as is (fail soft)
This was a recent addition to be conservative. I also read an old post wherein Robert mentioned this bounds check on exact evals. Once this bug is squashed, I'll start loosening things up again.
kbhearn wrote: on the other hand an entry type qualifier is necessary for returning a fail low based on TT entry - if you have a beta entry that says >= -2 and your alpha in current node is -1, you can't fail low based on that, it's possible that it'd also be > -1, you've gotta search :) If your logic was that a type beta can't reach that point - note that type beta that aren't sufficient to fail high DO reach that point.
Woops, that was a pseudocode error. The real code actually does the && bounds checks inside outer ifs on the entry types, like so...

Code: Select all

    if &#40;entry.type == Type.Exact&#41;
    &#123;
      if &#40;entry.eval > a && entry.eval < b&#41;
      &#123;
        return entry.eval;
      &#125;
    &#125;
    else if &#40;entry.type == Type.Beta&#41;
    &#123;
      if &#40;entry.eval >= b&#41;
      &#123;
        return b;
      &#125;
    &#125;
    else
    &#123;
      if &#40;entry.eval <= a&#41;
      &#123;
        return a;
      &#125;
    &#125;
That way, I can log more accurately, etc..

zenpawn
Posts: 299
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: transposition table pseudocode

Post by zenpawn » Tue Aug 23, 2016 10:21 am

ZirconiumX wrote: - Null move should store at original depth, not at depth - R or zero. This maximises cutoff potential, saving even a nullmove search.
Thanks. I've had it that way originally, but this bug has me locking everything down, since missing a hit is likely not the cause.
ZirconiumX wrote: - Don't store evaluations in the hash table, you'll pollute what could be useful searches with information useful only to the qsearch. Instead, use a separate eval hash table.
Good point. I do have another hash for that. It's checked at the top of evaluate() and populated at the bottom, so this is just redundant.

zenpawn
Posts: 299
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: transposition table pseudocode

Post by zenpawn » Tue Aug 23, 2016 8:49 pm

ZirconiumX wrote: - Don't store evaluations in the hash table, you'll pollute what could be useful searches with information useful only to the qsearch. Instead, use a separate eval hash table.
To clarify, you're referring to the beta cutoff in the quiesce section, right? That's how I took it this morning, but want to make sure we're on the same page. Thanks.

zenpawn
Posts: 299
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: transposition table pseudocode

Post by zenpawn » Tue Aug 23, 2016 8:53 pm

So, it seems there are no major faux pas. Of course, as you all know, that's both good and bad news when you're trying to track down an elusive bug! :)

PK
Posts: 834
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: transposition table pseudocode

Post by PK » Tue Aug 23, 2016 10:11 pm

popular source of transposition table bugs is saving score after a search has run out of time.

Post Reply