Returning values of beta cutoffs

[bhlangonijr]

It might be a silly question, but there we go...
By inspecting chess programs sources, whenever occurs a beta cutoff some of them:
1) returns beta and stores it in the hash as a lower bound value (Sloppy, Pawny, ...);
2) returns the score backed up by the search and stores it in the hash as a lower bound value (Stockfish, Robbolito, etc);
3) There are even some programs that stores in the hash the score backed up by the search and returns beta (Danasah, Redqueen, ...).

My question is: Is there any implication by choosing any of these options?

Thanks,

[rbarreira]

There are two ways of implementing alpha-beta: fail-soft and fail-hard.

Fail-hard means you never return a score out of the expected bounds ( alpha <= x <= beta ). Fail-soft means you can return any score.

To qualify as fully fail-soft, a search algorithm must always return scores which are as high or as low as possible. It's not enough to return scores above beta, as an ALL node above would turn it into a fail-hard score (i.e. = alpha). This means that you need an extra variable in the search function, which records the best score found so far even if it's below alpha.

They are exactly equivalent from an alpha-beta point of view, since alpha-beta only checks if the score is >= beta, <= alpha or in between alpha and beta. But when you add transposition tables into the mix, fail soft records more accurate bounds than fail-hard which should somewhat improve performance.

In a PVS-type search, fail soft can also return more accurate scores that you can use to better choose the window of a subsequent confirmation search.

PS: I don't see the sense of option 3... if you have a better bound to return, why not return it?

[bhlangonijr]

There are two ways of implementing alpha-beta: fail-soft and fail-hard.

Fail-hard means you never return a score out of the expected bounds ( alpha <= x <= beta ). Fail-soft means you can return any score.

To qualify as fully fail-soft, a search algorithm must always return scores which are as high or as low as possible. It's not enough to return scores above beta, as an ALL node above would turn it into a fail-hard score (i.e. = alpha). This means that you need an extra variable in the search function, which records the best score found so far even if it's below alpha.

They are exactly equivalent from an alpha-beta point of view, since alpha-beta only checks if the score is >= beta, <= alpha or in between alpha and beta. But when you add transposition tables into the mix, fail soft records more accurate bounds than fail-hard which should somewhat improve performance.

In a PVS-type search, fail soft can also return more accurate scores that you can use to better choose the window of a subsequent confirmation search.

Hi Ricardo, thanks for the response.

Ok I read that on chess programming wiki.

PS: I don't see the sense of option 3... if you have a better bound to return, why not return it?

That's why I'm asking, I use PVS + ZWS in my engine and it always is doing worse in tests if I return the score backed up by the search. It might be a bug though...

[rbarreira]

That's why I'm asking, I use PVS + ZWS in my engine and it always is doing worse in tests if I return the score backed up by the search. It might be a bug though...

It seems quite strange that a more accurate score would slow things down. Are you doing any complex pruning based on the scores, or is it pretty much just straightforward PVS?

[bhlangonijr]

That's why I'm asking, I use PVS + ZWS in my engine and it always is doing worse in tests if I return the score backed up by the search. It might be a bug though...

It seems quite strange that a more accurate score would slow things down. Are you doing any complex pruning based on the scores, or is it pretty much just straightforward PVS?

I have some pruning stuffs like razoring, static null move pruning, regular null move pruning and futility. The strange thing is if I return the score outside the bounds - backed up by search - it fix some search instabilities I usually have when running my engine against some test positions. But surprisingly it does much worse when testing against older versions...

You can see my search class here:

http://redqueenchess.svn.sourceforge.ne ... iew=markup

[bob]

It might be a silly question, but there we go...
By inspecting chess programs sources, whenever occurs a beta cutoff some of them:
1) returns beta and stores it in the hash as a lower bound value (Sloppy, Pawny, ...);
2) returns the score backed up by the search and stores it in the hash as a lower bound value (Stockfish, Robbolito, etc);
3) There are even some programs that stores in the hash the score backed up by the search and returns beta (Danasah, Redqueen, ...).

My question is: Is there any implication by choosing any of these options?

Thanks,

Barely makes any difference. "fail soft" is the idea of returning scores < alpha or > beta. It is important in mtd(f) searches as it gives you an idea of how far to shift the bound to get closer to the true score. Otherwise, it doesn't make much if any difference at all...

[rbarreira]

