Restarting iterative deepening

[bob]

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(alpha < realAlpha) alpha = realAlpha;
  }
  do {
    int startAlpha = alpha;
    for(ALL_MOVES) {
      MakeMove();
      score = -Search(-beta, -alpha, aspirationWidth*0.95);
      UnMake();
      if(score > alpha) {
        alpha = score;
        ...
      }
    }
    retry = (alpha <= startAlpha && alpha < realAlpha);
    alpha = realAlpha;
  } while(retry);
  return alpha;
}

// Root call:
Search(-MATE, +MATE, 100*centiPawn);

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.

Will keep it on my list. I have a version with no fail lows at the root now (window=(-inf, +inf)). Testing and tweaking as this affected several places in the code.

First thing I noticed is a massive reduction in those fail high followed by a fail low (at the root) circumstances that were always annoying... But I have to first confirm I haven't broken anything, then test thoroughly...

[bob]

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(alpha < realAlpha) alpha = realAlpha;
  }
  do {
    int startAlpha = alpha;
    for(ALL_MOVES) {
      MakeMove();
      score = -Search(-beta, -alpha, aspirationWidth*0.95);
      UnMake();
      if(score > alpha) {
        alpha = score;
        ...
      }
    }
    retry = (alpha <= startAlpha && alpha < realAlpha);
    alpha = realAlpha;
  } while(retry);
  return alpha;
}

// Root call:
Search(-MATE, +MATE, 100*centiPawn);

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.

Will keep it on my list. I have a version with no fail lows at the root now (window=(-inf, +inf)). Testing and tweaking as this affected several places in the code.

First thing I noticed is a massive reduction in those fail high followed by a fail low (at the root) circumstances that were always annoying... But I have to first confirm I haven't broken anything, then test thoroughly...

Next thing I noticed was about a -25 Elo change. Apparently the way I do aspiration windows (and code related to that) works pretty well. Code was a bit simpler without it, but also about -25 Elo worse, so obviously it is back in again...

Another wasted day...

[cdani]

Another wasted day...

I do not consider such essays as wasted, and I suppose you too, even if, like when one lose a game, might think that has wasted the time

[bob]

Another wasted day...

I do not consider such essays as wasted, and I suppose you too, even if, like when one lose a game, might think that has wasted the time

aspiration windows have always worked for me. always. Why I took the time to confirm they still do I will never know.

[hgm]

But you are using them in an unusual way. Normally the idea behind aspiration is that you don't want the search to bother figuring out exactly how much the score of the PV move dropped when it drops more than the aspiration-window width. Because you are confident (without evidence, based on statistics only) that one of the other root moves will score inside that window too, so that an upper bound on the score of the old PV move below the aspiration window is already good enough. This is why you do the aspiration in the root, so that you will return there if the PV score dropped, so you can switch moves.

If you don't want to switch moves anyway, you might as well have applied the aspiration in node at a higher ply level.

If you find that it is better to not switch moves in the root (ply=1), then why would you expect it is better to switch moves on a PV that fails low in the PV node at ply=2 or ply=3?

[bob]

But you are using them in an unusual way. Normally the idea behind aspiration is that you don't want the search to bother figuring out exactly how much the score of the PV move dropped when it drops more than the aspiration-window width. Because you are confident (without evidence, based on statistics only) that one of the other root moves will score inside that window too, so that an upper bound on the score of the old PV move below the aspiration window is already good enough. This is why you do the aspiration in the root, so that you will return there if the PV score dropped, so you can switch moves.

If you don't want to switch moves anyway, you might as well have applied the aspiration in node at a higher ply level.

If you find that it is better to not switch moves in the root (ply=1), then why would you expect it is better to switch moves on a PV that fails low in the PV node at ply=2 or ply=3?

What I am doing. When I fail low on the aspiration window I immediately lower the alpha bound and re-search this first root move again.

What I tried. I simply set the window to -inf,+inf for each iteration so there was never a fail low at all.

