hashing, check extensions and depth

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
adams161
Posts: 365
Joined: Sun May 13, 2007 7:55 pm
Location: Tacoma, WA USA

hashing, check extensions and depth

Post by adams161 » Sun May 27, 2007 8:32 pm

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

User avatar
hgm
Posts: 22327
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: hashing, check extensions and depth

Post by hgm » Mon May 28, 2007 7:23 am

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.

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: hashing, check extensions and depth

Post by Onno Garms » Mon May 28, 2007 8:10 am

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.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: hashing, check extensions and depth

Post by Chan Rasjid » Mon May 28, 2007 8:53 am

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
Don't believe when you're told "There's no free lunch!" There is Linux.

Post Reply