SEE

[AlvaroBegue]

Oh, in case it's not evident to everyone in this thread, the version with `material + victimValue < alpha' has the advantage that you can prune the rest of the captures, because MVV-LVA order guarantees that all remaining moves will also fail the test.

[hgm]

Yes, that is a situation where this technique would prune too much. Testing is the only way to tell if this is enough of a problem that the technique is not worth it. According to Bob's tests and my own, it is definitely worth it.

But have you tried to exempt even-valued SEE, to test if it is even better?

[AlvaroBegue]

Yes, that is a situation where this technique would prune too much. Testing is the only way to tell if this is enough of a problem that the technique is not worth it. According to Bob's tests and my own, it is definitely worth it.

But have you tried to exempt even-valued SEE, to test if it is even better?

It's not particularly easy for me to test that, and I don't have much hope that it will help. Most stupid captures are of the type QxP, ?xQ, which have "even SEE". I don't want to spend any time on them.

[hgm]

Yes, but I am talking about captures with SEE > 0, but material + SEE < alpha. Q x protected P usually do not fall in that category. (Could be QxP, QxQ, KxQ, though, for a clean +1.)

[hgm]

I had an interesting idea for implementing BLIND in a quite trivial way, so that even future versions of micro-Max might be able to afford pruning of bad captures in QS:

Code: Select all

int QS(alpha, beta, sacred)
{
  int currentEval = Evaluate();
  if(currentEval > alpha) return currentEval; // stand pat
  GenerateCaptures();
  for(ALL_MOVES) {
    if(toSqr == sacred) return INF; // abort because recapture was possible
    sortKey[moveNr] = 16*value[victim] - value[piece] // MVV/LVA key
  }
  SortMoves();
  for(ALL_MOVES) {
    MakeMove();
    score = -QS&#40;-beta, -alpha, value&#91;victim&#93; < value&#91;piece&#93; ? toSqr &#58; INVALID_SQR&#41;;
    UnMake&#40;);
    if&#40;score > alpha&#41; &#123; // usual alpha-beta stuff
      if&#40;score >= beta&#41; return beta;
      alpha = score;
    &#125;
  &#125;
  return alpha;
&#125;

Or in words: whenever a High x Low capture takes place, you pass a flag to the daughter node that declares the capturer 'sacred', i.e. temporary royal in that node. So that if the captured piece was protected, the daughter will abort without searching any moves, leaving the HxL capture with a score -INF, like it was illegal or did not exist. Thus you effectively prune all H x protected L. The work to determine that the victim was protected is deferred to the daughter node, which runs the move generator for it.

In less dumb engines, with staged capture generation by victim value, you would do this by generating captures of the sacred piece before trying to capture anything else, even if that would violate MVV ordering, as the first capture of it that you find would allow you to abort the node without search. (Hairy detail: this assume legal move generation; with pseudo-legal moves you would still have to check if that recapture was legal, because 'false protectors', pinned on King, should not scare you off.)


You can even refine it a bit, allowing the search of HxL captures that lure a piece to the swap square the capture of which could conceivably make you break even (e.g. RxB, NxR, ?xN or QxP, QxQ, ?xQ):

Code: Select all

int QS(alpha, beta, sacred, threshold)
{
  int currentEval = Evaluate();
  if(currentEval >= alpha) return currentEval; // stand pat
  GenerateCaptures();
  for(ALL_MOVES) {
    if&#40;toSqr == sacred && value&#91;piece&#93;<=threshold&#41; return INF; // abort because cheap recapture was possible
    sortKey&#91;moveNr&#93; = 16*value&#91;victim&#93; - value&#91;piece&#93; // MVV/LVA key
  &#125;
  SortMoves&#40;);
  for&#40;ALL_MOVES&#41; &#123;
    MakeMove&#40;);
    score = -QS&#40;-beta, -alpha, value&#91;victim&#93; < value&#91;piece&#93; ? toSqr &#58; INVALID_SQR, value&#91;piece&#93;-value&#91;victim&#93;);
    UnMake&#40;);
    if&#40;score > alpha&#41; &#123; // usual alpha-beta stuff
      if&#40;score >= beta&#41; return beta;
      alpha = score;
    &#125;
  &#125;
  return alpha;
&#125;

Or you could still abort on any recapture, but report back whether the recapture was 'cheap' (i.e. by a piece that is not worth the investment) or not:

Code: Select all

    if(toSqr == sacred) return INF + (value[piece]>threshold); // abort because recapture was possible

The parent node can recognize the return value INF+1, and use it to schedule the move for a retry after all obviously good (LxH or equal) captures of lower victims have been searched first. (I.e. group it with the 'dubious captures'. Which would of course be searched, when their time comes, with sacred = INVALID_SQR, so they would not be aborted again.)

Note that none of this uses SEE in any way. But it does a lot of pruning.