Solving a fail low situation at the root

[Ron Murawski]

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

[jhellis3]

Yes, you misread Lucas's patch. The patch shifts the non-failing bound in the direction of the failing bound, not away from it.

EX:

SF original (-16, 16) -> (-16, 24)

SF new (-16, 16) -> (0, 24)

[bob]

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

I've tested lots of things here, but changing just the boundary that failed seems to work best. By keeping the other the same, all of the TT entries that are of type UPPER (assuming you improved beta and left alpha alone) would still work since alpha and the UPPER bound would still be compatible with failing low...

[Joerg Oster]

I've tested lots of things here, but changing just the boundary that failed seems to work best. By keeping the other the same, all of the TT entries that are of type UPPER (assuming you improved beta and left alpha alone) would still work since alpha and the UPPER bound would still be compatible with failing low...

That's exactly how Stockfish handled it until Lucas' patch.
Now the non-failing bound first gets centered in the window, and then the failing bound is widened.

[Joerg Oster]

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

[Ron Murawski]

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

[bob]

Stockfish explicitly excludes EXACT hash matches along the PV. The reason seems to make little sense since they retrieve the PV from the table anyway and it is often wrong. Worrying about one that is cut short would seem to be less of an issue than actually producing a PV where some of the moves are outright wrong.

[gladius]

Stockfish explicitly excludes EXACT hash matches along the PV. The reason seems to make little sense since they retrieve the PV from the table anyway and it is often wrong. Worrying about one that is cut short would seem to be less of an issue than actually producing a PV where some of the moves are outright wrong.

This is not true. Until a week ago, SF did prune exact hash matches along the PV. It no longer does, but that's to allow the newly added triangular pv code to work without having to add a PV hash.

[bob]

Stockfish explicitly excludes EXACT hash matches along the PV. The reason seems to make little sense since they retrieve the PV from the table anyway and it is often wrong. Worrying about one that is cut short would seem to be less of an issue than actually producing a PV where some of the moves are outright wrong.

This is not true. Until a week ago, SF did prune exact hash matches along the PV. It no longer does, but that's to allow the newly added triangular pv code to work without having to add a PV hash.

SO they are still willing to accept short PVs without the PV hash??? The triangular array won't solve that by itself...

[gladius]

Stockfish explicitly excludes EXACT hash matches along the PV. The reason seems to make little sense since they retrieve the PV from the table anyway and it is often wrong. Worrying about one that is cut short would seem to be less of an issue than actually producing a PV where some of the moves are outright wrong.

This is not true. Until a week ago, SF did prune exact hash matches along the PV. It no longer does, but that's to allow the newly added triangular pv code to work without having to add a PV hash.

SO they are still willing to accept short PVs without the PV hash??? The triangular array won't solve that by itself...

Last week, there was a patch to use the triangular array method to gather the PV instead of the hash. In the same patch, pruning exact matches in the PV was disabled, to allow full length PVs to show.