hashing in quiescent

[adams161]

i was reading the older post about differences from quiescent from regular search. two questions about hashing in quiescent. i recently implemented it, rating wise it hasnt hurt and might have helped so i dont think i screwed it up, but i have two questions.

One i orginally checked for a hash move before getting the new evaluate score in alpha beta. i felt it was more correct to test your bounds against the new score

val=evaluate();
if(val >=beta)
return beta;
else if(val>alpha)
alpha=val;

check for a hash fail high low or score.

is this correct?
Second is the depth issue. i'm counting down depths starting at 0 then -1 then -2. and i test that depth of hash is >=depth of queisc. so a -1 hash wouldnt return anything if its at the first ply or 0 depth of quiesc. ( fails depth test). but the article posted in the earlir quiesc search said there is no concept of depth in quiesc. does this mean no depth test?

otherwise my quiesc seems to conform to the article ( sorry dont have the link but its on a few posts back from today on second page the thread and article).

Mike

[jdart]

The problem with hashing in the q-search is that there are many more quiescence nodes than non q-nodes in a typical search. And the time saved by a hash hit in quiescence is much less than for a hash hit higher in the tree. So generally IMO you don't want to waste your limited hash size on storing q-nodes.

That said, I have for many years kept a small eval cache that holds recent full evaluations (it doesn't hold evals that are cut off early by futility checking in the eval code). The call to evaluate() checks the cache and returns the cached value if it is there. Depth doesn't matter for this: either the value exists in the cache or it doesn't and if does it is valid.

--Jon

[bob]

i was reading the older post about differences from quiescent from regular search. two questions about hashing in quiescent. i recently implemented it, rating wise it hasnt hurt and might have helped so i dont think i screwed it up, but i have two questions.

One i orginally checked for a hash move before getting the new evaluate score in alpha beta. i felt it was more correct to test your bounds against the new score

val=evaluate();
if(val >=beta)
return beta;
else if(val>alpha)
alpha=val;

check for a hash fail high low or score.

is this correct?

The purpose of hashing is to avoid as much effort as possible. Why not hash probe _before_ you do a positional evaluation. If you have seen this position previously, at the same depth, it seems pointless to do the evaluation work a second time around. You should store the final result as you exit this ply, and you should probe before you do _any_ work when you reach this ply. Other ways will work, but will not be quite as fast.

Second is the depth issue. i'm counting down depths starting at 0 then -1 then -2. and i test that depth of hash is >=depth of queisc. so a -1 hash wouldnt return anything if its at the first ply or 0 depth of quiesc. ( fails depth test). but the article posted in the earlir quiesc search said there is no concept of depth in quiesc. does this mean no depth test?

otherwise my quiesc seems to conform to the article ( sorry dont have the link but its on a few posts back from today on second page the thread and article).

Mike

[adams161]

From my testing i think i was seeing a lower nps but a slight depth increase, maybe a 1/2 depth. But one thing i noticed is that when i started hashing in quiet it didnt peform as well with lower hash table sizes. If you have enough hash i think its beneficial. If memory space is limited you dont want to do it. I find pulsar is playing slightly better but i've also increased its hash to compensate for the more nodes hashed.

Mike

[frankp]

............ there are many more quiescence nodes than non q-nodes in a typical search. ...............
--Jon

Now I am worried. Mine hovers around the 10% of level.

time 8.05 sec 3.26M nps (26.28M nodes)
ABnodes 23.21M (88.31%) qNodes 3.07M (11.69%)

time 7.96 sec 3.29M nps (26.15M nodes)
ABnodes 23.33M (89.23%) qNodes 2.82M (10.77%)

[adams161]

I'm not sure what mine is but its not fixed. Back awhile i set up some pruning in qsearch, if a capture free and clear plus evaluate score didnt look like it was going to improve alpha ( something like evalutatescore + captured piece value < alpha -50) i didnt try the capture. If you are not pruning captures as futile i'd say 10% is way to low. Even with pruning it definetly seems low. I think before i had any pruning and tried all captures that qsearch was like 80% of nodes.

Mike

[adams161]

i moved the hash check to above the evalluate call and eyballing its nps in a few games looked to be a 10% speed improvement or put me back simimlarly to where i was before.

[adams161]

Currently i'm clearing all hash from move to move so i figured i'd use that to my advantage in choosing a hash replacement policy. Now quiescent hash nodes can only be put on the table if the space is empty of they are replacing a quiescent node. regular search nodes can allways replace quiescent search nodes. So basicly regular search nodes have full use of the table, and quiescent search nodes dance around looking for a spot if the regular search isnt useing it. in a match between teh current pulsar and my release before this, even with a low hash, the new pulsar with quiescent hashing outscores the old pulsar.

Mike

[adams161]

One thing that comes to mind is you only score in quiesc search. so you figure your end nodes of search are 90% of your search nodes, and each one has to call quiesc. So its almost impossible to make q nodes less than 50% of search, if you are counting qnodes as any time the qfunction is called. Now if you are only counting it as a quiesc node if you have to generate and try moves, i.e you cant fail high, I dont know what that number is.

[frankp]

Yes: I am not counting the first call from ABsearch() at depth = 0.
If I do then the qnode % is >>50%, as John suggested.