Restarting iterative deepening

[hgm]

I have been doing some interactive analysis these past days, using my mini-Shogi program. Mini-Shogi is like walking through a mine filed: a move can look pretty good upto quite high depth, and then suddenly change into a dead loss in the next iteration. E.g. at 18 ply the score can be +0.36, and then at 19 ply it drops to -3.40, indicating you will lose some material (which is tantamount to losing the game). Usually moves are singular, meaning that all other moves will also losing material

I noticed that when such a thing happens (i.e. score of the PV move suddenly drops, and no alternative move can take its place) that it will take about forever for the iteration to complete. I guess this is to be expected, because it now has to completely recalculate the refutation trees of the other moves, to make them beat the much lowered alpha. Most of the cut moves the opponent was using for this purpose at d=18 will not nearly be good enough to push the score that low. So in almost every cut-node the hash move will now fail low, and it has to start trying other moves that it never tried before at high depth to find a better one.

When I restart the search, however, it picks up the very low d=19 score for the PV move from the hash starting at d=1, and it will gradually build the refutation trees for the other moves with cut moves good enough to to match that. Getting far past d=19 then takes only a fraction of the time it would take to finish the d=19.

So it seems the engine is doing something very wrong. And I wonder if this is not a very general thing: If the best move of the previous iteration (possibly obtained via the hash table) suffers en enormous score drop at the currently requested depth, it might be genrally better to not attempt to search other moves at that depth, but start IID from scratch with alpha set by the new, lowered score of the old PV move.

Does anyone do that?

[mar]

Does anyone do that?

I'm not sure but I think Houdart did something similar (except only when resolving fail highs?)

[bob]

I have been doing some interactive analysis these past days, using my mini-Shogi program. Mini-Shogi is like walking through a mine filed: a move can look pretty good upto quite high depth, and then suddenly change into a dead loss in the next iteration. E.g. at 18 ply the score can be +0.36, and then at 19 ply it drops to -3.40, indicating you will lose some material (which is tantamount to losing the game). Usually moves are singular, meaning that all other moves will also losing material

I noticed that when such a thing happens (i.e. score of the PV move suddenly drops, and no alternative move can take its place) that it will take about forever for the iteration to complete. I guess this is to be expected, because it now has to completely recalculate the refutation trees of the other moves, to make them beat the much lowered alpha. Most of the cut moves the opponent was using for this purpose at d=18 will not nearly be good enough to push the score that low. So in almost every cut-node the hash move will now fail low, and it has to start trying other moves that it never tried before at high depth to find a better one.

When I restart the search, however, it picks up the very low d=19 score for the PV move from the hash starting at d=1, and it will gradually build the refutation trees for the other moves with cut moves good enough to to match that. Getting far past d=19 then takes only a fraction of the time it would take to finish the d=19.

So it seems the engine is doing something very wrong. And I wonder if this is not a very general thing: If the best move of the previous iteration (possibly obtained via the hash table) suffers en enormous score drop at the currently requested depth, it might be genrally better to not attempt to search other moves at that depth, but start IID from scratch with alpha set by the new, lowered score of the old PV move.

Does anyone do that?

I can't tell you how many times this discussion has erupted over the past 40+ years.

One school of thought, originally proposed by John Stanback, was that after a fail low, which I assume you would see before the bottom falls out, that you re-start at depth=1. Ideally the hash table will retain the data, particularly the ply=2 move/score that causes the root move to fail low, and you will pick up a different best move at the early iterations and whiz back up to the last ply but with a different best move that is probably lower than the original through the early plies, but which should be better at the ply where things fell apart. But I kept running into problems. Once you start to pile up those second-time-around iterations, you had better not overwrite the key position that makes the old best move fail low, else you are now in a loop, you find the original best move as best again, you get to the magic depth, fail low again, and there you go...

Another approach says to use a reasonable aspiration window and then if the first move fails low, keep on searching and do not widen the window until all root moves fail low. I never liked this because I have always used the current score to adjust the time limit for this search. If the score drops, search longer. I no longer do it this way so perhaps I might try some experimentation with both of the above again, since I now don't really care how much the score has dropped...

My current approach (fail low - research with widened window on same move) is more informative, but perhaps not as efficient as it could be...

[D Sceviour]

So it seems the engine is doing something very wrong. And I wonder if this is not a very general thing: If the best move of the previous iteration (possibly obtained via the hash table) suffers en enormous score drop at the currently requested depth, it might be generally better to not attempt to search other moves at that depth, but start IID from scratch with alpha set by the new, lowered score of the old PV move.

Does anyone do that?

Of course, the solution is to set:

bestmove=NULL;

and pass the information to a trick on an Internal Iterative Deepening routine. It is a way of guaranteeing a shallow full width search on the position so nothing is missed. The entire theory can be traced here:

http://talkchess.com/forum/viewtopic.ph ... refutation

[hgm]

