Zero window TT entry

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
vladstamate
Posts: 161
Joined: Thu Jan 08, 2009 8:06 pm
Location: San Francisco, USA
Contact:

Zero window TT entry

Post by vladstamate » Fri Mar 05, 2010 12:35 am

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
Posts: 161
Joined: Thu Jan 08, 2009 8:06 pm
Location: San Francisco, USA
Contact:

Re: Zero window TT entry

Post by vladstamate » Fri Mar 05, 2010 12:37 am

Hi,

I meant that *I think* that

Code: Select all

TTStore&#40;alpha, UPPER&#41;
line should not be done if in a zero window search.

Regards,
Vlad.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Zero window TT entry

Post by Edmund » Fri Mar 05, 2010 5:24 am

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

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Zero window TT entry

Post by rvida » Fri Mar 05, 2010 12:17 pm

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.

Richard

User avatar
hgm
Posts: 23713
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Zero window TT entry

Post by hgm » Fri Mar 05, 2010 1:26 pm

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.

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Zero window TT entry

Post by rvida » Fri Mar 05, 2010 4:42 pm

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.

vladstamate
Posts: 161
Joined: Thu Jan 08, 2009 8:06 pm
Location: San Francisco, USA
Contact:

Re: Zero window TT entry

Post by vladstamate » Fri Mar 05, 2010 7:18 pm

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
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Zero window TT entry

Post by Sven » Sat Mar 06, 2010 10:09 am

vladstamate wrote:

Code: Select all

        if returned_value>beta
            TTStore&#40;beta, LOWER&#41;
            return beta &#40;I have a fail-hard implementation&#41;
Don't forget to fix this into "returned_value >= beta" if you haven't already. It is important for the algorithm.

Sven

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Zero window TT entry

Post by Sven » Sat Mar 06, 2010 10:16 am

rvida wrote:
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?

Sven

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Zero window TT entry

Post by rvida » Sat Mar 06, 2010 4:42 pm

Sven Schüle wrote:
rvida wrote:
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?

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

Post Reply