Aspiration window with TT question

[sandermvdb]

I've tried to add aspiration windows to my iterative deepening code but there is something I don't understand: suppose you start a search at a particular depth with a small window. This could cause cutoffs which are stored in the transposition-table. When the search is done the code checks that the score is not within alpha and beta and if so, a re-search is done with larger boundaries. The problem I see is that this next search will be influenced by (bad) TT-values so cutoffs will occur which should not occur...
I also experience this in the following way: sometimes I don't have an EXACT TT value for extracting the PV, even at ply 0!
Am I missing something?

[H.G.Muller]

With a properimplementation of the TT this cannot happen. E.g. if the initialsearch has window {-50,+50}, you will get cutoffs for score > 50, say 60. But cutoffs are lower bounds. If you enlarge the windowto{-100,+100} (say) for a re-search, and you hit upon that entry, you will find a lower bound of +60. Compared to the new search window this will be a useless bound. To use a TT result it should be a lower bound >= beta, an upper bound <= alpha, or an exact value between alpha and beta. 60 is between alpha (-100) and beta (+100), but it was not an exact value, because when it was obtained its was > beta.

So the re-search cannot use the score contained in the TT entry. It can use the move for sorting purposes. Most engines do this, although it is not obvious that it would always be helpful. A move good enough to score +60 might not be good enough to score +100, while there could be moves that score +120, which you did not get to on the previous search because you were happy with the +60. In principle the most useful info you could get from that hash move is that all moves you would normally search before it must have had a score below +60, so certainly below +100, so that re-searching those seems a waste of time. So you could not only sort the hashmove in front, but actually all moves before it to the back. I don't know if anyone does that. It might not save you as much as it looks, because all the re-searches of these moves would likely give immediate hash hits in the daughter nodes that would be sufficient for a hash cutoff.

[hyatt]

Actually there can be a problem.

Simple case: you search very deeply while pondering and store entries, most of which are >= beta or <= alpha. Your opponent plays a different move and you start getting hash hits that suggest a fail high or fail low, but when you relax the bound, you can't see nearly deeply enough to actually see why it failed high on that deep search. So you fail high, then you fail low, and look confused.

[sandermvdb]

With a properimplementation of the TT this cannot happen. E.g. if the initialsearch has window {-50,+50}, you will get cutoffs for score > 50, say 60. But cutoffs are lower bounds. If you enlarge the windowto{-100,+100} (say) for a re-search, and you hit upon that entry, you will find a lower bound of +60. Compared to the new search window this will be a useless bound. To use a TT result it should be a lower bound >= beta, an upper bound <= alpha, or an exact value between alpha and beta. 60 is between alpha (-100) and beta (+100), but it was not an exact value, because when it was obtained its was > beta.

I am trying to understand your comment.
Can you have a look at the negamax with TT implementation at wikipedia?
https://en.wikipedia.org/wiki/Negamax#N ... ion_tables

This is how my engine works but it seems different than your comment!

[hyatt]

Normally you don't see a lot of fail highs and fail lows in the same search. UNLESS you use mtd(f) which is where the two-bound tables originated, since you keep re-searching the same iteration with a zero width window where the window shifts around. It is quite common to see a search fail high, followed by a fail low when the window is shifted. Keeping both bounds makes a lot of sense.

In a normal PVS search, this is not very common and the second bound is generally not very helpful. In fact, it can be harmful since it takes memory and makes a table entry larger...

But testing with it is always a good idea to see if it helps your search.

His explanation of how to use the bounds is straight out of hash-table 101. You can't fail low when you have an UPPER bound table entry unless the upper bound from the table is less than or equal to current alpha bound. Ditto for a LOWER bound table entry where the table bound has to be greater than or equal to beta, otherwise you can't use the entry.

[H.G.Muller]

Can you have a look at the negamax with TT implementation at wikipedia?
https://en.wikipedia.org/wiki/Negamax#N ... ion_tables

This is how my engine works but it seems different than your comment!

This seems to be an implementation that shrinks the search window to bounds from earlier searches transferred through the TT. I would not recommend that, because it easily backfires in case there is search instability.(E.g. if the earlier search gave a lower bound of +60, and the window is now {-100,100}, and you correct that to {60, 100}, search again, and find (say) a score of +50, the +50 is really an upper bound obtained from a low-failing search. But because it is inside the original window {-100, 100}, the caller would interpret it as an exact score, and make the branch the new PV. While in reality the score could be arbitrary low. So horrible blunders could become PV with a good score. So unless you take special action on scores between the original window limit and the one found in the TT, like ordering a re-search, you invited trouble.)

Without search instability things would be similar to my description. The result from the aspirated search would increase alpha (because it was a lower bound) to +60, but not enough to get above the new beta of +100. So it wouldnot be used forcutting off the branch.