If I find myself in a zero window (-alpha-1, -alpha) search and no value above beta (inside that search) was found, do I still store the TT entry at the end before returning?
int search(alpha, beta, depth, ...)
{
for all moves
returned_value = -search(-beta, -alpha)
if returned_value>beta
TTStore(beta, LOWER)
return beta (I have a fail-hard implementation)
if returned_value>alpha
alpha = returned value
if originalAlpha < alpha
TTStore(alpha, EXACT)
else
TTStore(alpha, UPPER)
}
However I think that is wrong. I think that last line should not be done if not in a PV node. If beta=alpha+1 then it seems wrong to store anything in the TT.
How do others deal with this situation?
Also note that I use a fail-hard implementation. Can that really cause problems with storing UPPER and LOWER values in the TT?
seems good to me. After you have finished searching the node, you know that no move scored above alpha, the next time you enter the node (<= depth) with a higher alpha, you can prune it using the previously gained knowledge.
The more difficult question is what bestmove to store in the case of a fail low.
Edmund wrote:
The more difficult question is what bestmove to store in the case of a fail low.
In the case of fail low you don't know which move is the best, you only know that all moves are worse than alpha. You should store only the bound without any move.
You might not know which move is best, but it could be that you know that some moves that come early in the static move ordering are very bad indeed. And it seems a waste to erase that information, so that next time you encouter this position, you will start searching these stupid moves.
E.g., suppose you have RxR, NxB and PxP at your disposal, but your Q is being attacked by a defended Pawn. Alas, rescuing the Queen by withdrawal to a safe square marginally fails low, as does the entire node.
I think there would be some benefit in starting next time with the Queen evasion, which at least could have a chance of beating the alpha threshold due to a small evaluation change after the line is extended, than insisting on the three captures that all lose you a Queen...
If the next time it is still an all-node, you haven't really lost anything by trying a non-sensical hash move first.
hgm wrote:Alas, rescuing the Queen by withdrawal to a safe square marginally fails low, as does the entire node.
He explicitly stated that he uses fail-hard framework which implies that there is no such thing as "just barely fail low". Every fail low is seen as same (exactly alpha-1).
On the other hand, one may measure the "effort" required to refute a move. Counting nodes comes to mind. The move with largest sub-tree node count is probably the hardest to refute.
Yes, I was using fail-hard. I've spent some time now and changed my whole search to be fail soft. And as per advice in this thread I am adding the UPPER entry in the TT if no move can raise the alpha.
At the moment I am not storing a move for this situation. However I do like the idea of having some heuristic to chose an interesting move to add. I will look into this.
hgm wrote:Alas, rescuing the Queen by withdrawal to a safe square marginally fails low, as does the entire node.
He explicitly stated that he uses fail-hard framework which implies that there is no such thing as "just barely fail low". Every fail low is seen as same (exactly alpha-1).
If you speak about zero-window search in a fail-hard framework then I think that every fail low means "exactly alpha" and every fail high "exactly beta (== alpha+1)". Did you mean that, or have I missed that you were talking about something different?
hgm wrote:Alas, rescuing the Queen by withdrawal to a safe square marginally fails low, as does the entire node.
He explicitly stated that he uses fail-hard framework which implies that there is no such thing as "just barely fail low". Every fail low is seen as same (exactly alpha-1).
If you speak about zero-window search in a fail-hard framework then I think that every fail low means "exactly alpha" and every fail high "exactly beta (== alpha+1)". Did you mean that, or have I missed that you were talking about something different?
