Aspiration window with TT question

Code, algorithms, languages, construction...

Aspiration window with TT question

Postby sandermvdb » Mon Aug 01, 2016 6:55 am

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?
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Aspiration window with TT question

Postby H.G.Muller » Mon Aug 01, 2016 8:46 am

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.
H.G.Muller
 
Posts: 179
Joined: Sun Jul 14, 2013 10:00 am

Re: Aspiration window with TT question

Postby hyatt » Mon Aug 01, 2016 9:50 pm

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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Aspiration window with TT question

Postby sandermvdb » Tue Aug 02, 2016 7:39 pm

H.G.Muller wrote: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! :?
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Aspiration window with TT question

Postby hyatt » Tue Aug 02, 2016 9:52 pm

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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Aspiration window with TT question

Postby H.G.Muller » Wed Aug 03, 2016 8:15 am

sandermvdb wrote: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.
H.G.Muller
 
Posts: 179
Joined: Sun Jul 14, 2013 10:00 am


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Google [Bot] and 2 guests