diff options
Diffstat (limited to 'src/probe.c')
| -rw-r--r-- | src/probe.c | 629 |
1 files changed, 330 insertions, 299 deletions
diff --git a/src/probe.c b/src/probe.c index 2d8c43d..242612c 100644 --- a/src/probe.c +++ b/src/probe.c @@ -8,12 +8,21 @@ Module Name: Abstract: - Routines for probing endgame tablebases; much of this code is - "borrowed" from crafty. + Routines for probing endgame tablebases. This uses Ronald de + Man's Syzygy tablebase format via Jon Dart's "Fathom" probing + library (see fathom/) instead of Eugene Nalimov's original + tablebases. Syzygy tables store WDL (win/draw/loss) + DTZ + (distance to zeroing move) rather than Nalimov's DTM (distance + to mate); they are dramatically smaller on disk and the probing + code is far simpler as a result. We lose literal mate-distance + information from interior-node probes, so a probed win/loss is + reported as a large-but-not-mate-range score rather than a + precise mate score. Author: Scott Gasch ([email protected]) 02 Jul 2004 + Converted to Syzygy/Fathom 23 Aug 2026 Revision History: @@ -22,105 +31,34 @@ Revision History: **/ #include "chess.h" - -#define XX (127) // sq not on the board -#define C_PIECES (3) // max num pieces of one color +#include "fathom/tbprobe.h" ULONG g_uEgtbLock = 0; // -// define INDEX type -// -#define T_INDEX64 // use 64 bit indexes -#if defined (T_INDEX64) && defined (_MSC_VER) -typedef unsigned __int64 INDEX; -#elif defined (T_INDEX64) -typedef unsigned long long INDEX; -#else -typedef unsigned long INDEX; -#endif - -// -// define square type and tb type -// -typedef unsigned int squaret; -typedef signed char tb_t; - -// -// define color -// -typedef int color; -#define x_colorWhite 0 -#define x_colorBlack 1 -#define x_colorNeutral 2 -#define COLOR_DECLARED - -// -// define pieces -// -typedef int piece; -#define x_pieceNone 0 -#define x_piecePawn 1 -#define x_pieceKnight 2 -#define x_pieceBishop 3 -#define x_pieceRook 4 -#define x_pieceQueen 5 -#define x_pieceKing 6 -#define PIECES_DECLARED - -// -// scores returned from egtb.cpp -// -#define pageL 65536 -#define tbbe_ssL ((pageL-4)/2) -#define bev_broken (tbbe_ssL+1) /* illegal or busted */ -#define bev_mi1 tbbe_ssL /* mate in 1 move */ -#define bev_mimin 1 /* mate in max moves */ -#define bev_draw 0 /* draw */ -#define bev_limax (-1) /* mated in max moves */ -#define bev_li0 (-tbbe_ssL) /* mated in 0 moves */ - -// -// define PfnCalcIndex -// -typedef INDEX(TB_FASTCALL * PfnCalcIndex)(squaret *, - squaret *, - squaret, - int fInverse); - -// -// prototypes for functions in egtb.cpp -// -extern int IDescFindFromCounters(int *); -extern int FRegisteredFun(int, color); -extern PfnCalcIndex PfnIndCalcFun(int, color); -extern int TB_FASTCALL L_TbtProbeTable(int, color, INDEX); -#define PfnIndCalc PfnIndCalcFun -#define FRegistered FRegisteredFun -extern int IInitializeTb(char *); -extern int FTbSetCacheSize(void *buffer, unsigned long size); -extern int TB_CRC_CHECK; - +// A probed tablebase win/loss doesn't carry a real distance-to-mate +// (Syzygy WDL doesn't encode one), so we report a large decisive +// score that stays safely below NMATE. This keeps it from being +// mistaken for (and ply-adjusted as) a literal forced mate elsewhere +// in the engine while still dominating ordinary evaluation scores. // -// Globals -// -static int EGTBMenCount = 0; -void *egtb_cache = NULL; -#define EGTB_CACHE_SIZE (8*1024*1024) +#define EGTB_WIN_SCORE (NMATE - VALUE_QUEEN) +#define EGTB_LOSS_SCORE (-EGTB_WIN_SCORE) +static FLAG g_fEgtbInitialized = FALSE; -void +void InitializeEGTB(void) /** Routine description: - [Re]Initialize the Nalimov EGTB system. Called during system + [Re]Initialize the Syzygy EGTB system. Called during system startup and when the user uses "set" to change the EGTB path. Parameters: - void (uses g_OPtionz.szEGTBPath) + void (uses g_Options.szEGTBPath) Return value: @@ -130,33 +68,33 @@ Return value: { CHAR *szPath = g_Options.szEGTBPath; - if ((szPath != NULL) && strlen(szPath) > 0) { - // TB_CRC_CHECK = 1; - EGTBMenCount = IInitializeTb(szPath); - if (0 != EGTBMenCount) + if (TRUE == g_fEgtbInitialized) + { + tb_free(); + g_fEgtbInitialized = FALSE; + } + + if ((szPath != NULL) && strlen(szPath) > 0) + { + if (TRUE == tb_init(szPath)) { - Trace("Found %d-men endgame tablebases.\n\n", EGTBMenCount); - if (NULL != egtb_cache) + g_fEgtbInitialized = TRUE; + if (TB_LARGEST > 0) { - SystemFreeMemory(egtb_cache); - egtb_cache = NULL; - } - egtb_cache = SystemAllocateMemory(EGTB_CACHE_SIZE); - if (NULL != egtb_cache) - { - FTbSetCacheSize(egtb_cache, EGTB_CACHE_SIZE); + Trace("Found Syzygy endgame tablebases (up to %u men).\n\n", + TB_LARGEST); } } } } -void +void CleanupEGTB(void) /** Routine description: - Cleanup the Nalimov EGTB system. + Cleanup the Syzygy EGTB system. Parameters: @@ -168,22 +106,108 @@ Return value: **/ { - if (NULL != egtb_cache) + if (TRUE == g_fEgtbInitialized) { - SystemFreeMemory(egtb_cache); - egtb_cache = NULL; + tb_free(); + g_fEgtbInitialized = FALSE; } } -FLAG +static void +_BuildFathomBitboards(IN POSITION *pos, + OUT UINT64 *pu64White, + OUT UINT64 *pu64Black, + OUT UINT64 *pu64Kings, + OUT UINT64 *pu64Queens, + OUT UINT64 *pu64Rooks, + OUT UINT64 *pu64Bishops, + OUT UINT64 *pu64Knights, + OUT UINT64 *pu64Pawns) +/** + +Routine description: + + Build the set of bitboards Fathom's tb_probe_wdl wants out of our + POSITION. Fathom expects the standard tablebase square numbering + (a1 == bit 0 ... h8 == bit 63), which is exactly what our TO64() + macro produces -- note this is *not* the same square numbering as + our engine's own internal BBSQUARE/COOR_TO_BB bitboards, so we + must not use those macros here. + +Parameters: + + POSITION *pos, + UINT64 *pu64White ... pu64Pawns + +Return value: + + static void + +**/ +{ + ULONG uColor; + ULONG u; + COOR c; + PIECE p; + UINT64 bb; + + *pu64White = *pu64Black = 0ULL; + *pu64Kings = *pu64Queens = *pu64Rooks = 0ULL; + *pu64Bishops = *pu64Knights = *pu64Pawns = 0ULL; + + for (uColor = BLACK; uColor <= WHITE; uColor++) + { + UINT64 *pu64Side = (uColor == WHITE) ? pu64White : pu64Black; + + for (u = 0; u < pos->uPawnCount[uColor]; u++) + { + c = pos->cPawns[uColor][u]; + ASSERT(IS_ON_BOARD(c)); + bb = (1ULL << (TO64(c))); + *pu64Side |= bb; + *pu64Pawns |= bb; + } + + for (u = 0; u < pos->uNonPawnCount[uColor][0]; u++) + { + c = pos->cNonPawns[uColor][u]; + ASSERT(IS_ON_BOARD(c)); + bb = (1ULL << (TO64(c))); + *pu64Side |= bb; + + if (0 == u) + { + ASSERT(IS_KING(pos->rgSquare[c].pPiece)); + *pu64Kings |= bb; + continue; + } + + p = pos->rgSquare[c].pPiece; + ASSERT(p && !IS_PAWN(p) && !IS_KING(p)); + if (IS_KNIGHT(p)) *pu64Knights |= bb; + else if (IS_BISHOP(p)) *pu64Bishops |= bb; + else if (IS_ROOK(p)) *pu64Rooks |= bb; + else + { + ASSERT(IS_QUEEN(p)); + *pu64Queens |= bb; + } + } + } +} + + +FLAG ProbeEGTB(SEARCHER_THREAD_CONTEXT *ctx, SCORE *piScore) /** Routine description: - Search for a board position in the EGTB files on disk. + Search for a board position in the Syzygy EGTB files on disk via + Fathom. This only returns a WDL (win/draw/loss) result, not a + literal mate distance -- see EGTB_WIN_SCORE / EGTB_LOSS_SCORE. Parameters: @@ -197,236 +221,243 @@ Return value: **/ { POSITION *pos = &(ctx->sPosition); - int pcCount[10]; - int wSquares[C_PIECES*5+1], bSquares[C_PIECES*5+1]; - int iTB; - ULONG uColor; - int invert; - int *wp, *bp; - int ep; - INDEX index; - int value; + UINT64 u64White, u64Black, u64Kings, u64Queens; + UINT64 u64Rooks, u64Bishops, u64Knights, u64Pawns; + unsigned uEp; + unsigned uWdl; + ULONG wcount, bcount; FLAG fResult; - ULONG x; - int y; - COOR c; - PIECE p; - PfnCalcIndex fp; - // - // EGTB initialized? - // - ULONG wcount = (pos->uNonPawnCount[WHITE][0] + - pos->uPawnCount[WHITE]); - ULONG bcount = (pos->uNonPawnCount[BLACK][0] + - pos->uPawnCount[BLACK]); - if ((wcount + bcount > (ULONG)EGTBMenCount) || - (wcount > 3) || - (bcount > 3)) + if (FALSE == g_fEgtbInitialized || 0 == TB_LARGEST) { return(FALSE); } - INC(ctx->sCounters.egtb.uProbes); - memset(pcCount, 0, sizeof(pcCount)); - for (x = 0; - x < pos->uPawnCount[WHITE]; - x++) + // + // Syzygy WDL probing requires no castling rights on the board and + // a zero halfmove (fifty move rule) clock; the WDL tables don't + // encode either. + // + if ((0 != pos->bvCastleInfo) || (0 != pos->uFifty)) { - c = pos->cPawns[WHITE][x]; - ASSERT (IS_ON_BOARD(c)); - ASSERT(pos->rgSquare[c].pPiece && IS_PAWN(pos->rgSquare[c].pPiece)); - - c = TO64(c); - ASSERT((c >= 0) && (c <= 64)); - - y = pcCount[0]; - ASSERT(y >= 0); - ASSERT(y < (C_PIECES * 5 + 1)); - wSquares[y] = c; - pcCount[0]++; + return(FALSE); } - for (x = 1; - x < pos->uNonPawnCount[WHITE][0]; - x++) + wcount = pos->uNonPawnCount[WHITE][0] + pos->uPawnCount[WHITE]; + bcount = pos->uNonPawnCount[BLACK][0] + pos->uPawnCount[BLACK]; + if ((wcount + bcount) > TB_LARGEST) { - c = pos->cNonPawns[WHITE][x]; - ASSERT (IS_ON_BOARD(c)); - - p = pos->rgSquare[c].pPiece; - ASSERT(p && !IS_PAWN(p) && !IS_KING(p)); - - // - // convert: into: - // XXX_PAWN 0 - // XXX_KNIGHT 1 - // XXX_BISHOP 2 - // XXX_ROOK 3 - // XXX_QUEEN 4 - // - p = ((p >> 1) & 0x7) - 1; - ASSERT(p > 0); - ASSERT(p < 5); - - c = TO64(c); - ASSERT((c >= 0) && (c <= 64)); - - y = p * C_PIECES + pcCount[p]; - ASSERT(y >= 0); - ASSERT(y < (C_PIECES * 5 + 1)); - wSquares[y] = c; - pcCount[p]++; + return(FALSE); } + INC(ctx->sCounters.egtb.uProbes); - for (x = 0; - x < pos->uPawnCount[BLACK]; - x++) - { - c = pos->cPawns[BLACK][x]; - ASSERT(IS_ON_BOARD(c)); - ASSERT(pos->rgSquare[c].pPiece && IS_PAWN(pos->rgSquare[c].pPiece)); - - c = TO64(c); - ASSERT(c >= 0); - ASSERT(c <= 64); - - y = pcCount[5]; - ASSERT(y >= 0); - ASSERT(y < (C_PIECES * 5 + 1)); - bSquares[y] = c; - pcCount[5]++; - } + _BuildFathomBitboards(pos, &u64White, &u64Black, &u64Kings, &u64Queens, + &u64Rooks, &u64Bishops, &u64Knights, &u64Pawns); - for (x = 1; - x < pos->uNonPawnCount[BLACK][0]; - x++) + uEp = 0; + if (IS_ON_BOARD(pos->cEpSquare)) { - c = pos->cNonPawns[BLACK][x]; - ASSERT(IS_ON_BOARD(c)); - - p = pos->rgSquare[c].pPiece; - ASSERT(p && !IS_PAWN(p) && !IS_KING(p)); - - // - // convert: into: - // XXX_PAWN 0 - // XXX_KNIGHT 1 - // XXX_BISHOP 2 - // XXX_ROOK 3 - // XXX_QUEEN 4 - // - p = ((p >> 1) & 0x7) - 1; - ASSERT(p > 0); - ASSERT(p < 5); - - c = TO64(c); - ASSERT(c >= 0); - ASSERT(c <= 64); - - y = p * C_PIECES + pcCount[5 + p]; - ASSERT(y >= 0); - ASSERT(y < (C_PIECES * 5 + 1)); - bSquares[y] = c; - pcCount[5 + p]++; + uEp = TO64(pos->cEpSquare); } AcquireSpinLock(&g_uEgtbLock); - iTB = IDescFindFromCounters(pcCount); - if (iTB == 0) - { - fResult = FALSE; - goto end; - } - - // - // Add the kings to the piece lists - // - ASSERT(pos->rgSquare[pos->cNonPawns[WHITE][0]].pPiece == WHITE_KING); - wSquares[C_PIECES * 5] = TO64(pos->cNonPawns[WHITE][0]); - ASSERT(wSquares[C_PIECES * 5] >= 0); - ASSERT(wSquares[C_PIECES * 5] <= 64); - - ASSERT(pos->rgSquare[pos->cNonPawns[BLACK][0]].pPiece == BLACK_KING); - bSquares[C_PIECES * 5] = TO64(pos->cNonPawns[BLACK][0]); - ASSERT(bSquares[C_PIECES * 5] >= 0); - ASSERT(bSquares[C_PIECES * 5] <= 64); + uWdl = tb_probe_wdl(u64White, u64Black, u64Kings, u64Queens, u64Rooks, + u64Bishops, u64Knights, u64Pawns, + /* rule50 */ 0, /* castling */ 0, uEp, + (pos->uToMove == WHITE)); + ReleaseSpinLock(&g_uEgtbLock); - if (iTB > 0) + if (TB_RESULT_FAILED == uWdl) { - uColor = (pos->uToMove == WHITE) ? 0 : 1; - invert = 0; - wp = wSquares; - bp = bSquares; - } - else - { - uColor = (pos->uToMove == WHITE) ? 1 : 0; - invert = 1; - wp = bSquares; - bp = wSquares; - iTB = -iTB; + return(FALSE); } - - if (!FRegisteredFun(iTB, uColor)) + + switch (uWdl) { - fResult = FALSE; - goto end; + case TB_WIN: + *piScore = EGTB_WIN_SCORE; + break; + case TB_LOSS: + *piScore = EGTB_LOSS_SCORE; + break; + case TB_CURSED_WIN: + case TB_BLESSED_LOSS: + case TB_DRAW: + default: + *piScore = 0; // g_iDrawValue[pos->uToMove]; + break; } - ep = XX; - if (IS_ON_BOARD(pos->cEpSquare)) + fResult = TRUE; + +#ifdef PERF_COUNTERS + INC(ctx->sCounters.egtb.uHits); +#endif + return(fResult); +} + + +// +// Convert a Fathom tablebase square index (a1==0 ... h8==63) back into +// our own COOR encoding. Inverse of TO64(). +// +#define FROM64(s) \ + ((((7 - ((s) >> 3)) << 4)) | ((s) & 0x7)) + + +static PIECE +_TbPromotesToPiece(IN unsigned uPromotes) +/** + +Routine description: + + Map a TB_PROMOTES_* value from a Fathom root probe result to our + own PIECE constant. + +Parameters: + + unsigned uPromotes + +Return value: + + static PIECE + +**/ +{ + switch (uPromotes) { - ASSERT((IS_ON_BOARD(pos->cEpSquare + 1) && - IS_PAWN(pos->rgSquare[pos->cEpSquare + 1].pPiece)) || - (IS_ON_BOARD(pos->cEpSquare - 1) && - IS_PAWN(pos->rgSquare[pos->cEpSquare - 1].pPiece))); - ep = TO64(pos->cEpSquare); + case TB_PROMOTES_QUEEN: return(QUEEN); + case TB_PROMOTES_ROOK: return(ROOK); + case TB_PROMOTES_BISHOP: return(BISHOP); + case TB_PROMOTES_KNIGHT: return(KNIGHT); + default: return(0); } - -#if 0 - DumpPosition(pos); - Trace("iTB = %d, uColor = %u, ep = %u, invert = %u\n", - iTB, uColor, ep, invert); - Trace("wp =\t\t\tbp =\n"); - for(x = 0; x < 16; x++) +} + + +FLAG +ProbeEGTBRoot(SEARCHER_THREAD_CONTEXT *ctx, + MOVE *pmv, + SCORE *piScore) +/** + +Routine description: + + Probe the Syzygy DTZ tables for the best move at the root. Unlike + ProbeEGTB (WDL-only, used at interior nodes), this uses DTZ to + pick a move that actually makes progress towards mate / the + fifty-move-rule reset -- Syzygy WDL alone has no notion of "closer + to mate" so relying on it exclusively could shuffle forever inside + a won position. This is expected to be called once at the root, + before the normal iterative search, when <= TB_LARGEST pieces + remain on the board. + + We ask Fathom for its suggested (from, to, promotion) and then + find the matching move in our own already-generated root move + list, rather than reconstructing a MOVE by hand, so we inherit our + engine's own move flags (capture, en passant, special, etc). + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + MOVE *pmv, + SCORE *piScore + +Return value: + + FLAG : TRUE if a move was found and *pmv / *piScore were set. + +**/ +{ + POSITION *pos = &(ctx->sPosition); + UINT64 u64White, u64Black, u64Kings, u64Queens; + UINT64 u64Rooks, u64Bishops, u64Knights, u64Pawns; + unsigned uEp; + unsigned uResult; + unsigned uWdl; + COOR cFrom, cTo; + PIECE pPromotes; + ULONG wcount, bcount; + ULONG u; + + if (FALSE == g_fEgtbInitialized || 0 == TB_LARGEST) { - Trace("%u\t\t\t%u\n", wSquares[x], bSquares[x]); + return(FALSE); } -#endif - ASSERT(IS_VALID_COLOR(uColor)); - fp = PfnIndCalcFun(iTB, uColor); - index = fp((squaret *)wp, - (squaret *)bp, - (squaret)ep, - invert); - value = L_TbtProbeTable(iTB, uColor, index); - if (value == bev_broken) + + wcount = pos->uNonPawnCount[WHITE][0] + pos->uPawnCount[WHITE]; + bcount = pos->uNonPawnCount[BLACK][0] + pos->uPawnCount[BLACK]; + if ((wcount + bcount) > TB_LARGEST) { - fResult = FALSE; - goto end; + return(FALSE); } - if (value > 0) + _BuildFathomBitboards(pos, &u64White, &u64Black, &u64Kings, &u64Queens, + &u64Rooks, &u64Bishops, &u64Knights, &u64Pawns); + + uEp = 0; + if (IS_ON_BOARD(pos->cEpSquare)) { - *piScore = INFINITY + (2*(-bev_mi1+value)) - 1; + uEp = TO64(pos->cEpSquare); } - else if (value < 0) + + AcquireSpinLock(&g_uEgtbLock); + uResult = tb_probe_root(u64White, u64Black, u64Kings, u64Queens, u64Rooks, + u64Bishops, u64Knights, u64Pawns, + pos->uFifty, pos->bvCastleInfo, uEp, + (pos->uToMove == WHITE), NULL); + ReleaseSpinLock(&g_uEgtbLock); + + if ((TB_RESULT_FAILED == uResult) || + (TB_RESULT_CHECKMATE == uResult) || + (TB_RESULT_STALEMATE == uResult)) { - *piScore = -INFINITY + (2*(bev_mi1+value)); + // + // No usable move (either failed, or the earlier terminal-state + // check already handles checkmate/stalemate). + // + return(FALSE); } - else + + // + // A blessed win / cursed loss / plain draw at the root: don't + // steer the search away from its own move choice, since these + // are all draws under the fifty move rule and normal search + // handles that correctly already. Only override the root move + // when this is a clear win or a position we must play carefully + // to avoid losing (both cases: follow the DTZ suggestion). + // + uWdl = TB_GET_WDL(uResult); + if ((TB_DRAW == uWdl) || + (TB_CURSED_WIN == uWdl) || + (TB_BLESSED_LOSS == uWdl)) { - *piScore = 0; // g_iDrawValue[pos->uToMove]; + return(FALSE); } - fResult = TRUE; - end: - ReleaseSpinLock(&g_uEgtbLock); -#ifdef PERF_COUNTERS - if (fResult == TRUE) + cFrom = FROM64(TB_GET_FROM(uResult)); + cTo = FROM64(TB_GET_TO(uResult)); + pPromotes = _TbPromotesToPiece(TB_GET_PROMOTES(uResult)); + + for (u = ctx->sMoveStack.uBegin[ctx->uPly]; + u < ctx->sMoveStack.uEnd[ctx->uPly]; + u++) { - INC(ctx->sCounters.egtb.uHits); + MOVE mv = ctx->sMoveStack.mvf[u].mv; + if ((mv.cFrom == cFrom) && + (mv.cTo == cTo) && + (mv.pPromoted == pPromotes)) + { + *pmv = mv; + *piScore = (TB_WIN == uWdl) ? EGTB_WIN_SCORE : EGTB_LOSS_SCORE; + return(TRUE); + } } -#endif - return(fResult); + + // + // Fathom suggested a move we couldn't find in our own move list; + // this shouldn't happen for a legally-generated root, but don't + // trust it if it does. + // + ASSERT(FALSE); + return(FALSE); } |