Restarting iterative deepening

[jwes]

There are several possible sources of this "25 elo". My time management which reacts to fail lows significantly, but without aspiration there are zero fail-lows, which negates part of that fairly well-tuned code (crafty's "pseudo-easy-move/hard-move" approach)...

This is why playing games is really the wrong approach to measure this. This is just a tree-size issue, and measuring time-to-depth on some 10,000 positions should give you a much more reliable result, in a fraction of the time (10,000 positions ~ 100 games...).

I am not sure that is so reliable. A 50 move game is far different from 50 independent positions. Hash table. move ordering. time accumulation across positions... All play into how this works, in my case... Not to mention how things are connected with respect to evaluation (move to move sees relatively consistent scores, etc).

It is a reliable way to answer a different question, not how aspiration windows affect playing strength, but how aspiration windows affect tree size.

[hgm]

Well, if it is a concern that in a game you usually start a search with a hash table loaded with the remains of a previous search, this still can be tested directly by not using isolated test positions, but letting it run through a few test games, analyzing each position to the same depth as it was analyzed in the original game, and timing how long that takes.

[bob]

There are several possible sources of this "25 elo". My time management which reacts to fail lows significantly, but without aspiration there are zero fail-lows, which negates part of that fairly well-tuned code (crafty's "pseudo-easy-move/hard-move" approach)...

This is why playing games is really the wrong approach to measure this. This is just a tree-size issue, and measuring time-to-depth on some 10,000 positions should give you a much more reliable result, in a fraction of the time (10,000 positions ~ 100 games...).

I am not sure that is so reliable. A 50 move game is far different from 50 independent positions. Hash table. move ordering. time accumulation across positions... All play into how this works, in my case... Not to mention how things are connected with respect to evaluation (move to move sees relatively consistent scores, etc).

It is a reliable way to answer a different question, not how aspiration windows affect playing strength, but how aspiration windows affect tree size.

Yes, but as I said, aspiration window affects other parts of the program. IE fail lows can trigger an alteration in time usage. So JUST reducing tree size is not the goal I am trying to reach. Everything is about playing strength in games...

[hgm]

It seems to me that if you would use a larger-than-necessary tree size just to provide your time management with clues, you would be putting the horse behind the cart. I would go for minimal tree size first, and then optimize my time management based on its behavior. It isn't so difficult to derive clues for when extra time would be useful from a non-aspirated search. If you insist that the tree size is optimized using the existing time management, and that the time management is optimized using the existing search, that is as good as a guarantee you will never make any progress.

[bob]

It seems to me that if you would use a larger-than-necessary tree size just to provide your time management with clues, you would be putting the horse behind the cart. I would go for minimal tree size first, and then optimize my time management based on its behavior. It isn't so difficult to derive clues for when extra time would be useful from a non-aspirated search. If you insist that the tree size is optimized using the existing time management, and that the time management is optimized using the existing search, that is as good as a guarantee you will never make any progress.

This is just one of a dozen decisions. I have been pondering for longer than my original target when my opponent moves. I am stuck on searching the first move. Should I immediately stop or continue? If I am not in the middle of resolving a fail-low, I stop immediately. The time allocation stuff is based on tree size, # of pv changes, etc, but that is a different decision. This one only applies on this pondering scenario. But it turns out it is worth doing, among other things that I also do (i.e. fails of any kind instantly affect the time budget for this move. But if I don't fail, that can't happen. Another plus for aspiration.

[hgm]

It should not be so difficult in to see in a non-aspirated search if a very low score is propagating towards you along the PV, or a very high score. You don't have to actually wait for that score to arrive in the root to see that the search of the PV move is taking so long because of a looming fail low. If your strategy was to allow the time for the fail low to resolve, you could just give extra time (within reason) to wait for the search of the PV move to finish.

[bob]

It should not be so difficult in to see in a non-aspirated search if a very low score is propagating towards you along the PV, or a very high score. You don't have to actually wait for that score to arrive in the root to see that the search of the PV move is taking so long because of a looming fail low. If your strategy was to allow the time for the fail low to resolve, you could just give extra time (within reason) to wait for the search of the PV move to finish.

I don't think it is that easy. You can see that something is propagating back up one path, but you can't tell how far it will go until it gets back to the root. And that is a slow process to boot. Before you get a score back to the root, you have to evaluate ALL sibling branches at ply=2. A fail low only has to evaluate one, so it happens much quicker... And can be used to raise a flag if you want...

[hgm]

Well, at ply=2 you would already know the aspirated search would have given a fail low in the root in an aspirated search after the first move there scores higher than what you would have set as aspiration window. The sibblings can only make it worse, so there is no need to wait for those. The real problem is at ply=4. When a move scores above the aspiration margin there, switching to a better move at ply=3 could still save the day, and when it does, you would have wasted time on searching sibblings at ply=4 to figure out the exact best score there, rather than the lower bound the first move gave you, before you would know that. But this is already pretty deep in the tree.

Note that an alternative would be to do a null-window search at the lower limit of the aspiration window before doing an open-window search. Then you would know even earlier whether you are going to fail low or not.

I think the more interesting thing, however, is what the optimum way to apply aspiration would be. There is something inconsistent in what you (and Wesley) are doing, which suggests that it will not be optimal, and can be improved further:

You both found that it is better not to change move after the PV node fails low on the aspirated search, but immediately re-search it with open window. But in this strategy, at ply=3 the aspirated search would switch move in the PV node, after the PV move failed low. Now if it is better to not switch move at ply=1, how could it be better to switch move at ply=3? AFter all, two moves later, if both sides play the expected moves, ply=3 will have become the new ply=1, and we already know that it is better not to switch move there.

So it seems that it coud also be better to not switch move after a fail low at ply=3, but imediately open the window there, and re-search. If you would do that at every level, however, would basically do away completely with aspiration, and only add the feature that when a PV move fails high, the parent node is informed of this (without using the information) before the sibblings are searched. So this cannot be optimal either.

The real question thus is: "what is the ply level where you have to switch from immediate re-search of a low-failing PV move to trying sibblings first?". And would this depend on the window width? This is why I proposed the "tapered auto-aspiration search" above.

[bob]

Well, at ply=2 you would already know the aspirated search would have given a fail low in the root in an aspirated search after the first move there scores higher than what you would have set as aspiration window. The sibblings can only make it worse, so there is no need to wait for those. The real problem is at ply=4. When a move scores above the aspiration margin there, switching to a better move at ply=3 could still save the day, and when it does, you would have wasted time on searching sibblings at ply=4 to figure out the exact best score there, rather than the lower bound the first move gave you, before you would know that. But this is already pretty deep in the tree.

Note that an alternative would be to do a null-window search at the lower limit of the aspiration window before doing an open-window search. Then you would know even earlier whether you are going to fail low or not.

I think the more interesting thing, however, is what the optimum way to apply aspiration would be. There is something inconsistent in what you (and Wesley) are doing, which suggests that it will not be optimal, and can be improved further:

You both found that it is better not to change move after the PV node fails low on the aspirated search, but immediately re-search it with open window. But in this strategy, at ply=3 the aspirated search would switch move in the PV node, after the PV move failed low. Now if it is better to not switch move at ply=1, how could it be better to switch move at ply=3? AFter all, two moves later, if both sides play the expected moves, ply=3 will have become the new ply=1, and we already know that it is better not to switch move there.

So it seems that it coud also be better to not switch move after a fail low at ply=3, but imediately open the window there, and re-search. If you would do that at every level, however, would basically do away completely with aspiration, and only add the feature that when a PV move fails high, the parent node is informed of this (without using the information) before the sibblings are searched. So this cannot be optimal either.

The real question thus is: "what is the ply level where you have to switch from immediate re-search of a low-failing PV move to trying sibblings first?". And would this depend on the window width? This is why I proposed the "tapered auto-aspiration search" above.

I use a recursive parallel search so when I check the time, I have no idea what is going on in each individual thread, since I can't see what they are doing... What you suggest is certainly possible, but is not so easy in a parallel search. And down in the tree, I am not sure you want to widen the window as when this backs up, it might get tossed out at earlier plies.

The reason I went to aspiration search (and stepwise widening at the root when a fail low or high happens) came from some positions Harry Nelson had, where the root score was pretty normal, but there were literally a zillion non-forced checkmates in the tree, they were just all irrelevant. Aspiration cut the time to search some of those by 100x, leaving all those unforced checkmates outside the window where they were quickly dismissed.