The worst problems I see occur when there is not really another best move to pick up, but the root score plummets, keeping the same move. Aspiration would not really help much in that case; you would just get fail low after fail low, and all the root non-PV moves would have to find more stringent bounds at high depth on each of these fail lows. Once an alternative move is quickly found in the root with a score only slightly lower than the PV score of the previous iteration, proving the remaining moves worse is cheap again. And the aspiration prevents you wasting time on proving how poor exactly the old PV move has become. But if no such alternative is found...

What I had in mind is something like this:

Code: Select all

RootSearch()
{
  for(IDdepth = 1; !TimeOut(); IDdepth++) {
    alpha = -INF; // aspiration could be done here
    beta = +INF;
    for((move = NextMove())) {
      MakeMove(move);
#if TRICK
      for&#40;d=1; d<=IDdepth; d++)
        score = - Search&#40;-beta, -alpha, d-1&#41;;
#else
      score = -Search&#40;-beta, -alpha, IDdepth-1&#41;;
#endif
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
      &#125;
    &#125;
  &#125;
&#125;

This seems harmless; in a stable search (when the score did not drop compared to the previous iteration) the hashed bound for all d<IDdepth would produce an immediate hash cutoff. If the score would have dropped so that the hashed bounds are no good, it would start from d=1 finding better cut moves in the refutation tree of the other moves. This would initially overwrite hash entries with high draft, but useless bounds with those with lower draft but useful bounds, but eventually the draft will be cranked up to the depth of the new iteration.

I don't see any danger for infinite looping here.

[bob]

The worst problems I see occur when there is not really another best move to pick up, but the root score plummets, keeping the same move. Aspiration would not really help much in that case; you would just get fail low after fail low, and all the root non-PV moves would have to find more stringent bounds at high depth on each of these fail lows. Once an alternative move is quickly found in the root with a score only slightly lower than the PV score of the previous iteration, proving the remaining moves worse is cheap again. And the aspiration prevents you wasting time on proving how poor exactly the old PV move has become. But if no such alternative is found...

What I had in mind is something like this:

Code: Select all

RootSearch()
{
  for(IDdepth = 1; !TimeOut(); IDdepth++) {
    alpha = -INF; // aspiration could be done here
    beta = +INF;
    for((move = NextMove())) {
      MakeMove(move);
#if TRICK
      for&#40;d=1; d<=IDdepth; d++)
        score = - Search&#40;-beta, -alpha, d-1&#41;;
#else
      score = -Search&#40;-beta, -alpha, IDdepth-1&#41;;
#endif
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
      &#125;
    &#125;
  &#125;
&#125;

This seems harmless; in a stable search (when the score did not drop compared to the previous iteration) the hashed bound for all d<IDdepth would produce an immediate hash cutoff. If the score would have dropped so that the hashed bounds are no good, it would start from d=1 finding better cut moves in the refutation tree of the other moves. This would initially overwrite hash entries with high draft, but useless bounds with those with lower draft but useful bounds, but eventually the draft will be cranked up to the depth of the new iteration.

I don't see any danger for infinite looping here.

The one that burned me over and over was the case where your opponent makes a subtle move, and for the first N plies you think you are winning something. But once you reach the magic depth (typically 1 ply less than what your opponent searched) the best move fails low given that material gain as a lower bound. In fact ALL moves fail low. And this is not all that uncommon.

I wasted a lot of time with Cray Blitz working on the "restart at ply 1" approach, but for this kind of position it was a train wreck, because it kept backing up, finding a different best move that kept the material advantage, until reaching the right depth for it to see that this doesn't work either. There are a lot of variations on this theme, and they were all problematic. I decided eventually to use the model I still use today, if the first move fails low, I re-search immediately so at least I know what I am dealing with, score wise...

The only thing I need to measure today is whether researching on the fail low immediately, or trying all root moves before expanding the window is better. Since I no longer use the score to drive the time usage, there might be some advantage in trying everything before relaxing alpha. If there is not any move that prevents the fail low, Berliner always said "just play the first one (best move from previous iteration) rather than doing something stupid (this about playing humans, NOT computers)...

Your idea seems reasonable, I probably should experiment with all of this again anyway, since the change was made to not depend on how bad the score is any longer.. It might go a long way toward eliminating those "barriers" we occasionally see where the search hangs because the search has uncovered something that negates most of the hash information.

[hgm]

I decided eventually to use the model I still use today, if the first move fails low, I re-search immediately so at least I know what I am dealing with, score wise...

That search strategy seems to make aspiration useless. If you would repeat searching the same move without first trying any others, it might be better to search it with a fully open window in the first place.

This does raise an interesting point, though. A search with a fully open window would try to solve any setback it encounters at the tip of the PV, when it adds a ply on top of it, by changing PV move as closely to the tip as possible. E.g. if you deepen from 20 to 21, and the QS score in the node after the added move is very different, it first tries other moves at ply 20, then at 19, etc. That is how recursive tree-walking works.

But if the search doesn't manage to get a score similar to that of the previous iteration quickly, even though it has backed up all the way to, say, ply 12, it becomes rather expensive to determine the exact score there. While it is quite likely that some side branch between the root and ply 12 would do better than the very much lower exact score you would be caluclating at ply 12. So calculating the latter is likely to be a complete waste of time. You would on the average save work by gampling a move lower-down will beta-cut it. Aspiration will have that effect: scores of former PV nodes that walk out of the window will make the search on that node fail without determining the exact score, so that nodes closer to the root get a chance to try their alternatives first.

So any time a PV move in some internal node scores a lot lower than on the previous iteration, you have the dilemma of trying to solve in in that node, or gamble that a node closer to the root can solve it. The more the score in the current node will drop, the larger the chances that in some node between it and the root the move leading to it will no longer be the best move. So you would want to use an aspiration window in that node to reflect that. In particular, the more nodes you have between the root and the current node, the more likely it will be that one of the moves there will save the day. So the less willing you would be to tolerate a large score change. This suggests the optimal aspiration window should get progressively narrower when you approach the leaves.

This argues for every PV node determining itself how to reduce the window width over what it shoud formally be.

[Rein Halbersma]

Does anyone do that?

The Chinook checkers engine did restart the iterative deepening search at d=1 after a fail-low at the root: see section 2 of Search Ideas in Chinook

[bob]

I decided eventually to use the model I still use today, if the first move fails low, I re-search immediately so at least I know what I am dealing with, score wise...

That search strategy seems to make aspiration useless. If you would repeat searching the same move without first trying any others, it might be better to search it with a fully open window in the first place.

This does raise an interesting point, though. A search with a fully open window would try to solve any setback it encounters at the tip of the PV, when it adds a ply on top of it, by changing PV move as closely to the tip as possible. E.g. if you deepen from 20 to 21, and the QS score in the node after the added move is very different, it first tries other moves at ply 20, then at 19, etc. That is how recursive tree-walking works.

But if the search doesn't manage to get a score similar to that of the previous iteration quickly, even though it has backed up all the way to, say, ply 12, it becomes rather expensive to determine the exact score there. While it is quite likely that some side branch between the root and ply 12 would do better than the very much lower exact score you would be caluclating at ply 12. So calculating the latter is likely to be a complete waste of time. You would on the average save work by gampling a move lower-down will beta-cut it. Aspiration will have that effect: scores of former PV nodes that walk out of the window will make the search on that node fail without determining the exact score, so that nodes closer to the root get a chance to try their alternatives first.

So any time a PV move in some internal node scores a lot lower than on the previous iteration, you have the dilemma of trying to solve in in that node, or gamble that a node closer to the root can solve it. The more the score in the current node will drop, the larger the chances that in some node between it and the root the move leading to it will no longer be the best move. So you would want to use an aspiration window in that node to reflect that. In particular, the more nodes you have between the root and the current node, the more likely it will be that one of the moves there will save the day. So the less willing you would be to tolerate a large score change. This suggests the optimal aspiration window should get progressively narrower when you approach the leaves.

This argues for every PV node determining itself how to reduce the window width over what it shoud formally be.

I wanted to play around a bit, but the aspiration window is always a problematic issue. I am running a test with it removed, IE my initial alpha/beta window for every last iteration is -MATE, +MATE. So no fail lows can happen. I can still get fail highs on null-window PVS searches, and I don't want to eliminate those as I end up back in Iterate() after a fail high at the root, and that lets me start a search with all threads looking at that specific move, which is an advantage I don't want to give up.

So far it looks "no worse". Will report back after 30K games have finished. If it is "no worse" I will remove it as there is a lot of code (graduated fail low stuff, etc, that can be cleaned out here and there to simplify things and make the "restart at ply 1" test much easier to try.

[hgm]

How about this algorithm?

Code: Select all

int Search(int realAlpha, int realBeta, int aspirationWidth)
{
  int alpha = realAlpha, beta = realBeta;
  ProbeHash();
  if(beta - alpha > 1) { // PV node
    alpha = hash.score - aspirationWidth;
    if&#40;alpha < realAlpha&#41; alpha = realAlpha;
  &#125;
  do &#123;
    int startAlpha = alpha;
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;);
      score = -Search&#40;-beta, -alpha, aspirationWidth*0.95&#41;;
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
        ...
      &#125;
    &#125;
    retry = &#40;alpha <= startAlpha && alpha < realAlpha&#41;;
    alpha = realAlpha;
  &#125; while&#40;retry&#41;;
  return alpha;
&#125;

// Root call&#58;
Search&#40;-MATE, +MATE, 100*centiPawn&#41;;

This would try to solve a fail low that just fails a little bit low in the current node, but on a drastic score drop would prefer to hand the fail low down to the parent.