Aspiration Windows: Rubbish!

[ZirconiumX]

Well, it is an Apple computer.

(Have you got it yet?)

Matthew:out

[Harald]

I have examined my implementation, and hope this pseudo code may clear things up:

Code: Select all

void search() {
    InitEverything();
    for (int depth = 1;;depth++) {
       if &#40;depth <= 3&#41; &#123;
          alpha = -ValueInf;
          beta = +ValueInf;
       &#125; else &#123;
          alpha = last_search_value - 32;
          beta = last_search_value + 32;
       &#125;
       alphabetaroot&#40;);
       if &#40;search_is_fail_high&#41; &#123; // This limits it to depth 4
          depth -= 3; // This may well be the culprit
       &#125;
       if &#40;search_is_fail_low&#41; &#123;
          alpha *= 2; // /= 2???
          beta *= 2;
       &#125;
   &#125;
&#125;

The fail low case is nonsense. Think about both alpha and beta being
positive (or negative). But fortunately it does not do anything
since it is overwritten immediately in the next loop. Better:

Code: Select all

void search() {
    InitEverything();
    low_aspiration_delta = 32;
    high_aspiration_delta = 32;
    for (int depth = 1;;depth++) {
       if &#40;depth <= 3&#41; &#123;
          alpha = -ValueInf;
          beta = +ValueInf;
       &#125; else &#123;
          alpha = last_search_value - low_aspiration_delta;
          beta = last_search_value + high_aspiration_delta;
       &#125;
       alphabetaroot&#40;);
       if &#40;search_is_fail_high&#41; &#123;
          high_aspiration_delta *= 4;
          depth--;
       &#125;
       else if &#40;search_is_fail_low&#41; &#123;
          low_aspiration_delta *= 4;
          depth--;
       &#125;
       else &#123;
          low_aspiration_delta = 32;
          high_aspiration_delta = 32;
       &#125;
   &#125;
&#125;

Harald

[Desperado]

I have examined my implementation, and hope this pseudo code may clear things up:

Code: Select all

void search() {
    InitEverything();
    for (int depth = 1;;depth++) {
       if &#40;depth <= 3&#41; &#123;
          alpha = -ValueInf;
          beta = +ValueInf;
       &#125; else &#123;
          alpha = last_search_value - 32;
          beta = last_search_value + 32;
       &#125;
       alphabetaroot&#40;);
       if &#40;search_is_fail_high&#41; &#123; // This limits it to depth 4
          depth -= 3; // This may well be the culprit
       &#125;
       if &#40;search_is_fail_low&#41; &#123;
          alpha *= 2; // /= 2???
          beta *= 2;
       &#125;
   &#125;
&#125;

So, the depth 4 search fails high, and the depth is reduced by three, giving me...a depth 1 search; maybe Robert Houdart has a minimum depth condition of >= 10. Since the depth 4 search finishes quickly, I only *just* see the depth 1 search, which sticks in my mind.

Yes, I know, you cannot work with information you aren't given, but really Lucas and Vincent, what you said was unkind.

Matthew:out

Matthew:out

Hi Matthew,

well what should i say ... ?

First, i dont want to be rude, but i really doubt you
understand what are doing in this case.

Doesnt matter, lets start with the snippet

General:
=========

Before going into details with the aspiration search concept,
here are some thoughts you should comment if they work but
that cannot be seen from the snippet like:

* how are alpha and beta passed to alphabetaroot() ?!!

?:
if there hasnt been an aspiration window concept before,
alpha and beta maybe set in alphabetaroot() to an open window
anyway.
?:
are alpha,beta global variables
!:
please make this point clear in the snippet.
just by a short comment. And also things which may be important
but cannot be seen from the snippet. This will help the readers
to help you finally.


Aspiration Window Concepts:
============================

There are 2 concepts to use Aspiration windows i know.

Code: Select all

 1. Inside the rootsearch for the first move.

    alphaBetaRoot()
    {
     ...
     while(moves)
     {
      if(moveNb == 1)
      {
       "INSERT HERE"
      }
      else
      {
       //handle all other moves
      }
     }
     ...
    } 

    
  "INSERT HERE":

     X: repeat 
     * set aspiration window
     * search with Aspiration window
     * Repeat search
       - on fail lo (open window to lower bound)
       - on fail hi (open window to upper bound)
     * (refinement: the research must not open into the failed direction
                    completly, so you can jump to "X" and try it with a wider
                    window, 2,3 or 4 times before open the window completly) 

     HINT: for the first trials you should open the window for
           the research completly (at least in the direction it failed)

     HINT: i am not sure, but i think that is the classical approach of 
           using aspiration window technique. Get it to work, play around with it.

2 The 2nd concept, you certainly did not understand (it looks like)

because:
* you try to widen the window somehow (alpha*=2 ?! explanation !?), BUT dont you
miss the research for that window ?!

so you need sth like

Code: Select all

              iterationLoop()
              {
               aspirationLoop( exit when pv value (within alpha and beta) has been found)
               {
                setAlpha;
                setBeta;
                alphaBetaRoot(alpha,beta)
               }
              }

            *
              ok, you set the starting window to lastvalue +- 32. 
              ok, you TRY to widen something somehow (alpha *=2)
              
              - how it should continue to handle the window ? when
 
              - you would have such an "aspirationloop", how do you control that
                the loop isnt infinite, and the computation for the bounds doesnt produce
                ähhhmmm ;-) (pls check out how alpha and beta will change with your formular with each loop,
                maybe it works somehow, but this must be figured out by yourself)

            *

             Why do you want to repeat the complete movelist (alphaBetaRoot()), unlike in
             the classic concept only the first move ?? Do you know it ? Well, it is not intuitive !

              - can it be better, then why ? (think about it a while...)
              

So, all in all there are a lot of things to check out for you,
or a lot of things you may explain to us (me), if you like.

IF i understand what you intended to do, a proposal may look like this. My advise is, that you
do not only code it into your engine but really ask yourself any question about it,
which comes to your mind, and why sth like this can be better (but not necessarily is better)

So, finally here is the concept taken from Robbolito, which
i tried out recently.

Code: Select all

void iterate()
{
 //...

 //ITERAION LOOP
 for(ctl->iteration = onePly;!stopSearch(canStop);ctl->iteration += onePly)
 {
  // ... robbo, aspiration search...
  if&#40; ctl->iteration >= 14 && absN&#40;lastValue&#41;<OPENWINDOW&#41;
  &#123;
   // aspirationWindow
   delta  = 8;
   aspiLo = guess - delta;
   aspiHi = guess + delta;

   // make sure technical bounds do not crash
   // or simply decide to open fully a direction
   // from a certain value on.
   if&#40; aspiLo < -OPENWINDOW )   aspiLo = lbound;
   if&#40; aspiHi >  OPENWINDOW )   aspiHi = ubound;

   // ASPIRATION LOOP
   do
   &#123;
     value = nodeRoot&#40;pos,mliRoot,aspiLo,aspiHi,ctl->iteration,plyRoot&#41;;

     // pv hit
     if&#40; value > aspiLo && value < aspiHi ) break;// goto END;
          
	 // handle fail lo
	 if&#40; value <= aspiLo )
     &#123;
	  aspiLo -= delta;
	  delta  += delta / 2;
      guess   = aspiLo;
     &#125;
	 // handle fail hi
     else
     &#123;
      aspiHi += delta;
      delta  += delta / 2;
      guess   = aspiHi;
     &#125;
    &#125;while&#40;1&#41;;
  &#125;
  else   value = nodeRoot&#40;pos,mliRoot,lbound,ubound,ctl->iteration,plyRoot&#41;;
  //...
 &#125;

And finally, if you take it personal, i mean such things with the "funny"
post, (i also had a good laugh), then also be aware that some people really try to help, AND spend some time writing posts like this.

So, please take it serious, otherwise nobody will take the time to help
again. Doesnt matter how old you are ? (Beside how old are you ? )

You can spend now a lot of time with the stuff i posted, use it...

cheers , Michael

[hgm]

What I wanted to say is that if you do a search like this:

Code: Select all

depth=1, alpha = -INF, beta= +INF

The root node will be a PV node and a frontier node at the same time.

and imagine you have a condition before make a move like this:

Code: Select all

if &#40;depth ==1 && board_eval + material_gain&#40;move&#41;  + FUTILE_MARGIN < alpha&#41;
  continue;

This contidion won't affect to anything, because you'll never enter inside the 'if'. Your alpha is -INF, so nothing is lower than this.

What I wanted to say is that the latter is not true. Because alpha won't stay -INF for the duration of the node. After the first move is search, you do

Code: Select all

if(score > alpha) alpha = score;

And if alpha starts as -INF you will certainly get into that if, and score will certainly be larger than -INF. In fact it could be board_eval + 950, and 950 is probably larger than FUTILE_MARGIN...

[Desperado]

What I wanted to say is that if you do a search like this:

Code: Select all

depth=1, alpha = -INF, beta= +INF

The root node will be a PV node and a frontier node at the same time.

and imagine you have a condition before make a move like this:

Code: Select all

if &#40;depth ==1 && board_eval + material_gain&#40;move&#41;  + FUTILE_MARGIN < alpha&#41;
  continue;

This contidion won't affect to anything, because you'll never enter inside the 'if'. Your alpha is -INF, so nothing is lower than this.

What I wanted to say is that the latter is not true. Because alpha won't stay -INF for the duration of the node. After the first move is search, you do

Code: Select all

if(score > alpha) alpha = score;

And if alpha starts as -INF you will certainly get into that if, and score will certainly be larger than -INF. In fact it could be board_eval + 950, and 950 is probably larger than FUTILE_MARGIN...

I think he mixed by accident 2 cases:

1: first case is exactly what you describe
2: second case, if this node is started with aspiration bounds
and there might be no "score > alpha", or no other condition
that leads to a real value. (so the complete move loop may
be pruned ??!) and additionally no bestValue update in a
failsoft framework, then there might be an undefined phantom
score returned...

I think he had in mind sth like that, but who knows...

[Desperado]

just a minor correction... better to handle the "openWindow" test
within the aspirationLoop i think..

Code: Select all

void iterate() 
{ 
 //... 

 //ITERAION LOOP 
 for(ctl->iteration = onePly;!stopSearch(canStop);ctl->iteration += onePly) 
 { 
  // ... robbo, aspiration search... 
  if&#40; ctl->iteration >= 14 && absN&#40;lastValue&#41;<OPENWINDOW&#41; 
  &#123; 
   // aspirationWindow 
   delta  = 8; 
   aspiLo = guess - delta; 
   aspiHi = guess + delta; 

   // ASPIRATION LOOP 
   do 
   &#123; 
     // make sure technical bounds do not crash 
     // or simply decide to open fully a direction 
     // from a certain value on. 
     if&#40; aspiLo < -OPENWINDOW )   aspiLo = lbound; 
     if&#40; aspiHi >  OPENWINDOW )   aspiHi = ubound;

     value = nodeRoot&#40;pos,mliRoot,aspiLo,aspiHi,ctl->iteration,plyRoot&#41;; 

     // pv hit 
     if&#40; value > aspiLo && value < aspiHi ) break;
          
     // handle fail lo 
     if&#40; value <= aspiLo ) 
     &#123; 
      aspiLo -= delta; 
      delta  += delta / 2; 
      guess   = aspiLo; 
     &#125; 
     // handle fail hi 
     else 
     &#123; 
      aspiHi += delta; 
      delta  += delta / 2; 
      guess   = aspiHi; 
     &#125; 
    &#125;while&#40;1&#41;; 
  &#125; 

  //full window
  else   value = nodeRoot&#40;pos,mliRoot,lbound,ubound,ctl->iteration,plyRoot&#41;; 
  //... 
 &#125; 

[Desperado]

Sorry, for the next one... (hope it is the last correction)
lastValue == guess (checking the first condition), just to avoid confusion...
time for bed now...

Code: Select all

void iterate() 
{ 
 //... 

 //ITERAION LOOP 
 for(ctl->iteration = onePly;!stopSearch(canStop);ctl->iteration += onePly) 
 { 
  // ... robbo, aspiration search... 
  if&#40; ctl->iteration >= 14 && absN&#40;guess&#41;<OPENWINDOW&#41; 
  &#123; 
   // aspirationWindow 
   delta  = 8; 
   aspiLo = guess - delta; 
   aspiHi = guess + delta; 

   // ASPIRATION LOOP 
   do 
   &#123; 
     // make sure technical bounds do not crash 
     // or simply decide to open fully a direction 
     // from a certain value on. 
     if&#40; aspiLo < -OPENWINDOW )   aspiLo = lbound; 
     if&#40; aspiHi >  OPENWINDOW )   aspiHi = ubound; 

     value = nodeRoot&#40;pos,mliRoot,aspiLo,aspiHi,ctl->iteration,plyRoot&#41;; 

     // pv hit 
     if&#40; value > aspiLo && value < aspiHi ) break; 
          
     // handle fail lo 
     if&#40; value <= aspiLo ) 
     &#123; 
      aspiLo -= delta; 
      delta  += delta / 2; 
      guess   = aspiLo; 
     &#125; 
     // handle fail hi 
     else 
     &#123; 
      aspiHi += delta; 
      delta  += delta / 2; 
      guess   = aspiHi; 
     &#125; 
    &#125;while&#40;1&#41;; 
  &#125; 

  //full window 
  else   value = nodeRoot&#40;pos,mliRoot,lbound,ubound,ctl->iteration,plyRoot&#41;; 
  //... 
 &#125; 

[asanjuan]

1: first case is exactly what you describe
2: second case, if this node is started with aspiration bounds
and there might be no "score > alpha", or no other condition
that leads to a real value. (so the complete move loop may
be pruned ??!) and additionally no bestValue update in a
failsoft framework, then there might be an undefined phantom
score returned...

well, at least one understood me

[hgm]

2: second case, if this node is started with aspiration bounds
and there might be no "score > alpha", or no other condition
that leads to a real value. (so the complete move loop may
be pruned ??!) and additionally no bestValue update in a
failsoft framework, then there might be an undefined phantom
score returned...

But bestValue starts at -INF, in a fail-soft framework, right? If you let it start as an uninitialized variable, it would almost always return phantom scores, because it will often start above alpha, or even beta, end thus never get updated.

[ZirconiumX]

I modelled my aspiration code on Harald's pseudocode.

Does this look OK?

Code: Select all

int search_full_root(list_t * list, board_t * board, int depth, int search_type) {

   int value;
   int alpha, beta;
   int alpha_delta, beta_delta;

   ASSERT(list_is_ok(list));
   ASSERT(board_is_ok(board));
   ASSERT(depth_is_ok(depth));
   ASSERT(search_type==SearchNormal||search_type==SearchShort);

   ASSERT(list==SearchRoot->list);
   ASSERT(!LIST_IS_EMPTY(list));
   ASSERT(board==SearchCurrent->board);
   ASSERT(board_is_legal(board));
   ASSERT(depth>=1);

   alpha_delta = 32;
   beta_delta = 32;

   if &#40;depth <= 3&#41; &#123;
      value = full_root&#40;list,board,-ValueInf,+ValueInf,depth,0,search_type&#41;;
   &#125; else &#123;
      do &#123;
         alpha = SearchRoot->last_value - alpha_delta;
         beta = SearchRoot->last_value + beta_delta;

         value = full_root&#40;list,board,alpha,beta,depth,0,search_type&#41;;

	 if &#40;false&#41; &#123;
	 &#125; else if &#40;value <= alpha&#41; &#123;
            alpha_delta *= 4;
	    depth--;
	 &#125; else if &#40;value >= beta&#41; &#123;
	    beta_delta *= 4;
	    depth--;
	 &#125; else break;
      &#125; while &#40;true&#41;;
   &#125;

   ASSERT&#40;value_is_ok&#40;value&#41;);
   ASSERT&#40;LIST_VALUE&#40;list,0&#41;==value&#41;;

   return value;
&#125;

I did tell a slight lie in that I do it in the middle-end (for want of a better phrase), not the front-end (Fruit's search() function in search.cpp)

@Michael: Cyclone uses the "classical approach", but after adding it, looking at it, I had a "nullmove moment" ("How can skipping your turn help so much???") and decided that Stockfish's method made much better sense. So I implemented it *from memory* and ummmm... Look where it has got me.

But, thanks to Harald, I can safely say that my engine searches deeper than Stockfish 2.2.2 o the same computer, for 1 minute. I am happy now.

Matthew:out