hashing question

[adams161]

hi,

I know if you fail high, i think it is, hash move > beta, you check if its still greater than beta.

If you fail low, hash move less than alpha, you check if its still less than alpha,

if you have an exact score, do you check that the score is <=beta and > alpha?

it seems if you play it out of range, it would just produce a beta cuttof. but maybe the score is not accurate anymore if its not bounded by alpha and beta.

Mike

[sje]

There are only three cases (carefully note the exact relationals):

score >= beta

score <= alpha

alpha < score < beta

The above assumes alpha < beta; if not, then there's a problem somewhere.

[adams161]

in my connect 4 bot i am violating rule 3.

i have it as

score >=beta
score <= alpha

but rule 3 is
alpha < score < beta

and i have

alpha <= score <= beta

so i'll change it. my chess program is breaking the rule too

thats one of main reasons i did connect 4, so i could see in a much simpler model then chess, the corect way to do things.

Mike

[adams161]

if i'm reading the numbers right, i've only had hasing implemented lass than 24 hours. it seems to be getting more depth with:

alpha < value < beta

than

alpha <= value <=beta

is that the case?

Mike

[bob]

hi,

I know if you fail high, i think it is, hash move > beta, you check if its still greater than beta.

If you fail low, hash move less than alpha, you check if its still less than alpha,

if you have an exact score, do you check that the score is <=beta and > alpha?

it seems if you play it out of range, it would just produce a beta cuttof. but maybe the score is not accurate anymore if its not bounded by alpha and beta.

Mike

You always honor alpha/beta. An exact score < alpha (with sufficient depth) means you want to fail low without searching. Ditto for fail high. If your exact value is > beta, clearly you want to fail high...

[adams161]

i'm confused. does this mean your disagreeing with the following

Steven Edwards
Joined: 13 Mar 2006
Posts: 1436
Location: Potholes'R'Us, NH, USA
Posted: Sat Oct 25, 2008 11:30 pm

post?

fail high if value > = beta
fail low if value <= alpha
and return score if alpha < value < beta ( not <= or >=)

assuming you have sufficient depth.

are you saying instead the last statement ( an exact score ) is:
return alpha if value <=alpha
return beta if value > = beta
else return score

Mike

[adams161]

as another follow up question, if you have an exact score, why return score only if its between alpha and beta otherwise return alpha or beta if the exact sccore ( i.e. it changed alpha in the past ) now fails high or low.

is that just good form? why cant you just return score in every case? a value less than alpha produces a beta cuttof down the road and a value > beta produces a beta cuttoff i thought down the road. is it just something that slows the chess engine down and allows more nodes to be searched than it should? So in that case it doesnt effect accuracy of search just speed of search. And does the same go for mate score? you should not return an exact mate score unless its between alpha and beta, otherwise return alpha or beta?

Mike

[Harald]

as another follow up question, if you have an exact score, why return score only if its between alpha and beta otherwise return alpha or beta if the exact sccore ( i.e. it changed alpha in the past ) now fails high or low.

is that just good form? why cant you just return score in every case? a value less than alpha produces a beta cuttof down the road and a value > beta produces a beta cuttoff i thought down the road. is it just something that slows the chess engine down and allows more nodes to be searched than it should? So in that case it doesnt effect accuracy of search just speed of search. And does the same go for mate score? you should not return an exact mate score unless its between alpha and beta, otherwise return alpha or beta?

Mike

Both methods are used and well known under the names "fail hard" and "fail soft".

Fail hard does not care too much about scores outside of alpha-beta.
It returns alpha or beta if the score is not inside the window.
With only three cases to consider
(returned_score == alpha, alpha < returned_score < beta, beta == returned_score)
it may be easier to understand and may be easier to implement.
AFAIK Bob uses fail hard in Crafty.

Fail soft tries to keep the scores outside alpha-beta.
The cutoffs should be the same but some extra coding is used to track a score < alpha.
May be you need a variable best_score_so_far or original_alpha inside the search function.
I think people hope that these scores inside the hash table are better
and there may be situations where you have an advantage from it.
Perhaps you could use a wild heuristic somewhere that uses these scores.
Or at the root level between iterative deepening searches the returned score
can influence the next search window.
I am not sure what the real benefits of this method are.

I also miss a good explanation and comparison of these two methods in the internet.
What is the correct implementation of each? Where are traps and pitfalls?
Which other typical algorithms must be adapted? What is the benefit?
The chesswiki would be a good place for this topic. I could only place
this posting there because I have too many questions myself.

Harald

[Gerd Isenberg]

as another follow up question, if you have an exact score, why return score only if its between alpha and beta otherwise return alpha or beta if the exact sccore ( i.e. it changed alpha in the past ) now fails high or low.

is that just good form? why cant you just return score in every case? a value less than alpha produces a beta cuttof down the road and a value > beta produces a beta cuttoff i thought down the road. is it just something that slows the chess engine down and allows more nodes to be searched than it should? So in that case it doesnt effect accuracy of search just speed of search. And does the same go for mate score? you should not return an exact mate score unless its between alpha and beta, otherwise return alpha or beta?

Mike

You have to distinct the "original" alpha of an node, from the "local" alpha which was already raised by best score during the search.

If you search a node with the lower bound alpha and the upper bound beta, you may
1. fail high with a lower bound score >= beta
2. fail low with an upper bound score <= "original" alpha
3. finding an exact score otherwise

Finding an exact score implies raising your local alpha by best score, which is now greater that the original alpha at the begin of that node. Thus exact score implies
"original" alpha < score < beta.

The other issue is related to fail hard versus fail soft. Fail hard restricts the returned value to the "hard" bounds alpha and beta, fail soft allows returned values outside that bounds (< alpha and > beta). Both schemes are sound. Fail soft searches less nodes, but has more issues related to search instability in conjunction with TT, pruning and reductions.

With fail soft, both score1 == beta and score2 > beta are both fail highs with a lower bound on the exact score (which might be greater). Whether score2 is really greater than score1 is another issue.

[bob]

i'm confused. does this mean your disagreeing with the following

Steven Edwards
Joined: 13 Mar 2006
Posts: 1436
Location: Potholes'R'Us, NH, USA
Posted: Sat Oct 25, 2008 11:30 pm

post?

fail high if value > = beta
fail low if value <= alpha
and return score if alpha < value < beta ( not <= or >=)

assuming you have sufficient depth.

are you saying instead the last statement ( an exact score ) is:
return alpha if value <=alpha
return beta if value > = beta
else return score

Mike

I don't see where I disagree at all. There are three possibilities...

(1) you get LOWER entry from the hash table. You stored this entry on a fail high, and all you know is that the score at that node was >= beta so you stored either beta (fail hard) or the score (fail soft). You know that the score is at least as big as that bound and most likely higher. If you compare the bound from the table to the current beta value, and the table value is >= current beta value, you fail high and stop searching.

(2) you get UPPER entry from the hash table. You stored this entry after searching all moves and not improving the alpha bound at all. So you know the alpha bound is an upper bound on the actual score, and the score might be even lower. If you compare the table bound to the current alpha value, and the table value is <= current alpha, you can fail low here and search no further.

(3) You get EXACT entry from the hash. If the value is <= alpha, you fail low immediately and do not search. If the value is >= beta, you fail high immediately and do not search. If the value is > alpha and < beta, you return the value and do not search.

All of the above assume the "draft" of the table entry is >= current remaining depth.