Using a Transposition Table with Zobrist Keys

[syzygy]

Regarding your code, the TT probe should take place BEFORE the "for all moves" loop, not within. (Of course you could move the check to the parent node, so that it would appear in the "for all moves loop" for each child node, but this complicates the code and doesn't seem worth it.)

Also you might want to consider replacing the two functions by a single function. Just replace alphaBetaMax and alphaBetaMin by a single alphaBeta(alpha, beta, depth) which recursively calls itself as score = -alphaBeta(-beta, -alpha, depth - 1).

[hyatt]

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.

Think about it like this:

(a) The first time you reach position P, you don't get a hash hit. So you do the complete search. At the end of the search from this position, you have 3 possible cases. (1) score > alpha and score < beta; In this case, store EXACT and score. (2) score <= alpha; in this case, store UPPER and alpha. (3) score >= beta; in this case, store LOWER and beta.

(b) the next time you reach this position, before searching anything, you do a hash probe and get a hit. You already know the result from this search, now, because that result comes from the hash table. Which means you either return hash value (EXACT), or alpha (UPPER) or beta (LOWER) and you don't need to search ANY siblings at all. This is the same position that you searched the last time, so why would you need to search it again? Just use the old search result and you are done...

[Miyagi403]

I think I get it. If i get an EXACT value for a node from the TT, then I can use that value as the score for that node, and do the two checks:

1) beta cutoff for alphabetamax(), which is v >= beta OR
alpha cutoff for alphabetamin(), which is v <= alpha
2) alpha < v < beta for both alphabetamax() and alphabetamin()

BUT, in this EXACT case, I still have to continue searching the sibling nodes (provided an alpha or beta cutoff doesn't occur in the above checks). correct?

Now, if i get an UPPER bound score from the TT, AND the depth is correct, AND score <= alpha, then you can use the score, which is the biggest of the three (current alpha, score, and v), and since the alpha cutoff will always be triggered in this case, you can return alpha, and thus no further siblings will be searched.

Similarly, if I get a LOWER bound score from the TT, AND the depth is correct, AND score >= beta, then again, use the score, which is the lowest of the three (current beta, score, and v), and since the beta cutoff will always be triggered in this case, you can return beta, and thus no further siblings will be searched.

If this is all correct, then I think I am starting to really understand this stuff. Again, thanks for your help, and I hope you will give me confirmation that my understanding is correct.

[Miyagi403]

Every time I think I understand, I realize I'm still kind of confused. Below is the code which should be the final draft. I have kept it in 2-function form, just because I've gotten used to it, and is easier for me to understand while I learn how to include the TT in it. I have also again attached the code in .cpp format to this post.

I guess my question this time pertains to something you wrote, which was:

"(b) the next time you reach this position, before searching anything, you do a hash probe and get a hit. You already know the result from this search, now, because that result comes from the hash table. Which means you either return hash value (EXACT), or alpha (UPPER) or beta (LOWER) and you don't need to search ANY siblings at all. This is the same position that you searched the last time, so why would you need to search it again? Just use the old search result and you are done..."

when you say "you don't need to search ANY siblings at all", did you mean children? In other words, did you mean, with reference to my code structure, don't go into the "for (all moves)" section, just return the value? This would make sense.


oid 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();

tableEntry entry = getEntryForNode(currentBoardConfig);
if (entry.depthleft <= depthleft)
{
if (entry.type == EXACT)
return entry.score;
else if (entry.type == UPPER && entry.score <= alpha)
return alpha;
else if (entry.type == LOWER && entry.score >= beta)
return beta;
}


for ( all moves)
{

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


if( score >= beta )
{
addNodeToTable(LOWER, beta);
return beta;
}
if( score > alpha )
{
addNodeToTable(EXACT,score);
alpha = score;
}
}

return alpha;
}


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

tableEntry entry = getEntryForNode(currentBoardConfig);

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


for ( all moves)
{

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


if( score <= alpha )
{
addNodeToTable(UPPER, alpha);
return alpha;
}
if( score > alpha )
{
addNodeToTable(EXACT,score);
beta = score;
}
}

return beta;
}

[User923005]

Every time I think I understand, I realize I'm still kind of confused. Below is the code which should be the final draft. I have kept it in 2-function form, just because I've gotten used to it, and is easier for me to understand while I learn how to include the TT in it. I have also again attached the code in .cpp format to this post.

I guess my question this time pertains to something you wrote, which was:

"(b) the next time you reach this position, before searching anything, you do a hash probe and get a hit. You already know the result from this search, now, because that result comes from the hash table. Which means you either return hash value (EXACT), or alpha (UPPER) or beta (LOWER) and you don't need to search ANY siblings at all. This is the same position that you searched the last time, so why would you need to search it again? Just use the old search result and you are done..."

