/** Copyright (c) Scott Gasch Module Name: recogn.c Abstract: This code is based on an article by Ernst A. Heinz: "Efficient Interior-Node Recognition" * ICCA Journal Volume 21, No. 3, pp 156-167 (also "Scalable Search in Computer Chess" pp 65-81). This code also borrows ideas from Thorsten Greiner's AMY chess program. Author: Scott Gasch (scott.gasch@gmail.com) 16 Oct 2005 Revision History: **/ #include "chess.h" // See eval.c's identical comment: routes this file's KBNK/KBKB // adjacency-check bitboard-scan loops (called every node via // RecognLookup in search.c) to the inlined // FastCoorFromBitBoardRank8ToRank1 (chess.h) instead of the real // out-of-line extern call. #ifndef CROUTINES #define CoorFromBitBoardRank8ToRank1 FastCoorFromBitBoardRank8ToRank1 #endif extern ULONG g_uIterateDepth; static COOR QUEENING_SQUARE_BY_COLOR_FILE[2][8] = { { A1, B1, C1, D1, E1, F1, G1, H1 }, { A8, B8, C8, D8, E8, F8, G8, H8 } }; #define RECOGN_INDEX(w, b) \ (((b) | (w)) + (32 * ((w) && (b)))) typedef ULONG RECOGNIZER(SEARCHER_THREAD_CONTEXT *ctx, SCORE *piScore); static RECOGNIZER *g_pRecognizers[64]; static BITV g_bvRecognizerAvailable[32]; static ULONG _MakeMaterialSig(IN FLAG fPawn, IN FLAG fKnight, IN FLAG fBishop, IN FLAG fRook, IN FLAG fQueen) /** Routine description: Make a material signature ULONG out of flags representing the presence of pawns, knights, bishops, rooks, queens on the board. Parameters: FLAG fPawn, FLAG fKnight, FLAG fBishop, FLAG fRook, FLAG fQueen Return value: static ULONG **/ { ULONG x; ASSERT(IS_VALID_FLAG(fPawn)); ASSERT(IS_VALID_FLAG(fKnight)); ASSERT(IS_VALID_FLAG(fBishop)); ASSERT(IS_VALID_FLAG(fRook)); ASSERT(IS_VALID_FLAG(fQueen)); x = fPawn | (fKnight << 1) | (fBishop << 2) | (fRook << 3) | (fQueen << 4); ASSERT((0 <= x) && (x <= 31)); return(x); } #ifdef DEBUG static FLAG _TablebasesSaySideWins(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uSide) { SCORE iScore; if (TRUE == ProbeEGTB(ctx, &iScore)) { if (ctx->sPosition.uToMove == uSide) { return iScore > 0; } else { return iScore < 0; } } return TRUE; } static FLAG _TablebasesSayDraw(IN SEARCHER_THREAD_CONTEXT *ctx) { SCORE iScore; if (TRUE == ProbeEGTB(ctx, &iScore)) { return iScore == 0; } return TRUE; } static FLAG _TablebasesSayDrawOrWin(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uSide) { SCORE iScore; if (TRUE == ProbeEGTB(ctx, &iScore)) { return ((iScore == 0) || ((iScore > 0) && (ctx->sPosition.uToMove == uSide)) || ((iScore < 0) && (ctx->sPosition.uToMove != uSide))); } return TRUE; } static FLAG _SanityCheckRecognizers(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iScore, IN ULONG uVal) { ULONG uToMove = ctx->sPosition.uToMove; switch(uVal) { case UNRECOGNIZED: return TRUE; case RECOGN_EXACT: if (iScore == 0) { return _TablebasesSayDraw(ctx); } else if (iScore > 0) { return _TablebasesSaySideWins(ctx, uToMove); } else { ASSERT(iScore < 0); return _TablebasesSaySideWins(ctx, !uToMove); } case RECOGN_LOWER: // // iScore is only a LOWER bound: the true score is >= // iScore, so we can only make a directional claim when the // bound itself pins one down. iScore > 0 forces a genuine // win for uToMove; iScore == 0 forces at least a draw. A // negative lower bound ("at least this bad, could be // better or worse") licenses no claim about who's actually // winning, so don't assert one. if (iScore == 0) { return _TablebasesSayDrawOrWin(ctx, uToMove); } else if (iScore > 0) { return _TablebasesSaySideWins(ctx, uToMove); } else { return TRUE; } case RECOGN_UPPER: // // Symmetric reasoning: iScore is only an UPPER bound (true // score <= iScore). iScore < 0 forces a genuine win for the // opponent; iScore == 0 forces at least a draw for the // opponent. A positive upper bound doesn't preclude uToMove // still winning by less than iScore, so no claim there. if (iScore == 0) { return _TablebasesSayDrawOrWin(ctx, !uToMove); } else if (iScore < 0) { return _TablebasesSaySideWins(ctx, !uToMove); } else { return TRUE; } default: ASSERT(FALSE); return FALSE; } } static FLAG _NothingBut(IN POSITION *pos, IN PIECE p, IN ULONG uColor) /** Routine description: Support routine to assert that nothing but the piece bits enumerated in parameter p are present in the position pos for side uColor. Parameters: POSITION *pos, PIECE p, ULONG uColor Return value: static FLAG **/ { static PIECE q[] = { KNIGHT, BISHOP, ROOK, QUEEN }; ULONG u; if (!(p & PAWN)) { if (FastCountBits(pos->bbPawns[uColor]) > 0) return(FALSE); } for (u = 0; u < ARRAY_LENGTH(q); u++) { if (!(p & q[u])) { if (FastCountBits(pos->bbPieces[uColor][q[u]]) > 0) return(FALSE); } } return(TRUE); } #endif static ULONG _RecognizeKK(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Encode the knowledge that two lone kings on the board are a draw. Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { *piScore = g_iDrawScore[ctx->sPosition.uToMove]; return(RECOGN_EXACT); } static ULONG _RecognizeKBK(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Attempt to recognize KB*KB+ positions. Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { ULONG uStrong; ULONG uBishops; COOR cWeakKing; ULONG u; ULONG uAdjacent; POSITION *pos = &ctx->sPosition; ASSERT((TotalNonPawnCount(pos, WHITE) <= 3) && (TotalNonPawnCount(pos, BLACK) <= 3)); ASSERT(_NothingBut(pos, BISHOP, WHITE)); ASSERT(_NothingBut(pos, BISHOP, BLACK)); // // Recognize KBKB as a draw unless there's a cornered king (in // which case it may be a mate-in-1) // if ((TotalNonPawnCount(pos, WHITE) == 2) && (TotalNonPawnCount(pos, BLACK) == 2)) { if ((CORNER_DISTANCE(KingPosition(pos, WHITE)) != 0) && (CORNER_DISTANCE(KingPosition(pos, BLACK)) != 0)) { *piScore = g_iDrawScore[pos->uToMove]; return(RECOGN_EXACT); } } // // Otherwise we want to deal with KB+ vs lone K. KBKBB etc are // too hard to recognize. // if ((TotalNonPawnCount(pos, WHITE) != 1) && (TotalNonPawnCount(pos, BLACK) != 1)) { return(UNRECOGNIZED); } // // If we get here then one side has no pieces (except the king). // uStrong = BLACK; if (TotalNonPawnCount(pos, WHITE) > 1) { uStrong = WHITE; } ASSERT(TotalNonPawnCount(pos, uStrong) > 1); ASSERT(TotalNonPawnCount(pos, FLIP(uStrong)) == 1); // // KB vs K is a draw, KB+ vs K is still a draw if all bishops are the // same color. // uBishops = FastCountBits(pos->bbPieces[uStrong][BISHOP]); if ((uBishops == 1) || (WhiteSqBishopCount(pos, uStrong) == 0) || (WhiteSqBishopCount(pos, uStrong) == uBishops)) { *piScore = g_iDrawScore[pos->uToMove]; return(RECOGN_EXACT); } // // If we get here the strong side has more than one bishop and has // at least one bishop on each color. // // // If the weak king is next to a strong side piece, fail to // recognize since the weak king may take the bishop with the // move. Note: we allow the weak king to be adjacent to up to one // enemy bishop as long as it's the strong side's turn to move. // cWeakKing = KingPosition(pos, FLIP(uStrong)); ASSERT(DISTANCE(cWeakKing, KingPosition(pos, uStrong)) > 1); uAdjacent = 0; { BITBOARD bbPieces = NON_KING_PIECES_BB(pos, uStrong); COOR c; while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bbPieces))) { uAdjacent += (DISTANCE(cWeakKing, c) == 1); } } if (uAdjacent > 1) { return(UNRECOGNIZED); } // // If it's the weak side's turn and the strong king is close // enough that the weak side may be stalemated, fail to recognize. // ASSERT(IS_ON_BOARD(KingPosition(pos, uStrong))); ASSERT(IS_KING(pos->rgSquare[KingPosition(pos, uStrong)].pPiece)); u = DISTANCE(cWeakKing, KingPosition(pos, uStrong)); ASSERT(u != 1); if (pos->uToMove != uStrong) { ASSERT(pos->uToMove == FLIP(uStrong)); if (uAdjacent == 1) { return(UNRECOGNIZED); } if ((u == 2) && (ON_EDGE(cWeakKing))) { return(UNRECOGNIZED); } } // // This is a recognized win for the strong side. Compute a score // that encourages cornering the weak king and making progress // towards a checkmate. // *piScore = (pos->iMaterialBalance[uStrong] + VALUE_QUEEN - (u * 16) - (CORNER_DISTANCE(cWeakKing) * 32)); ASSERT(IS_VALID_SCORE(*piScore)); if (pos->uToMove != uStrong) { *piScore *= -1; return(RECOGN_UPPER); } return(RECOGN_LOWER); } static ULONG _RecognizeKNK(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Recognize KN*KN+ positions. Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { POSITION *pos = &ctx->sPosition; ULONG uStrong; ASSERT((TotalNonPawnCount(pos, WHITE) <= 3) && (TotalNonPawnCount(pos, BLACK) <= 3)); ASSERT(_NothingBut(pos, KNIGHT, WHITE)); ASSERT(_NothingBut(pos, KNIGHT, BLACK)); // // KNKN is a draw unless someone has a K in the corner (in which case, // with the friend knight in the way, there's a possible mate) // if ((TotalNonPawnCount(pos, WHITE) == 2) && (TotalNonPawnCount(pos, BLACK) == 2)) { if ((CORNER_DISTANCE(KingPosition(pos, WHITE)) != 0) && (CORNER_DISTANCE(KingPosition(pos, BLACK)) != 0)) { *piScore = g_iDrawScore[pos->uToMove]; return(RECOGN_EXACT); } return(UNRECOGNIZED); } // // KNNKN etc... unrecognized. Heinz says "exceptional wins possible for // any side by mates in seven or less moves." TODO: add this knowledge. // if ((TotalNonPawnCount(pos, WHITE) != 1) || (TotalNonPawnCount(pos, BLACK) != 1)) { return(UNRECOGNIZED); } // // If we get here somebody has no pieces (except a lone king). // uStrong = WHITE; if (TotalNonPawnCount(pos, BLACK) > 1) { uStrong = BLACK; } ASSERT(TotalNonPawnCount(pos, uStrong) > 1); ASSERT(TotalNonPawnCount(pos, FLIP(uStrong)) == 1); // // Call KNNK a draw unless the weak K is on the edge of the board // where a checkmate is possible (e.g. 8/8/8/8/8/N2N4/4K3/2k5 b - -) // Everything else in here is a draw. // ASSERT(TotalNonPawnCount(pos, uStrong) < 4); if (ON_EDGE(KingPosition(pos, FLIP(uStrong)))) { return(UNRECOGNIZED); } *piScore = g_iDrawScore[pos->uToMove]; return(RECOGN_EXACT); } // // DISABLED -- not currently registered in InitializeInteriorNodeRecognizers // (see the comment there). testrecogn.c's EGTB cross-check found a // counterexample in the bare-lone-king mating branch below (1k6/8/8/8/ // 1bn5/8/1K6/8 w): the classic KBN-vs-K "wrong corner" subtlety -- // mate is only forceable in the corner matching the bishop's square // color, and this function's bail-out conditions don't fully capture // that. Left in place as a starting point; validate any future fix // against testrecogn.c's KNBK case before re-registering. // static ULONG __attribute__((unused)) _RecognizeKBNK(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { ULONG uStrong; COOR cWeakKing; COOR cKnight; ULONG u; ULONG uDist; ULONG uAdjacent; POSITION *pos = &ctx->sPosition; ASSERT((TotalNonPawnCount(pos, WHITE) <= 3) && (TotalNonPawnCount(pos, BLACK) <= 3)); ASSERT(_NothingBut(pos, BISHOP | KNIGHT, WHITE)); ASSERT(_NothingBut(pos, BISHOP | KNIGHT, BLACK)); if ((TotalNonPawnCount(pos, WHITE) > 1) && (TotalNonPawnCount(pos, BLACK) > 1)) { // // Do not recognize stuff like KNNKB or KNKBB etc... // if (TotalNonPawnCount(pos, WHITE) + TotalNonPawnCount(pos, BLACK) > 4) { return(UNRECOGNIZED); } // // This is KNKB; unless someone's king is on the edge, // recognize a draw. // ASSERT((TotalNonPawnCount(pos, WHITE) == 2) && (TotalNonPawnCount(pos, BLACK) == 2)); if (ON_EDGE(KingPosition(pos, WHITE)) || ON_EDGE(KingPosition(pos, BLACK))) { return(UNRECOGNIZED); } *piScore = g_iDrawScore[pos->uToMove]; return(RECOGN_EXACT); } // // If we get here we are in a KBNK endgame. // uStrong = WHITE; if (TotalNonPawnCount(pos, BLACK) > 1) { uStrong = BLACK; } ASSERT(TotalNonPawnCount(pos, uStrong) > 1); ASSERT(TotalNonPawnCount(pos, FLIP(uStrong)) == 1); cWeakKing = KingPosition(pos, FLIP(uStrong)); ASSERT(IS_ON_BOARD(cWeakKing)); ASSERT(IS_KING(pos->rgSquare[cWeakKing].pPiece)); // // Don't recognize anything where the N is in a corner near the // lone king. It's possible for the lone king to trap it there // thus drawing the game. // cKnight = CoorOfSingleBit(pos->bbPieces[uStrong][KNIGHT]); if ((CORNER_DISTANCE(cKnight) == 0) && (DISTANCE(cWeakKing, cKnight) == 1)) { return(UNRECOGNIZED); } // // Don't recognize anything if the weak king is next to a strong side's // piece. // uAdjacent = 0; { BITBOARD bbPieces = NON_KING_PIECES_BB(pos, uStrong); COOR c; while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bbPieces))) { uAdjacent += (DISTANCE(c, cWeakKing) == 1); } } if (uAdjacent) { return(UNRECOGNIZED); } // // Don't recognize if the two kings are close enough to each other // that there might be a stalemate if the weak side is on move and // on the edge. // ASSERT(IS_ON_BOARD(KingPosition(pos, uStrong))); ASSERT(IS_KING(pos->rgSquare[KingPosition(pos, uStrong)].pPiece)); u = DISTANCE(cWeakKing, KingPosition(pos, uStrong)); ASSERT(u != 1); if (pos->uToMove != uStrong) { ASSERT(pos->uToMove == FLIP(uStrong)); if ((u == 2) && (ON_EDGE(cWeakKing))) { return(UNRECOGNIZED); } } // // Calculate a score that grabs the search's attention and makes // progress towards driving the weak king to the correct corner to // mate him. // if (WhiteSqBishopCount(pos, uStrong) > 0) { uDist = WHITE_CORNER_DISTANCE(cWeakKing); } else { uDist = BLACK_CORNER_DISTANCE(cWeakKing); } ASSERT((0 <= uDist) && (uDist <= 7)); *piScore = (pos->iMaterialBalance[uStrong] + (7 * VALUE_PAWN) - (uDist * 32) - (u * 16)); ASSERT(IS_VALID_SCORE(*piScore)); if (pos->uToMove != uStrong) { *piScore *= -1; return(RECOGN_UPPER); } return(RECOGN_LOWER); } // // RE-ENABLED for the exact single-knight/single-pawn case only, backed // by exhaustive (not sampled) proof: testrecogn.c's // TestRecognExhaustiveKNKP enumerates every legal KNKP position with // exactly one knight and one pawn -- 10.2M raw square placements, 5.2M // of them actually checked against real Syzygy EGTB data (the rest // UNRECOGNIZED or outside coverage) -- and found zero disagreements. // The claim this function makes ("at best a draw for the pawn side") // genuinely is a two-knights-can't-force-mate fact in that exact // sub-case. // // It is FALSE once a second knight or a second pawn enters the // picture, though -- testrecogn.c's random sampling found two live // counterexamples in those cases (a real forced loss for the pawn // side despite its king being right next to its own pawn) before this // function was tightened to exclude them via the count==1 checks // below. Don't loosen those checks back to "<=2 knights" / "any pawn // count" without first extending the exhaustive verifier to cover // whatever case is being added and confirming zero disagreements the // same way. // ULONG _RecognizeKNKP(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Recognize KNKP positions: exactly one knight vs exactly one pawn. Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { ULONG uStrong; POSITION *pos = &ctx->sPosition; ASSERT((TotalNonPawnCount(pos, WHITE) <= 3) && (TotalNonPawnCount(pos, BLACK) <= 3)); ASSERT(_NothingBut(pos, PAWN | KNIGHT, WHITE)); ASSERT(_NothingBut(pos, PAWN | KNIGHT, BLACK)); // // Call the side with the knight "strong" // uStrong = WHITE; if (TotalNonPawnCount(pos, BLACK) > 1) { uStrong = BLACK; } ASSERT(TotalNonPawnCount(pos, uStrong) > 1); ASSERT(TotalNonPawnCount(pos, FLIP(uStrong)) == 1); // // Exhaustively proven correct only for exactly one knight and // exactly one pawn (see the comment above) -- also still exclude // K on the edge, per the original ON_EDGE reasoning. // if ((FastCountBits(pos->bbPieces[uStrong][KNIGHT]) != 1) || (FastCountBits(pos->bbPawns[FLIP(uStrong)]) != 1) || (ON_EDGE(KingPosition(pos, FLIP(uStrong))))) { return(UNRECOGNIZED); } // // This is at least a draw for the side with the pawn and at best a // draw for the side with the knight // *piScore = g_iDrawScore[pos->uToMove]; if (pos->uToMove == uStrong) { return(RECOGN_UPPER); } return(RECOGN_LOWER); } static ULONG _RecognizeKBKP(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Recognize KB+P*KP+ positions including knowledge about "wrong color bishop(s)". Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { ULONG uStrong; BITBOARD bb; COOR cWeakKing; POSITION *pos = &ctx->sPosition; ASSERT((TotalNonPawnCount(pos, WHITE) <= 3) && (TotalNonPawnCount(pos, BLACK) <= 3)); ASSERT(_NothingBut(pos, PAWN | BISHOP, WHITE)); ASSERT(_NothingBut(pos, PAWN | BISHOP, BLACK)); // // Call the side with bishop(s) "strong" // uStrong = WHITE; if (FastCountBits(pos->bbPieces[BLACK][BISHOP]) > 0) { uStrong = BLACK; } ASSERT(TotalNonPawnCount(pos, uStrong) > 1); ASSERT(TotalNonPawnCount(pos, FLIP(uStrong)) == 1); cWeakKing = KingPosition(pos, FLIP(uStrong)); ASSERT(IS_ON_BOARD(cWeakKing)); ASSERT(IS_KING(pos->rgSquare[cWeakKing].pPiece)); // // Strong side's pawn locations // bb = pos->bbPawns[uStrong]; if ((TotalNonPawnCount(pos, BLACK) + FastCountBits(pos->bbPawns[BLACK]) > 1) && (TotalNonPawnCount(pos, WHITE) + FastCountBits(pos->bbPawns[WHITE]) > 1)) { // // Neither side has a lone king. This is either KBKP+ or // KBP+KP+ -- i.e. the WEAK side has at least one pawn of its // own, not just a bare king. // // 2026-09-18: this used to still apply the "wrong-colored- // bishop rook-pawn corner fortress" shortcut here (same // bishop-color/pawn-file/king-distance checks as the bare- // weak-king KBPK branch below, goto at_best_draw_for_strong) // -- but that shortcut's soundness depends on the weak side // having nothing but a king to shelter with; it was never // re-derived for a weak side that has its OWN pawn(s), which // can hand the strong side real zugzwang/breakthrough // resources the fortress technique doesn't account for. // Found via fuzzing tests/cross_sectional_200k.ep_ (DEBUG // build, RECOGNIZER_SANITY_FAIL): 6k1/6p1/7p/7P/5K2/8/4B3/8 b // - - 0 0 (White Kf4/Be2/Ph5, Black Kg8/Pg7/Ph6) hit this // exact shortcut (light-squared bishop, h-file pawn, weak // king adjacent to h8) and returned a hard RECOGN_LOWER draw // bound, but EGTB says it's a near-forced loss for Black -- // the extra g7 pawn (irrelevant to the fortress logic as // written) apparently gives White exactly this kind of // resource. Rather than guess a formally-correct boundary // (e.g. "at most one weak-side pawn is still safe") without // EGTB-backed proof, conservatively defer this whole case to // UNRECOGNIZED -- same choice this session's earlier KPK fix // made for its own unsound shortcut. Slower (falls through to // real search/EGTB) but never wrong. The bare-weak-king KBPK // branch below is untouched -- its own shortcuts already // require TotalNonPawnCount(weak side) == 1, a genuinely bare // king, which this counterexample doesn't undermine. // return(UNRECOGNIZED); } else { // // KBPK: make sure the bishop is the right color. This time // there is no need to check for on-move. // ASSERT(TotalNonPawnCount(pos, FLIP(uStrong)) == 1); ASSERT(TotalNonPawnCount(pos, uStrong) > 1); if (uStrong == WHITE) { if (!(bb & ~BBFILE[A]) && (WhiteSqBishopCount(pos, WHITE) == 0) && (DISTANCE(cWeakKing, A8) <= 1)) { goto draw; } if (!(bb & ~BBFILE[H]) && (WhiteSqBishopCount(pos, WHITE) == FastCountBits(pos->bbPieces[WHITE][BISHOP])) && (DISTANCE(cWeakKing, H8) <= 1)) { goto draw; } } else { if (!(bb & ~BBFILE[A]) && (WhiteSqBishopCount(pos, BLACK) == FastCountBits(pos->bbPieces[BLACK][BISHOP])) && (DISTANCE(cWeakKing, A1) <= 1)) { goto draw; } if (!(bb & ~BBFILE[H]) && (WhiteSqBishopCount(pos, BLACK) == 0) && (DISTANCE(cWeakKing, H1) <= 1)) { goto draw; } } return(UNRECOGNIZED); } #ifdef DEBUG UtilPanic(SHOULD_NOT_GET_HERE, NULL, NULL, NULL, NULL, __FILE__, __LINE__); #endif draw: *piScore = g_iDrawScore[pos->uToMove]; return(RECOGN_EXACT); } static void _GetPassersCriticalSquares(IN ULONG uColor, IN COOR cPawn, IN OUT COOR *cSquare) /** Routine description: In an effort to classify KPK positions I read some stuff in "Pandolfini's Endgame Course" about critical squares. A critical square of a passed pawn is one that, if occupied by the friendly king, is sufficient to queen that pawn by force. This code is a helper routing for the KPK recognizer that returns the critical square given a pawn's location for color uColor. Note: rook pawns only have one critical square so this code returns the same square three times in this case. Parameters: ULONG uColor, COOR cPawn, COOR *cSquare Return value: static void **/ { static COOR cCriticalSquare[2][128] = { { 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0,0,0,0,0,0,0,0, 0x61, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x66, 0,0,0,0,0,0,0,0, 0x61, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x66, 0,0,0,0,0,0,0,0, 0x61, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x66, 0,0,0,0,0,0,0,0, 0x61, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x66, 0,0,0,0,0,0,0,0, 0x61, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x66, 0,0,0,0,0,0,0,0, 0x61, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x66, 0,0,0,0,0,0,0,0, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0,0,0,0,0,0,0,0, }, { 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0,0,0,0,0,0,0,0, 0x11, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x16, 0,0,0,0,0,0,0,0, 0x11, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x16, 0,0,0,0,0,0,0,0, 0x11, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x16, 0,0,0,0,0,0,0,0, 0x11, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x16, 0,0,0,0,0,0,0,0, 0x11, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x16, 0,0,0,0,0,0,0,0, 0x11, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x16, 0,0,0,0,0,0,0,0, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0x88, 0,0,0,0,0,0,0,0, } }; ULONG uFile = FILE(cPawn); ASSERT(IS_VALID_COLOR(uColor)); ASSERT(IS_ON_BOARD(cPawn)); ASSERT((RANK(cPawn) != 1) && (RANK(cPawn) != 8)); if ((uFile == A) || (uFile == H)) { cSquare[0] = cCriticalSquare[uColor][cPawn]; cSquare[1] = cCriticalSquare[uColor][cPawn]; cSquare[2] = cCriticalSquare[uColor][cPawn]; goto end; } cSquare[1] = cCriticalSquare[uColor][cPawn]; cSquare[0] = cSquare[1] - 1; cSquare[2] = cSquare[1] + 1; end: // // Note: don't assert cSquare[n] != 0 here -- COOR value 0 is A8, a // perfectly legal critical square (e.g. a black pawn's B-file // critical square at rank 7 has its adjacent/rook-file neighbor at // A8), not a sentinel for "uninitialized". IS_ON_BOARD is the // correct validity check. ASSERT(IS_ON_BOARD(cSquare[0])); ASSERT(IS_ON_BOARD(cSquare[1])); ASSERT(IS_ON_BOARD(cSquare[2])); } // // Is every square between cPawn and its queening square (inclusive of // the queening square itself) empty? The critical-square race math // below has no notion of a blocked pawn -- it assumes cPawn can walk // straight to promotion in RANK_DISTANCE(cQueen,cPawn) moves, which was // always true for _PawnCriticalSquareRace's original caller (lone-king // KPK, nothing else on the board) but is no longer guaranteed once the // opponent may have pawns of its own sitting in the way. Deliberately // simple/conservative: this also returns FALSE if the STRONG side's // own king blocks its own pawn's path (eval.c's now-superseded // _EvalPasserRacesAgainstLoneKings had a narrower rook-pawn-only // carve-out for exactly this shape and still separately credited a // non-rook-pawn "own king in the way" case as a tempo-cost rather than // a disqualifier) -- that nuance is not reproduced here; bailing to // UNRECOGNIZED for it is the conservative, "when in doubt do nothing" // choice this recognizer is supposed to make, not a proven-safe corner // this function has verified. // static FLAG _PawnPromotionPathClear(IN POSITION *pos, IN ULONG uColor, IN COOR cPawn) { COOR cQueen = QUEENING_SQUARE_BY_COLOR_FILE[uColor][FILE(cPawn)]; int iStep = (WHITE == uColor) ? -16 : 16; COOR c; for (c = cPawn + iStep; c != cQueen; c += iStep) { ASSERT(IS_ON_BOARD(c)); if (!IS_EMPTY(pos->rgSquare[c].pPiece)) { return(FALSE); } } return(IS_EMPTY(pos->rgSquare[cQueen].pPiece)); } // // Does the side to move have a pawn that safely promotes to a queen // THIS move -- a clean, non-capturing push from the 7th (or 2nd, for // Black) rank to an empty queening square that isn't attacked by the // opponent (so the new queen can't just be captured back for nothing), // with the resulting position not stalemating the opponent? // // This is a fundamentally different, much narrower and safer question // than a multi-move pawn race: since only the side to move can act this // move, there is no "does the opponent also have a race" ambiguity to // resolve at all -- whatever the opponent's other pawns are doing, they // get no say in whether THIS move safely produces a new queen. This is // exactly the shape of the position that motivated this whole // investigation (8/7P/6p1/3k1p2/2p5/3pK3/8/8 w - -, White's Ph7 one // push from queening). // // An earlier attempt at general KP+KP* coverage instead estimated each // side's "plies until queening" via a per-pawn critical-square/outrun // race analysis and compared the two numbers with a safety margin. Per // empirical testing (TestRecognSampleKPvKP), that approach has a // persistent ~15% wrong rate against EGTB ground truth NO MATTER how // generous the margin was made (tried up to 60 plies) -- because a // race-distance comparison answers "who queens first," not "is the // resulting position actually won," and those are different claims // once the "losing" side still has pawns of its own (even ones with no // confident race of their own can still produce real drawing // counterplay -- see the historical comment on this file's // _RecognizeKPK about a duo that isn't individually passed). That // approach was abandoned rather than kept as dead code; see git history // if it's ever worth revisiting. This function answers a narrower, // fully checkable question instead: it delegates the actual // legality/safety checking to the engine's own move generation and // attack detection rather than re-deriving any of it by hand, so // there's no independent-implementation risk. // // Deliberately narrow for v1: only a clean, non-capturing push // promotion to a QUEEN; a capturing promotion or underpromotion is // deferred (this function returns FALSE for them, not handled // unsafely). Mutates and restores ctx's ply/move-stack state (like // testrecogn.c's _GetEgtbLine) but leaves pos itself unchanged on // return. // // Also requires the OPPONENT not have a pending queen of their own // (_ColorHasPendingQueen) in the resulting position -- found via a real // counterexample (8/5K1P/8/8/2p5/1p1P4/6kp/8 w - -): White's Ph7 queens // safely by every check above, but Black's Ph2 is ALSO one push from // promoting and nothing about White's move touches it, so Black // immediately replies ...h1=Q and the position is mutual queens plus // Black's dangerous connected b3/c4 passers -- nowhere near the // confident material win this function is supposed to only claim when // certain. "My queening move is locally safe" and "the resulting // position is actually won" are different claims; this closes that gap // the cheap way (deny the claim entirely rather than try to evaluate // the resulting queen-and-pawns middlegame, which is well outside what // a recognizer should attempt). // static FLAG _ColorHasPendingQueen(IN POSITION *pos, IN ULONG uColor) { BITBOARD bb = pos->bbPawns[uColor] & ((WHITE == uColor) ? BBRANK77 : BBRANK22); COOR c; int iStep = (WHITE == uColor) ? -16 : 16; while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bb))) { PIECE pBlocker = pos->rgSquare[c + iStep].pPiece; // // A queening square blocked only by uColor's OWN king isn't a // real block -- the king just steps aside next move and the // pawn queens the move after, exactly as real a threat as an // already-clear square (one tempo later). Found via a real // counterexample (5K2/k4Pp1/8/8/8/4P3/3p4/8 b - -): White's // Pf7 sits one push from queening with White's OWN Kf8 sitting // on f8, which this check used to treat identically to a // genuine block (e.g. an enemy piece that isn't going anywhere) // and so never flagged as a threat -- but White simply plays // Kg8/Ke8 next and f8=Q follows, which is exactly the kind of // second queen _HasImmediateSafeQueen's caller needs to know // about before trusting Black's own immediate queening move as // a sure win. // if (IS_EMPTY(pBlocker) || (IS_KING(pBlocker) && (GET_COLOR(pBlocker) == uColor))) { return(TRUE); } } return(FALSE); } // // Does uColor have TWO OR MORE pawns (any files, connected or not) each // on the 6th or 7th rank (White) / 3rd or 2nd rank (Black)? Reverted // from a stricter "must be on ADJACENT files" version: that version // correctly stayed silent on the original motivating position (Black's // lone d3 pawn, nowhere near dangerous) but missed real counterexamples // like 8/8/PKP3P1/8/8/8/2p5/3k4 b - - (White's a6/c6/g6 aren't // file-adjacent to each other -- b6 has White's OWN KING sitting // between a6 and c6, not a pawn -- yet three pawns this advanced still // can't all be stopped). Plain count (>=2 anywhere in the zone) doesn't // have that blind spot and, per the original motivating position check, // still correctly ignores a single lone advanced pawn. // static FLAG _ColorHasMultipleAdvancedPassers(IN POSITION *pos, IN ULONG uColor) { BITBOARD bb = pos->bbPawns[uColor] & ((WHITE == uColor) ? (BBRANK77 | BBRANK66) : (BBRANK22 | BBRANK33)); return(FastCountBits(bb) >= 2); } // // Does uColor have a single NON-ROOK-FILE pawn on the 6th/7th (White) or // 3rd/2nd (Black) rank whose own king already controls (is adjacent to) // EITHER its queening square OR the square directly in front of it (the // pawn's very next push destination)? A rook pawn is excluded because // its single critical square and corner-stalemate resources make it a // fundamentally different (usually WEAKER, sometimes drawish-for-the- // runner) case, not a stronger one -- this check is specifically about // a pawn whose promotion is essentially guaranteed because its own king // is already standing guard over the square it needs next, the // escort-completed mirror image of the critical-square logic this // investigation dropped earlier for being too failure-prone to // hand-derive in the general case. Originally only checked the // queening square itself; broadened to also cover a king controlling // just the very next square (e.g. a 6th-rank pawn whose king guards the // 7th-rank square ahead of it, without yet reaching the queening square // itself) -- still a one-hop-from-the-king check, no race/tempo // arithmetic, so still judged safe enough to keep. // static FLAG _ColorHasEscortedAdvancedPasser(IN POSITION *pos, IN ULONG uColor) { BITBOARD bb = pos->bbPawns[uColor] & ((WHITE == uColor) ? (BBRANK77 | BBRANK66) : (BBRANK22 | BBRANK33)); COOR cKing = KingPosition(pos, uColor); int iStep = (WHITE == uColor) ? -16 : 16; COOR c; while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bb))) { if ((A != FILE(c)) && (H != FILE(c))) { COOR cQueen = QUEENING_SQUARE_BY_COLOR_FILE[uColor][FILE(c)]; COOR cAhead = c + iStep; if ((DISTANCE(cKing, cQueen) <= 1) || (DISTANCE(cKing, cAhead) <= 1)) { return(TRUE); } } } return(FALSE); } // // Does the side to move (in ctx's CURRENT position) have any legal pawn // move that gives check? Found via a real counterexample // (8/P7/8/4p3/8/2p5/8/1k1K4 w - -): White's Pa7 queens safely by every // check above (a8 unattacked, not stalemate, Black has no pawn already // pending), but Black's Pc3 -- not yet on its pending-queen rank, so // _ColorHasPendingQueen doesn't see it -- pushes to c2 with CHECK, // forces White's king to move, and only THEN queens: 1. a8=Q c2+ 2. Ke2 // c1=Q, mutual queens again. A tempo bought by a check is just as real // as a pawn that's already one push from queening; the fix is not to // hand-special-case "two squares away via a checking push" (which // would just invite the same gap one square further back, or via a // discovered/double check this codebase's move generator might produce // in some other pawn shape) but to ask the engine's own move generator // and check detector directly, the same way this whole function // already avoids hand-rolled legality logic elsewhere. Assumes // GenerateMoves has already been run for ctx's current position/ply // (true at both call sites below, which reuse the move list already // built for the stalemate check). // static FLAG _ColorHasCheckingPawnPush(IN OUT SEARCHER_THREAD_CONTEXT *ctx) { POSITION *pos = &ctx->sPosition; ULONG u; for (u = ctx->sMoveStack.uBegin[ctx->uPly]; u < ctx->sMoveStack.uEnd[ctx->uPly]; u++) { MOVE mv = ctx->sMoveStack.mvf[u].mv; FLAG fGivesCheck; if (FALSE == IS_PAWN(mv.pMoved)) { continue; } // // Only a push landing on the mover's OWN pending-queen-adjacent // rank matters here -- that's what turns a mere tempo-stealing // check into a real "queens next move" threat (see // _ColorHasPendingQueen), which is the actual danger the // original counterexample (c3-c2+, then c1=Q) showed. A check // from a pawn NOT landing there -- confirmed via a real false // positive on the motivating example itself, f5-f4+ two ranks // from queening in 8/7P/6p1/3k1p2/2p5/3pK3/8/8 w - -.-- costs a // tempo but touches no material, utterly harmless when the // stronger side just safely gained a whole queen. // if (0 == (COOR_TO_BB(mv.cTo) & ((WHITE == GET_COLOR(mv.pMoved)) ? BBRANK77 : BBRANK22))) { continue; } if (FALSE == MakeMove(ctx, mv)) { ASSERT(FALSE); continue; } fGivesCheck = InCheck(pos, pos->uToMove); UnmakeMove(ctx, mv); if (TRUE == fGivesCheck) { return(TRUE); } } return(FALSE); } // // Does uOpp have ANY pawn past its own halfway line (ranks 4-7 for // White, ranks 2-5 for Black) that OUR OWN king (uMoverColor) is too // far away from to help our brand new queen deal with? Originally // written narrower (only fire on a CONNECTED, adjacent-file pair -- // "two mutually-defended passers overwhelm a lone queen"), found via // 8/4Pp2/8/1K6/4p3/5p2/8/7k w - -. That version missed a related // counterexample with only ONE relevant advanced pawn (c3) diagnosed by // hand, 8/P4K2/4p3/8/8/2p5/8/4k3 w - - and its one-move-later sibling // Q7/5K2/4p3/8/8/8/2p5/4k3 w - -: White's king (f7) happens to be near // a DIFFERENT, irrelevant Black pawn (e6, nowhere near queening) while // the actually-dangerous c3 pawn is far away and unconnected to // anything -- checking "is the king near SOME pawn in the zone" (the // original version, scanning for connectivity across the whole zone // bitboard) can't tell relevant from irrelevant proximity. Fixed by // requiring the king be close to EVERY pawn in the zone, individually // -- a single one too far away is enough to disqualify, connected or // not: a lone queen can't always be assumed to handle even ONE // sufficiently advanced passer alone when its own king isn't around // (checking forever is a draw; letting it queen and having to trade // the queen for it is a draw), any more than it can handle two // connected ones. // // UNSUPPORTED_DUO_KING_DISTANCE is a coarse, empirically-tuned proximity // gate (see testrecogn.c's TestRecognSampleKPvKP), not a proof that any // particular distance is exactly the boundary between "queen can still // handle this alone" and "needs king help" -- consistent with this // whole investigation's approach of tuning cheap, conservative // thresholds against real counterexamples rather than deriving them // from first principles. // #define UNSUPPORTED_DUO_KING_DISTANCE (2) static FLAG _ColorHasUnsupportedAdvancedPawn(IN POSITION *pos, IN ULONG uOpp, IN ULONG uMoverColor) { BITBOARD bb = pos->bbPawns[uOpp] & ((WHITE == uOpp) ? (BBRANK77 | BBRANK66 | BBRANK55 | BBRANK44) : (BBRANK22 | BBRANK33 | BBRANK44 | BBRANK55)); COOR cKing = KingPosition(pos, uMoverColor); COOR c; while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bb))) { // Rook-file pawns get one tempo less slack: found via a real // counterexample (8/5K2/7P/8/8/3k4/6p1/8 b - -, White's Ph6 // exactly AT the general threshold) that a plain distance // check still let through. Same "rook pawns are a special, // MORE resilient case" theme that recurs throughout this file // (the KPK critical-square 2-tempo margin, the escorted-passer // rook-file exclusion above) -- corner-adjacent stalemate/ // fortress resources give the defender extra reach a center // pawn doesn't have, so the same raw king distance that's safe // for an internal file isn't safe here. ULONG uMargin = ((A == FILE(c)) || (H == FILE(c))) ? (UNSUPPORTED_DUO_KING_DISTANCE - 2) : UNSUPPORTED_DUO_KING_DISTANCE; COOR cQueen = QUEENING_SQUARE_BY_COLOR_FILE[uOpp][FILE(c)]; if (DISTANCE(cKing, cQueen) > uMargin) { return(TRUE); // this pawn is too far from our king to trust // our queen to handle it alone -- disqualify } } return(FALSE); // king's close enough to every zone pawn there is } // // Is uColor's king within one square of any board corner? Found via two // real counterexamples that survived every other check here // (6K1/8/7P/8/8/7k/1p6/8 b - -, Black's Kh3 tucked next to h1; // 8/2P5/8/8/8/2K2p2/8/7k w - -, Black's Kh1 in the corner itself): a // defending king already in or hugging a corner creates stalemate- // adjacent resources that a plain king-to-pawn distance measurement // (_ColorHasUnsupportedAdvancedPawn) doesn't see at all -- the exact // same corner-stalemate hazard already documented at length elsewhere // in this file (_RecognizeKPK's original 7k/8/5KP1/8/8/8/8/8 w - - // writeup, and the rook-pawn exclusion in // _ColorHasEscortedAdvancedPasser). Deliberately coarse (ANY corner, // distance<=1, no attempt to characterize exactly which corner // configurations are actually dangerous) -- consistent with this // investigation's whole approach of bailing to UNRECOGNIZED rather than // precisely characterizing a hazardous boundary. // static FLAG _ColorKingNearCorner(IN POSITION *pos, IN ULONG uColor) { COOR cKing = KingPosition(pos, uColor); static const COOR rgcCorner[4] = { A1, A8, H1, H8 }; ULONG u; for (u = 0; u < 4; u++) { if (DISTANCE(cKing, rgcCorner[u]) <= 1) { return(TRUE); } } return(FALSE); } // // Is uColor's king on A3/H3/A6/H6 with its OWN pawn sitting directly // behind it on A2/H2/A7/H7 respectively? Found via all 8 of the // remaining exhaustive-KPvKP counterexamples at this point in the // investigation (e.g. 8/pP6/k7/8/K7/8/8/8 w - -, Black Ka6+Pa7): the // king is on the edge file, can't retreat (its own pawn blocks the // only square behind it), can't advance either (the enemy king or // board edge takes the other square), and is left with only 2 legal // squares -- both on the file the newly-promoted queen is about to // fully control. The queening move that looked completely safe by // every other check here (destination unattacked, no stalemate by a // naive pseudo-legal move count, no pending/checking/connected/ // escorted opposing pawn) turns out to stalemate the opponent outright. // Deliberately a small, exact, hardcoded table rather than a general // "count the king's genuinely legal escape squares" geometric // computation -- the latter would need to reason about pawn-attacked // squares and enemy-king-adjacency in general, which starts sliding // back toward reimplementing move generation by hand (exactly what // this function is meant to avoid); this exact shape is what every // counterexample found so far actually looks like, so it's what gets // coded, not a generalization of it. // // Also requires the QUEENING pawn's own file be B or G -- the file // immediately next to the trapped corner, whose queen is what actually // sweeps the king's 2 remaining squares. A queening pawn on any other // file doesn't produce a queen that controls those particular squares, // so this shape wouldn't apply to it. // static FLAG _ColorKingTrappedByOwnRookPawn(IN POSITION *pos, IN ULONG uColor, IN ULONG uPawnFile) { static const COOR rgcKing[4] = { A3, H3, A6, H6 }; static const COOR rgcPawn[4] = { A2, H2, A7, H7 }; static const ULONG rguRequiredPawnFile[4] = { B, G, B, G }; COOR cKing = KingPosition(pos, uColor); ULONG u; for (u = 0; u < 4; u++) { if ((cKing == rgcKing[u]) && (uPawnFile == rguRequiredPawnFile[u]) && IS_PAWN(pos->rgSquare[rgcPawn[u]].pPiece) && (GET_COLOR(pos->rgSquare[rgcPawn[u]].pPiece) == uColor)) { return(TRUE); } } return(FALSE); } // // Is cPawn (belonging to uColor) confidently safe to queen, using ONLY // static, ctx-free positional analysis -- no move generation, no // MakeMove/UnmakeMove? This is every check from this investigation's // KPvKP recognizer EXCEPT the two genuinely move-generation-dependent // ones (immediate stalemate, a checking pawn push landing on the // opponent's pending-queen rank) -- see _HasImmediateSafeQueen (below) // for those, and HasStaticUnstoppablePasser (next) for the per-color // entry point. Exposed (non-static, declared in chess.h) specifically // so eval.c can call this SAME logic for a soft "unstoppable passer" // EVAL_TERM bonus: eval.c's Eval() runs interleaved with search's own // move-generation/iteration at the current ply (a caller may already be // mid-iteration over ctx->sMoveStack for that same ply), so anything in // Eval() that called GenerateMoves/MakeMove there would corrupt that // caller's move list out from under it -- exactly why none of eval.c's // existing code touches move generation at all, and exactly why this // function deliberately doesn't either. Missing the stalemate/ // checking-push checks means eval.c's soft version can occasionally be // wrong in ways this file's exhaustively-verified recogn.c version // isn't -- acceptable for an eval.c bonus (see this whole // investigation's very first framing: recogn.c must never be wrong, // eval.c is allowed to be a little wrong), not acceptable for a // RECOGN_LOWER/UPPER hard bound. // FLAG IsStaticSafeQueeningPawn(IN POSITION *pos, IN ULONG uColor, IN COOR cPawn) { ULONG uOpp = FLIP(uColor); COOR cQueen = QUEENING_SQUARE_BY_COLOR_FILE[uColor][FILE(cPawn)]; if (FALSE == _PawnPromotionPathClear(pos, uColor, cPawn)) { return(FALSE); } if (TRUE == IsAttacked(cQueen, pos, uOpp)) { return(FALSE); } if (TRUE == _ColorHasPendingQueen(pos, uOpp)) { return(FALSE); } if (TRUE == _ColorHasMultipleAdvancedPassers(pos, uOpp)) { return(FALSE); } if (TRUE == _ColorHasEscortedAdvancedPasser(pos, uOpp)) { return(FALSE); } if (TRUE == _ColorHasUnsupportedAdvancedPawn(pos, uOpp, uColor)) { return(FALSE); } if (TRUE == _ColorKingNearCorner(pos, uOpp)) { return(FALSE); } if (TRUE == _ColorKingTrappedByOwnRookPawn(pos, uOpp, FILE(cPawn))) { return(FALSE); } return(TRUE); } // // uColor's version of "does ANY pawn pass IsStaticSafeQueeningPawn" -- // the per-color entry point eval.c actually calls. Only ever examines // pawns already on the pending-queen rank (7th/2nd); see // IsStaticSafeQueeningPawn for everything that has to be true beyond // that. // FLAG HasStaticUnstoppablePasser(IN POSITION *pos, IN ULONG uColor, OUT COOR *pcPawn) { BITBOARD bb = pos->bbPawns[uColor] & ((WHITE == uColor) ? BBRANK77 : BBRANK22); COOR c; while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bb))) { if (TRUE == IsStaticSafeQueeningPawn(pos, uColor, c)) { *pcPawn = c; return(TRUE); } } return(FALSE); } static FLAG _HasImmediateSafeQueen(IN OUT SEARCHER_THREAD_CONTEXT *ctx, OUT COOR *pcPawn) { POSITION *pos = &ctx->sPosition; ULONG uColor = pos->uToMove; ULONG uOpp = FLIP(uColor); FLAG fInCheck = InCheck(pos, uColor); ULONG u; FLAG fFound = FALSE; if (0 == (pos->bbPawns[uColor] & ((WHITE == uColor) ? BBRANK77 : BBRANK22))) { return(FALSE); } // // Cheap, ctx-free positional pre-filter first (see // IsStaticSafeQueeningPawn -- shared with eval.c's soft // _EvalUnstoppablePasser, which can't touch move generation at all; // see that function's comment for why). If nothing even passes the // static checks, there's no need to touch the move generator at // all. // if (FALSE == HasStaticUnstoppablePasser(pos, uColor, pcPawn)) { return(FALSE); } ctx->sPlyInfo[ctx->uPly].fInCheck = fInCheck; GenerateMoves(ctx, NULLMOVE, fInCheck ? GENERATE_ESCAPES : GENERATE_ALL_MOVES); for (u = ctx->sMoveStack.uBegin[ctx->uPly]; (FALSE == fFound) && (u < ctx->sMoveStack.uEnd[ctx->uPly]); u++) { MOVE mv = ctx->sMoveStack.mvf[u].mv; FLAG fSafe; if ((0 == mv.pPromoted) || (FALSE == IS_QUEEN(mv.pPromoted)) || (0 != mv.pCaptured) || (FALSE == IS_PAWN(mv.pMoved)) || (FALSE == IsStaticSafeQueeningPawn(pos, uColor, mv.cFrom))) { continue; } if (FALSE == MakeMove(ctx, mv)) { ASSERT(FALSE); continue; } // // Everything reusable across eval.c has already been checked // by IsStaticSafeQueeningPawn above -- only the two genuinely // move-generation-dependent checks remain, which only recogn.c // (never eval.c -- see this function's header comment) can // afford to run. // { FLAG fOppInCheck = InCheck(pos, uOpp); ctx->sPlyInfo[ctx->uPly].fInCheck = fOppInCheck; GenerateMoves(ctx, NULLMOVE, fOppInCheck ? GENERATE_ESCAPES : GENERATE_ALL_MOVES); fSafe = TRUE; if ((ctx->sMoveStack.uBegin[ctx->uPly] == ctx->sMoveStack.uEnd[ctx->uPly]) && (FALSE == fOppInCheck)) { fSafe = FALSE; // stalemate -- the classic corner trick } else if (TRUE == _ColorHasCheckingPawnPush(ctx)) { fSafe = FALSE; // opponent buys a tempo with check, then // queens next -- see // _ColorHasCheckingPawnPush's comment } } UnmakeMove(ctx, mv); if (TRUE == fSafe) { *pcPawn = mv.cFrom; fFound = TRUE; } } return(fFound); } // // Does uStrong's single pawn cPawn beat a bare uWeak king via the // classic critical-square race, with the 2-tempo safety margin // TestRecognExhaustiveKPK verified gives 0 wrong verdicts across all // 165,676 EGTB-covered legal single-pawn KPK positions (a 1-tempo // margin gave 35 wrong -- see the long-standing comment this was // extracted from, still attached at _RecognizeKPK's call site below)? // Extracted verbatim (no behavior change) from _RecognizeKPK's own // lone-king branch so eval.c can reuse this SAME exhaustively-verified // logic for its "unstoppable passer" bonus in the true-lone-king case // (weak side has zero pawns) -- the "rule of the square" generalized // with a king escort, not just a pawn already on the 7th/2nd rank with // the move (that narrower case is IsStaticSafeQueeningPawn, above, for // when the weak side still has pawns of its own). Pure geometry -- // KingPosition/DISTANCE/_GetPassersCriticalSquares -- no move // generation, so just as safe for eval.c to call as // IsStaticSafeQueeningPawn is. // FLAG IsUnstoppableLoneKingPasser(IN POSITION *pos, IN ULONG uStrong, IN COOR cPawn) { ULONG uWeak = FLIP(uStrong); COOR cCritical[3]; ULONG uDist[2]; ULONG u; uDist[uStrong] = DISTANCE(KingPosition(pos, uStrong), cPawn); uDist[uWeak] = DISTANCE(KingPosition(pos, uWeak), cPawn); if (uDist[uStrong] > uDist[uWeak]) { return(FALSE); } _GetPassersCriticalSquares(uStrong, cPawn, cCritical); for (u = 0; u < 3; u++) { uDist[uStrong] = DISTANCE(KingPosition(pos, uStrong), cCritical[u]); uDist[uWeak] = DISTANCE(KingPosition(pos, uWeak), cCritical[u]); if (uDist[uWeak] > 0) { uDist[uWeak] -= (pos->uToMove == uWeak); } if (uDist[uStrong] > 0) { uDist[uStrong] += (pos->uToMove == uWeak) * 2; } if (uDist[uStrong] + 1 < uDist[uWeak]) { return(TRUE); } } return(FALSE); } static ULONG _RecognizeKPK(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore) /** Routine description: Attempt to recognize KP+KP* positions. Parameters: POSITION *pos, SCORE *piScore Return value: static ULONG **/ { ULONG uStrong; ULONG uWeak; COOR cPawn, cQueen; PAWN_HASH_ENTRY *pHash; POSITION *pos = &ctx->sPosition; ASSERT(TotalNonPawnCount(pos, WHITE) == 1); ASSERT(TotalNonPawnCount(pos, BLACK) == 1); ASSERT(_NothingBut(pos, PAWN, WHITE)); ASSERT(_NothingBut(pos, PAWN, BLACK)); // // Look to see if one side has a winning passed pawn // pHash = PawnHashLookup(ctx); ASSERT(pHash != NULL); if (pHash->u64Key == pos->u64PawnSig) { pos->iScore[BLACK] = pos->iScore[WHITE] = 0; if (TRUE == _EvalPasserRacesAgainstLoneKings(ctx, pHash)) { // // Someone wins -- but only trust this as a hard bound in // the two shapes it's been exhaustively/statistically // proven safe in, not universally. 2026-09-17: fuzzing // found _EvalPasserRacesAgainstLoneKings only checks // whether a pawn already flagged "passed" outruns the enemy // king -- it has no way to see a *connected*-pawn threat // where neither pawn is individually passed (each still // contested on an adjacent file) but together they still // produce a passer and a real race once one of them // advances. A real case: 8/2K5/6pk/2P2p2/8/6P1/8/8 b (white // Pc5 "wins the race" against the far-away black king per // this function) is actually a draw per Syzygy -- black's // f5/g6 duo (blocked from passed-pawn status by white's own // g3 pawn) produces enough real counterplay to hold. Crafty's // EvaluatePassedPawnRaces (evaluate.c) has this identical // blind spot -- same "only scan already-passed pawns" gate // -- but it's safe there only because it's a soft eval // nudge feeding real alpha-beta search, never a hard, // search-terminating bound the way RECOGN_LOWER/UPPER is // here. // // Two trusted shapes, both re-verified against the CURRENT // _EvalPasserRacesAgainstLoneKings (thresholds/fork-overload // fix included) before this was wired in, not just assumed // from an earlier version's numbers: // 1. Loser has zero pawns left -- no pawn to produce a // connected-duo counterplay like the Pc5 case above, // since there's nothing left to connect. // 2. Exact one-pawn-per-side KPKP -- exhaustively checked // against EGTB (testrecogn.c's // TestEvalPasserRacesAgainstLoneKings): 0 wrong across // all 14,872,176 EGTB-covered legal KPKP positions. // With only one pawn per side there is no second pawn // to form a duo with, so the exact same blind spot the // Pc5 case exploits structurally cannot occur here // either -- this isn't a narrower coincidental case of // #1, it's independently safe for the same underlying // reason. Any other multi-pawn-per-side shape (KPPKPP, // KPKPPP, ...) measured a real ~1-5% wrong rate via // random EGTB sampling (testrecogn.c's // TestEvalSamplePasserRacesKPPKPP/KPKPPP) and stays // OUT of this hard-bound trust -- falls through to the // UNRECOGNIZED/sophisticated-analysis logic below same // as always. // ASSERT((pos->iScore[BLACK] == 0) || (pos->iScore[WHITE] == 0)); ASSERT((pos->iScore[BLACK] != 0) || (pos->iScore[WHITE] != 0)); if ((pos->iScore[BLACK] > 0) && ((0 == FastCountBits(pos->bbPawns[WHITE])) || ((1 == FastCountBits(pos->bbPawns[WHITE])) && (1 == FastCountBits(pos->bbPawns[BLACK]))))) { ASSERT(pos->iScore[WHITE] == 0); *piScore = (pos->iMaterialBalance[BLACK] + 2 * VALUE_PAWN + pos->iScore[BLACK]); ASSERT(IS_VALID_SCORE(*piScore)); if (pos->uToMove == WHITE) { *piScore *= -1; return(RECOGN_UPPER); } return(RECOGN_LOWER); } else if ((pos->iScore[WHITE] > 0) && ((0 == FastCountBits(pos->bbPawns[BLACK])) || ((1 == FastCountBits(pos->bbPawns[BLACK])) && (1 == FastCountBits(pos->bbPawns[WHITE]))))) { *piScore = (pos->iMaterialBalance[WHITE] + 2 * VALUE_PAWN + pos->iScore[WHITE]); ASSERT(IS_VALID_SCORE(*piScore)); if (pos->uToMove == BLACK) { *piScore *= -1; return(RECOGN_UPPER); } return(RECOGN_LOWER); } // Else: the "losing" side still has 2+ pawns of its own -- // don't trust the race verdict as a hard bound. Fall // through to the UNRECOGNIZED/sophisticated-analysis logic // below, same as if _EvalPasserRacesAgainstLoneKings had // found no winner at all. } } // // No one has a winning passer (per the lone-king-only fast path // above) or we did not find the hash entry. // if ((FastCountBits(pos->bbPawns[WHITE]) > 0) && (FastCountBits(pos->bbPawns[BLACK]) > 0)) { // // Both sides still have pawns -- the general KP+KP* shape. Only // coverage attempted here: the side to move has a pawn that // safely queens THIS move (_HasImmediateSafeQueen) -- see its // comment for why this narrow question is answerable at all // when a general race-distance comparison was measured not to // be (~15% wrong no matter the safety margin). Everything else // in real king-and-pawn endgame theory (races that take more // than one move, breakthroughs, outside passers, opposition, // mutual zugzwang) is left as UNRECOGNIZED -- never wrong, not // always right. // COOR cPawn; if (TRUE == _HasImmediateSafeQueen(ctx, &cPawn)) { ULONG uColor = pos->uToMove; *piScore = (pos->iMaterialBalance[uColor] + VALUE_QUEEN + (2 * VALUE_PAWN)); return(RECOGN_LOWER); } return(UNRECOGNIZED); } // // If we get here then no one has a winning passer and one side // has only a lone king -- no pawns. Do some more "sophisticated" // analysis looking for a won passer. Also: this is at best a // draw for the weak side. // uStrong = WHITE; if (FastCountBits(pos->bbPawns[WHITE]) == 0) { uStrong = BLACK; } ASSERT(FastCountBits(pos->bbPawns[uStrong]) > 0); uWeak = FLIP(uStrong); ASSERT(FastCountBits(pos->bbPawns[uWeak]) == 0); if (FastCountBits(pos->bbPawns[uStrong]) > 1) { *piScore = g_iDrawScore[pos->uToMove]; if (pos->uToMove == uStrong) { return(RECOGN_LOWER); } return(RECOGN_UPPER); } // // The side with pawns has only one pawn, do some more // sophisticated analysis here to spot winning KPK // configurations earlier by using "critical squares" // ASSERT(FastCountBits(pos->bbPawns[uStrong]) == 1); cPawn = CoorOfSingleBit(pos->bbPawns[uStrong]); ASSERT(IS_ON_BOARD(cPawn)); ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece)); if (TRUE == IsUnstoppableLoneKingPasser(pos, uStrong, cPawn)) { cQueen = QUEENING_SQUARE_BY_COLOR_FILE[uStrong][FILE(cPawn)]; *piScore = (pos->iMaterialBalance[uStrong] + VALUE_QUEEN + (2 * VALUE_PAWN) - (RANK_DISTANCE(cPawn, cQueen) * 32)); if (pos->uToMove == uWeak) { *piScore *= -1; return(RECOGN_UPPER); } return(RECOGN_LOWER); } // // If we get here then the weak king is as close to or // closer to the lone passer than the strong king -or- the // weak king is as close to or closer to the passer's // critical squares than the strong king -or- the strong king's // margin at its best critical square was too thin to trust (see // the 2+ tempo comment above). This may still be won for the // strong side but we don't know -- the logic is ugly. This is // still at best drawn for the weak side though. // *piScore = g_iDrawScore[pos->uToMove]; if (pos->uToMove == uStrong) { return(RECOGN_LOWER); } return(RECOGN_UPPER); } static void _NewRecognizer(IN RECOGNIZER *pFunct, IN ULONG uWhiteSig, IN ULONG uBlackSig) /** Routine description: Register a recognizer function. Parameters: RECOGNIZER *pFunct, ULONG uWhiteSig, ULONG uBlackSig Return value: static void **/ { g_bvRecognizerAvailable[uWhiteSig] |= (1 << uBlackSig); g_bvRecognizerAvailable[uBlackSig] |= (1 << uWhiteSig); g_pRecognizers[RECOGN_INDEX(uWhiteSig, uBlackSig)] = pFunct; } void InitializeInteriorNodeRecognizers(void) /** Routine description: Init this recognizer module Parameters: void Return value: void **/ { memset(g_pRecognizers, 0, sizeof(g_pRecognizers)); memset(g_bvRecognizerAvailable, 0, sizeof(g_bvRecognizerAvailable)); // KK P N B R Q _NewRecognizer(_RecognizeKK, _MakeMaterialSig(0, 0, 0, 0, 0), _MakeMaterialSig(0, 0, 0, 0, 0)); // KB+K P N B R Q _NewRecognizer(_RecognizeKBK, _MakeMaterialSig(0, 0, 1, 0, 0), _MakeMaterialSig(0, 0, 0, 0, 0)); // KB+KB+ P N B R Q _NewRecognizer(_RecognizeKBK, _MakeMaterialSig(0, 0, 1, 0, 0), _MakeMaterialSig(0, 0, 1, 0, 0)); // KN+K P N B R Q _NewRecognizer(_RecognizeKNK, _MakeMaterialSig(0, 1, 0, 0, 0), _MakeMaterialSig(0, 0, 0, 0, 0)); // KN+KN+ P N B R Q _NewRecognizer(_RecognizeKNK, _MakeMaterialSig(0, 1, 0, 0, 0), _MakeMaterialSig(0, 1, 0, 0, 0)); // KN+KB+ and KN+B+K disabled: _RecognizeKBNK's lone-king mating // branch was found wrong by testrecogn.c's EGTB cross-check (the // KBN-vs-K "wrong corner" subtlety -- see the comment on // _RecognizeKBNK above). Not registered until that's fixed. // // _NewRecognizer(_RecognizeKBNK, // _MakeMaterialSig(0, 1, 0, 0, 0), // _MakeMaterialSig(0, 0, 1, 0, 0)); // // _NewRecognizer(_RecognizeKBNK, // _MakeMaterialSig(0, 1, 1, 0, 0), // _MakeMaterialSig(0, 0, 0, 0, 0)); // KN+KP+ -- re-enabled for exactly one knight vs exactly one pawn // only (the function itself bails to UNRECOGNIZED for anything // else); see the comment on _RecognizeKNKP for the exhaustive // proof backing this. P N B R Q _NewRecognizer(_RecognizeKNKP, _MakeMaterialSig(1, 0, 0, 0, 0), _MakeMaterialSig(0, 1, 0, 0, 0)); // KB+KP+ P N B R Q _NewRecognizer(_RecognizeKBKP, _MakeMaterialSig(1, 0, 0, 0, 0), _MakeMaterialSig(0, 0, 1, 0, 0)); // KP+B+KP+ P N B R Q _NewRecognizer(_RecognizeKBKP, _MakeMaterialSig(1, 0, 1, 0, 0), _MakeMaterialSig(1, 0, 0, 0, 0)); // KP+B+K P N B R Q _NewRecognizer(_RecognizeKBKP, _MakeMaterialSig(1, 0, 1, 0, 0), _MakeMaterialSig(0, 0, 0, 0, 0)); // KP+K P N B R Q _NewRecognizer(_RecognizeKPK, _MakeMaterialSig(0, 0, 0, 0, 0), _MakeMaterialSig(1, 0, 0, 0, 0)); // KP+KP+ P N B R Q _NewRecognizer(_RecognizeKPK, _MakeMaterialSig(1, 0, 0, 0, 0), _MakeMaterialSig(1, 0, 0, 0, 0)); } ULONG RecognLookup(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piScore, IN FLAG fProbeEGTB) /** Routine description: This is the interface to the recogn module; it is called from Search and Qsearch. Its job is to: 1. check high speed internal node recognizer functions if a recognizable material signature is present on the board and 2. probe on-disk EGTB files if no useful recognizer result is found. Parameters: SEARCHER_THREAD_CONTEXT *ctx, SCORE *piScore, FLAG fProbeEGTB Return value: ULONG **/ { ULONG uVal; POSITION *pos = &ctx->sPosition; ULONG uSig[2]; RECOGNIZER *pRec; SCORE iScore; // // Try interior node recognizers // if ((TotalNonPawnCount(pos, WHITE) <= 3) && (TotalNonPawnCount(pos, BLACK) <= 3)) { uSig[BLACK] = _MakeMaterialSig((FastCountBits(pos->bbPawns[BLACK]) > 0), (FastCountBits(pos->bbPieces[BLACK][KNIGHT]) > 0), (FastCountBits(pos->bbPieces[BLACK][BISHOP]) > 0), (FastCountBits(pos->bbPieces[BLACK][ROOK]) > 0), (FastCountBits(pos->bbPieces[BLACK][QUEEN]) > 0)); uSig[WHITE] = _MakeMaterialSig((FastCountBits(pos->bbPawns[WHITE]) > 0), (FastCountBits(pos->bbPieces[WHITE][KNIGHT]) > 0), (FastCountBits(pos->bbPieces[WHITE][BISHOP]) > 0), (FastCountBits(pos->bbPieces[WHITE][ROOK]) > 0), (FastCountBits(pos->bbPieces[WHITE][QUEEN]) > 0)); pRec = g_pRecognizers[RECOGN_INDEX(uSig[WHITE], uSig[BLACK])]; if (NULL != pRec) { if (g_bvRecognizerAvailable[uSig[WHITE]] & (1 << uSig[BLACK])) { uVal = pRec(ctx, &iScore); if (UNRECOGNIZED != uVal) { *piScore = iScore; ASSERT((-NMATE < iScore) && (iScore < +NMATE)); #ifdef DEBUG if (!_SanityCheckRecognizers(ctx, iScore, uVal)) { CHAR *pszDiagFen = PositionToFen(pos); SCORE iRawEgtb = -12345; FLAG fEgtbOk = ProbeEGTB(ctx, &iRawEgtb); Trace("RECOGNIZER_SANITY_FAIL uSigW=%u uSigB=%u uVal=%u " "iScore=%d egtbOk=%u egtbRawScore=%d (>0=win for " "side to move, 0=draw, <0=loss for side to move) " "fen=%s\n", uSig[WHITE], uSig[BLACK], uVal, (int)iScore, fEgtbOk, (int)iRawEgtb, (NULL != pszDiagFen) ? pszDiagFen : "?"); if (NULL != pszDiagFen) { SystemFreeMemory(pszDiagFen); } } #endif ASSERT(_SanityCheckRecognizers(ctx, iScore, uVal)); return(uVal); } } } } // // Try EGTB probe. No piece-count gate here: ProbeEGTB already // checks the position's piece count against the dynamic // TB_LARGEST (set from whatever tablebase files Fathom actually // found at init), so hardcoding a ceiling here would only ever // make this stricter than what's really installed, silently // capping us below the on-disk tables (e.g. if 6-man WDL files are // ever added alongside the 5-man set already present -- see // CLAUDE.md). // if (FALSE != fProbeEGTB) { if (TRUE == ProbeEGTB(ctx, &iScore)) { // // Syzygy WDL probes are win/draw/loss only -- there's no // mate distance to adjust for the present ply here (see // EGTB_WIN_SCORE / EGTB_LOSS_SCORE in probe.c). // *piScore = iScore; return(RECOGN_EXACT); } } return(UNRECOGNIZED); }