Ron Murawski wrote:Joerg Oster wrote:Ron Murawski wrote:Joerg Oster wrote:Ron Murawski wrote:Joerg Oster wrote:Ron Murawski wrote:Ron Murawski wrote:xmas79 wrote:
I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].
For me asymmetric widening works best. I've found that the other, non-failing bound must be widened too, but only by a small amount compared to the widening of the failed bound.
A less-aggressive form of this idea has worked for Stockfish:
Code: Select all
Author: lucasart
Date: Sat Nov 8 10:47:56 2014 -0500
Timestamp: 1415461676
Be more optimistic in aspiration window
Be more optimistic wrt search instability, and set the unviolated bound
half window.
STC
LLR: 2.96 (-2.94,2.94) [-1.00,4.00]
Total: 16362 W: 3371 L: 3197 D: 9794
LTC
LLR: 2.94 (-2.94,2.94) [0.00,5.00]
Total: 21666 W: 3780 L: 3569 D: 14317
Bench: 6807896
Resolves #105
Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.
Hi Joerg,
There is no inconsistency. Please re-read my original post.
Ron
Hi Ron,
I did, several times now. Still I always come to the same conclusion.
Assume beta is the non-failing bound. Narrowing means shift bound towards alpha, and widening means shift the bound towards +infinity. When you write the non-failing bound must be widened as well, I interpreted to do the latter.
Correct me if I'm wrong.
Hi Joerg,
Let's pretend that the current bounds are 0, 10 and there is a fail-high. Let us further suppose that at this point in the search the bounds usually get widened by 50. Normal alpha-beta with aspiration usually widens *both* bounds by this amount, so the new bounds would be -50, 60. The OP wondered if using new bounds of 0, 60 would work (all of the widening on one side). I suggested that a small widening of the non-failing bound is needed (based on testing that I did about 10 years ago). 'My' new bounds would be -12, 60. My reading of the comment written by Lucas ("set the unviolated bound half window") tells me that the new Stockfish bounds would be -25, 60, which has wider bounds than what I suggested.
Or are you saying that I misread the comment by Lucas?
Ron
Hi Ron,
to stick with your example, the new Stockfish would now set the bounds to 5, 60. So yes, it seems you misread Lucas' comment.
I also tried your idea, but it failed rather quickly. See here:
http://tests.stockfishchess.org/tests/v ... 213f58926f
Hi Joerg,
It seems that my first understanding of widening of bounds was totally wrong. I originally (wrongly) widened both bounds. When I saw Lucas's comment:
"set the unviolated bound half window"
I (wrongly) assumed that the unviolated bound would only be widened by half the violated one.
In my own testing I reduced the non-failing bound adjustment close to the point of not changing it at all, but I never arrived there.
I'm amazed that Lucas's patch doesn't cause a lot of search instability. Does a Stockfish TT hash entry keep track of the bounds? (I'm purposely not looking at Stockfish code until my engine is rewritten!) Does Stockfish avoid fetching pv scores from the hash?
Ron
I think that it probably does cause some search instability and that it also probably is worse when the hash table is saturated, which is on long searches. Going even deeper then, the re-searches of possible inferior first moves after a Fail Low of the PV move become more frequent and have a higher probability of Failing High into costly PV searches. Nevertheless proving at high depths that it costs Elo is not so easy. It may not.
It can't hurt to quote the
condensed wisdom of Bruce Moreland on this topic, it deserves to be framed and hung on the wall
Search Instability
Without this, life would be fun
Search instability is something that happens when you try to write a program that is strong, as opposed to one that is perfect. There are many causes of instability, and I will discuss how various search enhancements can lead to instability, when I discuss those enhancements. A few other search techniques must take into account the possibility of instability.
An unstable search is one that returns results that don't make any sense. You have an alpha-beta window of (5, 25) and fail high. So you re-search with (24, INFINITY) and fail low. This shouldn't happen, because the fail-high indicated very clearly that the score should be 25 or better. How can you fail low?
Fact is, a lot of the things that make a chess program fast or strong do sleazy things that result in searches returning slightly different values when called with different windows, and if you aren't expecting the values you get, you can crash or have a bug that might make your program play a dumb move.
Some chess programmers can't handle the idea of search instability, and they are willing to let very good search techniques go in order to avoid it, or in order to think that they are avoiding it.
I wish it was possible to get rid of it completely, but as long as certain very basic techniques are used, it will be a problem. I think that the solution is to defend against crashes and bad behavior, then try to put it out of your mind.
I think there can be a a remedy that is fairly easy in the case of Stockfish, and I think it will work even better with the aggressive aspiration windows of the new patch. Because FL of the move at the Root are very different from FH, and trust in the PV increases with depth, trust in FL will fall with depth, there is no need for aspiration windows to be completely symmetric around the expected value of the move. Especially on deep searches. Just widen the margin a little downward, alpha can be a little lower below than beta is higher above the expected value.
In case of a Fail Low then Lucas' patch will even more aggressively cut below the previous best value ((alpha + beta)/2 is below the previous expected value of the move), but the chance of the initial Fail Low will be less. If it is a false Fail Low this smaller margin actually helps again, in theory, to achieve a Fail High after the Fail Low (Search Instability is good
)