Page 1 of 1

hashing, check extensions and depth

Posted: Sun May 27, 2007 8:32 pm
by adams161
hi,

I use check extensions in my program ( pulsar ) and i also hash. I turn on extensions at a variable depth, like once its searched the first 2 ply. this means pottentailly that if a depth like depth 6 is hashed and it was hashed on ply 2, before check extensions, it may not be the same deepeness of search as something searched on ply 3 to 6 depth when check extensions were on for one additional level. Is this a problem? How would you correct it? I know how deep i searched when i hash in terms of where i came from but dont offhand know how deep i searched after the depth i hashed from. Some lines would get searched deeper than others if there was check extensions activated. I'm thinking it shouldnt matter to much but wanted to get others opinions.

thanks
Mike

Re: hashing, check extensions and depth

Posted: Mon May 28, 2007 7:23 am
by hgm
Always store the true depth to which a position is searched in the hash. When you retrieve it, you can judge if this depth is sufficient for the depth you want now, taking the extensions into account. You don't care if the entry in the hash was made in an extended 5-ply search or a non-extended 6-ply search, it is the same search and so it should lead to an identical entry.

If you worry about some sub-trees being searched deeper in some cases, you would really have to store that information in the hash table. Logically it is part of the depth information. A stored depth (draft) of 6 with extensions suppressed should not be able to satisfy a request for a search of depth 6 with extensions switched on ('depth 6+'), but the latter search should not be able to satisfy a request for a 7-ply search without extensions. It is really an intermediate depth.

Re: hashing, check extensions and depth

Posted: Mon May 28, 2007 8:10 am
by Onno Garms
adams161 wrote: Some lines would get searched deeper than others if there was check extensions activated. I'm thinking it shouldnt matter to much but wanted to get others opinions.
I think this is hard to avoid and in deed should not matter too much. If you turn extensions on at say ply 9, then the same position at ply 1, 3, 5, 7, 9 all will have different results. Storing the extension information in the hash table might still be possible in this case, but when you add other search heuristics later, you will have to extend the hash table. For some heuristics, e.g. history pruning, it is not possible to store the information in the hash table.

Re: hashing, check extensions and depth

Posted: Mon May 28, 2007 8:53 am
by Chan Rasjid
Hello,

I think Muller's comment to just hash the actual depth to which a position is searched is normally sufficient in hashing and the rests will fall into proper perspectives.
...Storing the extension information in the hash table might still be possible in this case,...
I doubt anyone do this. It would add too much complexity and, even if things can be maintained logically, there may not be any benefits or elo gain even if successful.

As long as there is hashing+ pruning+extention, it is not expected that a position that is re-searched will search the same tree as conditions change. This is the unavoidable problem of search instability that may be related to what you are trying to resolved.

Best Regards,
Rasjid