Page 1 of 1
Transposition Table Usage
Posted: Tue Jul 12, 2016 4:35 am
by theturk1234
Hi,
I was wondering if any of you could tell me how to use a transposition table. I already have it implemented, I just need to know when I should probe the table, when I should be saving nodes, which node types at different places in the tree, and any other advice you could give me. Your comments are greatly appreciated!
David Cimbalista
Re: Transposition Table Usage
Posted: Tue Jul 12, 2016 7:33 am
by H.G.Muller
I normally use the TT to retore the state of the node to that where I left it on the previous visit, if the information in it is useful.
Code: Select all
Search(alpha, beta, depth)
{
int bestScore;
int hashMove = INVALID;
int iterDepth = 0; // normal IID starting point
HashEntry *tt = ProbeTT();
if( tt != NULL && (tt->flags == EXACT ||
tt->score <= alpha && tt->flags == UPPER_BOUND ||
tt->score >= beta && tt->flags == LOWER_BOUND)) {
iterDepth = tt->depth;
hashMove = tt->move;
bestScore = tt->score; // to make sure we return something if tt->depth >= depth
}
while(++iterDepth <= depth) {
bestScore = -INF;
PlaceInFront(hashMove);
for(ALL_MOVES) {
MakeMove(move);
score = -Search(-beta, -max(alpha, bestScore), iterDepth-1);
UnMake();
if(score > bestScore) {
bestScore = score;
hashMove = move;
if(score >= beta) break; // beta cutoff
}
}
tt = ReplaceTT();
tt->score = bestScore;
tt->depth = iterDepth;
tt->move = hashMove;
tt->flags = (bestScore >= beta ? LOWER_BOUND : bestScore <= alpha ? UPPER_BOUND : EXACT);
}
return bestScore;
}
Re: Transposition Table Usage
Posted: Wed Jul 13, 2016 5:19 pm
by theturk1234
Ok, thanks for the response!
Another quick question: should I be probing and saving to the table in quiescence search? I'm doing it now and it's slowing down the engine.
Thanks,
David Cimbalista
Re: Transposition Table Usage
Posted: Wed Jul 13, 2016 10:18 pm
by H.G.Muller
You can only know that by testing. In my engines (all single-threaded) it always helped to probe in QS.
Re: Transposition Table Usage
Posted: Sat Jul 16, 2016 9:33 pm
by theturk1234
All right, thanks for the assistance!
David Cimbalista
Re: Transposition Table Usage
Posted: Sun Jul 24, 2016 3:33 pm
by sandermvdb
H.G.Muller wrote:You can only know that by testing. In my engines (all single-threaded) it always helped to probe in QS.
Do you use a special FLAG for quiescence? Or a separate table?
Re: Transposition Table Usage
Posted: Sun Jul 24, 2016 3:44 pm
by hyatt
Just store "draft = 0" and it will work just fine...
Re: Transposition Table Usage
Posted: Sun Jul 24, 2016 7:04 pm
by H.G.Muller
No special flag. The draft stored can be 0, 1 or 2, depending on the situation, so that 1-ply or 2-ply probes can be satisfied by them. (0 for nodes that return the static evaluation, 1 for a beta cutoff, 2 for a fail low where non-captures where futile.)