summaryrefslogtreecommitdiff
path: root/src/recogn.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/recogn.c')
-rw-r--r--src/recogn.c1347
1 files changed, 1347 insertions, 0 deletions
diff --git a/src/recogn.c b/src/recogn.c
new file mode 100644
index 0000000..c0b1bb8
--- /dev/null
+++ b/src/recogn.c
@@ -0,0 +1,1347 @@
+/**
+
+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 ([email protected]) 16 Oct 2005
+
+Revision History:
+
+**/
+
+#include "chess.h"
+
+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:
+ if (iScore == 0) {
+ return _TablebasesSayDrawOrWin(ctx, uToMove);
+ } else if (iScore > 0) {
+ return _TablebasesSaySideWins(ctx, uToMove);
+ } else {
+ ASSERT(iScore < 0);
+ return _TablebasesSaySideWins(ctx, !uToMove);
+ }
+ case RECOGN_UPPER:
+ if (iScore == 0) {
+ return _TablebasesSayDrawOrWin(ctx, !uToMove);
+ } else if (iScore > 0) {
+ return _TablebasesSayDrawOrWin(ctx, !uToMove);
+ } else {
+ ASSERT(iScore < 0);
+ return _TablebasesSaySideWins(ctx, !uToMove);
+ }
+ 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:
+
+ #ifdef DEBUG
+static FLAG
+
+**/
+{
+ static PIECE q[] = { KNIGHT, BISHOP, ROOK, QUEEN };
+ ULONG u;
+
+ if (!(p & PAWN))
+ {
+ if (pos->uPawnCount[uColor] > 0) return(FALSE);
+ }
+
+ for (u = 0; u < ARRAY_LENGTH(q); u++)
+ {
+ if (!(p & q[u]))
+ {
+ if (pos->uNonPawnCount[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 = 0;
+ 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((pos->uNonPawnCount[WHITE][0] <= 3) &&
+ (pos->uNonPawnCount[BLACK][0] <= 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 ((pos->uNonPawnCount[WHITE][0] == 2) &&
+ (pos->uNonPawnCount[BLACK][0] == 2))
+ {
+ if ((CORNER_DISTANCE(pos->cNonPawns[WHITE][0]) != 0) &&
+ (CORNER_DISTANCE(pos->cNonPawns[BLACK][0]) != 0))
+ {
+ *piScore = 0;
+ return(RECOGN_EXACT);
+ }
+ }
+
+ //
+ // Otherwise we want to deal with KB+ vs lone K. KBKBB etc are
+ // too hard to recognize.
+ //
+ if ((pos->uNonPawnCount[WHITE][0] != 1) &&
+ (pos->uNonPawnCount[BLACK][0] != 1))
+ {
+ return(UNRECOGNIZED);
+ }
+
+ //
+ // If we get here then one side has no pieces (except the king).
+ //
+ uStrong = BLACK;
+ if (pos->uNonPawnCount[WHITE][0] > 1)
+ {
+ uStrong = WHITE;
+ }
+ ASSERT(pos->uNonPawnCount[uStrong][0] > 1);
+ ASSERT(pos->uNonPawnCount[FLIP(uStrong)][0] == 1);
+
+ //
+ // KB vs K is a draw, KB+ vs K is still a draw if all bishops are the
+ // same color.
+ //
+ uBishops = pos->uNonPawnCount[uStrong][BISHOP];
+ if ((uBishops == 1) ||
+ (pos->uWhiteSqBishopCount[uStrong] == 0) ||
+ (pos->uWhiteSqBishopCount[uStrong] == uBishops))
+ {
+ *piScore = 0;
+ 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 = pos->cNonPawns[FLIP(uStrong)][0];
+ ASSERT(DISTANCE(cWeakKing, pos->cNonPawns[uStrong][0]) > 1);
+ uAdjacent = 0;
+ for (u = 1; u < pos->uNonPawnCount[uStrong][0]; u++)
+ {
+ uAdjacent += DISTANCE(cWeakKing, pos->cNonPawns[uStrong][u] == 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.
+ //
+ if (pos->uToMove != uStrong)
+ {
+ ASSERT(pos->uToMove == FLIP(uStrong));
+ if (uAdjacent == 1)
+ {
+ return(UNRECOGNIZED);
+ }
+
+ ASSERT(IS_ON_BOARD(pos->cNonPawns[uStrong][0]));
+ ASSERT(IS_KING(pos->rgSquare[pos->cNonPawns[uStrong][0]].pPiece));
+ u = DISTANCE(cWeakKing, pos->cNonPawns[uStrong][0]);
+ ASSERT(u != 1);
+ 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((pos->uNonPawnCount[WHITE][0] <= 3) &&
+ (pos->uNonPawnCount[BLACK][0] <= 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 ((pos->uNonPawnCount[WHITE][0] == 2) &&
+ (pos->uNonPawnCount[BLACK][0] == 2))
+ {
+ if ((CORNER_DISTANCE(pos->cNonPawns[WHITE][0]) != 0) &&
+ (CORNER_DISTANCE(pos->cNonPawns[BLACK][0]) != 0))
+ {
+ *piScore = 0;
+ 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 ((pos->uNonPawnCount[WHITE][0] != 1) ||
+ (pos->uNonPawnCount[BLACK][0] != 1))
+ {
+ return(UNRECOGNIZED);
+ }
+
+ //
+ // If we get here somebody has no pieces (except a lone king).
+ //
+ uStrong = WHITE;
+ if (pos->uNonPawnCount[BLACK][0] > 1)
+ {
+ uStrong = BLACK;
+ }
+ ASSERT(pos->uNonPawnCount[uStrong][0] > 1);
+ ASSERT(pos->uNonPawnCount[FLIP(uStrong)][0] == 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(pos->uNonPawnCount[uStrong][0] < 4);
+ if (ON_EDGE(pos->cNonPawns[FLIP(uStrong)][0]))
+ {
+ return(UNRECOGNIZED);
+ }
+ *piScore = 0;
+ return(RECOGN_EXACT);
+}
+
+
+static ULONG
+_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((pos->uNonPawnCount[WHITE][0] <= 3) &&
+ (pos->uNonPawnCount[BLACK][0] <= 3));
+ ASSERT(_NothingBut(pos, BISHOP | KNIGHT, WHITE));
+ ASSERT(_NothingBut(pos, BISHOP | KNIGHT, BLACK));
+
+ if ((pos->uNonPawnCount[WHITE][0] > 1) &&
+ (pos->uNonPawnCount[BLACK][0] > 1))
+ {
+ //
+ // Do not recognize stuff like KNNKB or KNKBB etc...
+ //
+ if (pos->uNonPawnCount[WHITE][0] + pos->uNonPawnCount[BLACK][0] > 4)
+ {
+ return(UNRECOGNIZED);
+ }
+
+ //
+ // This is KNKB; unless someone's king is on the edge,
+ // recognize a draw.
+ //
+ ASSERT((pos->uNonPawnCount[WHITE][0] == 2) &&
+ (pos->uNonPawnCount[BLACK][0] == 2));
+ if (ON_EDGE(pos->cNonPawns[WHITE][0]) ||
+ ON_EDGE(pos->cNonPawns[BLACK][0]))
+ {
+ return(UNRECOGNIZED);
+ }
+ *piScore = 0;
+ return(RECOGN_EXACT);
+ }
+
+ //
+ // If we get here we are in a KBNK endgame.
+ //
+ uStrong = WHITE;
+ if (pos->uNonPawnCount[BLACK][0] > 1)
+ {
+ uStrong = BLACK;
+ }
+ ASSERT(pos->uNonPawnCount[uStrong][0] > 1);
+ ASSERT(pos->uNonPawnCount[FLIP(uStrong)][0] == 1);
+ cWeakKing = pos->cNonPawns[FLIP(uStrong)][0];
+ 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 = pos->cNonPawns[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;
+ for (u = 1; u < pos->uNonPawnCount[uStrong][0]; u++)
+ {
+ uAdjacent = (DISTANCE(pos->cNonPawns[uStrong][u], 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.
+ //
+ if (pos->uToMove != uStrong)
+ {
+ ASSERT(pos->uToMove == FLIP(uStrong));
+ if (uAdjacent == 1)
+ {
+ return(UNRECOGNIZED);
+ }
+
+ ASSERT(IS_ON_BOARD(pos->cNonPawns[uStrong][0]));
+ ASSERT(IS_KING(pos->rgSquare[pos->cNonPawns[uStrong][0]].pPiece));
+ u = DISTANCE(cWeakKing, pos->cNonPawns[uStrong][0]);
+ ASSERT(u != 1);
+ 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 (pos->uWhiteSqBishopCount[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);
+}
+
+
+static ULONG
+_RecognizeKNKP(IN SEARCHER_THREAD_CONTEXT *ctx,
+ IN OUT SCORE *piScore)
+/**
+
+Routine description:
+
+ Recognize KN+KP+ positions.
+
+Parameters:
+
+ POSITION *pos,
+ SCORE *piScore
+
+Return value:
+
+ static ULONG
+
+**/
+{
+ ULONG uStrong;
+ POSITION *pos = &ctx->sPosition;
+
+ ASSERT((pos->uNonPawnCount[WHITE][0] <= 3) &&
+ (pos->uNonPawnCount[BLACK][0] <= 3));
+ ASSERT(_NothingBut(pos, PAWN | KNIGHT, WHITE));
+ ASSERT(_NothingBut(pos, PAWN | KNIGHT, BLACK));
+
+ //
+ // Call the side with knight(s) "strong"
+ //
+ uStrong = WHITE;
+ if (pos->uNonPawnCount[BLACK][0] > 1)
+ {
+ uStrong = BLACK;
+ }
+ ASSERT(pos->uNonPawnCount[uStrong][0] > 1);
+ ASSERT(pos->uNonPawnCount[FLIP(uStrong)][0] == 1);
+
+ //
+ // Don't recognize KNNKP or KNKP with K on edge
+ //
+ if ((pos->uNonPawnCount[uStrong][KNIGHT] > 2) ||
+ (ON_EDGE(pos->cNonPawns[FLIP(uStrong)][0])))
+ {
+ return(UNRECOGNIZED);
+ }
+
+ //
+ // This is at least a draw for the side with the pawn(s) and at
+ // best a draw for the side with the knight(s)
+ //
+ *piScore = 0;
+ 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;
+ ULONG u;
+ COOR c;
+ COOR cWeakKing;
+ POSITION *pos = &ctx->sPosition;
+
+ ASSERT((pos->uNonPawnCount[WHITE][0] <= 3) &&
+ (pos->uNonPawnCount[BLACK][0] <= 3));
+ ASSERT(_NothingBut(pos, PAWN | BISHOP, WHITE));
+ ASSERT(_NothingBut(pos, PAWN | BISHOP, BLACK));
+
+ //
+ // Call the side with bishop(s) "strong"
+ //
+ uStrong = WHITE;
+ if (pos->uNonPawnCount[BLACK][BISHOP] > 0)
+ {
+ uStrong = BLACK;
+ }
+ ASSERT(pos->uNonPawnCount[uStrong][0] > 1);
+ ASSERT(pos->uNonPawnCount[FLIP(uStrong)][0] == 1);
+
+ cWeakKing = pos->cNonPawns[FLIP(uStrong)][0];
+ ASSERT(IS_ON_BOARD(cWeakKing));
+ ASSERT(IS_KING(pos->rgSquare[cWeakKing].pPiece));
+
+ //
+ // Construct a strong side bitboard of pawn locations
+ //
+ bb = 0ULL;
+ for (u = 0; u < pos->uPawnCount[uStrong]; u++)
+ {
+ c = pos->cPawns[uStrong][u];
+ ASSERT(IS_ON_BOARD(c));
+ bb |= COOR_TO_BB(c);
+ }
+
+ if ((pos->uNonPawnCount[BLACK][0] + pos->uPawnCount[BLACK] > 1) &&
+ (pos->uNonPawnCount[WHITE][0] + pos->uPawnCount[WHITE] > 1))
+ {
+ //
+ // Neither side has a lone king. This is either KBKP+ or
+ // KBP+KP+.
+ //
+ if (pos->uPawnCount[uStrong] > 0)
+ {
+ //
+ // Strong side can maybe take an adjacent pawn and survive the
+ // bad bishop.
+ //
+ if (uStrong == pos->uToMove)
+ {
+ return(UNRECOGNIZED);
+ }
+
+ //
+ // Make sure the strong side has the right color bishop
+ // for his pawns.
+ //
+ if (uStrong == WHITE)
+ {
+ if (!(bb & ~BBFILE[A]) &&
+ (pos->uWhiteSqBishopCount[WHITE] == 0) &&
+ (DISTANCE(cWeakKing, A8) <= 1))
+ {
+ goto at_best_draw_for_strong;
+ }
+
+ if (!(bb & ~BBFILE[H]) &&
+ (pos->uWhiteSqBishopCount[WHITE] ==
+ pos->uNonPawnCount[WHITE][BISHOP]) &&
+ (DISTANCE(cWeakKing, H8) <= 1))
+ {
+ goto at_best_draw_for_strong;
+ }
+ }
+ else
+ {
+ if (!(bb & ~BBFILE[A]) &&
+ (pos->uWhiteSqBishopCount[BLACK] ==
+ pos->uNonPawnCount[BLACK][BISHOP]) &&
+ (DISTANCE(cWeakKing, A1) <= 1))
+ {
+ goto at_best_draw_for_strong;
+ }
+
+ if (!(bb & ~BBFILE[H]) &&
+ (pos->uWhiteSqBishopCount[BLACK] == 0) &&
+ (DISTANCE(cWeakKing, H1) <= 1))
+ {
+ goto at_best_draw_for_strong;
+ }
+ }
+ return(UNRECOGNIZED);
+ }
+ else
+ {
+ //
+ // Strong side has no pawns... there's a mate-in-1 here if
+ // the weak king is stuck in the corner.
+ //
+ if ((pos->uNonPawnCount[uStrong][BISHOP] > 1) ||
+ (CORNER_DISTANCE(cWeakKing) == 0))
+ {
+ return(UNRECOGNIZED);
+ }
+ goto at_best_draw_for_strong;
+ }
+ }
+ else
+ {
+ //
+ // KBPK: make sure the bishop is the right color. This time
+ // there is no need to check for on-move.
+ //
+ ASSERT(pos->uNonPawnCount[FLIP(uStrong)][0] == 1);
+ ASSERT(pos->uNonPawnCount[uStrong][0] > 1);
+
+ if (uStrong == WHITE)
+ {
+ if (!(bb & ~BBFILE[A]) &&
+ (pos->uWhiteSqBishopCount[WHITE] == 0) &&
+ (DISTANCE(cWeakKing, A8) <= 1))
+ {
+ goto draw;
+ }
+ if (!(bb & ~BBFILE[H]) &&
+ (pos->uWhiteSqBishopCount[WHITE] ==
+ pos->uNonPawnCount[WHITE][BISHOP]) &&
+ (DISTANCE(cWeakKing, H8) <= 1))
+ {
+ goto draw;
+ }
+ }
+ else
+ {
+ if (!(bb & ~BBFILE[A]) &&
+ (pos->uWhiteSqBishopCount[BLACK] ==
+ pos->uNonPawnCount[BLACK][BISHOP]) &&
+ (DISTANCE(cWeakKing, A1) <= 1))
+ {
+ goto draw;
+ }
+ if (!(bb & ~BBFILE[H]) &&
+ (pos->uWhiteSqBishopCount[BLACK] == 0) &&
+ (DISTANCE(cWeakKing, H1) <= 1))
+ {
+ goto draw;
+ }
+ }
+ return(UNRECOGNIZED);
+ }
+#ifdef DEBUG
+ UtilPanic(SHOULD_NOT_GET_HERE,
+ NULL, NULL, NULL, NULL,
+ __FILE__, __LINE__);
+#endif
+
+ at_best_draw_for_strong:
+ *piScore = 0;
+ if (pos->uToMove == uStrong)
+ {
+ return(RECOGN_UPPER);
+ }
+ return(RECOGN_LOWER);
+
+ draw:
+ *piScore = 0;
+ 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:
+ ASSERT(cSquare[0] != 0);
+ ASSERT(cSquare[1] != 0);
+ ASSERT(cSquare[2] != 0);
+ ASSERT(IS_ON_BOARD(cSquare[0]));
+ ASSERT(IS_ON_BOARD(cSquare[1]));
+ ASSERT(IS_ON_BOARD(cSquare[2]));
+}
+
+
+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;
+ COOR cCritical[3];
+ ULONG uDist[2];
+ ULONG u;
+ PAWN_HASH_ENTRY *pHash;
+ POSITION *pos = &ctx->sPosition;
+
+ ASSERT(pos->uNonPawnCount[WHITE][0] == 1);
+ ASSERT(pos->uNonPawnCount[BLACK][0] == 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 == EvalPasserRaces(pos, pHash))
+ {
+ //
+ // Someone wins.
+ //
+ ASSERT((pos->iScore[BLACK] == 0) || (pos->iScore[WHITE] == 0));
+ ASSERT((pos->iScore[BLACK] != 0) || (pos->iScore[WHITE] != 0));
+ if (pos->iScore[BLACK] > 0)
+ {
+ 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
+ {
+ ASSERT(pos->iScore[WHITE] > 0);
+ *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);
+ }
+ }
+ }
+
+ //
+ // No one has a winning passer or we did not find the hash entry.
+ //
+ if ((pos->uPawnCount[WHITE] > 0) && (pos->uPawnCount[BLACK] > 0))
+ {
+ 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 (pos->uPawnCount[WHITE] == 0)
+ {
+ uStrong = BLACK;
+ }
+ ASSERT(pos->uPawnCount[uStrong] > 0);
+ uWeak = FLIP(uStrong);
+ ASSERT(pos->uPawnCount[uWeak] == 0);
+
+ if (pos->uPawnCount[uStrong] > 1)
+ {
+ *piScore = 0;
+ 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(pos->uPawnCount[uStrong] == 1);
+ cPawn = pos->cPawns[uStrong][0];
+ ASSERT(IS_ON_BOARD(cPawn));
+ ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece));
+
+ //
+ // Step 1: the strong king must be closer to the pawn than
+ // the weak king.
+ //
+ uDist[uStrong] = DISTANCE(pos->cNonPawns[uStrong][0], cPawn);
+ ASSERT((1 <= uDist[uStrong]) && (uDist[uStrong] <= 7));
+ uDist[uWeak] = DISTANCE(pos->cNonPawns[uWeak][0], cPawn);
+ ASSERT((1 <= uDist[uWeak]) && (uDist[uWeak] <= 7));
+ if (uDist[uStrong] <= uDist[uWeak])
+ {
+ //
+ // Step 2: the strong king must be closer to one of the
+ // passer's critical squares than the weak king.
+ //
+ _GetPassersCriticalSquares(uStrong, cPawn, cCritical);
+ for (u = 0; u < 3; u++)
+ {
+ uDist[uStrong] = DISTANCE(pos->cNonPawns[uStrong][0],
+ cCritical[u]);
+ ASSERT((0 <= uDist[uStrong]) && (uDist[uStrong] <= 7));
+ uDist[uWeak] = DISTANCE(pos->cNonPawns[uWeak][0],
+ cCritical[u]);
+
+ //
+ // Assume if the weak side is on move he will move
+ // towards the critical square. Also assume that
+ // in so doing he will increase the path that the
+ // strong king must take to get to the critical
+ // square.
+ //
+ if (uDist[uWeak] > 0) {
+ uDist[uWeak] -= (pos->uToMove == uWeak);
+ }
+ if (uDist[uStrong] > 0) {
+ uDist[uStrong] += (pos->uToMove == uWeak) * 2;
+ }
+ ASSERT((0 <= uDist[uWeak]) && (uDist[uWeak] <= 7));
+ if (uDist[uStrong] < uDist[uWeak])
+ {
+ 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. 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 = 0;
+ 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+ P N B R Q
+ _NewRecognizer(_RecognizeKBNK,
+ _MakeMaterialSig(0, 1, 0, 0, 0),
+ _MakeMaterialSig(0, 0, 1, 0, 0));
+
+ // KN+B+K P N B R Q
+ _NewRecognizer(_RecognizeKBNK,
+ _MakeMaterialSig(0, 1, 1, 0, 0),
+ _MakeMaterialSig(0, 0, 0, 0, 0));
+
+ // KN+KP+ 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 ((pos->uNonPawnCount[WHITE][0] <= 3) &&
+ (pos->uNonPawnCount[BLACK][0] <= 3))
+ {
+ uSig[BLACK] = _MakeMaterialSig((pos->uPawnCount[BLACK] > 0),
+ (pos->uNonPawnCount[BLACK][KNIGHT] > 0),
+ (pos->uNonPawnCount[BLACK][BISHOP] > 0),
+ (pos->uNonPawnCount[BLACK][ROOK] > 0),
+ (pos->uNonPawnCount[BLACK][QUEEN] > 0));
+ uSig[WHITE] = _MakeMaterialSig((pos->uPawnCount[WHITE] > 0),
+ (pos->uNonPawnCount[WHITE][KNIGHT] > 0),
+ (pos->uNonPawnCount[WHITE][BISHOP] > 0),
+ (pos->uNonPawnCount[WHITE][ROOK] > 0),
+ (pos->uNonPawnCount[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));
+ ASSERT(_SanityCheckRecognizers(ctx, iScore, uVal));
+ return(uVal);
+ }
+ }
+ }
+ }
+
+ //
+ // Try EGTB probe as long as some conditions are met
+ //
+ if ((FALSE != fProbeEGTB) &&
+ ((pos->uNonPawnCount[WHITE][0] + pos->uNonPawnCount[BLACK][0] +
+ pos->uPawnCount[WHITE] + pos->uPawnCount[BLACK]) <= 5))
+ {
+ if (TRUE == ProbeEGTB(ctx, &iScore))
+ {
+ //
+ // We have an exact score from EGTB but if it's a mate in N
+ // we still have to adjust it for the present ply.
+ //
+ if (iScore >= +NMATE) {
+ iScore -= ctx->uPly;
+ }
+ else if (iScore <= -NMATE) {
+ iScore += ctx->uPly;
+ }
+#ifdef DEBUG
+ else
+ {
+ ASSERT(iScore == 0); // iDrawValue[side]
+ }
+#endif
+ *piScore = iScore;
+ return(RECOGN_EXACT);
+ }
+ }
+ return(UNRECOGNIZED);
+}
generated by cgit v1.3 (git 2.53.0) at 2026-07-17 13:59:52 +0000