Early futility pruning

[sje]

Early futility pruning in the quiescence search

A common scheme is to generate moves at a node then try only those which can pass some threshold test based in part on possible gain for that move.

Now it may be the case that none of the moves can pass the threshold test. It would be nice if this case were detected early, prior to move ordering and even before move generation.

To help with this, a program needs a routine which will quickly determine the maximum possible gain in a position. Here's Symbolic's version:

Code: Select all

SV Position::CalcMaxGain(void) const
{
  // For the given position, determine the maximum possible material gain
  
  SV maxgain = 0;
  Bitboard bb;
  Sq sq;
  
  // If there's a valid en passant target, then a pawn can be gained

  if (IsSqNotNil(fss.epsq))
    maxgain = SvPawn;

  // Update the maximum gain by scanning all attacked evil men for simple captures
  
  bb = bbdb.GetLocbc(fss.evil) & bbdb.GetAtkbc(fss.good);
  while (IsSqNotNil(sq = bb.NextSq()))
  {
    const SV gain = ManSvVec[board.GetMan(sq)];

    if (maxgain < gain)
      maxgain = gain;
  };

  // Update the maximum gain with any pawn promotion moves
  
  bb = bbdb.GetLocbm(SynthPawn[fss.good]) & Bitboard::RankBBVec[CvColorToOrd7Rank[fss.good]];
  while (IsSqNotNil(sq = bb.NextSq()))
  {
    SqPtr tosqptr;
    Sq tosq;
    
    // Check non-capture promotions

    tosq = NextSquare[sq][CvColorToAdvanceDir[fss.good]];
    if (IsManVacant(board.GetMan(tosq)))
    {
      const SV gain = SvQueen - SvPawn;

      if (maxgain < gain)
        maxgain = gain;
    };

    // Check capture promotions

    tosqptr = PawnRunPtrs[fss.good][sq];
    while (IsSqNotNil(tosq = *tosqptr++))
    {
      const Man toman = board.GetMan(tosq);

      if (CvManToColor[toman] == fss.evil)
      {
        const SV gain = SvQueen - SvPawn + ManSvVec[toman];

        if (maxgain < gain)
          maxgain = gain;
      };
    };
  };

  return maxgain;
}

[zd3nik]

Do you have any stats around this? I'd be interested in seeing how much time is spent in this routine compared to how much time it saves. Or at least how much time this routine uses compared to quiescence move generation - which is generally really fast if you're using bitboards or some other scheme that provides very fast capture generation.

I'm thinking it might be more efficient to write a quiescence move generator that produces one move at a time in (likely) best first order. I've written move generators like this, so I know it's possible. Then you would only need to spend the time generating one move to know if you can pass the threshold. And if it does pass the threshold you haven't wasted any time prior to move generation.

[sje]

Do you have any stats around this? I'd be interested in seeing how much time is spent in this routine compared to how much time it saves.

Very roughly, the time savings runs from zero to ten percent. Much depends on how much time is saved by eliminating generation and ordering at terminal candidate nodes.

[hgm]

This seems to require knowledge on which pieces are attacked, which sort of implies that move generation must already have been done. I usually do this kind of 'global futility' just based on the enemy material present on the board, as recorded in the material key. The non-Pawn part of that key can only have 54 different values if there haven't been any super-numerary promotions (and 81 if you allow for two Queens), so it is quite cheap to keep tables that you can index by it that give you the value of the highest piece, or the sum of the value of the two highest pieces.

That doesn't guarantee they are attacked, of course, but for that you need move generation. When you do staged move generation, and generate captures victim by victim in decreasing value order (as I do in Spartacus) this kind of 'global futility' becomes sort of automatic: you start with the highest piece in the opponent's piece list, and the first thing you do with any potential victim then is to check if its capture would be futile. If it is, you are done with move generation (at d <= 1) and can fail low immediately. (Perhaps except for checks; if you do those at that level you continue with a dedicate checks generator.) So you limit the move generation effort in a globally futile node to conclude for the non-futile potential victims that they were not actually capturable.

In the capture-matrix approach you would keep that information incrementally, in a bitmap where each bit corresponds to an (attacker, victim) combination, so that you would only have to mask out the set of bits for all non-futile victims, and if it is zero the node is globally futile. You can even do that based on the capture matrix as it was before update, as the update can only add moves that the preceding opponent ply discovered. You then in addition would have to test for presence of slider captures to the from-square of the previous move, and in the comparatively rare case there were, do a more complex test to see if the elongated move would hit a non-futile victim. Conversely you would have to confirm non-futility for not being based on a capture with the victim of the previous move (or, in the case it was a non-capture, by a capture with a move that was blocked). The latter test is a bit complex, and not much is lost by postponing it until after update of the capture matrix, as it is comparatively rare that the test would have to be invoked, and even rarer that it would decide that the move was futile after all: futility typically happens in deep QS nodes when you start to run out of captures, and when the parent node is also QS there aren't many non-captures in there. And if there are, most of them would not block your only non-futile captures.

Checking for promotions can be done cheaply with a primary filter for having 7th-rank Pawns based on your Pawn bitboard, (and only worry about whether they can actually move if it passes that test, which would rarely happen). Or for mailbox, where this is more expensive, it can be a flag in in the Pawn-hash info. (In fact the simple demo engine I started writing already keeps the location of the most advanced passer in the PawnInfo struct, which could be used as basis for a primary filter.)