fail hard

[syzygy]

Otherwise it should pretty much return the first move and then storing doesn't hurt anyway.

It hurts if you're overwriting a move you found earlier.
It probably hurts as well if you're not reducing the random move you stored just because it was randomly stored. (Assuming you use LMR, it is unlikely you reduce hash moves.)

I think it is better to store nothing than to store a move that was the "least bad" move that score below alpha.

[bob]

In fail hard, the lazy approach is indeed to reuse "alpha" as "best_score" and update it accordingly. But often you also need to keep track of the original value of "alpha" that was valid when entering a new node, e.g. for correct tracking of the PV or to store correct "exact/lower bound/upper bound" information in the TT.

So in fact you still need two variables, one for the original alpha and one for the best score, which allows to implement fail soft and fail hard with exactly the same algorithm except for the initialization of "best_score": you set it to "alpha" in fail hard and to "-INF" in fail soft. Apart from that initialization, both fail hard and fail soft can do the recursive call to search() (or the equivalent in an iterative implementation) with "-beta, -Max(alpha, best_score)". That "Max(...)" expression looks pointless for fail hard, and of course you can replace it by "best_score" when optimizing for speed, but for the purpose of comparing the algorithms the original form could be kept.

Isn't the orinigal alpha, still the alpha of depth - 2 ?

Or -beta at depth-1...

[bob]

I don't think the "best" move should be used for anything in case alpha is not improved upon. It's basically a random move because the search has made no effort to see how bad or not-so-bad all of the "below alpha" moves are.

Sure, though pretty funny things get returned in a fail soft search and it's always been my hope that once in a while < alpha scoring turns up something in the sense of a least worst capture or so. Otherwise it should pretty much return the first move and then storing doesn't hurt anyway. Ofcourse that's something to test but I've never done that.
(My previous efforts pretty much show what happens when you code completely by intuition/do no testing at all except for programming bugs.
While ago I came up with a really fast (for me) mailbox datastructure/generator and recently I've finally felt inspired to code it up. Hence my current renewed spark of interest in computerchess. ..But I'm doing it for the C64. 8 bit 6502 assembly ftw. With a pc version on the side to wrap my head around the datastructures. But I have no plans to develop it into a full program again. ..or maybe.)

Best move at ALL nodes can be a bad thing. Rather than choosing a random move to search first the next time you reach this position, you could do better with normal move ordering, starting with good captures and working your way down through killers. Any "best move" you remember will be searched first. It really needs to be good most of the time.

[bob]

Otherwise it should pretty much return the first move and then storing doesn't hurt anyway.

It hurts if you're overwriting a move you found earlier.
It probably hurts as well if you're not reducing the random move you stored just because it was randomly stored. (Assuming you use LMR, it is unlikely you reduce hash moves.)

I think it is better to store nothing than to store a move that was the "least bad" move that score below alpha.

There is one trick that does work. Store the FIRST move you searched first. Why? This would be one of two possible choices.

(1) the best move from a hash hit which did not terminate the search, but it did suggest a decent move;

(2) the first move you actually search, and what better move to search first the next time you try a search from this same position? And since you can search the move before generating any captures or anything, sometimes the payoff is there.

Of the two, (2) is a minor speed optimization, where (1) is a more significant search efficiency improvement caused by trying a better move first.

[Sven]

In fail hard, the lazy approach is indeed to reuse "alpha" as "best_score" and update it accordingly. But often you also need to keep track of the original value of "alpha" that was valid when entering a new node, e.g. for correct tracking of the PV or to store correct "exact/lower bound/upper bound" information in the TT.

So in fact you still need two variables, one for the original alpha and one for the best score, which allows to implement fail soft and fail hard with exactly the same algorithm except for the initialization of "best_score": you set it to "alpha" in fail hard and to "-INF" in fail soft. Apart from that initialization, both fail hard and fail soft can do the recursive call to search() (or the equivalent in an iterative implementation) with "-beta, -Max(alpha, best_score)". That "Max(...)" expression looks pointless for fail hard, and of course you can replace it by "best_score" when optimizing for speed, but for the purpose of comparing the algorithms the original form could be kept.

Isn't the orinigal alpha, still the alpha of depth - 2 ?

Or -beta at depth-1...

You guys may be right in an iterative approach. But the "recursive guys" have no access to those values, they get "alpha" and "beta" as parameters. (EDIT: Unless they use the same array style for alpha/beta as it is required for iterative search, but who does that ...)

[Sven]

correct me whether I'm wrong, but I'm I don't use originalAlpha in my failsoft.
I set the type of the node to typeScoreLowerThanAlpha entering the search and then I change it to typeExact when I check if the score>alpha
at the end of each iteration.
Just before saving it to the TranspositionTable I cheched if score>=beta, if it's true i set the type to typeScoreHigherThanBeta

