Using a Transposition Table with Zobrist Keys

[syzygy]

All 3 get done at the same exact place, namely at the TOP of search, before you do any searching at all, even before you try null-move search...

I thought you wrote earlier that you do it when you are ready to return a value. But now you're saying before you begin searching? Confused.

That's when you store a score in the transposition table.

The TT is there simply to prevent double work. So you probe the TT _before_ you do the work in order to check whether you can skip (or speed up) the work and you update the TT _after_ you did the work in order to prevent doing the same work in the future.

[Miyagi403]

Hey everyone,

I have been coding for a long time now, trying different versions of alphabeta with a TT, and am close to being done. I'm still a little confused about one thing:

If you are at a root node, and you retrieve an UPPER bound from the TT, and if you find that
"UPPER BOUND FROM TABLE <= alpha", you can safely return alpha. But, like I said, if you are at the root node,
can you safely use the move stored in the TT, since that corresponded to the upper bound in the table, which was less than the current alpha, and corresponds to a different move?

And, same for LOWER bound. if "LOWER BOUND FROM TABLE >= beta", you can safely return beta. But, can you safely return that move if you are at a root node, because it technically corresponds to a different "beta"?

Thanks.

[Miyagi403]

and, in the case of UPPER, if you cannot fail-low and return alpha right then and there, do you adjust alpha or beta to the entry value?

and, in the case of LOWER, if you cannot fail-high and return beta right then and there, do you adjust alpha or beta to the entry value?

[Miyagi403]

Just to make sure I'm being clear, I'm using a single alpha-beta function

int alphabeta(int alpha, int beta, int depth)
{

// TT Retrieval

for (all moves)
{
score = -alphabeta (-beta, -alpha, depth -1);

if (score > alpha)
alpha = score;
if (alpha >= beta)
return alpha;
}

// TT Storage
return alpha;

I hope this isn't too confusing.

[RobertP]

if (entry.depthleft <= depthleft) { ... }

That should be:
if (entry.depthleft >= depthleft) { ... }

[RobertP]

If you are at a root node, and you retrieve an UPPER bound from the TT, and if you find that
"UPPER BOUND FROM TABLE <= alpha", you can safely return alpha. But, like I said, if you are at the root node,
can you safely use the move stored in the TT, since that corresponded to the upper bound in the table, which was less than the current alpha, and corresponds to a different move?

And, same for LOWER bound. if "LOWER BOUND FROM TABLE >= beta", you can safely return beta. But, can you safely return that move if you are at a root node, because it technically corresponds to a different "beta"?

Root level is special. The window is initially {-INFINITY, INFINITY} and RootSearch() is required to return the exact score of the best move.
The simplest answer to your questions is "Don't do a TT lookup at root level".
Do save the best move and score into the TT at the end of RootSearch().

[syzygy]

for (all moves)
{
score = -alphabeta (-beta, -alpha, depth -1);

if (score > alpha)
alpha = score;
if (alpha >= beta)
return alpha;
}

That should be:

if (alpha >= beta)
break;

And a trivial optimization:
if (score > alpha) {
alpha = score;
if (alpha >= beta)
break;
}

[Alexander077]

Hello to everyone. I do not quite understand how works TT. Why do we have to check that the score <= alpha (in case of UpperBound) and score > = beta (in the case of Lower bound)?

[hyatt]

Hello to everyone. I do not quite understand how works TT. Why do we have to check that the score <= alpha (in case of UpperBound) and score > = beta (in the case of Lower bound)?

Let's take both possible search outcomes.

1. You completely search the current position, and you don't get a fail-high anywhere. You store a TT entry that says "this is an upper bound" and you store the value for alpha. That means you know the score is <= alpha, not greater than, otherwise you would have failed high. Now suppose you reach this same position at some other place in the tree. If the TT entry, which is an upper bound on the score, is <= your current alpha value (lower bound) you can just return alpha and not do a search, because you will again fail low. If your alpha value has changed enough, the tt entry score might not be bad enough to allow you to stop, if the current alpha value is actually < the tt bound, so you get to keep searching. If the tt value is > your current alpha value, that would create a "loop hole" here where the score could be <= the tt score, but > your current alpha, and you should NOT fail low. That's why the test is done for this bound.

2. You partially search (or completely perhaps) search the current position, and you either fail high, or you get a score > alpha. (I am going to ignore the exact score / real score case and just consider the fail-high case). Since you failed high on the tt score, you know that tt score is a lower bound on the real score and that it might actually be higher. If the tt score is >= your current beta value, you can again stop, return beta, and fail high without doing the search. If the tt score is < your current beta value, you have that same "loop hole". The score could be > the tt entry bound, but < your current beta value, and you don't want to fail high here either.

The easy way to think about this is to consider each of the above two cases. If you fail low here this time around, you'd like to fail low the next time you get here, without doing any work, if that is possible. Ditto for a fail high. It is all about "avoiding duplicated work".

[Alexander077]

Thanks for reply Hyatt. But I have another question. How return value > alpha and < beta can be true at the end of search in alphaBetaMax and alphaBetaMin since we have this blocks: if( score > alpha ) alpha = score;(AlphaBetaMax), and if( score < beta ) beta = score;(AlphaBetaMin)?