Aspiration window - effect? Issue with hashtables?!

[JBNielsen]

How much will the use of aspiration window usually make an engine faster?

Is there an issue with hashtables?
When the engine is doing an iteration that fails to be inside the window, it will store a lot of wrong scores in the hashtables?!?

[ZirconiumX]

How much will the use of aspiration window usually make an engine faster?

Is there an issue with hashtables?
When the engine is doing an iteration that fails to be inside the window, it will store a lot of wrong scores in the hashtables?!?

Aspiration windows are 10-20 Elo, usually, though it depends on your implementation.

There isn't really an issue for TT, actually. You just do a search that isn't full-width - something that happens often in a modern AB searcher.

I don't quite understand the last question, since you (should) store upper bound/exact/lower bound in the hash entry, iow this is handled by your code without aspiration.

Matthew:out

[JBNielsen]

There isn't really an issue for TT, actually. You just do a search that isn't full-width - something that happens often in a modern AB searcher.

I don't quite understand the last question, since you (should) store upper bound/exact/lower bound in the hash entry, iow this is handled by your code without aspiration.

Matthew:out

My hashtables only store the score, the best move, some depths etc - but not the bounds.

So perhaps I should make my silly hashtables work better instead of making the aspiration window...

[ZirconiumX]

Storing bounds is a must for TTs - it gives you a small speed gain by making you not do stupid things like checking if the score is >= beta when it failed low last time - Crafty also has a trick of avoiding nullmove when it failed low last time.

Matthew:out

[lucasart]

How much will the use of aspiration window usually make an engine faster?

Is there an issue with hashtables?
When the engine is doing an iteration that fails to be inside the window, it will store a lot of wrong scores in the hashtables?!?

Aspiration windows are 10-20 Elo, usually, though it depends on your implementation.

I agree. I got over 30 elo with aspiration in DiscoCheck:
https://github.com/lucasart/chess/commi ... 8605b85717
But that was self-play at super fast time control. Also, due to the good results, I stopped the experience early according to SPRT algorithm, which means that the final result is a biaised estimation anyway.

So in normal conditions (against other engines and at long time control) it's probably in the range 10-20 elo that you indicate. Maybe 25 ? But it's certainly not the the huge improvement that people often expect.

Be very careful of search inconcistencies whtn you implement aspiration. So when the search fails low and gives you a value x < alpha < beta, you research the window [new_alpha, beta], and NOT [new_alpha, alpha] or [new_alpha, x]. And symetrically for fail high, obviously.

[lucasart]

Crafty also has a trick of avoiding nullmove when it failed low last time.

Hey, that makes sense! I'm going to experiment with this.

[hgm]

My hashtables only store the score, the best move, some depths etc - but not the bounds.

But bounds are scores. So what exactly do you mean? You ony store a score when you have an eact score (i.e. in PV nodes), and something that marks it as 'invalid' otherwise? And how do you use the info in the TT. Do you take cutoffs based on scores you find there, or just use the move for move odering?

It does seem you could gain a lot more than 20 Elo by a more complete TT implementation.

[elcabesa]

when you save a score in the hashtable you have also to save what they call bounds.
what "bounds" mean?

it means that if you are saving a score after you found a score inside the desidered window (alpha-beta) the score is exact, but if you are saving a score after a beta Cutoff you are saving a lowBound because the beta cutoff only tell you that you have found a score above the beta, you don't know how much higher, and you haven't searched all the nodes because you have done a cutoff at the first node failing high.

so when you use this score you have to look at the score and at the bound info.
if You are searching with a window (-20,50) and your score is 70 lowBound you can safely use the score to create a betacutoff because you know that the score means >=70, but if your window is (80,100) you can't use he score for a cutoff because you are searching a value x between 80 and 100 and you know the result is >70, so it's not useful.

You could found the code inside every strong engine

[ZirconiumX]

Be very careful of search inconcistencies whtn you implement aspiration. So when the search fails low and gives you a value x < alpha < beta, you research the window [new_alpha, beta], and NOT [new_alpha, alpha] or [new_alpha, x]. And symetrically for fail high, obviously.

Things like that also depend on your implementation. In current modern-day engines there are a few implementations: (coded off the top of my head)