Right for fail soft, there your "alpha" is always "original_alpha". But here my point was about fail hard where you can't do that check "if (best_score > alpha)" unless you keep alpha unchanged and track best_score as a separate variable.

[syzygy]

Otherwise it should pretty much return the first move and then storing doesn't hurt anyway.

It hurts if you're overwriting a move you found earlier.
It probably hurts as well if you're not reducing the random move you stored just because it was randomly stored. (Assuming you use LMR, it is unlikely you reduce hash moves.)

I think it is better to store nothing than to store a move that was the "least bad" move that score below alpha.

There is one trick that does work. Store the FIRST move you searched first. Why? This would be one of two possible choices.

(1) the best move from a hash hit which did not terminate the search, but it did suggest a decent move;

(2) the first move you actually search, and what better move to search first the next time you try a search from this same position? And since you can search the move before generating any captures or anything, sometimes the payoff is there.

Of the two, (2) is a minor speed optimization, where (1) is a more significant search efficiency improvement caused by trying a better move first.

My suggestion (store nothing) corresponds to (1): don't overwrite the old hash move if there is one.

(2) is not unreasonable, but seems to have the disadvantage that the search has no clue whether the hash move is likely a good move or whether the hash move was simply the move that was searched/generated first in a previous iteration. If the search knows there is no good move, it could choose to do internal iterative deepening to find one.

[bob]

In fail hard, the lazy approach is indeed to reuse "alpha" as "best_score" and update it accordingly. But often you also need to keep track of the original value of "alpha" that was valid when entering a new node, e.g. for correct tracking of the PV or to store correct "exact/lower bound/upper bound" information in the TT.

So in fact you still need two variables, one for the original alpha and one for the best score, which allows to implement fail soft and fail hard with exactly the same algorithm except for the initialization of "best_score": you set it to "alpha" in fail hard and to "-INF" in fail soft. Apart from that initialization, both fail hard and fail soft can do the recursive call to search() (or the equivalent in an iterative implementation) with "-beta, -Max(alpha, best_score)". That "Max(...)" expression looks pointless for fail hard, and of course you can replace it by "best_score" when optimizing for speed, but for the purpose of comparing the algorithms the original form could be kept.

Isn't the orinigal alpha, still the alpha of depth - 2 ?

Or -beta at depth-1...

You guys may be right in an iterative approach. But the "recursive guys" have no access to those values, they get "alpha" and "beta" as parameters. (EDIT: Unless they use the same array style for alpha/beta as it is required for iterative search, but who does that ...)

I was talking a non-algorithmic approach. You can "see" those values with some work. The stack is clearly visible, if you know how to look. Painful, but doable.

[bob]

Otherwise it should pretty much return the first move and then storing doesn't hurt anyway.

It hurts if you're overwriting a move you found earlier.
It probably hurts as well if you're not reducing the random move you stored just because it was randomly stored. (Assuming you use LMR, it is unlikely you reduce hash moves.)

I think it is better to store nothing than to store a move that was the "least bad" move that score below alpha.

There is one trick that does work. Store the FIRST move you searched first. Why? This would be one of two possible choices.

(1) the best move from a hash hit which did not terminate the search, but it did suggest a decent move;

(2) the first move you actually search, and what better move to search first the next time you try a search from this same position? And since you can search the move before generating any captures or anything, sometimes the payoff is there.

Of the two, (2) is a minor speed optimization, where (1) is a more significant search efficiency improvement caused by trying a better move first.

My suggestion (store nothing) corresponds to (1): don't overwrite the old hash move if there is one.

(2) is not unreasonable, but seems to have the disadvantage that the search has no clue whether the hash move is likely a good move or whether the hash move was simply the move that was searched/generated first in a previous iteration. If the search knows there is no good move, it could choose to do internal iterative deepening to find one.

I only do IID on actual PV nodes, nowhere else. I'm not sure the best move stored there could ever be anything other than (a) a real best move from last iteration since I certainly follow that first; (b) an IID search result although I am not quite sure how this might happen unless a fail-high at the root triggers a re-search. I don't see very many IID searches in Crafty, mainly when something goes wrong at the root like a fail high or fail low, suggesting move ordering is broken already..

[jdart]

I use fail hard in the sense that "best_score" is initialized to alpha at the start of the search, and normally a call to the search routine will not return scores < alpha. But I am not consistent about this and can return scores > beta (which of course is < alpha in the parent node). This is probably broken although the magnitude of any effect is not clear. As it happens I am looking into fixing this.

There are a lot of possible exits from search in a typical program: static null pruning, razoring, null move, etc. not to mention all the exits from the normal search itself so it is easy to be inconsistent.

--Jon