Using a Transposition Table with Zobrist Keys

[Miyagi403]

Hi,

My name is Dan, and I am developing a chess engine from scratch. I have the alphabeta function working, and have a few questions about how to implement the Transposition Table and make it work with alphabeta. I am using Zobrist keys for hashing, and if anyone has any insight on how to write a transposition table, especially how to use the 3 node types (PV, CUT, and ALL), I would love to hear some suggestions.

This is my understanding so far:

A node is a PV node if the exact value of the node was calculated (leaf nodes, and left-most nodes, basically nodes where there is not an alpha or beta cutoff.

A node is a Cut node if score >= beta in alphaBetaMax().

A node is an All node if score <= alpha in alphabetaMin().

My biggest questions are these:

1) Where in the below code do you determine if a node is a PV, Cut, or All node?
2) When retrieving the entry from the Transposition Table, and I see the type of node (PV, Cut, or All), what do I do about it?

Below is the general alphaBetaMax and alphaBetaMin structure I used (taken from WIKI)

int alphaBetaMax( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMin( alpha, beta, depthleft - 1 );
if( score >= beta )
return beta; // beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}

int alphaBetaMin( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return -evaluate();
for ( all moves) {
score = alphaBetaMax( alpha, beta, depthleft - 1 );
if( score <= alpha )
return alpha; // alpha-cutoff
if( score < beta )
beta = score; // beta acts like min in MiniMax
}
return beta;
}



Thanks everyone for all of your help.

Dan

[hyatt]

Hi,

My name is Dan, and I am developing a chess engine from scratch. I have the alphabeta function working, and have a few questions about how to implement the Transposition Table and make it work with alphabeta. I am using Zobrist keys for hashing, and if anyone has any insight on how to write a transposition table, especially how to use the 3 node types (PV, CUT, and ALL), I would love to hear some suggestions.

This is my understanding so far:

A node is a PV node if the exact value of the node was calculated (leaf nodes, and left-most nodes, basically nodes where there is not an alpha or beta cutoff.

A node is a Cut node if score >= beta in alphaBetaMax().

A node is an All node if score <= alpha in alphabetaMin().

My biggest questions are these:

1) Where in the below code do you determine if a node is a PV, Cut, or All node?
2) When retrieving the entry from the Transposition Table, and I see the type of node (PV, Cut, or All), what do I do about it?

Below is the general alphaBetaMax and alphaBetaMin structure I used (taken from WIKI)