It might be a silly question, but there we go...
By inspecting chess programs sources, whenever occurs a beta cutoff some of them:
1) returns beta and stores it in the hash as a lower bound value (Sloppy, Pawny, ...);
2) returns the score backed up by the search and stores it in the hash as a lower bound value (Stockfish, Robbolito, etc);
3) There are even some programs that stores in the hash the score backed up by the search and returns beta (Danasah, Redqueen, ...).

My question is: Is there any implication by choosing any of these options?

Thanks,

Barely makes any difference. "fail soft" is the idea of returning scores < alpha or > beta. It is important in mtd(f) searches as it gives you an idea of how far to shift the bound to get closer to the true score. Otherwise, it doesn't make much if any difference at all...

With fail-soft you may know whether a move results in checkmate even with a zero-window search around a low score. What's the point of throwing away such data when it's so easy to get?

Considering that chess engines are apparently so near a local maximum that people spend time going for 1-5 elo point changes, I would think that fail soft can easily be worth it.

[Mincho Georgiev]

It might be a silly question, but there we go...
By inspecting chess programs sources, whenever occurs a beta cutoff some of them:
1) returns beta and stores it in the hash as a lower bound value (Sloppy, Pawny, ...);
2) returns the score backed up by the search and stores it in the hash as a lower bound value (Stockfish, Robbolito, etc);
3) There are even some programs that stores in the hash the score backed up by the search and returns beta (Danasah, Redqueen, ...).

My question is: Is there any implication by choosing any of these options?

Thanks,

This was in old versions of pawny, when I was still experimenting with the fail-hard framework. With the couple of thousands games of testing I got rid of it completely (as well as the "bounding" in tt). Currently (and best IMO) the returned value is the value of the node (search). It's simple. It comes down not to the returned value in particular, but to the way it's being manipulated (move ordering, storing, e.t.c.). In my code, fail-soft don't work as well, since I don't do anything special with values lower than alpha. So I'm doing it "the 3rd way"

[michiguel]

There are two ways of implementing alpha-beta: fail-soft and fail-hard.

Fail-hard means you never return a score out of the expected bounds ( alpha <= x <= beta ). Fail-soft means you can return any score.

To qualify as fully fail-soft, a search algorithm must always return scores which are as high or as low as possible. It's not enough to return scores above beta, as an ALL node above would turn it into a fail-hard score (i.e. = alpha). This means that you need an extra variable in the search function, which records the best score found so far even if it's below alpha.

They are exactly equivalent from an alpha-beta point of view, since alpha-beta only checks if the score is >= beta, <= alpha or in between alpha and beta. But when you add transposition tables into the mix, fail soft records more accurate bounds than fail-hard which should somewhat improve performance.

In a PVS-type search, fail soft can also return more accurate scores that you can use to better choose the window of a subsequent confirmation search.

Hi Ricardo, thanks for the response.

Ok I read that on chess programming wiki.

PS: I don't see the sense of option 3... if you have a better bound to return, why not return it?

That's why I'm asking, I use PVS + ZWS in my engine and it always is doing worse in tests if I return the score backed up by the search. It might be a bug though...

Correct. When in doubt, fail hard. Fail soft is a source of potential bugs if you are not aware of certain things. If you are aware of those, then it is ok but the performance should be the same. Then the question is, why not fail hard . Fail soft may help you if you use the return scores as a hint for something. For instance, threats. If you do not do that, the performance should be identical.

BE CAREFUL: if you search every single node in an ALL node, there is no risk to return score as a bound. But if you do not search every node, you cannot know with certainty whether that bound was correct. It is possible that another move you did not search may improve it. What "ALL" nodes do you not search completely? quies nodes, when you do delta pruning, leaf nodes when you do futility pruning.

The problem is when you return to this node, with different alpha and betas, and take the score+bound from the hash table. Now, that wrong bound may be able to give a wrong cutoff. The combination of careless fail-soft with hash table could give you very nasty and difficult to trace bugs.

The solution in those cases (delta pruning, futility nodes) is NOT to return the score, but to take into account the safety margin you were using. Even safer, if you do not even want to think about it, return alpha and fail hard.

You can still fail hard in certain place and soft in others (checkmates and stalemates) if you could use that information. It is very interesting to check the same program with fail hard and fail soft as you do. If there is a huge discrepancy, there is a bug somewhere.

Miguel

[rbarreira]

I wouldn't say that fail soft can be a source of bugs per se. But maybe it can expose latent bugs which are already in your code.