The only special thing I was doing was this: If I am pondering, and I ponder longer than the set target time because my opponent thinks a while, when he makes a move I could bail out instantly since I have already exceeded the target (but on his clock). What I currently do is notice that the first move has failed low, even though I don't have an actual score back yet, and I do NOT terminate the search, as I want to try to avoid the score drop. I can't imagine that is worth 25 Elo. But what I did notice is that iterations took longer with -/+inf bounds, which is not a surprise, but what was surprising was how much longer they tended to take, and apparently that was worth 25 Elo or so...

[jwes]

But you are using them in an unusual way. Normally the idea behind aspiration is that you don't want the search to bother figuring out exactly how much the score of the PV move dropped when it drops more than the aspiration-window width. Because you are confident (without evidence, based on statistics only) that one of the other root moves will score inside that window too, so that an upper bound on the score of the old PV move below the aspiration window is already good enough. This is why you do the aspiration in the root, so that you will return there if the PV score dropped, so you can switch moves.

If you don't want to switch moves anyway, you might as well have applied the aspiration in node at a higher ply level.

If you find that it is better to not switch moves in the root (ply=1), then why would you expect it is better to switch moves on a PV that fails low in the PV node at ply=2 or ply=3?

What I am doing. When I fail low on the aspiration window I immediately lower the alpha bound and re-search this first root move again.

What I tried. I simply set the window to -inf,+inf for each iteration so there was never a fail low at all.

The only special thing I was doing was this: If I am pondering, and I ponder longer than the set target time because my opponent thinks a while, when he makes a move I could bail out instantly since I have already exceeded the target (but on his clock). What I currently do is notice that the first move has failed low, even though I don't have an actual score back yet, and I do NOT terminate the search, as I want to try to avoid the score drop. I can't imagine that is worth 25 Elo. But what I did notice is that iterations took longer with -/+inf bounds, which is not a surprise, but what was surprising was how much longer they tended to take, and apparently that was worth 25 Elo or so...

I tried some experiments a while ago and found that it was good to re-search the same move on the first fail low, but if it fails low again, try the other moves first. Another way of looking at it is, if a move is likely to lose, I would rather try other moves first, because if the first move is the best move, the waste of time hardly matters.

I am also surprised that aspiration windows are worth 25 ELO, as that about 1/3 more nodes. I might double-check by running some positions to fixed depth and see that I get the same result while using a bunch more nodes.

[bob]

But you are using them in an unusual way. Normally the idea behind aspiration is that you don't want the search to bother figuring out exactly how much the score of the PV move dropped when it drops more than the aspiration-window width. Because you are confident (without evidence, based on statistics only) that one of the other root moves will score inside that window too, so that an upper bound on the score of the old PV move below the aspiration window is already good enough. This is why you do the aspiration in the root, so that you will return there if the PV score dropped, so you can switch moves.

If you don't want to switch moves anyway, you might as well have applied the aspiration in node at a higher ply level.

If you find that it is better to not switch moves in the root (ply=1), then why would you expect it is better to switch moves on a PV that fails low in the PV node at ply=2 or ply=3?

What I am doing. When I fail low on the aspiration window I immediately lower the alpha bound and re-search this first root move again.

What I tried. I simply set the window to -inf,+inf for each iteration so there was never a fail low at all.

The only special thing I was doing was this: If I am pondering, and I ponder longer than the set target time because my opponent thinks a while, when he makes a move I could bail out instantly since I have already exceeded the target (but on his clock). What I currently do is notice that the first move has failed low, even though I don't have an actual score back yet, and I do NOT terminate the search, as I want to try to avoid the score drop. I can't imagine that is worth 25 Elo. But what I did notice is that iterations took longer with -/+inf bounds, which is not a surprise, but what was surprising was how much longer they tended to take, and apparently that was worth 25 Elo or so...

I tried some experiments a while ago and found that it was good to re-search the same move on the first fail low, but if it fails low again, try the other moves first. Another way of looking at it is, if a move is likely to lose, I would rather try other moves first, because if the first move is the best move, the waste of time hardly matters.

I am also surprised that aspiration windows are worth 25 ELO, as that about 1/3 more nodes. I might double-check by running some positions to fixed depth and see that I get the same result while using a bunch more nodes.

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)...

[hgm]

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...).

[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).