QSearch and endgames

[MOBMAT]

When an engine doesn't use EGTBs or if they are disabled, what is a good rule about when to / when not to call QSearch prior to calling specialized endgame code, such as a mop-up routine?

I'm proceeding with the premise that if the number of pieces is left is low enough to trigger endgame code, then don't bother with QS.

I haven't seen a thread on this topic, but the little testing I've done has shown that calls to QS slow things down in these situations.

Opps, forgot the example code...

Code: Select all

	if (depth <= 0)
		{
		if (p->PieceCount() <= 6)
			v = Evaluate(p);
		else
			v = QSearch(p, alpha, beta);
		return v;

[hgm]

If you would not call QS your end-game code would have to evaluate non-quiet positions. This seems just as bad an idea as not calling QS in the middle game, and let the static evaluation deal with hanging pieces.

There are positions where it is pointless to search on, however. (E.g. in KBKN with the Kings not in a corner.) If a full-width search is pointless, QS will of course also be pointless. If you have the possibility to convert to KBK near the root (say from KBPKN through NxP, KxN), you would not want the KBK branch to be searched as deeply as the KBPKN sub-tree before you conclude that wherever it goes it will be a draw. (Eating away nodes from the part that matters.)

So end-game code comes in two varieties: special cases of static evaluation, and absolute evaluations that need no further search. Winning / losing EGT probes fall in the latter category.

Note that it is not very important to have the code for a specific end-game cover all possible positions. The important thing is to cover the positions that would be mis-evaluated by the normal evaluation, and where this misevaluation would be persistent. Positions where the mis-evaluation would resolve itself in a few moves are not so much of a problem (although any correct knowledge of course will have some positive effect, even if only marginal). E.g. it is pretty hard to determine when exactly KBPK is a draw, but when the defending King is on or adjacent to the promotion square of a rook Pawn, and the Bishop has the wrong color, it is certainly a draw. Implementing only that rule (as absolute evaluation) leaves it to the search to figure out whether you can cut off the King from the promotion square, and consequently win. When the defending King can reach the corner it would not take more than a few moves to reach it, and the search will have no problem to see that. Otherwise the normal evaluation is satisfactory. Or you could give it a discount of a factor 2 when the Pawn is a rook Pawn and the Bishop has the wrong color, to make it prefer going for KPPK rather than such a KBPK when it still has the choice and not enough depth left to figure out the exact fate of the KBPK.

In a similar spirit, for KPK you would just need to recognize the case where the defending King is one or two squares in front of the Pawn, or has opposition, to correct the 'naive' evaluation score to draw. These are the situations where the defender could hold out forever, and the attacker can avoid repetitions or stalemate for a long time, so that the search could only discover it is a draw through the 50-move rule, which would be way beyond the horizon before it is too late. Just be sure that all positions that the defender would have to go through in the process of defending will be recognized as (absolute) draw. This also geratly speeds up the search for a win, because bad moves for the attacker (which usually are most moves, in a won position) get pruned immediately, or have very small subtrees before the defender punishes them, so that it takes far fewer nodes to find the promotion.

[Sven]

In a similar spirit, for KPK you would just need to recognize the case where the defending King is one or two squares in front of the Pawn, or has opposition, to correct the 'naive' evaluation score to draw.

Note the exceptions: against a non-rook pawn on 6th (3rd) rank the defending king two squares in front of the pawn only holds a safe draw if it is his turn (otherwise it depends on the position of the attacking king), and on 7th (2nd) rank the defending king one square in front of the pawn only draws safely if it is not his turn. For rook pawns the drawing zone for the defending king is also much larger, and there are additional draws with horizontal opposition and the attacking king in front of his pawn.

Apart from these special cases I fully agree: not calling QS in special endgames is dangerous without EGTB access since it would require a perfect static endgame evaluation in some cases. For instance one might have a hard time evaluating the following position correctly without both EGTB and QS:

[d]4K3/3N1P2/8/2bk4/8/8/8/8 w - - 0 1
A rule of thumb might say: White only has one pawn left and Black can "always" sacrifice his bishop against that pawn, so it would be a draw.

[hgm]

Indeed, I did not mean to imply opposition would always guarantee a draw. This is the code I used in KingSlayer (simple.c in my on-line source repository):

Code: Select all

int
KPKdraw (int side)
{ // identify some draw positions that will not quickly resolve.
  int king = location[side+KING], pawn = location[side+PAWN], hisKing = location[KING+8-side];
  int myTurn = (side == stm), forward = 16-4*side; // from strong-side POV
  int promo = (pawn & 7) + 7*16*!side;             // promotion square
  int lastRank = !((hisKing^promo) & 0x70);        // bare King is on last rank
  int next = (king == pawn+1 || king == pawn-1);   // strong-side King standing beside Pawn
  int edge = (pawn & 7) == 0 || (pawn & 7) == 7;   // Pawn is on edge file
  int d = dist[pawn-promo], stopSqr;

  if(board[pawn] != side+PAWN) return 0;       // sanity check, as location[] is not 100% reliable for Pawns
  if(dist[hisKing-king] < 2) return 0;         // reject illegal position. (KPKdraw is called before legality test...)
  if(myTurn && aligned[hisKing-pawn] & code[side+PAWN]) return 0; // Pawn captures King

  // rule of squares
  d -= (d ==6);                                      // account for initial double-push
  if(d - myTurn < dist[hisKing-promo] - 1) return 0; // outside 'square' is always won

  if(edge) { // rook-pawns: detect some cases that don't apply to other Pawns
    int dPath = (hisKing^pawn) & 7;                                       // distance of bare King to Pawn path
    if(dPath < 2 && dist[hisKing - promo] < d - dPath) return 1;          // bare King in or next to path of Pawn
    if(((king^pawn) & 7) == 0 && dist[hisKing - (king^2)] < 2 - myTurn)   // own King is trapped in path of Pawn
      return 1;
  }

  if(hisKing == pawn + forward)   return (!lastRank | myTurn);            // I must stalemate him or abandon Pawn
  if(pawn == (promo^16)) return 0;                                        // play out other 7th-rank Pawns

  stopSqr = pawn + 2*forward;
  if(stopSqr == promo) { // last-rank defense; quite tricky!
    return (dist[hisKing - promo] < 2 && (!next || dist[king + 2*forward - hisKing] + myTurn == 1));
  } else return (dist[stopSqr - king] - myTurn > dist[stopSqr - hisKing]);
  if(hisKing == stopSqr) return (edge | !lastRank | !myTurn | !next);     // 2 squares in front of Pawn

  if((pawn&0x70) == (king&0x70)) { // attacking K is on same rank as P
    if(dist[stopSqr - hisKing] <= 1 && !myTurn && !lastRank) return 1;    // he can step in path
    if(hisKing == king + 2*forward) return (!lastRank || next && myTurn); // oppose K next to P (cut off on last rank!)
    if(dist[king + 4*forward - hisKing] + myTurn == 1) return 1;                   // he has far opposition (or can take it)
  }
  if((pawn&0x70) == (king&0x70) - forward) { // attacking K is on rank before P
    return (!lastRank & dist[king + 2*forward - hisKing] + myTurn == 1);           // he has opposition, or can take it
  }

  return 0;
}

(The values to identify white and black in stm and side are 0 and 8, respectively. The routine returns 1 to indicate the position is a draw.)