PVS

[Rein Halbersma]

Yes. Maybe we should repost the code with the 2 bugfixes

Code: Select all

Call from root:
    rootscore = PVS(-infinite,infinite,depthleft);


int PVS(alfa,beta,depthleft) {
  if( depthleft <= 0 ) return qsearch(alfa,beta);

  // using fail soft with negamax:
  bestscore = -PVS(-beta,-alfa,depthleft-1);
  if( bestscore > alfa ) {
    if( bestscore >= beta )
      return bestscore;
    alfa = bestscore;
  }

  for( all remaining moves ) {
    score = -PVS(-alfa-1,-alfa,depthleft-1);
    if( score > alfa && score < beta ) {
      // research with window [alfa;beta]
      score = -PVS(-beta,-alfa,depthleft-1);
      if( score > alfa )
        alfa = score;
    }

    if( score > bestscore ) {
      if( score >= beta )
        return score;
      bestscore = score;
    }
  }
  return bestscore;
}

Sven

This version of PVS is now also used at CPW. I wonder why the research is with alpha as a lower bound, rather than score. I.e. why

Code: Select all

// research with window [alfa;beta]
      score = -PVS(-beta,-alfa,depthleft-1);

rather than

Code: Select all

// research with window [score;beta]
      score = -PVS(-beta,-score,depthleft-1);

The old paper by Marsland (1986) http://webdocs.cs.ualberta.ca/~tony/Old ... review.pdf gives the latter version. Any help appreciated.

[Gian-Carlo Pascutto]

The version from Marsland is ok if you don't use hashtables, nullmove, extensions and whatever else. Then you can be confident that if a search fails high with some score, it's going to return at least the same score on the research.

But while that sounds logical, it's just not true in real programs, so you want the more pessimistic window.

[Rein Halbersma]

The version from Marsland is ok if you don't use hashtables, nullmove, extensions and whatever else. Then you can be confident that if a search fails high with some score, it's going to return at least the same score on the research.

But while that sounds logical, it's just not true in real programs, so you want the more pessimistic window.

OK, if I understand it correctly: if the null-window search fails high, then using the fail-soft score as a bound in the re-search can give a fail-low if one uses fancy pruning tricks. That makes sense, but don't such search instabilities also occur if you research with alpha as a bound, or do they just occur less often? And if they do, how does one treat such search instabilities? Yet another re-search?

[Gian-Carlo Pascutto]

OK, if I understand it correctly: if the null-window search fails high, then using the fail-soft score as a bound in the re-search can give a fail-low if one uses fancy pruning tricks. That makes sense, but don't such search instabilities also occur if you research with alpha as a bound, or do they just occur less often? And if they do, how does one treat such search instabilities? Yet another re-search?

Your understanding is correct.

One point to note: in the original post, the window of -beta, -score doesn't allow you to determine, for a result of "score", whether this is a true score or a bound. Regardless of pruning etc this can cause some additional issues, such as not having a PV. So even if you use that, you want -score+1.

If you use a window of alpha, beta, and the score comes back outside alpha, you will propagate the fail high upwards and perform the research at that level. This wouldn't be the case when the result would be "score".

[Rein Halbersma]

OK, if I understand it correctly: if the null-window search fails high, then using the fail-soft score as a bound in the re-search can give a fail-low if one uses fancy pruning tricks. That makes sense, but don't such search instabilities also occur if you research with alpha as a bound, or do they just occur less often? And if they do, how does one treat such search instabilities? Yet another re-search?

Your understanding is correct.

One point to note: in the original post, the window of -beta, -score doesn't allow you to determine, for a result of "score", whether this is a true score or a bound. Regardless of pruning etc this can cause some additional issues, such as not having a PV. So even if you use that, you want -score+1.

If you use a window of alpha, beta, and the score comes back outside alpha, you will propagate the fail high upwards and perform the research at that level. This wouldn't be the case when the result would be "score".

OK, some time was needed to process your arguments. So the fail-high returning v on the [a,a+1] search can be triggered by spurious null move prunings 2 plies from the root. Re-searching with [a,b] will remove most such false null move triggers. Then the re-search will get either a fail-low or get a new pv. Either case, all is well.

OTOH, if you had re-searched with [v,b], the spurious null moves still would have been removed and the search might have returned a little cheaper (because of the tighter v bound). However, now you could introduce a spurious null move at 1 ply from the root (again because of the tighter v bound). Even worse, if a+1 < v < b, you can get a fail-low at the root with value w below the re-search window but above the old null window! The (theoretically) slightly quicker re-search probably doesn't outweigh the hassle of this annoying case.

So you convinced me that the research needs to be done with [a,b]. Thanks for the help!