RobboLito (as used by Stockfish)

Code: Select all

void search(...)
{
   init_search(...);
   int score;
   for &#40;int depth = 1; depth < DEPTH_MAX && !search_stop&#40;); depth++) &#123;
      int alpha, beta, delta;
      delta = 16;

      if &#40;depth <= 4&#41; &#123; // Avoid doing aspiration at low depths - it's a waste of time
         alpha = -INF;
         beta = +INF;
      &#125; else &#123;
         alpha = score - delta;
         beta = score + delta;
      &#125;

      while &#40;1&#41; &#123;
         score = Search&#40;depth, alpha, beta, ...)
         if &#40;score <= alpha&#41; &#123; // fail-low
            alpha += delta;
            delta += delta / 2; // don't widen too quickly
         &#125; else if &#40;score >= beta&#41; &#123; // fail-high
            beta += delta;
            delta += delta / 2;
         &#125; else break;
      &#125;

      print_stats&#40;);
   &#125;
&#125;

There are a few different ideas floating around about this, including, but not limited to:

1. Doing aspiration earlier/later
2. Having separate deltas for alpha and beta
3. delta += delta * 2 instead of delta += delta / 2 to get a more stable result.
4. Wider/narrower initial deltas
5. Making alpha and beta local to the search, rather than the depth (alpha and beta are declared where score is) so that you have a roughly stable window for the next iteration.

Feel free to experiment - what I put here is by no means the perfect implementation.

Classical (as used by Cyclone)

Code: Select all

void search()
{
   int score, alpha, beta, delta;

   delta = 50;
   alpha = -INF;
   beta = +INF;

   for &#40;int depth = 1; depth < DEPTH_MAX && !search_stop&#40;); depth++) &#123;
      score = search_slave&#40;depth, alpha, beta, ...);
      
      alpha = score - delta;
      beta = score + delta;

      print_stats&#40;);
   &#125;
&#125;

int search_slave&#40;int depth, int alpha, int beta, ...)
&#123;
   int score, best;
   MOVETYPE move;

   gen_moves&#40;);

   best = -INF;

   while (&#40;move = next_move&#40;)) != NO_MOVE&#41; &#123;
      make_move&#40;move&#41;;
      score = -Search&#40;depth-1, -beta, -alpha, ...);
      if &#40;score <= alpha&#41; &#123; // fail low
         alpha = -INF;
         score = -Search&#40;depth-1, -beta, -alpha, ...);
         alpha = score - 50;
      &#125;
      if &#40;score >= beta&#41; &#123; // fail high
         beta = +INF;
         score = -Search&#40;depth-1, -beta, -alpha, ...);
         beta = score + 50;
      &#125;

      if &#40;score > best&#41;
         best = score;
   &#125;

   return best;
&#125;

This type tends to work best with Fruit-type engines as the infrastructure is already in place. It also tends to have less problems with fail highs and lows, as the window is opened quite considerably.

Bruce Moreland (as used by Ferret)

Code: Select all

void search()
{
   int score, alpha, beta, delta;

   alpha = -INF;
   beta = +INF;

   delta = 50;

   for &#40;int depth = 1; depth < DEPTH_MAX && !search_stop&#40;);) &#123; // note no depth++
      score = Search&#40;depth, alpha, beta&#41;;

      if &#40;score <= alpha || score >= beta&#41; &#123;
         alpha = -INF;
         beta = +INF;
         continue;
     &#125;

     alpha = score - delta;
     beta = score + delta;

     print_stats&#40;);

     depth++;
   &#125;
&#125;

This is a common reference implementation for beginners - it has barely any problems with fail highs and lows, but tends to give less of an improvement.

There are lots of enhancements to be made for the adventurous - for instance for the classical type, Ed Schroder's Programming Topics is the place to go.

Matthew:out

[lucasart]

Thanks Matthew. That's an interesting summary.

But out of these three methods, it's obvious that the best one is the "Robbolito" one. I would imagine that every strong program uses something closer to that than to the Cyclone or Ferret ones.

I use the "Robbolito method" with delta += delta, instead of delta += delta/2. And I also start aspiration at depth 5 (it's a waste of time below, and there were technical reasons like razoring and eval pruning at PV nodes for eg.)