Page 1 of 2
transposition table pseudocode
Posted: Tue Aug 23, 2016 1:51 am
by zenpawn
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 (entry.type == Type.Exact && entry.eval > a && entry.eval < b)
{
return entry.eval;
}
else if (entry.type == Type.Beta && entry.eval >= b)
{
return b;
}
else if (entry.eval <= a)
{
return a;
}
}
if (quiesce)
{
eval = evaluate();
if (eval > a)
{
if (eval >= b)
{
addTransposition(zobrist, 0, b, Type.Beta);
return b;
}
a = eval;
}
}
if (null_move_allowed)
{
makeMove(null);
eval = -absearch(-b, -b + 1, depth - R - 1);
undoMove(null);
if (eval >= b)
{
addTransposition(zobrist, max(0, depth - R), b, Type.Beta);
return b;
}
}
localBest = -inf;
movelist = getMoves(quiesce);
foreach move in movelist
{
makeMove(move);
eval = -absearch(-b, -a, depth - 1);
undoMove(move);
if (eval > a)
{
if (eval >= b)
{
addTransposition(zobrist, quiesce ? 0 : depth, b, Type.Beta, move);
return b;
}
addTransposition(zobrist, quiesce ? 0 : depth, eval, Type.Exact, move);
localBest = eval;
a = eval;
}
}
if (localBest < a)
{
addTransposition(zobrist, quiesce ? 0 : depth, a, Type.Alpha);
}
return a;
}
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 6:34 am
by kbhearn
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.
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 6:54 am
by jwes
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?
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 7:44 am
by Evert
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.
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 8:40 am
by ZirconiumX
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.
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 12:16 pm
by zenpawn
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 (entry.type == Type.Exact)
{
if (entry.eval > a && entry.eval < b)
{
return entry.eval;
}
}
else if (entry.type == Type.Beta)
{
if (entry.eval >= b)
{
return b;
}
}
else
{
if (entry.eval <= a)
{
return a;
}
}
That way, I can log more accurately, etc..
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 12:21 pm
by zenpawn
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.
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 10:49 pm
by zenpawn
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.
Re: transposition table pseudocode
Posted: Tue Aug 23, 2016 10:53 pm
by zenpawn
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!
Re: transposition table pseudocode
Posted: Wed Aug 24, 2016 12:11 am
by PK
popular source of transposition table bugs is saving score after a search has run out of time.