Zero window TT entry

[vladstamate]

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?

Right now I do something like this:

Code: Select all

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&#40;alpha, EXACT&#41;
    else
        TTStore&#40;alpha, UPPER&#41;
&#125;

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?

Regards,
Vlad.

[vladstamate]

Hi,

I meant that *I think* that

Code: Select all

TTStore(alpha, UPPER)

line should not be done if in a zero window search.

Regards,
Vlad.

[Edmund]

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.

regards,
Edmund

[rvida]

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.

Richard

[hgm]

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.

[rvida]

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.

[vladstamate]

Hi,

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.

Regards,
Vlad.

[Sven]

Code: Select all

        if returned_value>beta
            TTStore(beta, LOWER)
            return beta (I have a fail-hard implementation)

Don't forget to fix this into "returned_value >= beta" if you haven't already. It is important for the algorithm.

Sven

[Sven]

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?

Sven

[rvida]

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?

Sven

My bad, I meant alpha, not alpha-1.