handling Exact/Alpha/Beta flag for Transposition Table
I'm adding quiescence search to my chess engine using alpha-beta prunning with transposition tables called inside MTD(f) algorithm. In my main search, after reaching depth=0 (leaf node) I call Quiescence search that is implemented as simple alpha beta prunning without transposition table (because tests showed that searching only captures works faster without TT)
I noticed something that is not covered in pseudo codes on this topic: When I'm at depth=0 (leaf) in main search and I call quiescence search function to obtain node evaluation, I think I should obtain type of evaluation too: exact, alpha or beta:
... beginning of main alpha-beta search, checking node in TT
if (depth == 0)
{
// calling quiescence search with current alpha beta
int qresult = QuiescenceAlphaBetaSearch(node, alpha, beta);
saveInTT(node, qresult.Type, qresult.Value);
}
else
{
... run alpha beta search of node.children
}
In typical examples leaf-node evaluation is stored in TT always as "exact" value, but when node evaluation is based on alpha beta search through captures and this search starts with alpha-beta boundaries that are not (-inf,+inf), I think the result of QuiescenceAlphaBetaSearch will not be always exact value and if it's stored in TT it should be marked with flag returned from quiescence search, am I correct?
I'm not really sure if passing current alpha and beta from main search to Quiescence search is mathematically correct, so I would appreciate confirmation on this topic too.
As i said the TT entries of a quiescence search will be rarely used. Because of the expensive access to the main memory, its faster to not try the TT hit and calculate the position. If you implement the hashtable without overflow lists and overwrite hash entries, you definitely overwrite only existing entries, when the new entry was found in a "better" depth. So when you begin to fill the hashtable, there is fast no option to store a TT entry, because there are better entries who have not "more" than the maximum depth like this quiescence entries.
But if you like to write quiescence nodes to the TT table nevertheless you can use the "normal" flags exact, upper-bound and lower-bound. You can use the flag "exact" when there is no alpha- or beta-cut, because a new quiescence search which starts in the same position would return the same value.
it should be marked with flag returned from quiescence search
I don't think so. How or when would you use that flag?
The value is simply you best known value at that depth, iterative deepening will replace it when needed.
There is already a protection against using the quiescence TT value in a wrong way. The TT entry stores the depth in which the value was found and therefore it will only be used when the search is in the same or deeper search-depth. As you said the TT will not be used at the leave nodes, so it doesn't harm if the value came from a quiecence search or not.
链接地址: http://www.djcxy.com/p/56330.html上一篇: expectiminimax与回溯