Hash Tables - Holding Upper & Lower Bound Information?

[Steve Maughan]

A couple of months back I had a look at Fruit 2.0's code. One of the changes was the adoption of a different type of hash table from the norm. Fabian is storing both an upper and lower bound / depth for each position.

Does anyone have any idea of the logic / benefits of such an approach? What are the key advantages / disadvantages? Also what happens if you get a contradiction i.e. upper bound is lower then the lower bound - you certainly don't get a cutoff!

All thoughts appreciated,

Steve

[Reinhard Scharnagl]

Smirf also uses both values in cached data. But entries are stored level dependent. The benefits are just there, where multiple reevaluations of the same node are done, e.g. by Smirf's intelligence feed back algorithm, which leads to multiple reinterpretations of values of identic nodes.

Reinhard.

[Rémi Coulom]

A couple of months back I had a look at Fruit 2.0's code. One of the changes was the adoption of a different type of hash table from the norm. Fabian is storing both an upper and lower bound / depth for each position.

Does anyone have any idea of the logic / benefits of such an approach? What are the key advantages / disadvantages? Also what happens if you get a contradiction i.e. upper bound is lower then the lower bound - you certainly don't get a cutoff!

All thoughts appreciated,

Steve

As far as I know, this idea was also proposed by programmers who use MTD(f). It is very important to use such a scheme with MTD(f), since the same position is often searched at the same depth, with varying values of alpha and beta.

The reason for the benefit is easy to understand: if you store only one bound, and it is, say, a lower bound, then this information will be erased from the hash table if you get an upper bound later. This information that you erased might have been valuable later in the search.

R?mi

[Chan Rasjid]

It must be better, as a hash probe enable us to have options for 2 cases
instead of just one.

A probe of a node with alpha > Lb need to be search and the result may be a fail-low, ie a UB, usually LB <UB for same depth. I am quite sure LB may sometime exceed UB due to search unavoidable instability. If the result is exact, we don't need to keep the LB.

This node may be visited again with a different alpha/beta and
if beta<LB we have an immediate cutoff; had we not retained the LB, we need to search the node as alpha < UB.

Rasjid

p/s: LB may exceed UB only if we have fail soft (?)

[Jaime Benito de Valle]

I never quite understood the logic behind max_value and min_val completely. However, I'm not very competent in this field.
In any case I believe it is better ro have the lowest and highest values

[Chan Rasjid]

Jaime,

I think it is more helpful to use max_score(upper-bound, ceiling)
and min_score(lower-bound, floor); using score because it is all about scores returned from searching all moves of a node.
score = -search(-beta,-alpha, depth...);
if after searching all moves and all scores<= alpha it is a fail-low
and we hash this node as :-
hash-score = alpha( if we use fail hard)
hash-depth = depth
hash-type = upper-bound.


In all subsequent visit to this same node, we know if we actually do
the search we cannot have any move that will give a score better
than upper-bound(your max-value)

if we are seeking for a best score between -50, +50 then
we dont need to search if the hashed upper-bound(ceiling) is -70, we cannot get better than the -50 we need.

Same style of reasoning for lower-bound in fail high.

Best regards,
Rasjid