TTable questions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Henk
Posts: 5819
Joined: Mon May 27, 2013 8:31 am

TTable questions

Post by Henk » Sat Apr 11, 2015 3:17 pm

If there is a hash hit and it finds an upper bound (ubHash) in the hash table can you use that upper bound to limit the search.

For instance search (depth, lb, ub) where lb < ubHash < ub can you continue the search with ub = min (ubHash, ub). And why not ?

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: TTable questions

Post by bob » Sat Apr 11, 2015 3:39 pm

Henk wrote:If there is a hash hit and it finds an upper bound (ubHash) in the hash table can you use that upper bound to limit the search.

For instance search (depth, lb, ub) where lb < ubHash < ub can you continue the search with ub = min (ubHash, ub). And why not ?
Yes. But it won't work very often. 99+% of the search is with the window a,a+1. So if the UB is usable (draft is sufficient) and it is less than beta, then it must be less than or equal to alpha. Which means you would now not have a null-window, you would have a negatively-overlapping window. It would not make any sense to have a score s that is > beta AND < alpha at the same time. If the UB is less than the LB, you should instantly fail low. Or should you instantly fail high? There's no way to use such contradictory information, and no way for it to happen unless the search is broken. So the only place this could really happen would be where you are in a non-null window search, which is not often enough to make any difference in general, assuming you use PVS.

Edit: you will find reference to this idea in Slate/Atkin chapter of Frey's book, but in 1973 when chess 4.0 was written, nobody had yet heard of PVS, so there were no null-window searches at all and this did work pretty well.

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

Re: TTable questions

Post by hgm » Sat Apr 11, 2015 6:59 pm

Henk wrote:For instance search (depth, lb, ub) where lb < ubHash < ub can you continue the search with ub = min (ubHash, ub). And why not ?
Search instability. You should be prepared that the re-search (depth, lb, ubHash) at the same depth now and then will fail high, despite the fact that the previous search did claim the score could not be higher than ubHash. And what would you do then? Another re-search, with the true ub? To avoid complexity for minimal gain, it might be better to search with the full window the first try.

Post Reply