when you say "you don't need to search ANY siblings at all", did you mean children? In other words, did you mean, with reference to my code structure, don't go into the "for (all moves)" section, just return the value? This would make sense.

You need to check the depth of the hash table entry. It needs to be as deep as your search request.
Since the move is already analyzed you just return the result from the table. The result in the table was stored from a previous search where all the children were examined. No need to loop again.
Your version looks a little muddled. This explanation looks correct to me:
http://www.gamedev.net/topic/570278-negascout--tt/

[hyatt]

I think I get it. If i get an EXACT value for a node from the TT, then I can use that value as the score for that node, and do the two checks:

1) beta cutoff for alphabetamax(), which is v >= beta OR
alpha cutoff for alphabetamin(), which is v <= alpha
2) alpha < v < beta for both alphabetamax() and alphabetamin()

BUT, in this EXACT case, I still have to continue searching the sibling nodes (provided an alpha or beta cutoff doesn't occur in the above checks). correct?

Now, if i get an UPPER bound score from the TT, AND the depth is correct, AND score <= alpha, then you can use the score, which is the biggest of the three (current alpha, score, and v), and since the alpha cutoff will always be triggered in this case, you can return alpha, and thus no further siblings will be searched.

Similarly, if I get a LOWER bound score from the TT, AND the depth is correct, AND score >= beta, then again, use the score, which is the lowest of the three (current beta, score, and v), and since the beta cutoff will always be triggered in this case, you can return beta, and thus no further siblings will be searched.

If this is all correct, then I think I am starting to really understand this stuff. Again, thanks for your help, and I hope you will give me confirmation that my understanding is correct.

Not correct.

If you get an exact match, why do you need to search the siblings? you already know the EXACT score. You are done... Back up one ply and continue the search as if you had actually searched from this position and backed up an exact score...

[hyatt]

Every time I think I understand, I realize I'm still kind of confused. Below is the code which should be the final draft. I have kept it in 2-function form, just because I've gotten used to it, and is easier for me to understand while I learn how to include the TT in it. I have also again attached the code in .cpp format to this post.

I guess my question this time pertains to something you wrote, which was:

"(b) the next time you reach this position, before searching anything, you do a hash probe and get a hit. You already know the result from this search, now, because that result comes from the hash table. Which means you either return hash value (EXACT), or alpha (UPPER) or beta (LOWER) and you don't need to search ANY siblings at all. This is the same position that you searched the last time, so why would you need to search it again? Just use the old search result and you are done..."

when you say "you don't need to search ANY siblings at all", did you mean children? In other words, did you mean, with reference to my code structure, don't go into the "for (all moves)" section, just return the value? This would make sense.


oid 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();

tableEntry entry = getEntryForNode(currentBoardConfig);
if (entry.depthleft <= depthleft)
{
if (entry.type == EXACT)
return entry.score;
else if (entry.type == UPPER && entry.score <= alpha)
return alpha;
else if (entry.type == LOWER && entry.score >= beta)
return beta;
}


for ( all moves)
{

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


if( score >= beta )
{
addNodeToTable(LOWER, beta);
return beta;
}
if( score > alpha )
{
addNodeToTable(EXACT,score);
alpha = score;
}
}

return alpha;
}


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

tableEntry entry = getEntryForNode(currentBoardConfig);

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


for ( all moves)
{

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


if( score <= alpha )
{
addNodeToTable(UPPER, alpha);
return alpha;
}
if( score > alpha )
{
addNodeToTable(EXACT,score);
beta = score;
}
}

return beta;
}

I meant you don't search ANYTHING. No children... No siblings. But the concept "siblings" leads me to think maybe you are not quite "here" yet.

You make a move and recursively call search. At the top of search for this new ply, you do a hash probe, and if you get a hit with sufficient depth, you may avoid searching ANYTHING here. For EXACT, you will never search anything further here, you back up the TT score and continue searching one ply back. For UPPER/LOWER, you have to check the bounds as previously mentioned, and if the bounds are good, you also back up either alpha or beta and go back to the previous ply immediately...

[Miyagi403]

Cool got it. As for hash table additions, I know when to do the UPPER and LOWER ones (alpha and beta cutoffs), but for the EXACT, do I do it where I have it right now (when a < score < b) or when I return a value, i.e. at the end of the function. I would assume the latter, and I'm going to try that, just not sure.

[hyatt]

Cool got it. As for hash table additions, I know when to do the UPPER and LOWER ones (alpha and beta cutoffs), but for the EXACT, do I do it where I have it right now (when a < score < b) or when I return a value, i.e. at the end of the function. I would assume the latter, and I'm going to try that, just not sure.

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...

[Miyagi403]

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.