Negative alpha/beta windows: Are they useful?

[thomasahle]

(If those are already well known under a different name, I'd be grateful for a refer)

For many algorithmic search problems, such as nearest neighbour in high dimensions, the only viable algorithms have an 'approximation' band. E.g. given a query point, we may ask if there is a point within radius R or not. We can relax this to only require a negative answer if there is no point in radius c*R. That is, if the closest point is in [R, c*R] the algorithm may answer either true or false.

For chess this corresponds to, given a score interval [10, 20], distinguishing the case where the position value is less than 10 from the case where it's greater than 20. If the value is between 10 and 20 we can answer anything.
In terms of alpha/beta we can fail high if a child evaluates to more than 10.

Intuitively this should cut more aggressively than even zero-windows. Now I just wonder if it's useful for anything. Have you seen this technique being used anywhere successfully?

[bob]

(If those are already well known under a different name, I'd be grateful for a refer)

For many algorithmic search problems, such as nearest neighbour in high dimensions, the only viable algorithms have an 'approximation' band. E.g. given a query point, we may ask if there is a point within radius R or not. We can relax this to only require a negative answer if there is no point in radius c*R. That is, if the closest point is in [R, c*R] the algorithm may answer either true or false.

For chess this corresponds to, given a score interval [10, 20], distinguishing the case where the position value is less than 10 from the case where it's greater than 20. If the value is between 10 and 20 we can answer anything.
In terms of alpha/beta we can fail high if a child evaluates to more than 10.

Intuitively this should cut more aggressively than even zero-windows. Now I just wonder if it's useful for anything. Have you seen this technique being used anywhere successfully?

1. How can ANYTHING cut more aggressively than a zero-width window, since EVERYTHING either fails high or fails low.

2. You said "fail high if the child evaluates to more than 10." How/why? If beta = 20, and we are doing minimax, we want the best score possible, we would not want to just fail high on a score > alpha as we need to search the rest of the moves at this ply to see if any are greater than the just found best score. Or perhaps I did not understand what you meant?

[Evert]

For chess this corresponds to, given a score interval [10, 20], distinguishing the case where the position value is less than 10 from the case where it's greater than 20. If the value is between 10 and 20 we can answer anything.
In terms of alpha/beta we can fail high if a child evaluates to more than 10.

I don't fully understand what you want to do, but what you suggest to me sounds like an effective zero-window search with alpha as an upper bound - which is what you'd normally do in PVS anyway.

[thomasahle]

Say you are searching with beta=10 and alpha=20, that means you can fail high if you discover a child with score greater than 10. At the same time the children are allowed to fail low if their score is less than 20. This is what I mean by a negative window, which cuts more aggressively than a zero window.

Searching like this of course also gives us fewer guarantees than a positive width or zero width window. Where a zero width window can distinguish precisely between a position with a score smaller than gamma, versus one with a score greater than gamma; the negative window has an 'unknown interval' from beta to alpha, that the correct score may be in, no matter the result of the search.

What can we do with this? Well, if we know the score is within [-150, 150] and we search with beta=-50, alpha=50; we'll prove either that we are in [-150,50] or in [-50,150]. A zero window could have proven that we are either in [-150,0] or [0,150]. If we are doing a binary search for the correct score, reducing by a factor 3/2 instead of a factor 2 may be worth it if we can achieve faster searching(?)

Anyhow I was considering this in the context of search instability. If we can't trust the returned score 100% anyhow, we may as well embrace approximation and see if it saves us something. :)

[bob]

Say you are searching with beta=10 and alpha=20, that means you can fail high if you discover a child with score greater than 10. At the same time the children are allowed to fail low if their score is less than 20. This is what I mean by a negative window, which cuts more aggressively than a zero window.

Searching like this of course also gives us fewer guarantees than a positive width or zero width window. Where a zero width window can distinguish precisely between a position with a score smaller than gamma, versus one with a score greater than gamma; the negative window has an 'unknown interval' from beta to alpha, that the correct score may be in, no matter the result of the search.

What can we do with this? Well, if we know the score is within [-150, 150] and we search with beta=-50, alpha=50; we'll prove either that we are in [-150,50] or in [-50,150]. A zero window could have proven that we are either in [-150,0] or [0,150]. If we are doing a binary search for the correct score, reducing by a factor 3/2 instead of a factor 2 may be worth it if we can achieve faster searching(?)

Anyhow I was considering this in the context of search instability. If we can't trust the returned score 100% anyhow, we may as well embrace approximation and see if it saves us something.

You lost me in the first sentence. alpha = lower bound, beta = upper bound. Upper bound can't be less than lower bound. Then you lost me again when you used the term "binary search" which doesn't belong in the same sentence with alpha/beta search. The goal of alpha/beta is to establish a bound, and then prove all other moves are worse (with best ordering). Don't care about their scores at all, just prove they are worse. (or better in the case of a fail high, but we don't care how much better, just better.)

For your beta=10, alpha=20 example, what if the true score of a move is 15? Do you fail high or fail low or explode?

[thomasahle]

Say 's' is the correct value of the position we are searching, and 'r' is the value we return. Bear with me and say beta < alpha.

If s < beta, then r < beta.
If alpha < s, then alpha < r.

Hence if beta=10, alpha=20 and s=15, then the output is undefined, and we can return any value we want. This undefinedness is what allows us to fail high if we see a value greater than 10 (while maximising).


The binary search thing was just me trying to point out how the above may be useful. Another use could be wanting to check "who's winning" we might want to check if the score is below -100 or above 100. If it's in between, then either answer is fine. If we had used a zero window centered at 0, it might spend a lot of time if the correct value was actually very close to 0.

[mvk]

Say 's' is the correct value of the position we are searching, and 'r' is the value we return. Bear with me and say beta < alpha.

If s < beta, then r < beta.
If alpha < s, then alpha < r.

Hence if beta=10, alpha=20 and s=15, then the output is undefined, and we can return any value we want.

It sounds like you're proposing some variant of MTF(f), where instead of bipartitioning, you partition in threes. Correct? And instead of a positive window to do this (which is also possible), you use a negative window, where then you need researches to establish the best move if the score is in the middle section as well. Compared to the positive window, you might gain a few nodes. It might work, but I have my doubts. You're trying to get more information out of the scout search (compared to a zero window scout), which normally means more nodes must be searched. And mind that MTD(f) is not very popular in the domain of computer chess in the first place. We normally stick to PVS.

[thomasahle]

I'm actually trying to get less information. A scout search can be slow if the correct value is very close to your gamma. With negative windows there is more wiggle room without any sharp distinguishings having to be made.

I'm not partitioning into three intervals, but just two which even overlap.

I don't know if this would be any better than other types of search, if we repeat until we have a precise score. Probably not since narrowing the window iteratively gets us closer to a normal scout search. However perhaps it could be useful in certain situations where you don't need exact scores..

[mvk]

Ok I see. If you fail high on the lower beta, you still know nothing related to the higher alpha. So two overlapping partitions / less information from scout. If you want to know how it performs, it is best to try. Not knowing the exact score is acceptable in the root, as long as you know which move is best.

[thomasahle]

Right, so I wanted to test it, but I was looking for ideas on where to apply it.

Right now I'm thinking that it could be used for faster aspiration search in PVS. We'd get a chance of searching a move unnecessarily, but in case of a negative answer, we'd get it faster.

We could also use approximation for null move searches. This time placing the 'unknown' interval just above beta. Here we'd get a smaller chance for a cut, but again the search would be faster.

If you have any other ideas I should try, I'd be happy to know.