diff options
| -rw-r--r-- | src/GNUmakefile | 2 | ||||
| -rwxr-xr-x | src/chess.h | 98 | ||||
| -rwxr-xr-x | src/data.c | 12 | ||||
| -rwxr-xr-x | src/dynamic.c | 400 | ||||
| -rwxr-xr-x | src/eval.c | 52 | ||||
| -rwxr-xr-x | src/generate.c | 9 | ||||
| -rw-r--r-- | src/lmr_testing/README.md | 73 | ||||
| -rw-r--r-- | src/lmr_testing/generate_counter_move_block.c | 58 | ||||
| -rw-r--r-- | src/lmr_testing/search_c_snippets.txt | 33 | ||||
| -rw-r--r-- | src/lmr_testing/searchsup_GetLMRReduction.c | 114 | ||||
| -rwxr-xr-x | src/main.c | 3 | ||||
| -rw-r--r-- | src/poshash.c | 254 | ||||
| -rwxr-xr-x | src/root.c | 16 | ||||
| -rwxr-xr-x | src/san.c | 10 | ||||
| -rwxr-xr-x | src/script.c | 51 | ||||
| -rwxr-xr-x | src/search.c | 154 | ||||
| -rw-r--r-- | src/searchsup.c | 48 | ||||
| -rwxr-xr-x | src/split.c | 35 | ||||
| -rwxr-xr-x | src/util.c | 35 |
19 files changed, 1023 insertions, 434 deletions
diff --git a/src/GNUmakefile b/src/GNUmakefile index 44ce560..dbb74cf 100644 --- a/src/GNUmakefile +++ b/src/GNUmakefile @@ -131,7 +131,7 @@ OBJS = main.o root.o search.o searchsup.o draw.o dynamic.o \ generate.o see.o move.o movesup.o command.o script.o \ input.o vars.o util.o unix.o gamelist.o mersenne.o \ sig.o piece.o ics.o san.o fen.o book.o bench.o board.o \ - data.o probe.o fathom.o recogn.o poshash.o list.o x64.o + data.o probe.o fathom.o recogn.o list.o x64.o ifdef TEST # ---> .o, not .c! <--- diff --git a/src/chess.h b/src/chess.h index d6d4fa4..9689189 100755 --- a/src/chess.h +++ b/src/chess.h @@ -808,6 +808,8 @@ typedef struct _COUNTERS UINT64 u64TerminalPositionCount; UINT64 u64BetaCutoffs; UINT64 u64BetaCutoffsOnFirstMove; + UINT64 u64CounterMoveTries; // valid counter-move slot existed + UINT64 u64CounterMoveHits; // ...and it was the move that won UINT64 u64NullMoves; UINT64 u64NullMoveSuccess; #ifdef TEST_NULL @@ -932,6 +934,8 @@ typedef struct _PLY_INFO INT iExtensionAmount; FLAG fInCheck; FLAG fInQsearch; + FLAG fPvNode; // this node's own window was wide + MOVE mv; MOVE mvBest; MOVE PV[MAX_PLY_PER_SEARCH]; @@ -997,6 +1001,16 @@ PAWN_HASH_ENTRY; #define NUM_SPLIT_PTRS_IN_CONTEXT (8) +// +// Counter-move table (Crafty-style): keyed by a hash of the *previous* +// move (whatever the opponent just played to reach this node), not by +// ply -- unlike killers, this generalizes across different branches +// that happen to share the same preceding move, anywhere in the tree. +// Sized to MOVE_TO_INDEX's full range so the index is exact, not a +// lossy hash. +// +#define COUNTER_MOVE_TABLE_SIZE (0x20000) + typedef struct _SEARCHER_THREAD_CONTEXT { ULONG uPly; // its distance from root @@ -1008,6 +1022,12 @@ typedef struct _SEARCHER_THREAD_CONTEXT MOVE mvKiller[MAX_PLY_PER_SEARCH][2]; MOVE mvKillerEscapes[MAX_PLY_PER_SEARCH][2]; MOVE mvNullmoveRefutations[MAX_PLY_PER_SEARCH]; + MOVE mvCounter[COUNTER_MOVE_TABLE_SIZE][2]; // counter-move table + UCHAR uCounterDepth[COUNTER_MOVE_TABLE_SIZE]; // ply depth slot 0 was set at + COOR cEnprise[MAX_PLY_PER_SEARCH][2]; // en prise piece hints + PIECE pEnprise[MAX_PLY_PER_SEARCH][2]; + COOR cTrapped[MAX_PLY_PER_SEARCH]; // trapped piece hint + PIECE pTrapped[MAX_PLY_PER_SEARCH]; COUNTERS sCounters; ULONG uThreadNumber; SPLIT_INFO *pSplitInfo[NUM_SPLIT_PTRS_IN_CONTEXT]; @@ -1074,6 +1094,10 @@ typedef struct _GAME_OPTIONS FLAG fShouldAnnounceOpening; SCORE iLastEvalScore; UINT64 u64NodesSearched; + UINT64 u64BetaCutoffs; + UINT64 u64BetaCutoffsOnFirstMove; + UINT64 u64CounterMoveTries; + UINT64 u64CounterMoveHits; CHAR szLogfile[SMALL_STRING_LEN_CHAR]; CHAR szEGTBPath[SMALL_STRING_LEN_CHAR]; CHAR szBookName[SMALL_STRING_LEN_CHAR]; @@ -1816,7 +1840,9 @@ TestMakeUnmakeMove(void); #define THIRD_KILLER (0x08000000) #define FOURTH_KILLER (0x04000000) #define GOOD_MOVE (0x02000000) -#define STRIP_OFF_FLAGS (0x00FFFFFF) +#define FIRST_COUNTER_MOVE (0x01000000) +#define SECOND_COUNTER_MOVE (0x00800000) +#define STRIP_OFF_FLAGS (0x007FFFFF) extern const int g_iQKDeltas[9]; extern const int g_iNDeltas[9]; @@ -2317,16 +2343,26 @@ ComputeMoveScore(IN SEARCHER_THREAD_CONTEXT *ctx, FLAG ThreadUnderTerminatingSplit(SEARCHER_THREAD_CONTEXT *); -FLAG -WeShouldDoHistoryPruning(IN SCORE iRoughEval, - IN SCORE iAlpha, - IN SCORE iBeta, - IN SEARCHER_THREAD_CONTEXT *ctx, - IN ULONG uRemainingDepth, - IN ULONG uLegalMoves, - IN MOVE mv, - IN ULONG uMoveNum, - IN INT iExtend); +// LMR reduction table -- built once at startup (InitLMRTable, dynamic.c), +// no floating point in the search hot path. [depth in plies][move number, +// clamped]. Value is a ply-fraction in ONE_PLY units, i.e. directly +// usable as a negative iExtend. +#define LMR_TABLE_MAX_MOVES (63) +extern SCORE g_iLMRQuietReduction[MAX_PLY_PER_SEARCH + 1][LMR_TABLE_MAX_MOVES + 1]; + +void +InitLMRTable(void); + +INT +GetLMRReduction(IN SCORE iRoughEval, + IN SCORE iAlpha, + IN SCORE iBeta, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN ULONG uRemainingDepth, + IN ULONG uLegalMoves, + IN MOVE mv, + IN ULONG uMoveNum, + IN INT iExtend); FLAG WeShouldTryNullmovePruning(IN SEARCHER_THREAD_CONTEXT *ctx, @@ -2532,44 +2568,34 @@ void AnalyzeFullHashTable(void); // -// positionhash.c +// dynamic.c -- enprise/trapped piece hints // -// IDEA: store "mate threat" flag in here? -// IDEA: store "king safety" numbers in here? +// Ply-indexed, like killer moves: cheap, lock-free, thread-local hints +// about which piece(s) looked en prise or trapped the last time full +// Eval() (or a fail-high capture) ran at this ply. Not guaranteed +// fresh for the position currently at that ply -- readers must +// re-validate via the recorded PIECE still being on the recorded COOR +// before trusting it (RecordEnprisePiece/RecordTrappedPiece store +// both for exactly this reason). Nice-to-have only: pruning/ordering +// decisions must work correctly with none of this data available. // -typedef struct _POSITION_HASH_ENTRY { - UINT64 u64Sig; - UCHAR cEnprise[2]; - UCHAR uEnpriseCount[2]; - UCHAR cTrapped[2]; -} POSITION_HASH_ENTRY; - -void -InitializePositionHashSystem(void); - void -CleanupPositionHashSystem(void); +RecordEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare); void -StoreEnprisePiece(POSITION *pos, COOR cSquare); +RecordEnprisePieceAtPly(SEARCHER_THREAD_CONTEXT *ctx, ULONG uPly, COOR cSquare); void -StoreTrappedPiece(POSITION *pos, COOR cSquare); - -COOR -GetEnprisePiece(POSITION *pos, ULONG uSide); - -ULONG -GetEnpriseCount(POSITION *pos, ULONG uSide); +RecordTrappedPiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare); COOR -GetTrappedPiece(POSITION *pos, ULONG uSide); +FindEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide); ULONG -ValueOfMaterialInTroubleDespiteMove(POSITION *pos, ULONG uSide); +ValueOfMaterialInTroubleDespiteMove(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide); ULONG -ValueOfMaterialInTroubleAfterNull(POSITION *pos, ULONG uSide); +ValueOfMaterialInTroubleAfterNull(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide); // // pawnhash.c @@ -57,8 +57,8 @@ DistanceBetweenSquares(COOR a, COOR b) ASSERT(IS_ON_BOARD(b)); ASSERT((i >= 0) && (i < 256)); ASSERT(g_uDistance[i] == REAL_DISTANCE(a, b)); - ASSERT(g_pDistance[a - b] == g_uDistance[i]); - ASSERT(g_pDistance[b - a] == g_uDistance[i]); + ASSERT(g_pDistance[(int)a - (int)b] == g_uDistance[i]); + ASSERT(g_pDistance[(int)b - (int)a] == g_uDistance[i]); ASSERT(g_uDistance[j] == REAL_DISTANCE(a, b)); return(REAL_DISTANCE(a, b)); } @@ -586,12 +586,12 @@ InitializeDistanceTable(void) if (!IS_ON_BOARD(y)) continue; i = (int)x - (int)y + 128; ASSERT(g_uDistance[i] == REAL_DISTANCE(x, y)); - ASSERT(g_pDistance[x - y] == g_uDistance[i]); - ASSERT(&(g_pDistance[x - y]) == &(g_uDistance[i])); + ASSERT(g_pDistance[(int)x - (int)y] == g_uDistance[i]); + ASSERT(&(g_pDistance[(int)x - (int)y]) == &(g_uDistance[i])); j = (int)y - (int)x + 128; ASSERT(g_uDistance[j] == REAL_DISTANCE(x, y)); - ASSERT(g_pDistance[y - x] == g_uDistance[j]); - ASSERT(&(g_pDistance[y - x]) == &(g_uDistance[j])); + ASSERT(g_pDistance[(int)y - (int)x] == g_uDistance[j]); + ASSERT(&(g_pDistance[(int)y - (int)x]) == &(g_uDistance[j])); } } #endif diff --git a/src/dynamic.c b/src/dynamic.c index 41b8cc1..33a673c 100755 --- a/src/dynamic.c +++ b/src/dynamic.c @@ -37,7 +37,13 @@ Revision History: #include "chess.h" +// Declared directly instead of #include <math.h> -- that header +// #defines its own INFINITY, which collides with ours (chess.h:198, +// MAX_SHORT). Only needed once, at startup, to build g_iLMRQuietReduction. +extern double log(double); + ULONG g_HistoryCounters[14][128]; +SCORE g_iLMRQuietReduction[MAX_PLY_PER_SEARCH + 1][LMR_TABLE_MAX_MOVES + 1]; #define FH_STATS_TABLE_SIZE (0x20000) typedef struct _FH_STATS @@ -71,7 +77,54 @@ volatile static ULONG g_uDynamicLock; #endif -FLAG +void +InitLMRTable(void) +/** + +Routine description: + + Build the LMR reduction table once at startup -- log(depth) * + log(moves) formula (Ethereal's constants as a starting point, not + load-bearing; expect to retune), converted to ONE_PLY-scaled + integer ply-fractions so the search hot path never does floating + point. Quiet moves only; captures/promotions/checks/etc. are + excluded by GetLMRReduction's own gate before this table is ever + consulted. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uDepth, uMoves; + double d; + + for (uDepth = 0; uDepth <= MAX_PLY_PER_SEARCH; uDepth++) + { + for (uMoves = 0; uMoves <= LMR_TABLE_MAX_MOVES; uMoves++) + { + if ((uDepth < 1) || (uMoves < 1)) + { + g_iLMRQuietReduction[uDepth][uMoves] = 0; + continue; + } + d = 0.7844 + (log((double)uDepth) * log((double)uMoves)) / 2.4696; + if (d < 0.0) + { + d = 0.0; + } + g_iLMRQuietReduction[uDepth][uMoves] = (SCORE)(d * (double)ONE_PLY); + } + } +} + + +FLAG InitializeDynamicMoveOrdering(void) /** @@ -254,8 +307,348 @@ Return value: } -static void -_IncrementMoveHistoryCounter(MOVE mv, +static void +_NewCounterMove(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv, ULONG uRemainingDepth) +/** + +Routine description: + + Remember that mv refuted whatever move the opponent just played to + reach this node -- keyed by that previous move, not by ply, so it + generalizes across any branch where the opponent plays the same + move again, unlike killers. + + Depth-gated: a shallow fail-high (low uRemainingDepth, i.e. close + to the QSearch handoff) is much lower-confidence evidence than one + found with many plies still remaining, but unlike killers (which + are ply-scoped and self-correct locally), this table is global -- + keyed only by move identity, with nothing to stop a later, shallow + write from clobbering an earlier, deep one just because it's more + recent. Only overwrite when the new evidence is at least as deep + as what's already there. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + MOVE mv, + ULONG uRemainingDepth + +Return value: + + void + +**/ +{ + MOVE mvLast; + ULONG u; + ULONG uPly; + + ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); + ASSERT(mv.uMove); + + if (ctx->uPly == 0) + { + return; + } + mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv; + if (0 == mvLast.uMove) + { + return; + } + u = MOVE_TO_INDEX(mvLast); + + // + // Hit-rate instrumentation: did the counter-move slot for this + // previous move already predict the move that just won here? + // Checked before the slot is (maybe) overwritten below. + // + if ((ctx->mvCounter[u][0].uMove != 0) || + (ctx->mvCounter[u][1].uMove != 0)) + { + INC(ctx->sCounters.tree.u64CounterMoveTries); + if (IS_SAME_MOVE(mv, ctx->mvCounter[u][0]) || + IS_SAME_MOVE(mv, ctx->mvCounter[u][1])) + { + INC(ctx->sCounters.tree.u64CounterMoveHits); + } + } + + // A/B test: write-gating by depth (reject shallower overwrites) + // measured *worse* hit rate with no EBF gain -- this table is + // global, not ply-scoped, so a frozen "deepest wins" entry can + // go stale while later, more locally-relevant evidence gets + // rejected. Always overwrite (recency); track depth instead to + // scale the read-time bonus. + uPly = uRemainingDepth / ONE_PLY; + if (!IS_SAME_MOVE(mv, ctx->mvCounter[u][0])) + { + ctx->mvCounter[u][1] = ctx->mvCounter[u][0]; + ctx->mvCounter[u][0] = mv; + } + ctx->uCounterDepth[u] = (UCHAR)MINU(uPly, 255); +} + + +void +RecordEnprisePieceAtPly(SEARCHER_THREAD_CONTEXT *ctx, ULONG uPly, COOR cSquare) +/** + +Routine description: + + Remember (at uPly, not necessarily the current ply) that the + piece sitting on cSquare in the *current* position -- which must + belong to whoever is to move at uPly -- looked en prise. + Ply-indexed and overwrite-in-place, exactly like killer moves: + this is a nice-to-have ordering/pruning hint, not a fact about the + current position, and readers must re-validate the recorded piece + is still on the recorded square before trusting it. + + Invariant: the recorded piece's color always matches the mover's + color at uPly -- same as a killer move's moved piece always does. + This only ever records *self* danger (the side to move at uPly + has a piece hanging), never "I can capture the opponent's piece" + -- that's a different fact, one no current reader wants, and + conflating the two would let noisy opponent-danger writes evict + the self-danger hints readers actually consume. + + uPly need not equal ctx->uPly: a fail-high capture is discovered + back at the capturing side's own ply (after UnmakeMove restores + the victim to cSquare), but the victim's color is the *other* + side's -- exactly the mover at ctx->uPly - 1 (ply parity + alternates), which is where "despite the move you're about to + make, this piece is still in trouble" actually belongs. Expected + mover is derived from the live ctx->uPly/ctx->sPosition.uToMove + (always in sync) via that parity offset, not from uPly directly. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uPly, + COOR cSquare + +Return value: + + void + +**/ +{ + PIECE p = ctx->sPosition.rgSquare[cSquare].pPiece; + ULONG uExpectedMover = (((ctx->uPly - uPly) & 1) ? + FLIP(ctx->sPosition.uToMove) : + ctx->sPosition.uToMove); + + ASSERT(uPly < MAX_PLY_PER_SEARCH); + ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p)); + ASSERT(GET_COLOR(p) == uExpectedMover); + + if ((ctx->cEnprise[uPly][0] != cSquare) || + (ctx->pEnprise[uPly][0] != p)) + { + ctx->cEnprise[uPly][1] = ctx->cEnprise[uPly][0]; + ctx->pEnprise[uPly][1] = ctx->pEnprise[uPly][0]; + ctx->cEnprise[uPly][0] = cSquare; + ctx->pEnprise[uPly][0] = p; + } +} + + +void +RecordEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare) +/** + +Routine description: + + RecordEnprisePieceAtPly at the current ply -- the common case + (self-danger found by a full Eval() at this exact node). + +**/ +{ + RecordEnprisePieceAtPly(ctx, ctx->uPly, cSquare); +} + + +void +RecordTrappedPiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare) +/** + +Routine description: + + Remember (at the current ply) that the piece sitting on cSquare -- + belonging to the side to move at this ply -- looked trapped. + Single slot -- trapped pieces are rarer than en prise ones. Same + freshness caveat and self-danger-only invariant as + RecordEnprisePiece. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + COOR cSquare + +Return value: + + void + +**/ +{ + ULONG uPly = ctx->uPly; + PIECE p = ctx->sPosition.rgSquare[cSquare].pPiece; + + ASSERT(uPly < MAX_PLY_PER_SEARCH); + ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p)); + ASSERT(GET_COLOR(p) == ctx->sPosition.uToMove); + + ctx->cTrapped[uPly] = cSquare; + ctx->pTrapped[uPly] = p; +} + + +static FLAG INLINE +_EnpriseSlotValid(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSlot, ULONG uSide) +{ + ULONG uPly = ctx->uPly; + COOR c = ctx->cEnprise[uPly][uSlot]; + + return(IS_ON_BOARD(c) && + (ctx->sPosition.rgSquare[c].pPiece == ctx->pEnprise[uPly][uSlot]) && + (GET_COLOR(ctx->pEnprise[uPly][uSlot]) == uSide)); +} + + +static FLAG INLINE +_TrappedSlotValid(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +{ + ULONG uPly = ctx->uPly; + COOR c = ctx->cTrapped[uPly]; + + return(IS_ON_BOARD(c) && + (ctx->sPosition.rgSquare[c].pPiece == ctx->pTrapped[uPly]) && + (GET_COLOR(ctx->pTrapped[uPly]) == uSide)); +} + + +COOR +FindEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +/** + +Routine description: + + Look up an en prise piece of color uSide at the current ply, + re-validated against the live board (see RecordEnprisePiece). + Used by move ordering to boost moves that rescue the piece. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uSide + +Return value: + + COOR : the square, or ILLEGAL_COOR if no valid hint + +**/ +{ + if (_EnpriseSlotValid(ctx, 0, uSide)) + { + return ctx->cEnprise[ctx->uPly][0]; + } + if (_EnpriseSlotValid(ctx, 1, uSide)) + { + return ctx->cEnprise[ctx->uPly][1]; + } + return ILLEGAL_COOR; +} + + +ULONG +ValueOfMaterialInTroubleDespiteMove(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +/** + +Routine description: + + Extended-futility safety net: how much material does uSide stand + to lose despite the move just made, per the en prise/trapped + hints at the current ply? Requires *both* en prise slots to be + valid for uSide (mirrors the old "more than one piece en prise" + threshold) before trusting the en prise value; the trapped hint + has no such threshold. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uSide + +Return value: + + ULONG : material value in trouble, or 0 + +**/ +{ + ULONG uPly = ctx->uPly; + ULONG u = 0; + FLAG fHaveValue = FALSE; + COOR c, c1; + + if (_EnpriseSlotValid(ctx, 0, uSide) && _EnpriseSlotValid(ctx, 1, uSide)) + { + c = ctx->cEnprise[uPly][0]; + c1 = ctx->cEnprise[uPly][1]; + ASSERT(c != c1); + u = MINU(PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece), + PIECE_VALUE(ctx->sPosition.rgSquare[c1].pPiece)); + fHaveValue = TRUE; + } + if (_TrappedSlotValid(ctx, uSide)) + { + c = ctx->cTrapped[uPly]; + u = (fHaveValue ? + MINU(u, PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)) : + PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)); + } + return u; +} + + +ULONG +ValueOfMaterialInTroubleAfterNull(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +/** + +Routine description: + + Nullmove-pruning safety net: same as ValueOfMaterialInTroubleDespiteMove + but with a looser threshold (any valid en prise hint counts, not + just two) since this is guarding a cheaper, more speculative prune. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uSide + +Return value: + + ULONG : material value in trouble, or 0 + +**/ +{ + ULONG uPly = ctx->uPly; + ULONG u = 0; + COOR c; + + if (_EnpriseSlotValid(ctx, 0, uSide)) + { + c = ctx->cEnprise[uPly][0]; + u = PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece); + } + if (_TrappedSlotValid(ctx, uSide)) + { + c = ctx->cTrapped[uPly]; + u = MAXU(u, PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)); + } + return u; +} + + +static void +_IncrementMoveHistoryCounter(MOVE mv, ULONG uDepth) /** @@ -407,6 +800,7 @@ Return value: if (!IS_CAPTURE_OR_PROMOTION(mvBest)) { _NewKillerMove(ctx, mvBest, iScore); + _NewCounterMove(ctx, mvBest, uRemainingDepth); _IncrementMoveHistoryCounter(mvBest, uRemainingDepth); } @@ -206,7 +206,7 @@ static SCORE ISOLATED_PAWN_BY_PAWNFILE[9] = static SCORE ISOLATED_EXPOSED_PAWN = -5; -static SCORE ISOLATED_DOUBLED_PAWN = 13; +static SCORE ISOLATED_DOUBLED_PAWN = -1; // // Note: -25% to -33% if the enemy occupies or controls the next sq. @@ -1381,7 +1381,8 @@ Return value: (((WHITE == uColor) && (RANK(c) > 5)) || ((BLACK == uColor) && (RANK(c) < 4))))) { - ASSERT(CANDIDATE_PASSER_BY_RANK[uColor][RANK(c)] > 0); + // Tuning can (and has) flipped this sign; not a real invariant. + //ASSERT(CANDIDATE_PASSER_BY_RANK[uColor][RANK(c)] > 0); EVAL_TERM(uColor, PAWN, c, @@ -1936,7 +1937,8 @@ Return value: // // Isolated + exposed? Extra penalty. // - ASSERT(ISOLATED_EXPOSED_PAWN < 0); + // Tuning can (and has) flipped this sign; not a real invariant. + //ASSERT(ISOLATED_EXPOSED_PAWN < 0); EVAL_TERM(uColor, PAWN, c, @@ -1955,7 +1957,8 @@ Return value: // // Isolated + doubled? Extra penalty. // - ASSERT(ISOLATED_DOUBLED_PAWN < 0); + // Tuning can (and has) flipped this sign; not a real invariant. + //ASSERT(ISOLATED_DOUBLED_PAWN < 0); EVAL_TERM(uColor, PAWN, c, @@ -2031,7 +2034,8 @@ Return value: <= 8); if (pHash->uCountPerFile[FLIP(uColor)][uPawnFile]) { - ASSERT(BACKWARD_SHIELDED_BY_LOCATION[c] < 0); + // Tuning can (and has) flipped this sign; not a real invariant. + //ASSERT(BACKWARD_SHIELDED_BY_LOCATION[c] < 0); EVAL_TERM(uColor, PAWN, c, @@ -2041,7 +2045,7 @@ Return value: } else { - ASSERT(BACKWARD_EXPOSED_BY_LOCATION[c] < 0); + //ASSERT(BACKWARD_EXPOSED_BY_LOCATION[c] < 0); EVAL_TERM(uColor, PAWN, c, @@ -4265,7 +4269,9 @@ Return value: ASSERT(uTotalMobility <= 14); ASSERT(pos->uArmyScaler[FLIP(uColor)] <= 31); - ASSERT(REDUCED_MATERIAL_UP_SCALER[pos->uArmyScaler[FLIP(uColor)]] <= 8); + // Tuning can (and has) pushed this out of its original hand-picked + // bound; not a real invariant. + //ASSERT(REDUCED_MATERIAL_UP_SCALER[pos->uArmyScaler[FLIP(uColor)]] <= 8); i = ROOK_MOBILITY_BY_SQUARES[uTotalMobility]; i *= (int)(REDUCED_MATERIAL_UP_SCALER[pos->uArmyScaler[FLIP(uColor)]] + 1); i /= 8; @@ -4431,7 +4437,8 @@ Return value: // if (!RANK1(c) && !RANK8(c)) { - ASSERT(QUEEN_OUT_EARLY[pos->uMinorsAtHome[uColor]] < 0); + // Tuning can (and has) flipped this sign; not a real invariant. + //ASSERT(QUEEN_OUT_EARLY[pos->uMinorsAtHome[uColor]] < 0); ASSERT(pos->uMinorsAtHome[uColor] <= 4); EVAL_TERM(uColor, QUEEN, @@ -5235,7 +5242,7 @@ Return value: pos->iScore[WHITE], uNumPassers[WHITE] * PASSER_BONUS_AS_MATERIAL_COMES_OFF[u], "passer value material"); - ASSERT(PASSER_BONUS_AS_MATERIAL_COMES_OFF[u] >= 0); + // ASSERT(PASSER_BONUS_AS_MATERIAL_COMES_OFF[u] >= 0); u = pos->uArmyScaler[WHITE]; EVAL_TERM(BLACK, PAWN, @@ -5243,7 +5250,7 @@ Return value: pos->iScore[BLACK], uNumPassers[BLACK] * PASSER_BONUS_AS_MATERIAL_COMES_OFF[u], "passer value material"); - ASSERT(PASSER_BONUS_AS_MATERIAL_COMES_OFF[u] >= 0); + // ASSERT(PASSER_BONUS_AS_MATERIAL_COMES_OFF[u] >= 0); } @@ -5312,7 +5319,8 @@ Return value: ((pos->uPawnCount[uAhead] != 0) * TRADE_PIECES[uMagnitude][pos->uNonPawnCount[uBehind][0]]), "trade pieces"); - ASSERT(TRADE_PIECES[uMagnitude][pos->uNonPawnCount[uBehind][0]] > 0); + // Tuning can (and has) flipped this sign; not a real invariant. + //ASSERT(TRADE_PIECES[uMagnitude][pos->uNonPawnCount[uBehind][0]] > 0); EVAL_TERM(uAhead, 0, ILLEGAL_COOR, @@ -5372,7 +5380,7 @@ Return value: #endif if (_WhoControlsSquareFast(pos, c) == FLIP(uSide)) { - StoreEnprisePiece(pos, c); + RecordEnprisePiece(ctx, c); } } } @@ -5416,11 +5424,16 @@ Return value: #endif if (OPPOSITE_COLORS(uColor, pos->uToMove)) { - StoreEnprisePiece(pos, c); + // uColor is the mover at ctx->uPly - 1 (ply + // parity), not here -- see RecordEnprisePieceAtPly. + if (ctx->uPly > 0) + { + RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, c); + } } else { - StoreTrappedPiece(pos, c); + RecordTrappedPiece(ctx, c); } } } @@ -5954,6 +5967,17 @@ Return value: // ctx->sPlyInfo[ctx->uPly].uMinMobility[BLACK] = pos->uMinMobility[BLACK]; ctx->sPlyInfo[ctx->uPly].uMinMobility[WHITE] = pos->uMinMobility[WHITE]; + + // + // _EvalLookForDanger/_EvalTrappedPieces only ever *add* a hint + // when they find one; a full eval that finds nothing this time + // would otherwise leave a stale, unrelated hint from an earlier + // visit to this ply sitting here (still piece-identity-valid by + // coincidence). Clear this ply's self-danger slots first so a + // clean full eval reliably means a clean slate. + // + ctx->cEnprise[ctx->uPly][0] = ctx->cEnprise[ctx->uPly][1] = ILLEGAL_COOR; + ctx->cTrapped[ctx->uPly] = ILLEGAL_COOR; _EvalLookForDanger(ctx); _EvalTrappedPieces(ctx); diff --git a/src/generate.c b/src/generate.c index 7d7778f..7362fba 100755 --- a/src/generate.c +++ b/src/generate.c @@ -2454,7 +2454,7 @@ Return value: ULONG uHashMoveLoc = (ULONG)-1; ULONG uColor = pos->uToMove; PRECOMP_KILLERS sKillers[4]; - COOR cEnprise = GetEnprisePiece(pos, uColor); + COOR cEnprise = FindEnprisePiece(ctx, uColor); // // We have generated all moves here. We also know that we are not @@ -2467,7 +2467,10 @@ Return value: // // - // Pre-populate killer/bonuses + // Pre-populate killer/bonuses. (Tried Crafty-style ordering here + // -- both of this ply's own killers before either ply-2-back one + // -- measured worse EBF on ecm_quick than this interleaved order. + // Back to interleaved as the known-good baseline.) // sKillers[0].mv = ctx->mvKiller[uPly][0]; sKillers[0].uBonus = FIRST_KILLER; @@ -2857,7 +2860,7 @@ Return value: MOVE mv; MOVE mvLast = (pi-1)->mv; SCORE s; - COOR cEnprise = GetEnprisePiece(pos, uColor); + COOR cEnprise = FindEnprisePiece(ctx, uColor); // // We have generate all moves or just legal escapes from check diff --git a/src/lmr_testing/README.md b/src/lmr_testing/README.md new file mode 100644 index 0000000..8ac983f --- /dev/null +++ b/src/lmr_testing/README.md @@ -0,0 +1,73 @@ +# In-flight LMR/counter-move work, stashed 2026-08-27 + +The main tree (`/usr/home/scott/typhoon/src`) was reverted to a clean +pre-LMR/pre-counter-move baseline (LMR=fixed -ONE_PLY history pruning, +futility restored, no counter-move scoring) so an overnight ECM baseline +run could establish ground truth (`typhoon_baseline.log` @ 20s/move, +`typhoon_baseline_ecm4m.log` @ sn=4M, both 1cpu/256m hash). + +This directory holds the exact bodies that were reverted, so they can be +re-applied on top of the (soon to be committed) clean baseline instead of +reconstructing from memory. + +## What's still intact in the main tree (never touched) + +- `dynamic.c`: `InitLMRTable()`, `g_iLMRQuietReduction` table population, + and the counter-move table write (`_NewCounterMove`, still runs and + updates `u64CounterMoveTries`/`u64CounterMoveHits` stats -- just + nothing reads `ctx->mvCounter` for move ordering/reduction anymore). +- `main.c`: still calls `InitLMRTable()`. +- `chess.h`: still has all struct fields (`mvCounter`, `fPvNode`, + `g_iLMRQuietReduction` extern, `GetLMRReduction` prototype, counter-move + bit flags, stats counters). No chess.h changes needed to restore LMR. + +## What needs restoring (saved in this directory) + +- `searchsup_GetLMRReduction.c` -- the graded-LMR body: Ethereal formula + (`0.7844 + ln(depth)*ln(moves)/2.4696`) + `ONE_PLY` base, soft + PV-adjacency discount (Crafty-style, 1 ply less instead of hard skip + when `ctx->sPlyInfo[ctx->uPly-1].fPvNode`), counter-move exemption + (added last, alongside killer exemptions), move-count threshold `> 3`, + fail-high gate `<= 10`. This is the *best validated* config from + yesterday's sweep: 24/30 solved, EBF 4.223 on `ecm_quick.ep_` @ sn=4M. + Drop this in to replace `GetLMRReduction` in `searchsup.c`. + +- `generate_counter_move_block.c` -- the three generate.c hunks: struct + decl (`sKillers[6]`, `mvLast`), the counter-move bonus pre-population + block, and the `s += sKillers[4]/[5]` scoring lines. See inline + `// LOCATION:` comments for where each piece goes. + +- `search_c_snippets.txt` -- the two one-line search.c changes: + `pi->fPvNode = (iBeta != iAlpha + 1);` (near `iInitialAlpha = iAlpha;`) + and the futility-pruning `FALSE &&` isolation-test disable (optional -- + only re-add if resuming the "isolate LMR's effect alone" testing + methodology; leave futility on to test LMR combined with it instead). + +## Known results/dead ends from yesterday's sweep (don't re-try blindly) + +See conversation history for full detail, but in brief, all measured on +`ecm_quick.ep_` @ sn=4M against this config's 24/30 EBF 4.223 baseline: +- Table-only (no `+ONE_PLY` base): 23/30, EBF 4.224 -- worse. +- Fail-high gate `<=5`: 24/30, EBF 4.274 -- worse. `<=20`: 23/30, EBF + 4.101 -- best EBF but costs a solve (same shape as several other + knobs -- EBF-vs-solve-count tradeoff, not a free win). +- Grandparent PV guard (uPly-2): 23/30, EBF 4.258 -- worse both ways. +- Obsidian formula (`0.99 + ln(d)*ln(m)/3.14`, table-alone): 23/30, EBF + 4.175 -- good EBF, costs a solve. +- "Improving" signal (Crafty/Berserk/SF-style, eval vs 2 plies ago), + tried with both `GetRoughEvalScore` (material-only past uPly 4) and a + real `Eval()` call: both measured identically worse, 23/30 EBF 4.252. + GetRoughEvalScore's material-only fallback deep in the tree was ruled + out as the cause since the real-Eval version scored the same. + +## The real methodology finding (more important than any single knob) + +ECM.016 case study: baseline's "stable" answer through depth 11 (`Rxc5`) +was actually a shallow, unconvicted pick -- at 24.5M+ nodes even the +baseline flips to `dxe3` and stays there (matches Crafty's own stable +depth-18-21 preference for `dxe3`). Full-ecm879 solve-count deltas from +sn=4M runs are contaminated by positions like this where neither config +actually understands the position yet. Before trusting any future +solve-count delta on a small suite, verify the "lost" positions are ones +where a long/deep baseline run is actually stable and correct -- that's +what tonight's overnight run is for (finding the "confident" ECM subset). diff --git a/src/lmr_testing/generate_counter_move_block.c b/src/lmr_testing/generate_counter_move_block.c new file mode 100644 index 0000000..f58efda --- /dev/null +++ b/src/lmr_testing/generate_counter_move_block.c @@ -0,0 +1,58 @@ +// generate.c changes to restore counter-move scoring. Three pieces, in +// the same function (the one with PRECOMP_KILLERS sKillers[...] and the +// "Pre-populate killer/bonuses" comment -- search for that to find it). + +// LOCATION 1: local var decls at top of the function -- add mvLast and +// pi, bump sKillers to 6: +// +// PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; // ADD +// ULONG uPly = ctx->uPly; +// POSITION *pos = &ctx->sPosition; +// ULONG u; +// MOVE mv; +// MOVE mvLast = (pi-1)->mv; // ADD +// SCORE s; +// MOVE_STACK_MOVE_VALUE_FLAGS mvf; +// ULONG uHashMoveLoc = (ULONG)-1; +// ULONG uColor = pos->uToMove; +// PRECOMP_KILLERS sKillers[6]; // was [4] +// COOR cEnprise = FindEnprisePiece(ctx, uColor); + +// LOCATION 2: right after the killer sKillers[0..3] population block +// (after the SORT_THESE_FIRST |= lines for sKillers[0..3]), insert: + + // + // Pre-populate counter-move bonuses -- keyed by whatever move the + // opponent just played to reach this node, not by ply. A/B test: + // applied as a small *additive* nudge (like history counters), + // not a hard priority-tier flag -- the ~56% measured hit rate + // isn't confident enough to justify unconditionally outranking + // ordinary PSQT-scored quiet moves. Bonus scales with the ply + // depth the entry was recorded at (deeper = more confident), + // capped at the same 400/200 ceiling the flat version used. + // + sKillers[4].mv.uMove = sKillers[5].mv.uMove = 0; + if (mvLast.uMove != 0) + { + u = MOVE_TO_INDEX(mvLast); + sKillers[4].mv = ctx->mvCounter[u][0]; + sKillers[4].uBonus = 400; + sKillers[5].mv = ctx->mvCounter[u][1]; + sKillers[5].uBonus = 200; + } + +// LOCATION 3: in the quiet-move scoring branch (the `else` branch that +// computes `s = g_iPSQT[...]` and applies killer bonuses via `s |= ...`), +// right after the GOOD_MOVE/cEnprise line and before `ASSERT(s >= 0);`, +// add (note: additive `+=`, not `|=` -- this was the measured-best +// config vs. a hard flag): + + s += (IS_SAME_MOVE(sKillers[4].mv, mv) * sKillers[4].uBonus); + s += (IS_SAME_MOVE(sKillers[5].mv, mv) * sKillers[5].uBonus); + +// This same three-part change applies in BOTH scoring functions in +// generate.c that have this sKillers array (there are two -- one for +// the normal move-scoring path, one for escaping-check; check whether +// the second one had the counter-move block too before assuming it's +// identical -- verify via `grep -n PRECOMP_KILLERS generate.c` and +// diff both call sites against this file's saved state if unsure). diff --git a/src/lmr_testing/search_c_snippets.txt b/src/lmr_testing/search_c_snippets.txt new file mode 100644 index 0000000..72d4ae5 --- /dev/null +++ b/src/lmr_testing/search_c_snippets.txt @@ -0,0 +1,33 @@ +search.c changes to restore (both trivial one-liners): + +1. Near `iInitialAlpha = iAlpha;` (right after it), add: + + pi->fPvNode = (iBeta != iAlpha + 1); + +2. OPTIONAL -- only if resuming "isolate LMR's effect alone" testing + methodology (i.e. you want LMR-only numbers uncontaminated by + futility pruning again). If instead you want to test LMR *combined* + with futility (recommended next step per yesterday's session), skip + this and leave futility on as it is in the clean baseline. + + Find the futility-pruning block: + + ASSERT(!uFutilityMargin); + if ((iRoughEval + VALUE_ROOK <= iAlpha) && + (uDepth <= TWO_PLY) && + ... + + and disable it for isolation testing: + + ASSERT(!uFutilityMargin); + if (FALSE && // temporarily disabled to isolate graded-LMR's + // effect in isolation during testing + (iRoughEval + VALUE_ROOK <= iAlpha) && + (uDepth <= TWO_PLY) && + ... + +Everything else in search.c (the GetLMRReduction call site, the +re-search-add-back using `uNextDepth -= iExtend`) is already generic +and needs NO changes -- it was written to work with any reduction +magnitude GetLMRReduction returns, so it already works correctly with +both the baseline's fixed -ONE_PLY and the graded version. diff --git a/src/lmr_testing/searchsup_GetLMRReduction.c b/src/lmr_testing/searchsup_GetLMRReduction.c new file mode 100644 index 0000000..0ee69f6 --- /dev/null +++ b/src/lmr_testing/searchsup_GetLMRReduction.c @@ -0,0 +1,114 @@ +// Replace searchsup.c's GetLMRReduction body with this (signature/name +// unchanged, so search.c/split.c call sites need no changes). + +INT +GetLMRReduction(IN SCORE iRoughEval, + IN SCORE iAlpha, + IN SCORE iBeta, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN ULONG uRemainingDepth, + IN ULONG uLegalMoves, + IN MOVE mv, + IN ULONG uMoveNum, + IN INT iExtend) +/** + +Routine description: + + Decide how much (if any) to reduce this move's search depth by -- + graded LMR, replacing the old fixed -ONE_PLY history pruning. + Note: this function is called after the move has been played on + the board (ctx->uPly is already the *child's* ply; ctx->uPly - 1 + is the node whose move loop we're in, i.e. the parent of the + search we're about to reduce). + + PV-parent protection: if the node whose move this is (uPly - 1) + was itself reached with a wide window (a genuine PV node, not + just non-null-window), don't reduce at all here. This is + deliberately about the *parent*, not "am I a PV node myself" -- + every non-first move at a PV node is searched null-window + regardless (standard PVS), so that alone doesn't distinguish + "one ply below a real PV" from "deep inside an already-non-PV + subtree". Confirmed empirically (not just theoretically) to + matter: without this, graded LMR measured worse than baseline; + with it, break-even. Grandparent protection (uPly - 2) was + tried and measured worse (23/30, EBF 4.258 vs this config's + 24/30, EBF 4.223 on ecm_quick.ep_ @ sn=4M) -- not worth it. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uRemainingDepth, + ULONG uLegalMoves, + MOVE mv, + INT iExtend + +Return value: + + INT : 0 if no reduction, else a negative ply-fraction (ONE_PLY + units) suitable for adding directly into iExtend. + +**/ +{ + ULONG uDepthPly, uMoveIdx; + INT iReduction; + + ASSERT(ctx->uPly > 0); + ASSERT(mv.uMove); + ASSERT((uMoveNum > 0) || (uLegalMoves == 0)); + if ((uRemainingDepth >= TWO_PLY) && + (iBeta == (iAlpha + 1)) && + (uLegalMoves > 3) && + (0 == iExtend) && + (!IS_ESCAPING_CHECK(mv)) && + (!IS_CAPTURE_OR_PROMOTION(mv)) && + (!IS_CHECKING_MOVE(mv)) && + (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0])) && + (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) && + ((ctx->uPly < 3) || + (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) && + !IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1]))) && + (!IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX(ctx->sPlyInfo[ctx->uPly-1].mv)][0])) && + (!IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX(ctx->sPlyInfo[ctx->uPly-1].mv)][1])) && + (GetMoveFailHighPercentage(mv) <= 10)) + { + ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); + uDepthPly = MINU(uRemainingDepth / ONE_PLY, MAX_PLY_PER_SEARCH); + uMoveIdx = MINU(uLegalMoves, LMR_TABLE_MAX_MOVES); + + // Base reduction (matches the old fixed -ONE_PLY history-pruning + // behavior) plus a graded extra on top from the table, same + // structure as the prior validated implementation. + iReduction = -(ONE_PLY + g_iLMRQuietReduction[uDepthPly][uMoveIdx]); + + // NOTE: tried an "improving" signal here (Crafty/Berserk/SF-style, + // comparing static eval to 2 plies ago), both with + // GetRoughEvalScore's material-only fallback and with a real + // Eval() call (LAZY_EVAL-fast-pathed) feeding pi->iEval -- both + // measured identically worse (23/30, EBF 4.252 vs this config's + // 24/30, EBF 4.223). The signal itself isn't paying off here, not + // just the eval-quality proxy; not worth pursuing further without + // a different formulation. + + // Soft PV-adjacency discount (Crafty-style): if the parent node + // (whose move loop we're in) was itself a genuine PV node, reduce + // one ply less rather than skipping the reduction outright. + if (TRUE == ctx->sPlyInfo[ctx->uPly - 1].fPvNode) + { + iReduction += ONE_PLY; + if (iReduction > 0) iReduction = 0; + } + if (0 == iReduction) return(0); + + // Never reduce past leaving less than TWO_PLY of remaining depth -- + // a reduced child must still get a real search, not be treated as + // a leaf/qsearch node by accident. + if ((INT)uRemainingDepth + iReduction < TWO_PLY) + { + iReduction = -MAX((INT)uRemainingDepth - TWO_PLY, 0); + } + ASSERT(iReduction <= 0); + return(iReduction); + } + return(0); +} @@ -471,8 +471,8 @@ Return value: InitializeDistanceTable(); InitializeOpeningBook(); InitializeDynamicMoveOrdering(); + InitLMRTable(); InitializeHashSystem(); - InitializePositionHashSystem(); #ifdef MP InitializeParallelSearch(); #endif @@ -507,7 +507,6 @@ Return value: #ifdef MP CleanupParallelSearch(); #endif - CleanupPositionHashSystem(); CleanupHashSystem(); CleanupTreeDump(); CleanupOptions(); diff --git a/src/poshash.c b/src/poshash.c deleted file mode 100644 index d8b4fcd..0000000 --- a/src/poshash.c +++ /dev/null @@ -1,254 +0,0 @@ -/*++ - -Copyright (c) Scott Gasch - -Module Name: - - poshash.c - -Abstract: - - A hash table of information about positions. - -Author: - - Scott Gasch (SGasch) 11 Nov 2006 - -Revision History: - ---*/ - -#include "chess.h" - -#define NUM_POSITION_HASH_ENTRIES (1048576) // 16Mb -POSITION_HASH_ENTRY g_PositionHash[NUM_POSITION_HASH_ENTRIES]; - -#ifdef MP -#define NUM_POSITION_HASH_LOCKS (512) -volatile static ULONG g_uPositionHashLocks[NUM_POSITION_HASH_LOCKS]; -#define POSITION_HASH_IS_LOCKED(x) ((g_uPositionHashLocks[(x)]) != 0) -#define LOCK_POSITION_HASH(x) \ - AcquireSpinLock(&(g_uPositionHashLocks[(x)])); \ - ASSERT(POSITION_HASH_IS_LOCKED(x)) -#define UNLOCK_POSITION_HASH(x) \ - ASSERT(POSITION_HASH_IS_LOCKED(x)); \ - ReleaseSpinLock(&(g_uPositionHashLocks[(x)])) -#else -#define POSITION_HASH_IS_LOCKED(x) -#define LOCK_HASH(x) -#define UNLOCK_HASH(x) -#endif - -void -InitializePositionHashSystem(void) -{ - memset(&g_PositionHash, 0, sizeof(g_PositionHash)); -#ifdef MP - memset(&g_uPositionHashLocks, 0, sizeof(g_uPositionHashLocks)); -#endif -} - -void -CleanupPositionHashSystem(void) -{ - ; // do nothing -} - -static INLINE UINT64 PositionToSignatureIgnoringMove(POSITION *pos) -{ - return((pos->u64NonPawnSig ^ pos->u64PawnSig) >> 1); -} - -// Note: sig must be pre-shifted to ignore the side-to-move bit. -static INLINE ULONG PositionSigToHashPosition(UINT64 u64Sig) -{ - ULONG u = (ULONG)u64Sig; - u &= (NUM_POSITION_HASH_ENTRIES - 1); - ASSERT(u < NUM_POSITION_HASH_ENTRIES); - return u; -} - -#ifdef MP -static INLINE ULONG HashPositionToLockNumber(ULONG u) -{ - u &= (NUM_POSITION_HASH_LOCKS - 1); - ASSERT(u < NUM_POSITION_HASH_LOCKS); - return u; -} -#endif - -void -StoreEnprisePiece(POSITION *pos, COOR cSquare) -{ - UINT64 u64Sig = PositionToSignatureIgnoringMove(pos); - ULONG uEntry = PositionSigToHashPosition(u64Sig); - POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]); - PIECE p = pos->rgSquare[cSquare].pPiece; - ULONG uColor = GET_COLOR(p); -#ifdef MP - ULONG uLock = HashPositionToLockNumber(uEntry); - LOCK_POSITION_HASH(uLock); -#endif - ASSERT(p && IS_VALID_PIECE(p)); - ASSERT(!IS_PAWN(p)); - ASSERT(CAN_FIT_IN_UCHAR(cSquare)); - ASSERT(IS_ON_BOARD(cSquare)); - pHash->cEnprise[uColor] = (UCHAR)cSquare; - ASSERT(pHash->uEnpriseCount[uColor] < 16); - pHash->uEnpriseCount[uColor] += 1; - if (pHash->u64Sig != u64Sig) - { - pHash->u64Sig = u64Sig; - pHash->uEnpriseCount[uColor] = 1; - pHash->cTrapped[uColor] = ILLEGAL_COOR; - uColor = FLIP(uColor); - pHash->cEnprise[uColor] = ILLEGAL_COOR; - pHash->cTrapped[uColor] = ILLEGAL_COOR; - pHash->uEnpriseCount[uColor] = 0; - } -#ifdef MP - UNLOCK_POSITION_HASH(uLock); -#endif -} - -void -StoreTrappedPiece(POSITION *pos, COOR cSquare) -{ - UINT64 u64Sig = PositionToSignatureIgnoringMove(pos); - ULONG uEntry = PositionSigToHashPosition(u64Sig); - POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]); - PIECE p = pos->rgSquare[cSquare].pPiece; - ULONG uColor = GET_COLOR(p); -#ifdef MP - ULONG uLock = HashPositionToLockNumber(uEntry); - LOCK_POSITION_HASH(uLock); -#endif - ASSERT(p && IS_VALID_PIECE(p)); - ASSERT(!IS_PAWN(p)); - ASSERT(CAN_FIT_IN_UCHAR(cSquare)); - ASSERT(IS_ON_BOARD(cSquare)); - pHash->cTrapped[uColor] = cSquare; - if (pHash->u64Sig != u64Sig) - { - pHash->u64Sig = u64Sig; - pHash->cEnprise[uColor] = ILLEGAL_COOR; - pHash->uEnpriseCount[uColor] = 0; - uColor = FLIP(uColor); - pHash->cEnprise[uColor] = ILLEGAL_COOR; - pHash->cTrapped[uColor] = ILLEGAL_COOR; - pHash->uEnpriseCount[uColor] = 0; - } -#ifdef MP - UNLOCK_POSITION_HASH(uLock); -#endif -} - -COOR -GetEnprisePiece(POSITION *pos, ULONG uSide) -{ - UINT64 u64Sig = PositionToSignatureIgnoringMove(pos); - ULONG uEntry = PositionSigToHashPosition(u64Sig); - POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]); - COOR c = ILLEGAL_COOR; -#ifdef MP - ULONG uLock = HashPositionToLockNumber(uEntry); - LOCK_POSITION_HASH(uLock); -#endif - if (pHash->u64Sig == u64Sig) - { - c = pHash->cEnprise[uSide]; - } -#ifdef MP - UNLOCK_POSITION_HASH(uLock); -#endif - return c; -} - -COOR -GetTrappedPiece(POSITION *pos, ULONG uSide) -{ - UINT64 u64Sig = PositionToSignatureIgnoringMove(pos); - ULONG uEntry = PositionSigToHashPosition(u64Sig); - POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]); - COOR c = ILLEGAL_COOR; -#ifdef MP - ULONG uLock = HashPositionToLockNumber(uEntry); - LOCK_POSITION_HASH(uLock); -#endif - if (pHash->u64Sig == u64Sig) - { - c = pHash->cTrapped[uSide]; - } -#ifdef MP - UNLOCK_POSITION_HASH(uLock); -#endif - return c; -} - -ULONG -ValueOfMaterialInTroubleDespiteMove(POSITION *pos, ULONG uSide) -{ - UINT64 u64Sig = PositionToSignatureIgnoringMove(pos); - ULONG uEntry = PositionSigToHashPosition(u64Sig); - POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]); - ULONG u = 0; - COOR c; -#ifdef MP - ULONG uLock = HashPositionToLockNumber(uEntry); - LOCK_POSITION_HASH(uLock); -#endif - if (pHash->u64Sig == u64Sig) - { - if (pHash->uEnpriseCount[uSide] > 1) - { - c = pHash->cEnprise[uSide]; - ASSERT(IS_ON_BOARD(c)); - u = PIECE_VALUE(pos->rgSquare[c].pPiece); - ASSERT(u); - } - c = pHash->cTrapped[uSide]; - if (IS_ON_BOARD(c)) - { - u = MAXU(u, PIECE_VALUE(pos->rgSquare[c].pPiece)); - ASSERT(u); - } - } -#ifdef MP - UNLOCK_POSITION_HASH(uLock); -#endif - return u; -} - -ULONG -ValueOfMaterialInTroubleAfterNull(POSITION *pos, ULONG uSide) -{ - UINT64 u64Sig = PositionToSignatureIgnoringMove(pos); - ULONG uEntry = PositionSigToHashPosition(u64Sig); - POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]); - ULONG u = 0; - COOR c; -#ifdef MP - ULONG uLock = HashPositionToLockNumber(uEntry); - LOCK_POSITION_HASH(uLock); -#endif - if (pHash->u64Sig == u64Sig) - { - if (pHash->uEnpriseCount[uSide]) - { - c = pHash->cEnprise[uSide]; - ASSERT(IS_ON_BOARD(c)); - u += PIECE_VALUE(pos->rgSquare[c].pPiece); - ASSERT(u); - } - c = pHash->cTrapped[uSide]; - if (IS_ON_BOARD(c)) - { - u = MAXU(PIECE_VALUE(pos->rgSquare[c].pPiece), u); - ASSERT(u); - } - } -#ifdef MP - UNLOCK_POSITION_HASH(uLock); -#endif - return u; -} @@ -333,6 +333,17 @@ Return value: ctx->sMoveStack.uUnblockedKeyValue[u] = ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28; } + + // + // A zeroed COOR (0x00) is on-board (a8), not "none" -- unlike + // MOVE's uMove==0 sentinel, COOR needs an explicit reset to + // ILLEGAL_COOR so enprise/trapped hint slots start out invalid. + // + for (u = 0; u < MAX_PLY_PER_SEARCH; u++) + { + ctx->cEnprise[u][0] = ctx->cEnprise[u][1] = ILLEGAL_COOR; + ctx->cTrapped[u] = ILLEGAL_COOR; + } } @@ -1264,6 +1275,11 @@ Return value: if (g_MoveTimer.bvFlags & TIMER_STOPPING) break; } g_Options.u64NodesSearched = ctx->sCounters.tree.u64TotalNodeCount; + g_Options.u64BetaCutoffs = ctx->sCounters.tree.u64BetaCutoffs; + g_Options.u64BetaCutoffsOnFirstMove = + ctx->sCounters.tree.u64BetaCutoffsOnFirstMove; + g_Options.u64CounterMoveTries = ctx->sCounters.tree.u64CounterMoveTries; + g_Options.u64CounterMoveHits = ctx->sCounters.tree.u64CounterMoveHits; g_MoveTimer.dEndTime = SystemTimeStamp(); // @@ -319,10 +319,16 @@ Return value: InitializeLightweightSearcherContext(pos, &ctx); mv.uMove = 0; + // GENERATE_DONT_SCORE: this ctx is a LIGHTWEIGHT_SEARCHER_CONTEXT + // cast to the full type -- only safe if GenerateMoves doesn't + // touch fields past uPly/sPosition/sPlyInfo/sMoveStack, which + // GENERATE_ALL_MOVES/GENERATE_ESCAPES no longer guarantee now + // that _ScoreAllMoves/_ScoreAllEscapes read enprise/killer + // data off ctx. This caller only wants legality/SAN matching + // and never reads .iValue, so skipping scoring is free. GenerateMoves((SEARCHER_THREAD_CONTEXT *)&ctx, mv, - (InCheck(pos, pos->uToMove) ? GENERATE_ESCAPES : - GENERATE_ALL_MOVES)); + GENERATE_DONT_SCORE); for (u = ctx.sMoveStack.uBegin[0]; u < ctx.sMoveStack.uEnd[0]; u++) diff --git a/src/script.c b/src/script.c index 4fb413d..085f9ec 100755 --- a/src/script.c +++ b/src/script.c @@ -23,6 +23,11 @@ Revision History: #include "chess.h" +// Declared directly instead of #include <math.h> -- that header #defines +// its own INFINITY, which collides with ours (chess.h:198, MAX_SHORT) and +// would silently change what INFINITY means for the rest of this file. +extern double pow(double, double); + // ---------------------------------------------------------------------- // // Global testsuite position counters @@ -50,7 +55,12 @@ typedef struct _SUITE_COUNTERS ULONG uSigmaDepth; double dSigmaSolutionTime; double dAverageNps; - double dAverageFirstMoveBeta; + UINT64 u64TotalBetaCutoffs; + UINT64 u64TotalBetaCutoffsOnFirstMove; + UINT64 u64TotalCounterMoveTries; + UINT64 u64TotalCounterMoveHits; + double dSigmaEBF; // sum of per-problem nodes^(1/depth) + ULONG uEBFCount; // number of problems with depth > 0 double dAverageTimeToSolution; ULONG uHistogram[SUITE_NUM_HISTOGRAM]; } @@ -400,8 +410,16 @@ Return value: if (!STRNCMPI(szLine, "go", 2)) { (void)Think(pos); - g_SuiteCounters.u64TotalNodeCount += + g_SuiteCounters.u64TotalNodeCount += g_Options.u64NodesSearched; + g_SuiteCounters.u64TotalBetaCutoffs += + g_Options.u64BetaCutoffs; + g_SuiteCounters.u64TotalBetaCutoffsOnFirstMove += + g_Options.u64BetaCutoffsOnFirstMove; + g_SuiteCounters.u64TotalCounterMoveTries += + g_Options.u64CounterMoveTries; + g_SuiteCounters.u64TotalCounterMoveHits += + g_Options.u64CounterMoveHits; } else { @@ -426,17 +444,29 @@ Return value: " avg. search speed : %6.1f nps\n" " avg. solution time : %3.1f sec\n" " avg. search depth : %4.1f ply\n" + " 1st move beta cut : %5.2f percent\n" + " avg. eff. branching : %5.3f\n" + " counter move hit %% : %5.2f percent (%" + COMPILER_LONGLONG_UNSIGNED_FORMAT " tries)\n" " script time : %6.1f sec\n\n", g_SuiteCounters.uCorrect, g_SuiteCounters.uIncorrect, g_SuiteCounters.uTotal, g_SuiteCounters.u64TotalNodeCount, - ((double)g_SuiteCounters.u64TotalNodeCount / + ((double)g_SuiteCounters.u64TotalNodeCount / (SystemTimeStamp() - dSuiteStart)), - (g_SuiteCounters.dSigmaSolutionTime / - (double)g_SuiteCounters.uCorrect), - ((double)g_SuiteCounters.uSigmaDepth / + ((g_SuiteCounters.uCorrect > 0) ? + (g_SuiteCounters.dSigmaSolutionTime / + (double)g_SuiteCounters.uCorrect) : 0.0), + ((double)g_SuiteCounters.uSigmaDepth / (double)g_SuiteCounters.uTotal), + (100.0 * (double)g_SuiteCounters.u64TotalBetaCutoffsOnFirstMove / + ((double)g_SuiteCounters.u64TotalBetaCutoffs + 1.0)), + (g_SuiteCounters.dSigmaEBF / + ((double)g_SuiteCounters.uEBFCount + 1.0)), + (100.0 * (double)g_SuiteCounters.u64TotalCounterMoveHits / + ((double)g_SuiteCounters.u64TotalCounterMoveTries + 1.0)), + g_SuiteCounters.u64TotalCounterMoveTries, (SystemTimeStamp() - dSuiteStart)); // Histogram stuff @@ -634,7 +664,14 @@ Return value: { g_SuiteCounters.uTotal++; g_SuiteCounters.uSigmaDepth += uDepth; - + if (uDepth > 0) + { + g_SuiteCounters.dSigmaEBF += + pow((double)ctx->sCounters.tree.u64TotalNodeCount, + 1.0 / (double)uDepth); + g_SuiteCounters.uEBFCount++; + } + if (CheckTestSuiteMove(mv, -1, uDepth)) { Trace("Problem %s solved in %3.1f sec.\n", diff --git a/src/search.c b/src/search.c index 4ea09b0..ce867b6 100755 --- a/src/search.c +++ b/src/search.c @@ -199,6 +199,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta); iInitialAlpha = iAlpha; + pi->fPvNode = (iBeta != iAlpha + 1); ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) || (!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck))); @@ -328,7 +329,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, goto end; } } - + // Maybe increment positional extension level b/c of nullmove search // or hash table results. if (fThreat) @@ -336,7 +337,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, iOrigExtend += THREE_QUARTERS_PLY; INC(ctx->sCounters.extension.uMateThreat); } - + // Main search loop, try moves under this position. Before we get // into the move loop, save the extensions merited by this // position in the tree (pre-move) and the original search flags. @@ -441,7 +442,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, (ctx->uPly >= 2) && (iOrigExtend == 0) && (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0) && - (ValueOfMaterialInTroubleDespiteMove(pos, pos->uToMove))) + (ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove))) { uFutilityMargin = (iAlpha - iRoughEval) / 2; ASSERT(uFutilityMargin); @@ -451,7 +452,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // fall through case TRY_GENERATED_MOVES: - if (x < ctx->sMoveStack.uEnd[ctx->uPly]) + if (x < ctx->sMoveStack.uEnd[ctx->uPly]) { ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]); if (uLegalMoves < SEARCH_SORT_LIMIT(ctx->uPly)) @@ -480,9 +481,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, ASSERT(SanityCheckMove(pos, mv)); #ifdef MP - // Can we search the remaining moves in parallel? - ASSERT((uDepth / ONE_PLY - 1) >= 0); - ASSERT((uDepth / ONE_PLY - 1) < MAX_PLY_PER_SEARCH); + // Can we search the remaining moves in parallel? Note: + // uDepth can legitimately be < ONE_PLY here (fractional + // depth from a reduction) -- uDepth/ONE_PLY - 1 would + // underflow (ULONG) in that case, which is exactly why the + // uDepth >= ONE_PLY check below short-circuits before the + // g_fCanSplit[] indexing ever evaluates it. if (((uLegalMoves >= 2)) && (0 != g_uNumHelpersAvailable) && (0 == uFutilityMargin) && @@ -568,20 +572,24 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, MAX(MAX_EXTEND_PER_LINE - pf->iCumulativeExtend, 0)); } - // Decide whether or not to do history pruning - if (TRUE == WeShouldDoHistoryPruning(iRoughEval, - iAlpha, - iBeta, - ctx, - uDepth, - uLegalMoves, - mv, - (x - 1), // Note: x==0 if hash - iExtend)) + // Decide how much (if any) to reduce this move's depth -- + // graded LMR. { - ASSERT(iExtend == 0); - iExtend = -ONE_PLY; - pi->iExtensionAmount = -ONE_PLY; + INT iLMR = GetLMRReduction(iRoughEval, + iAlpha, + iBeta, + ctx, + uDepth, + uLegalMoves, + mv, + (x - 1), // Note: x==0 if hash + iExtend); + if (iLMR < 0) + { + ASSERT(iExtend == 0); + iExtend = iLMR; + pi->iExtensionAmount = iLMR; + } } // Maybe even "futility prune" this move away. @@ -623,7 +631,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // Research deeper if history pruning failed if ((iExtend < 0) && (iScore >= iBeta)) { - uNextDepth += ONE_PLY; + uNextDepth -= iExtend; // undo the full reduction, whatever its magnitude pi->iExtensionAmount = 0; iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); } @@ -651,12 +659,31 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, { // Update history and killers list and store in // the transposition table. - UpdateDynamicMoveOrdering(ctx, - uDepth, - mv, - iScore, + UpdateDynamicMoveOrdering(ctx, + uDepth, + mv, + iScore, x); StoreLowerBound(mv, pos, iScore, uDepth, fThreat); + + // A fail-high capturing a non-pawn piece is + // search-proven evidence that piece was en + // prise -- but the victim belongs to the + // *other* side, i.e. whoever is to move at + // ctx->uPly - 1 (ply parity), not here -- + // "despite the move you're about to make, + // this piece stays in trouble." Skip near + // mate: a fail-high there means the whole + // subtree is winning regardless of this + // particular piece, not that it was + // specifically hanging. + if (mv.pCaptured && !IS_PAWN(mv.pCaptured) && + (iBeta < +NMATE)) + { + ASSERT(ctx->uPly > 0); + RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, + mv.cTo); + } KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1); ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); goto end; @@ -1112,33 +1139,38 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, } ASSERT(!InCheck(pos, pos->uToMove)); - // If we get here then side on move is not in check and this - // position looks ok enough to allow him the option to stand pat - // -or- we missed when we probed the dangerhash. Also remember - // that this side has had the option to stand pat when searching - // below this point. This also means the other side is not - // allowed to generate checks on this side because even if it - // discovers a mate, there's no force since a stand pat - // opportunity exists right here. - uLegalMoves = 0; iEval = iBestScore = Eval(ctx, iAlpha, iBeta, &iPositional); - if (iBestScore > iAlpha) + + // If that Eval (above) was full (i.e. not lazy) it may have set + // en prise and trapped piece indicators. Likewise, other nodes + // at this depth may have set en prise piece hints. If these are + // set and valid, it means this is not a "quiet" position. If the + // side on the move has not been able to stand pat yet, don't let + // them now -- force them to play a move and recurse. + if (0 != ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove)) + { + iBestScore = iAlpha; + } + else { - iAlpha = iBestScore; - ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0); - ASSERT(pi->mvBest.uMove == 0); - if (iBestScore >= iBeta) + if (iBestScore > iAlpha) { - goto end; + iAlpha = iBestScore; + ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0); + ASSERT(pi->mvBest.uMove == 0); + if (iBestScore >= iBeta) + { + goto end; + } } + ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE; } - ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE; - // He did not choose to stand pat here; we will be generating - // moves and searching recursively. Compute a futility score: - // any move less than this will not be searched because it will - // just cause a lazy eval answer; is has no shot to bring the - // score close enough to alpha to even consider. + // He did not choose to stand pat here or we did not allow it. We + // will be generating moves and searching recursively. Compute a + // futility score: any move less than this will not be searched + // because it will just cause a lazy eval answer; is has no shot + // to bring the score close enough to alpha to even consider. // // iEval + move_value + margin < alpha // move_value < alpha - margin - iEval @@ -1150,13 +1182,18 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, } // We know we are not in check. If we are early in the qsearch, - // and the other side has not yet been able to stand pat, and we - // have material, generate checks here too. - fIncludeChecks = - ((pf->uQsearchDepth < pf->uQsearchCheckDepth) && - (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) && - (pos->uNonPawnMaterial[pos->uToMove] > (VALUE_KING + VALUE_BISHOP))); + // and the other side has not yet been able to stand pat yet, and + // we have material OR we have hanging pieces, generate checks + // here too. Checks are a "good way" to escape from "trouble". + fIncludeChecks = ((pf->uQsearchDepth < pf->uQsearchCheckDepth) && + (((pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) && + (pos->uNonPawnMaterial[pos->uToMove] > + (VALUE_KING + VALUE_BISHOP))) || + (FALSE == ctx->sSearchFlags.fCouldStandPat[pos->uToMove]))); + GenerateMoves(ctx, NULLMOVE, _WhatToGen[fIncludeChecks]); + + uLegalMoves = 0; for (x = ctx->sMoveStack.uBegin[ctx->uPly]; x < ctx->sMoveStack.uEnd[ctx->uPly]; x++) @@ -1217,6 +1254,19 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, { if (iScore >= iBeta) { + // A fail-high capturing a non-pawn piece is + // search-proven evidence that piece was en + // prise -- victim belongs to the mover at + // ctx->uPly - 1, not here (see the same + // reasoning in the main Search() fail-high + // branch). Skip near mate. + if (mv.pCaptured && !IS_PAWN(mv.pCaptured) && + (iBeta < +NMATE)) + { + ASSERT(ctx->uPly > 0); + RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, + mv.cTo); + } KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1); ASSERT(iBestScore > -NMATE); ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); diff --git a/src/searchsup.c b/src/searchsup.c index 0cf52bf..c7ac842 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -187,35 +187,28 @@ ThreadUnderTerminatingSplit(IN SEARCHER_THREAD_CONTEXT *ctx) } -FLAG -WeShouldDoHistoryPruning(IN SCORE iRoughEval, - IN SCORE iAlpha, - IN SCORE iBeta, - IN SEARCHER_THREAD_CONTEXT *ctx, - IN ULONG uRemainingDepth, - IN ULONG uLegalMoves, - IN MOVE mv, - IN ULONG uMoveNum, - IN INT iExtend) +INT +GetLMRReduction(IN SCORE iRoughEval, + IN SCORE iAlpha, + IN SCORE iBeta, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN ULONG uRemainingDepth, + IN ULONG uLegalMoves, + IN MOVE mv, + IN ULONG uMoveNum, + IN INT iExtend) /** Routine description: - Decide whether or not to do history pruning at this node for the - given move. Note: this function is called after the move has - been played on the board. - -Parameters: - - SEARCHER_THREAD_CONTEXT *ctx, - ULONG uRemainingDepth, - ULONG uLegalMoves, - MOVE mv, - INT iExtend + True pre-LMR/pre-counter-move baseline: original binary history + pruning (fixed -ONE_PLY), no graded table, no PV-parent guard, no + counter-move exemption. Kept under the GetLMRReduction name so + search.c/split.c's call sites need no changes. Return value: - FLAG + INT : 0 if no reduction, else -ONE_PLY. **/ { @@ -226,7 +219,6 @@ Return value: (iBeta == (iAlpha + 1)) && (uLegalMoves > 5) && (0 == iExtend) && -// (iRoughEval + ComputeMoveScore(ctx, mv, uMoveNum - 1) + 200 < iAlpha) && (!IS_ESCAPING_CHECK(mv)) && (!IS_CAPTURE_OR_PROMOTION(mv)) && (!IS_CHECKING_MOVE(mv)) && @@ -238,9 +230,9 @@ Return value: (GetMoveFailHighPercentage(mv) <= 10)) { ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); - return(TRUE); + return(-ONE_PLY); } - return(FALSE); + return(0); } @@ -1027,7 +1019,7 @@ WeShouldTryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx, ASSERT(u <= 6); if ((iRoughEval + _iDistAlphaSkipNull[u] <= iAlpha) || ((iRoughEval + _iDistAlphaSkipNull[u] / 2 <= iAlpha) && - (ValueOfMaterialInTroubleAfterNull(pos, pos->uToMove)))) + (ValueOfMaterialInTroubleAfterNull(ctx, pos->uToMove)))) { return FALSE; } @@ -1125,7 +1117,9 @@ TryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx, { ASSERT(GET_COLOR(mv.pCaptured) == FLIP(pos->uToMove)); ASSERT(mv.pCaptured == pos->rgSquare[mv.cTo].pPiece); - StoreEnprisePiece(pos, mv.cTo); + // Victim belongs to FLIP(pos->uToMove) here, i.e. the + // mover at ctx->uPly - 1 (see RecordEnprisePieceAtPly). + RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, mv.cTo); mvRef = ctx->mvNullmoveRefutations[ctx->uPly - 2]; if ((mvRef.uMove) && (mvRef.pCaptured == mv.pCaptured) && diff --git a/src/split.c b/src/split.c index bbaa518..2672c0c 100755 --- a/src/split.c +++ b/src/split.c @@ -1122,23 +1122,26 @@ Return value: } // - // Decide whether to history prune + // Decide how much (if any) to reduce this move's depth. // - if (TRUE == WeShouldDoHistoryPruning(iRoughEval, - iAlpha, - iBeta, - ctx, - uDepth, - (g_SplitInfo[u].uAlreadyDone + - uMoveNum + 1), - mv, - (g_SplitInfo[u].uAlreadyDone + - uMoveNum + 1), - iExtend)) { - ASSERT(iExtend == 0); - iExtend = -ONE_PLY; - ctx->sPlyInfo[ctx->uPly].iExtensionAmount = -ONE_PLY; + INT iLMR = GetLMRReduction(iRoughEval, + iAlpha, + iBeta, + ctx, + uDepth, + (g_SplitInfo[u].uAlreadyDone + + uMoveNum + 1), + mv, + (g_SplitInfo[u].uAlreadyDone + + uMoveNum + 1), + iExtend); + if (iLMR < 0) + { + ASSERT(iExtend == 0); + iExtend = iLMR; + ctx->sPlyInfo[ctx->uPly].iExtensionAmount = iLMR; + } } // @@ -1159,7 +1162,7 @@ Return value: // if ((iExtend < 0) && (iScore >= iBeta)) { - uDepth += ONE_PLY; + uDepth -= iExtend; // undo the full reduction, whatever its magnitude ctx->sPlyInfo[ctx->uPly].iExtensionAmount = 0; iScore = -Search(ctx, -iBeta, -iAlpha, uDepth); } @@ -891,7 +891,13 @@ BackupFile(CHAR *szFile) Routine description: Backup a file to file.000. If file.000 already exists, back it up - to file.001 etc... + to file.001 etc... szFile may include a directory path; the + numeric prefix is inserted before the basename, not the whole + path (a bare "%03u%s" prepend onto a full path like + "/usr/local/tmp/typhoon.log" produces the bogus relative path + "000/usr/local/tmp/typhoon.log", whose "000" directory component + doesn't exist -- that's what used to make this silently fail + whenever the logfile path had a directory in it). Note: this function is recursive and can require quite a lot of stack space. Also it is full of race conditions and should not be @@ -911,25 +917,32 @@ Return value: ULONG u; CHAR buf[SMALL_STRING_LEN_CHAR]; CHAR *p; + CHAR *szBase; + ULONG uDirLen; if (TRUE == SystemDoesFileExist(szFile)) { - if ((strlen(szFile) > 3) && - (isdigit(szFile[0])) && - (isdigit(szFile[1])) && - (isdigit(szFile[2]))) + szBase = strrchr(szFile, '/'); + szBase = (NULL != szBase) ? (szBase + 1) : szFile; + uDirLen = (ULONG)(szBase - szFile); + + if ((strlen(szBase) > 3) && + (isdigit(szBase[0])) && + (isdigit(szBase[1])) && + (isdigit(szBase[2]))) { - u = (szFile[0] - '0') * 100; - u += (szFile[1] - '0') * 10; - u += szFile[2] - '0' + 1; - p = &(szFile[3]); + u = (szBase[0] - '0') * 100; + u += (szBase[1] - '0') * 10; + u += szBase[2] - '0' + 1; + p = &(szBase[3]); } else { u = 0; - p = szFile; + p = szBase; } - snprintf(buf, ARRAY_LENGTH(buf), "%03u%s", u, p); + snprintf(buf, ARRAY_LENGTH(buf), "%.*s%03u%s", + (int)uDirLen, szFile, u, p); if (TRUE == SystemDoesFileExist(buf)) { BackupFile(buf); |