Apiration window

[Don]

Something I've been meaning to ask the other program authors concerns aspiration windows.

I have always considered it a given that it helps. Komodo uses PVS search, but many programs (including the very best) use an aspiration window on top of that. Komodo does not.

So I'm questioning the wisdom of doing that. It's good to occasionally question long held beliefs and I try to make a practice of playing devils advocate with myself once in a while.

The normal method I use to determine how effective this is to implement a version that uses aspiration and time a few positions. The assumption is that the version which is faster is best.

Whenever I do this, I get a nice win for aspiration search. It appears to be a slightly faster search timed over many positions. Of course it's understood that the occasional position will search slower, but on average most positions search faster and some much faster.

However, when I actually properly test the assumption that this is right thing to do (because everybody else does it) by playing real games, I see absolutely NO improvement in the program and more often than not I see an almost imperceptible weakening (it's a real close call in this case.) It bugs me that I may be missing a small ELO gain somewhere.

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Imagine that you make some change that makes some searches faster and some searches slower but causes the times (for a given depth search) to vary much more on average. Would this strengthen your program, weaken it, or have no effect on the strength? I think it will probably weaken your program and thus the average time must be more than just slightly faster to compensate.

I say this because I believe that computer chess strength should be looked at from the point of view of what you are deficient in. In some idealistic sense you are not "good" at something in chess, you are just not as deficient. The old proverb is that the winner is the guy who made the next to the last mistake. And of course you probably cannot beat an opponent unless he makes an error. So you don't beat anyone at chess, you just wait for him to beat himself (without you doing the same.) A program that alternates between 4 and 6 ply searches will be much weaker than one that does 5 ply searches only even though I believe it will consume more time on average. I have not tested this but I'm pretty sure this will be the case because the 4 ply searches will kill it more than the 6 ply helps it. I think it will try this experiment just for fun.

So my question is whether you authors who do aspiration have really tested it thoroughly with many thousands of games to prove that it really helps? For me it does not help. And of course aspiration is slightly messy so I'm not motivated to use something that clutters up my program unless it's actually going to make my program stronger.

[zamar]

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Two points:

* You could start with huge aspiration window [prev eval - 100cp, prev eval + 100cp] which speeds up things only a little bit, but where aspiration fail low/high never happens (or when it happens the game is already decided). If this works for you, then try to make it a little bit more aggressive and so on...

* Aspiration fail highs and lows are very closely related to time management. They are good indicators when it's useful moment to use extra time. So even if the speed up would be zero, aspiration search still gives you information.

Third point:

* Each chess engine is a different beast, so what works for one, doesn't necessarily work for other.

[Don]

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Two points:

* You could start with huge aspiration window [prev eval - 100cp, prev eval + 100cp] which speeds up things only a little bit, but where aspiration fail low/high never happens (or when it happens the game is already decided). If this works for you, then try to make it a little bit more aggressive and so on...

* Aspiration fail highs and lows are very closely related to time management. They are good indicators when it's useful moment to use extra time. So even if the speed up would be zero, aspiration search still gives you information.

Third point:

* Each chess engine is a different beast, so what works for one, doesn't necessarily work for other.

These are good comments and suggestions.

The time management issue is definitely a factor - so I even tried experimenting some with this - primarily viewing a fail low as a problem that triggers extra search time. Also I realized that on a fail low you don't necessarily want to time-out. A fail low usually seems to happen pretty quickly compared to fail highs. Nevertheless I could not improve the program, so maybe your third point applies here.

I also varied the window as you suggest in your first point but it's difficult to measure anything here as the error margins are large and tens of thousands of games are required to zero in on such small improvements. I think virtually every test showed that this weakened the program but not in a statistically measurable amount - but taken together it appeared that it probably weakened the program very slightly.

[bob]

Something I've been meaning to ask the other program authors concerns aspiration windows.

I have always considered it a given that it helps. Komodo uses PVS search, but many programs (including the very best) use an aspiration window on top of that. Komodo does not.

So I'm questioning the wisdom of doing that. It's good to occasionally question long held beliefs and I try to make a practice of playing devils advocate with myself once in a while.

The normal method I use to determine how effective this is to implement a version that uses aspiration and time a few positions. The assumption is that the version which is faster is best.

Whenever I do this, I get a nice win for aspiration search. It appears to be a slightly faster search timed over many positions. Of course it's understood that the occasional position will search slower, but on average most positions search faster and some much faster.

However, when I actually properly test the assumption that this is right thing to do (because everybody else does it) by playing real games, I see absolutely NO improvement in the program and more often than not I see an almost imperceptible weakening (it's a real close call in this case.) It bugs me that I may be missing a small ELO gain somewhere.

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Imagine that you make some change that makes some searches faster and some searches slower but causes the times (for a given depth search) to vary much more on average. Would this strengthen your program, weaken it, or have no effect on the strength? I think it will probably weaken your program and thus the average time must be more than just slightly faster to compensate.

I say this because I believe that computer chess strength should be looked at from the point of view of what you are deficient in. In some idealistic sense you are not "good" at something in chess, you are just not as deficient. The old proverb is that the winner is the guy who made the next to the last mistake. And of course you probably cannot beat an opponent unless he makes an error. So you don't beat anyone at chess, you just wait for him to beat himself (without you doing the same.) A program that alternates between 4 and 6 ply searches will be much weaker than one that does 5 ply searches only even though I believe it will consume more time on average. I have not tested this but I'm pretty sure this will be the case because the 4 ply searches will kill it more than the 6 ply helps it. I think it will try this experiment just for fun.

So my question is whether you authors who do aspiration have really tested it thoroughly with many thousands of games to prove that it really helps? For me it does not help. And of course aspiration is slightly messy so I'm not motivated to use something that clutters up my program unless it's actually going to make my program stronger.

I have only tested it once, when we were looking at other "inter-iteration" changes such as making a decision to not start the next iteration if it looked to be hopeless to get anything back at all. At that time, we tried turning each "idea" off, just to sanity-check them (this let us find a few "broken" ideas that were good, but implemented improperly so that they actually hurt.) All I can say is that I kept the idea because it tested better. I do not remember how much better but am certain that it was a very small thing, not huge.

The way we do it is a bit more complicated than just choosing a window, because we have a mechanism that can repeatedly fail low or high, where on each fail we widen that window by a fixed (but increasing as the number of failures climbs) amount. We did this because of pathological positions Harry used to find in the Cray Blitz days. I am not sure I can find the best example, but it was a position where CB was winning handily, but was wildly tactical. And there were literally millions of ways our opponent could mate us if we played a wrong move (one of those positions where every move is critical, one wrong move and a win becomes a loss). On an infinite-window search, we could not get a value back in reasonable time because we had to search thru all the variations where we were getting mated before we got to the ones where we were winning. The same could happen in positions were we could win a pawn, but had to sort thru millions of pathways where we could mate our opponent but it was not forced. We developed a staged fail-high/fail-low approach and explained it in detail at one of the ACM panel discussions we used to have, and it seems that many commercial programs use this approach now. The idea is to tightly constrain the initial aspiration window, and if you fail outside that window, increase that edge, but gradually rather than just jumping to +/- infinity.

Overall, this idea is worth a few Elo, but only a few. Wish I could be more specific, but do not remember the specifics. If you ever fail high and hang until timing out, that is a position where this will help, if you increase that edge gradually. Of course, a fail high or low on the aspiration introduces overhead. And a narrower window that does not fail low or high improves efficiency. It needs tuning, but it works.

[Don]

Something I've been meaning to ask the other program authors concerns aspiration windows.

I have always considered it a given that it helps. Komodo uses PVS search, but many programs (including the very best) use an aspiration window on top of that. Komodo does not.

So I'm questioning the wisdom of doing that. It's good to occasionally question long held beliefs and I try to make a practice of playing devils advocate with myself once in a while.

The normal method I use to determine how effective this is to implement a version that uses aspiration and time a few positions. The assumption is that the version which is faster is best.

Whenever I do this, I get a nice win for aspiration search. It appears to be a slightly faster search timed over many positions. Of course it's understood that the occasional position will search slower, but on average most positions search faster and some much faster.

However, when I actually properly test the assumption that this is right thing to do (because everybody else does it) by playing real games, I see absolutely NO improvement in the program and more often than not I see an almost imperceptible weakening (it's a real close call in this case.) It bugs me that I may be missing a small ELO gain somewhere.

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Imagine that you make some change that makes some searches faster and some searches slower but causes the times (for a given depth search) to vary much more on average. Would this strengthen your program, weaken it, or have no effect on the strength? I think it will probably weaken your program and thus the average time must be more than just slightly faster to compensate.

I say this because I believe that computer chess strength should be looked at from the point of view of what you are deficient in. In some idealistic sense you are not "good" at something in chess, you are just not as deficient. The old proverb is that the winner is the guy who made the next to the last mistake. And of course you probably cannot beat an opponent unless he makes an error. So you don't beat anyone at chess, you just wait for him to beat himself (without you doing the same.) A program that alternates between 4 and 6 ply searches will be much weaker than one that does 5 ply searches only even though I believe it will consume more time on average. I have not tested this but I'm pretty sure this will be the case because the 4 ply searches will kill it more than the 6 ply helps it. I think it will try this experiment just for fun.

So my question is whether you authors who do aspiration have really tested it thoroughly with many thousands of games to prove that it really helps? For me it does not help. And of course aspiration is slightly messy so I'm not motivated to use something that clutters up my program unless it's actually going to make my program stronger.

I have only tested it once, when we were looking at other "inter-iteration" changes such as making a decision to not start the next iteration if it looked to be hopeless to get anything back at all. At that time, we tried turning each "idea" off, just to sanity-check them (this let us find a few "broken" ideas that were good, but implemented improperly so that they actually hurt.) All I can say is that I kept the idea because it tested better. I do not remember how much better but am certain that it was a very small thing, not huge.

The way we do it is a bit more complicated than just choosing a window, because we have a mechanism that can repeatedly fail low or high, where on each fail we widen that window by a fixed (but increasing as the number of failures climbs) amount. We did this because of pathological positions Harry used to find in the Cray Blitz days. I am not sure I can find the best example, but it was a position where CB was winning handily, but was wildly tactical. And there were literally millions of ways our opponent could mate us if we played a wrong move (one of those positions where every move is critical, one wrong move and a win becomes a loss). On an infinite-window search, we could not get a value back in reasonable time because we had to search thru all the variations where we were getting mated before we got to the ones where we were winning. The same could happen in positions were we could win a pawn, but had to sort thru millions of pathways where we could mate our opponent but it was not forced. We developed a staged fail-high/fail-low approach and explained it in detail at one of the ACM panel discussions we used to have, and it seems that many commercial programs use this approach now. The idea is to tightly constrain the initial aspiration window, and if you fail outside that window, increase that edge, but gradually rather than just jumping to +/- infinity.

Overall, this idea is worth a few Elo, but only a few. Wish I could be more specific, but do not remember the specifics. If you ever fail high and hang until timing out, that is a position where this will help, if you increase that edge gradually. Of course, a fail high or low on the aspiration introduces overhead. And a narrower window that does not fail low or high improves efficiency. It needs tuning, but it works.

It starts to look almost like mtd(f) the way you describe it. I used to use mtd(f) in cilkchess and it actually was better than PVS search. But it is a lot of trouble to get right.

Do you have a paper on this somewhere? I would like to take a look. I have seen positions where Komodo seems to hang.

[Don]

Something I've been meaning to ask the other program authors concerns aspiration windows.

I have always considered it a given that it helps. Komodo uses PVS search, but many programs (including the very best) use an aspiration window on top of that. Komodo does not.

So I'm questioning the wisdom of doing that. It's good to occasionally question long held beliefs and I try to make a practice of playing devils advocate with myself once in a while.

The normal method I use to determine how effective this is to implement a version that uses aspiration and time a few positions. The assumption is that the version which is faster is best.

Whenever I do this, I get a nice win for aspiration search. It appears to be a slightly faster search timed over many positions. Of course it's understood that the occasional position will search slower, but on average most positions search faster and some much faster.

However, when I actually properly test the assumption that this is right thing to do (because everybody else does it) by playing real games, I see absolutely NO improvement in the program and more often than not I see an almost imperceptible weakening (it's a real close call in this case.) It bugs me that I may be missing a small ELO gain somewhere.

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Imagine that you make some change that makes some searches faster and some searches slower but causes the times (for a given depth search) to vary much more on average. Would this strengthen your program, weaken it, or have no effect on the strength? I think it will probably weaken your program and thus the average time must be more than just slightly faster to compensate.

I say this because I believe that computer chess strength should be looked at from the point of view of what you are deficient in. In some idealistic sense you are not "good" at something in chess, you are just not as deficient. The old proverb is that the winner is the guy who made the next to the last mistake. And of course you probably cannot beat an opponent unless he makes an error. So you don't beat anyone at chess, you just wait for him to beat himself (without you doing the same.) A program that alternates between 4 and 6 ply searches will be much weaker than one that does 5 ply searches only even though I believe it will consume more time on average. I have not tested this but I'm pretty sure this will be the case because the 4 ply searches will kill it more than the 6 ply helps it. I think it will try this experiment just for fun.

So my question is whether you authors who do aspiration have really tested it thoroughly with many thousands of games to prove that it really helps? For me it does not help. And of course aspiration is slightly messy so I'm not motivated to use something that clutters up my program unless it's actually going to make my program stronger.

I decided to do the test where I play 6 ply versus the same program that randomly chooses to do a 5 or 7 ply search.

To my surprise, the 5,7 appears to be stronger. But of course it takes longer on average to make moves.

The 5,7 version takes 0.989 seconds per game on average and the 6 ply version takes 0.813 seconds per game. The 5,7 version after 3000 games is playing 33 ELO stronger. I expected the 5,7 to actually lose - and it would be losing if time was taken into consideration.

[Daniel Shawul]

What worked for me recently is to use very small windows <= 10. I believe this is related to a change i made with root move selectivity that reduces every move other than the first and those that get extended. This made it spend more effort on the first move at the root. Other pv only extensions add to that behaviour also. One could go all the way and use MTD, it is just PVS with an aspiration window of 1. BTW this reduction of root moves I did brought some unforeseen problems with it but that is irrelevant for this discussion.
So in my view, aspiration search is like iterative deepening only that in this case the window is "iterated" instead of the depth. So if ID works for you aspiration windwos should work too with a particular optimum window size.
YMMV.

[bob]

Something I've been meaning to ask the other program authors concerns aspiration windows.

I have always considered it a given that it helps. Komodo uses PVS search, but many programs (including the very best) use an aspiration window on top of that. Komodo does not.

So I'm questioning the wisdom of doing that. It's good to occasionally question long held beliefs and I try to make a practice of playing devils advocate with myself once in a while.

The normal method I use to determine how effective this is to implement a version that uses aspiration and time a few positions. The assumption is that the version which is faster is best.

Whenever I do this, I get a nice win for aspiration search. It appears to be a slightly faster search timed over many positions. Of course it's understood that the occasional position will search slower, but on average most positions search faster and some much faster.

However, when I actually properly test the assumption that this is right thing to do (because everybody else does it) by playing real games, I see absolutely NO improvement in the program and more often than not I see an almost imperceptible weakening (it's a real close call in this case.) It bugs me that I may be missing a small ELO gain somewhere.

One possibility is that the slowdown from the occasional aspiration miss cancels out the improvement. I believe this is a strong possibility.

Imagine that you make some change that makes some searches faster and some searches slower but causes the times (for a given depth search) to vary much more on average. Would this strengthen your program, weaken it, or have no effect on the strength? I think it will probably weaken your program and thus the average time must be more than just slightly faster to compensate.

I say this because I believe that computer chess strength should be looked at from the point of view of what you are deficient in. In some idealistic sense you are not "good" at something in chess, you are just not as deficient. The old proverb is that the winner is the guy who made the next to the last mistake. And of course you probably cannot beat an opponent unless he makes an error. So you don't beat anyone at chess, you just wait for him to beat himself (without you doing the same.) A program that alternates between 4 and 6 ply searches will be much weaker than one that does 5 ply searches only even though I believe it will consume more time on average. I have not tested this but I'm pretty sure this will be the case because the 4 ply searches will kill it more than the 6 ply helps it. I think it will try this experiment just for fun.

So my question is whether you authors who do aspiration have really tested it thoroughly with many thousands of games to prove that it really helps? For me it does not help. And of course aspiration is slightly messy so I'm not motivated to use something that clutters up my program unless it's actually going to make my program stronger.

I have only tested it once, when we were looking at other "inter-iteration" changes such as making a decision to not start the next iteration if it looked to be hopeless to get anything back at all. At that time, we tried turning each "idea" off, just to sanity-check them (this let us find a few "broken" ideas that were good, but implemented improperly so that they actually hurt.) All I can say is that I kept the idea because it tested better. I do not remember how much better but am certain that it was a very small thing, not huge.

The way we do it is a bit more complicated than just choosing a window, because we have a mechanism that can repeatedly fail low or high, where on each fail we widen that window by a fixed (but increasing as the number of failures climbs) amount. We did this because of pathological positions Harry used to find in the Cray Blitz days. I am not sure I can find the best example, but it was a position where CB was winning handily, but was wildly tactical. And there were literally millions of ways our opponent could mate us if we played a wrong move (one of those positions where every move is critical, one wrong move and a win becomes a loss). On an infinite-window search, we could not get a value back in reasonable time because we had to search thru all the variations where we were getting mated before we got to the ones where we were winning. The same could happen in positions were we could win a pawn, but had to sort thru millions of pathways where we could mate our opponent but it was not forced. We developed a staged fail-high/fail-low approach and explained it in detail at one of the ACM panel discussions we used to have, and it seems that many commercial programs use this approach now. The idea is to tightly constrain the initial aspiration window, and if you fail outside that window, increase that edge, but gradually rather than just jumping to +/- infinity.

Overall, this idea is worth a few Elo, but only a few. Wish I could be more specific, but do not remember the specifics. If you ever fail high and hang until timing out, that is a position where this will help, if you increase that edge gradually. Of course, a fail high or low on the aspiration introduces overhead. And a narrower window that does not fail low or high improves efficiency. It needs tuning, but it works.

It starts to look almost like mtd(f) the way you describe it. I used to use mtd(f) in cilkchess and it actually was better than PVS search. But it is a lot of trouble to get right.

Do you have a paper on this somewhere? I would like to take a look. I have seen positions where Komodo seems to hang.

I don't think the discussion about Harry's problematic position was in either of the "Using time wisely" papers. That was discussed at one of our panel discussions at an ACM event somewhere along the way.

And it is a loose form of mtd(f) except that we do not use a null or narrow window so that only about one out of every six times we change our mind, and just a small fraction of those fall outside the normal aspiration window.