int alphaBetaMax( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMin( alpha, beta, depthleft - 1 );
if( score >= beta )
return beta; // beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}

int alphaBetaMin( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return -evaluate();
for ( all moves) {
score = alphaBetaMax( alpha, beta, depthleft - 1 );
if( score <= alpha )
return alpha; // alpha-cutoff
if( score < beta )
beta = score; // beta acts like min in MiniMax
}
return beta;
}


Thanks everyone for all of your help.

Dan

The basic idea is that when you finish and are ready to return a value, you have 3 choices.

(1) return value > alpha and < beta. That is, by definition, a PV node (or for hashing, we call this an EXACT entry

(2) return value <= alpha. This is an ALL node. And the hash entry is called "UPPER" because the score you have is an upper bound on the bad side (the score could actually be worse than alpha, but it can not be greater than alpha).

(3) return value >= beta. This is a CUT node, and the hash entry is called "LOWER" because the score you have is a lower bound, where the real score is greater than or equal to beta...

[Miyagi403]

Thanks Hyatt,

Your reply was very helpful. I am just wondering how one would use this information when retrieving entries from the transposition table. Do you just make sure that the node you retrieved has the same type as the node you are about to search? That seems like it would be the answer, but I want to make sure. Again, thank you for your help.

Dan

[Miyagi403]

But if I am correct about just checking to make sure the node types are the same, how would you know the node you are about to search is a PV, Cut, or All node unless you actually searched it. Or am I just not understanding something basic?

[hyatt]

Thanks Hyatt,

Your reply was very helpful. I am just wondering how one would use this information when retrieving entries from the transposition table. Do you just make sure that the node you retrieved has the same type as the node you are about to search? That seems like it would be the answer, but I want to make sure. Again, thank you for your help.

Dan

OK, different subject. Now we are doing a lookup.

Goes like this:

1. Is the draft >= remaining depth of search (was this hash entry stored from a search at least as deep as the current one?)

2. If so, there are three types of entries with 3 different actions. All of these depend on the hash entry "type"

a. EXACT. Return the score from the table. When you get back to search, you do not need to search any further, you can use that score as the "search result" and return.

b. UPPER. If the value from the table, which is an "upper bound" (but is actually alpha at the time the entry was stored) is less than or equal to the current alpha value, return a "fail low" indication to search which says "just return alpha, no need to search". This test ensures that the stored "upper bound" is <= the current alpha value, otherwise we don't know whether to fail low or not.

c. LOWER. If the value from the table, which is a "lower bound" (but is actually beta at the time the entry was stored) is >= beta, return a "fail high" indication to search which says "just return beta, no need to do a search."

There is also a trick to avoid null-move searches but I thought that might confuse the issue here...

[hyatt]

But if I am correct about just checking to make sure the node types are the same, how would you know the node you are about to search is a PV, Cut, or All node unless you actually searched it. Or am I just not understanding something basic?

You don't need to know when doing a hash probe... You just take the hash score and type and go from there...

[Miyagi403]

So I read your reply, and have been trying to write some C++ like code to make sure I have the correct structure and algorithm for storing/retrieving entries, and what to do in all of the cases.

I wrote a few comments which say "Should I return here?" during the EXACT case, because I'm still not sure. Recursion is still pretty tricky for me. Please let me know where I need to restructure the code. Thanks.


void addNodeToTable(int TYPE, int SCORE, int DEPTHLEFT)
{
// add node with parameters
}

tableEntry getEntryForNode (chessBoard boardconfiguration)
{
// get the entry for the current board configuration, (if it exists)
}


int alphaBetaMax( int alpha, int beta, int depthleft )
{
if ( depthleft == 0 ) return evaluate();

for ( all moves)
{

tableEntry entry = getEntryForNode(currentBoardConfig);
bool entryLookupResult = false;

if (entry.depthleft <= depthleft)
{
if (entry.type == EXACT)
{
score = entry.score;
entryLookupResult = true;
// do I return here?
}
else if (entry.type == UPPER)
{
if (entry.score <= alpha)
{
return alpha;
}
}
else if (entry.type == LOWER)
{
if (entry.score >= beta)
{
return beta;
}
}
}

if (entryLookupResult == false)
score = alphaBetaMin( alpha, beta, depthleft - 1 );


if( score >= beta )
{
addNodeToTable(LOWER, beta); // should "beta" be "score" instead?
return beta; // beta-cutoff
}
if( score > alpha )
{
addNodeToTable(EXACT,score);
alpha = score; // alpha acts like max in MiniMax
}
}

return alpha;
}

int alphaBetaMin( int alpha, int beta, int depthleft )
{
if ( depthleft == 0 ) return -evaluate();
for ( all moves)
{

tableEntry entry = getEntryForNode(currentBoardConfig);
bool entryLookupResult = false;

if (entry.depthleft <= depthleft)
{
if (entry.type == EXACT)
{
score = entry.score;
entryLookupResult = true;
// do i return here?
}

else if (entry.type == UPPER)
{
if (entry.score <= alpha)
{
return alpha;
}
}
else if (entry.type == LOWER)
{
if (entry.score >= beta)
{
return beta;
}
}
}


if (entryLookupResult == false)
score = alphaBetaMax( alpha, beta, depthleft - 1 );

if( score <= alpha )
{
addNodeToTable(UPPER, alpha); // should "alpha" be "score" instead?
return alpha// alpha-cutoff
}
if( score < beta )
{
addNodeToTable(EXACT,score);
beta = score; // beta acts like min in MiniMax
}
}

return beta;


}

[hyatt]

That's hard to read, but at least for the EXACT case, it looks correct. And the "do I return here?" is "yes" for that section.

The key is that if you get a useful hash hit (where one of the three conditions I gave is satisfied) then search returns immediately with no further searching at that node. Otherwise, the search continues normally, although you do have the hash move from the hash hit to try as the first move searched, to improve ordering.

[Miyagi403]

I just don't see how we can return from an EXACT case, because we know the retrieved value is between the current alpha and beta values (we tested that), but what about the rest of the moves that are siblings (same parent) to that move? What if we might find a value that is better than that value? Again, this recursion stuff is tricky for me, so I may not be understanding it perfectly.

And where I commented, "Should this be "score" instead of "alpha"", and "Should this be "score" instead of beta", is there a need for change there? Sorry for all the questions. I am attaching the code that I previously pasted which you said was hard to read. If you get a chance, could you take a look at it? It is a .cpp file so you can open it in any compiler and will be easier to read.

Thanks again.

[syzygy]

I just don't see how we can return from an EXACT case, because we know the retrieved value is between the current alpha and beta values (we tested that), but what about the rest of the moves that are siblings (same parent) to that move?

The TT entry for a position stores the score (or an upper or lower bound on the score) for THAT position. The siblings of the node therefore have nothing to do with it.

It might help to look at alpha-beta as a black box, forgetting about the recursion for a moment. If v is the score of a position as determined by minimax, then alpha-beta should return:

• v, if alpha < v < beta
• alpha, if v <= alpha
• beta, if v >= beta

Now when doing alpha-beta on a particular node, the first thing you do is check if that node is in the TT with a score (of the right depth). If it is, you check whether that score already tells you the outcome. If the score is EXACT, then you already know the exact value of v, so you simply return that value (or alpha or beta depending on the case). If the score is an UPPER bound, then you know that v <= score, so you check whether also score <= alpha. If so, then v <= score <= alpha, so you return alpha. If the score is a LOWER bound, then you know that v >= score, so you check whether also score >= beta. If so, then v >= score >= beta, so you return beta.