CODEWITHSUNDEEP
algorithmartificial-intelligencechessheuristicsalpha-beta-pruning
PanJanek
PanJanek

Reputation: 6685

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

Upvotes: 4

Views: 1792

Answers (2)

TheSlater
TheSlater

Reputation: 660

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.

Upvotes: 1

TheSlater
TheSlater

Reputation: 660

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.

Upvotes: 0

Related Questions