B* in QS

[hgm]

For my Shogi engine I am in need of a search algorithm that can handle scores with error bars. It seems that the required algorithm is called B*. Would this be a correct implementation?

Code: Select all

int returnedUpperLim;

int Search(alpha, beta)
{
  bestScore = bestUpperLimit = Eval();
  for(ALL_CAPTURES) {
    if(bestScore > alpha) {
      alpha = bestScore;
      if(alpha >= beta) {
        bestUpperLimit = INFINITY; // unsearched moves can be arbitrary strong
        break;
      }
    }
    upperLimit = - Search(-beta, -alpha);
    score = -returnedUpperLim; // score is the lower limit after negamax swap
    if(upperLimit > bestUpperLimit) bestUpperLimit = upperLimit;
    if(score > bestScore) bestScore = score;
  }
  returnedUpperLim = bestUpperLimit;
  return bestScore;
}

[Michael Sherwin]

B* is searching the supposed best move first all the way to max depth as long as its eval does not fall below that of the second best. If it does, then that line is stopped and computation starts from the before second best. So in B* you must retain the tree except for those branches that have been permanently pruned. B* can and does miss shallow tactics and yet sees very deep tactics, including mate. It is like a mouse in a maze. The mouse might find the cheese that is 12 turns away and never find the cheese that is 3 turns away. However, using B* at the end leafs for just a few ply before entering qsearch may be an effective way of getting deeper along those lines that are deemed more critical.

[Antonio Torrecillas]

If you agree that the upperLimit of one player is the lower limit of the other,
you need two values, who exchange places (upper/lower) and sign as you backup.
As we do with (alpha,beta) -> (-beta,-alpha), but for the returned (upper,lower) value -> (-lower,-upper).

This is how Hitech B* backed up this bounds values.

(with this idea, the upperlimit can't be a global variable.)

I think there is two types of error: the static evaluation error, and the imcomplete search stuff.
Berliner, Palay ... only try to address the evaluation error in PB*.
With this restriction the search say:
this is the node who best represent the search so far,
that his PV and his associated value, and this upper,lower bound etc...

If you follow the same idea, it should be appropriate to return the limits from the same node who gave the value.

Berliner used these limits to establish the separation criterion:
If no value overlaps the best move we can finish the search.

As we are only interested to know the best move in the root,
the separation criterion was not used in any intermediate node.

Unfortunately this criterion is not good enough.
the search can change the PV path in each iteration (ID) or step (B*) and therefore the values associated...
and may be the criterion no longer meet.

The other use of the limits is to estimate the probability of being the best move ...
this would be useful if you want to implement PB * or a Monte Carlo algorithm.

I Hope this dirty summary help you.