// Berserk is a UCI compliant chess engine written in C // Copyright (C) 2026 Jay Honnold // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this program. If not, see . #include "search.h" #include #include #include #include #include #include "board.h" #include "eval.h" #include "history.h" #include "move.h" #include "movegen.h" #include "movepick.h" #include "nn/accumulator.h" #include "options.h" #include "pyrrhic/tbprobe.h" #include "see.h" #include "tb.h" #include "thread.h" #include "transposition.h" #include "tune.h" #include "types.h" #include "uci.h" #include "util.h" #include "zobrist.h" // arrays to store these pruning cutoffs at specific depths SearchParams Limits; static int LMR[MAX_SEARCH_PLY][64]; static int LMP[2][MAX_SEARCH_PLY]; static int STATIC_PRUNE[2][MAX_SEARCH_PLY]; static Score Negamax(Score alpha, Score beta, Depth depth, Bool cutnode, ThreadData* thread, PV* pv, SearchStack* ss); static Score Quiesce(Score alpha, Score beta, Depth depth, ThreadData* thread, SearchStack* ss); static void SortRootMoves(ThreadData* thread, int offset); static Bool ValidRootMove(ThreadData* thread, Move move); void ResetLimits(void) { memset(&Limits, 0, sizeof(Limits)); Limits.start = GetTimeMS(); Limits.max = INT_MAX; Limits.depth = MAX_SEARCH_PLY - 1; Limits.multiPV = 1; Limits.hitrate = 1000; } void InitPruningAndReductionTables(void) { for (Depth depth = 1; depth < MAX_SEARCH_PLY; depth++) for (int moves = 1; moves < 64; moves++) LMR[depth][moves] = (log(depth) * log(moves) / LMR_DIV + LMR_BASE) * 1024; // in 1/1024 plies LMR[0][0] = LMR[0][1] = LMR[1][0] = 0; for (Depth depth = 0; depth < MAX_SEARCH_PLY; depth++) { // LMP has both a improving (more strict) and non-improving evalution // parameter for lmp. If the evaluation is getting better we want to check // more LMP[0][depth] = LMP_BASE + LMP_SCALE * depth * depth; LMP[1][depth] = LMP_IMP_BASE + LMP_IMP_SCALE * depth * depth; STATIC_PRUNE[0][depth] = -SEE_QUIET * depth * depth; // quiet move cutoff STATIC_PRUNE[1][depth] = -SEE_NOISY * depth; // capture cutoff } } INLINE Bool CheckLimits(ThreadData* thread) { if (--thread->calls > 0) return 0; thread->calls = Limits.hitrate; if (Threads.ponder) return 0; long elapsed = GetTimeMS() - Limits.start; if ((Limits.timeset && elapsed >= Limits.max) || // (Limits.nodes && NodesSearched() >= Limits.nodes)) { Threads.stop = 1; return 1; } return 0; } // Whole plies from a reduction kept in 1/1024 plies, rounding down (also for negatives) INLINE int ReductionPlies(int r) { return r >> 10; } INLINE Score AdjustEvalOnFMR(Board* board, Score eval) { return (EVAL_FMR_DIV - board->fmr) * eval / EVAL_FMR_DIV; } INLINE int ThreadValue(ThreadData* thread, const Score worstScore) { return (thread->rootMoves[0].score - worstScore) * thread->depth; } // Static eval of a node not in check. Sets *rawEval to the uncorrected eval (what the TT keeps) and // ss->staticEval to the corrected one, and returns the eval search prunes with: scaled toward 0 by the // fifty move counter and, on a TT hit, replaced by a TT score whose bound says it is tighter. Without a // TT hit the fresh eval is stored in the TT entry. INLINE Score StaticEval(ThreadData* thread, SearchStack* ss, TTEntry* tt, Bool ttHit, Score ttEval, Score ttScore, HashBound ttBound, Bool ttPv, Score* rawEval) { Board* board = &thread->board; *rawEval = ttHit && ttEval != EVAL_UNKNOWN ? ttEval : Evaluate(board, thread); ss->staticEval = ClampEval(*rawEval + GetCorrectionScore(board, ss)); Score eval = AdjustEvalOnFMR(board, ss->staticEval); if (!ttHit) TTPut(tt, board->zobrist, -1, UNKNOWN, BOUND_UNKNOWN, NULL_MOVE, ss->ply, *rawEval, ttPv); else if (ttScore != UNKNOWN && (ttBound & (ttScore > eval ? BOUND_LOWER : BOUND_UPPER))) eval = ttScore; return eval; } // Record move on the search stack, count the node and play it INLINE void PlayMove(ThreadData* thread, SearchStack* ss, Move move) { Board* board = &thread->board; TTPrefetch(KeyAfter(board, move)); ss->move = move; ss->ch = &thread->ch[IsCap(move)][Moving(move)][To(move)]; ss->cont = &thread->contCorrection[Moving(move)][To(move)]; IncRlx(thread->nodes); MakeMove(move, board); } // As PlayMove, with the null move's history pointing at the unused [0][WHITE_PAWN][A1] slots INLINE void PlayNullMove(ThreadData* thread, SearchStack* ss) { Board* board = &thread->board; TTPrefetch(KeyAfter(board, NULL_MOVE)); ss->move = NULL_MOVE; ss->ch = &thread->ch[0][WHITE_PAWN][A1]; ss->cont = &thread->contCorrection[WHITE_PAWN][A1]; IncRlx(thread->nodes); MakeNullMove(board); } INLINE void InitRootMove(RootMove* rm, Move move) { rm->move = move; rm->previousScore = rm->score = rm->avgScore = -CHECKMATE; rm->pv.moves[0] = move; rm->pv.count = 1; rm->nodes = 0; } static void SetupMainThread(Board* board) { ThreadData* mainThread = Threads.threads[0]; mainThread->calls = Limits.hitrate; mainThread->nodes = 0; mainThread->tbhits = 0; mainThread->nmpMinPly = 0; memcpy(&mainThread->board, board, offsetof(Board, accumulators)); if (Limits.searchMoves) { for (int i = 0; i < Limits.searchable.count; i++) InitRootMove(&mainThread->rootMoves[i], Limits.searchable.moves[i]); mainThread->numRootMoves = Limits.searchable.count; } else { SimpleMoveList ml[1]; TBRootMoves(ml, board); if (!ml->count) RootMoves(ml, board); for (int i = 0; i < ml->count; i++) InitRootMove(&mainThread->rootMoves[i], ml->moves[i]); mainThread->numRootMoves = ml->count; } } static void SetupOtherThreads(Board* board) { ThreadData* mainThread = Threads.threads[0]; for (int i = 1; i < Threads.count; i++) { ThreadData* thread = Threads.threads[i]; thread->calls = Limits.hitrate; thread->nodes = 0; thread->tbhits = 0; thread->nmpMinPly = 0; for (int j = 0; j < mainThread->numRootMoves; j++) InitRootMove(&thread->rootMoves[j], mainThread->rootMoves[j].move); thread->numRootMoves = mainThread->numRootMoves; memcpy(&thread->board, board, offsetof(Board, accumulators)); } } void StartSearch(Board* board, uint8_t ponder) { if (Threads.searching) ThreadWaitUntilSleep(Threads.threads[0]); Threads.stopOnPonderHit = 0; Threads.stop = 0; Threads.ponder = ponder; // Setup Threads SetupMainThread(board); SetupOtherThreads(board); Threads.searching = 1; ThreadWake(Threads.threads[0], THREAD_SEARCH); } void MainSearch(void) { ThreadData* mainThread = Threads.threads[0]; Board* board = &mainThread->board; TTUpdate(); for (int i = 1; i < Threads.count; i++) ThreadWake(Threads.threads[i], THREAD_SEARCH); Search(mainThread); pthread_mutex_lock(&Threads.lock); if (!Threads.stop && (Threads.ponder || Limits.infinite)) { Threads.sleeping = 1; pthread_mutex_unlock(&Threads.lock); ThreadWait(mainThread, &Threads.stop); } else { pthread_mutex_unlock(&Threads.lock); } Threads.stop = 1; for (int i = 1; i < Threads.count; i++) ThreadWaitUntilSleep(Threads.threads[i]); int voteMap[64 * 64]; Score worstScore = UNKNOWN; for (int i = 0; i < Threads.count; i++) { ThreadData* thread = Threads.threads[i]; worstScore = Min(worstScore, thread->rootMoves[0].score); voteMap[FromTo(thread->rootMoves[0].move)] = 0; } for (int i = 0; i < Threads.count; i++) { ThreadData* thread = Threads.threads[i]; voteMap[FromTo(thread->rootMoves[0].move)] += ThreadValue(thread, worstScore); } ThreadData* bestThread = mainThread; Score bestScore = bestThread->rootMoves[0].score; int bestVoteScore = voteMap[FromTo(bestThread->rootMoves[0].move)]; for (int i = 1; i < Threads.count; i++) { ThreadData* curr = Threads.threads[i]; Score currScore = curr->rootMoves[0].score; int currVoteScore = voteMap[FromTo(curr->rootMoves[0].move)]; // Always choose the fastest mate or longest avoidance of mate if (abs(bestScore) >= TB_WIN_BOUND) { if (currScore > bestScore) bestThread = curr, bestScore = currScore, bestVoteScore = currVoteScore; } // If this move avoids mate, choose it if: // It's strictly better in terms of voting // or if it's equal in voting and it's individual score is stronger // when considering if this move was a FH or FL in the window // This logic originates verbatim in SF ThreadPool::get_best_thread() else if (currScore > -TB_WIN_BOUND && (currVoteScore > bestVoteScore || (currVoteScore == bestVoteScore && (ThreadValue(curr, worstScore) * (curr->rootMoves[0].pv.count > 2)) > (ThreadValue(bestThread, worstScore) * (bestThread->rootMoves[0].pv.count > 2))))) bestThread = curr, bestScore = currScore, bestVoteScore = currVoteScore; } if (bestThread != mainThread || MINIMAL) PrintUCI(bestThread, bestThread->completedDepth, -CHECKMATE, CHECKMATE, board); if (bestThread != mainThread) { // / If a new thread is best, make it the main thread mainThread->idx = bestThread->idx; Threads.threads[mainThread->idx] = mainThread; bestThread->idx = 0; Threads.threads[0] = bestThread; } bestThread->previousScore = bestThread->rootMoves[0].score; Move bestMove = bestThread->rootMoves[0].move; Move ponderMove = NULL_MOVE; if (bestThread->rootMoves[0].pv.count > 1) ponderMove = bestThread->rootMoves[0].pv.moves[1]; else { // Pull ponder move from the TT if PV doesn't have one. MakeMove(bestMove, board); Bool ttHit = 0, ttPv = 0; Score ttScore, ttEval; Depth ttDepth; HashBound ttBound; TTProbe(board->zobrist, 0, &ttHit, &ponderMove, &ttScore, &ttEval, &ttDepth, &ttBound, &ttPv); // Set to NULL if not legal if (!(ttHit && IsPseudoLegal(ponderMove, board) && IsLegal(ponderMove, board))) ponderMove = NULL_MOVE; UndoMove(bestMove, board); } PrintBestMove(bestMove, ponderMove, board); } void Search(ThreadData* thread) { Board* board = &thread->board; Bool mainThread = !thread->idx; thread->depth = 0; thread->completedDepth = 0; ResetAccumulator(board->accumulators, board, WHITE); ResetAccumulator(board->accumulators, board, BLACK); SetContempt(thread->contempt, board->stm); PV nullPv; Score scores[MAX_SEARCH_PLY]; int searchStability = 0; Move previousBestMove = NULL_MOVE; enum { searchOffset = 6 }; SearchStack searchStack[MAX_SEARCH_PLY + searchOffset]; SearchStack* ss = searchStack + searchOffset; memset(searchStack, 0, (searchOffset + 1) * sizeof(SearchStack)); for (size_t i = 0; i < MAX_SEARCH_PLY; i++) (ss + i)->ply = i, (ss + i)->reduction = 0; for (size_t i = 1; i <= searchOffset; i++) { (ss - i)->ch = &thread->ch[0][WHITE_PAWN][A1]; (ss - i)->cont = &thread->contCorrection[WHITE_PAWN][A1]; (ss - i)->reduction = 0; } while (++thread->depth < MAX_SEARCH_PLY) { if (Limits.depth && mainThread && thread->depth > Limits.depth) break; for (int i = 0; i < thread->numRootMoves; i++) thread->rootMoves[i].previousScore = thread->rootMoves[i].score; for (thread->multiPV = 0; thread->multiPV < Limits.multiPV; thread->multiPV++) { Score alpha = -CHECKMATE; Score beta = CHECKMATE; Score delta = CHECKMATE; Depth searchDepth = thread->depth; Score score = thread->rootMoves[thread->multiPV].avgScore; thread->seldepth = 0; // One at depth 5 or later, start search at a reduced window if (thread->depth >= 5) { delta = ASP_DELTA; alpha = Max(score - delta, -CHECKMATE); beta = Min(score + delta, CHECKMATE); } while (1) { // Go checkmate hunting once our eval is at the edge of it's bounds (-2045, 2045) if (alpha < -2000) alpha = -CHECKMATE; if (beta > 2000) beta = CHECKMATE; // search! score = Negamax(alpha, beta, Max(1, searchDepth), 0, thread, &nullPv, ss); // the score cannot be trusted, leave the root moves as the last completed iteration if (LoadRlx(Threads.stop)) break; SortRootMoves(thread, thread->multiPV); if (mainThread && !MINIMAL && (score <= alpha || score >= beta) && Limits.multiPV == 1 && GetTimeMS() - Limits.start >= 2500) PrintUCI(thread, thread->depth, alpha, beta, board); if (score <= alpha) { // adjust beta downward when failing low beta = (alpha + beta) / 2; alpha = Max(alpha - delta, -CHECKMATE); searchDepth = thread->depth; if (mainThread) Threads.stopOnPonderHit = 0; } else if (score >= beta) { beta = Min(beta + delta, CHECKMATE); if (abs(score) < TB_WIN_BOUND) searchDepth--; } else break; // delta x 1.25 delta += ASP_GROWTH * delta / 64; } if (LoadRlx(Threads.stop)) break; SortRootMoves(thread, 0); // Print if final multipv or time elapsed if (mainThread && !MINIMAL && (thread->multiPV + 1 == Limits.multiPV || GetTimeMS() - Limits.start >= 2500)) PrintUCI(thread, thread->depth, -CHECKMATE, CHECKMATE, board); } if (LoadRlx(Threads.stop)) break; thread->completedDepth = thread->depth; if (!mainThread) continue; Move bestMove = thread->rootMoves[0].move; Score bestScore = thread->rootMoves[0].score; // Found mate? if (Limits.mate && CHECKMATE - abs(bestScore) <= 2 * abs(Limits.mate)) break; if (Limits.softNodes && NodesSearched() >= Limits.softNodes) break; // Time Management stuff long elapsed = GetTimeMS() - Limits.start; // Soft TM checks if (Limits.timeset && thread->depth >= 5 && !Threads.stopOnPonderHit) { Bool sameBestMove = bestMove == previousBestMove; // same move? searchStability = sameBestMove ? Min(10, searchStability + 1) : 0; // increase how stable our best move is double stabilityFactor = TM_STABILITY_BASE - TM_STABILITY_SCALE * searchStability; Score searchScoreDiff = scores[thread->depth - 3] - bestScore; Score prevScoreDiff = thread->previousScore - bestScore; // if we don't know the previous score, work only on the searchscore if (thread->previousScore == UNKNOWN) searchScoreDiff *= 2, prevScoreDiff = 0; double scoreChangeFactor = TM_SCORE_BASE + // TM_SCORE_SEARCH * searchScoreDiff * (searchScoreDiff > 0) + // TM_SCORE_PREV * prevScoreDiff * (prevScoreDiff > 0); scoreChangeFactor = Max(TM_SCORE_MIN, Min(TM_SCORE_MAX, scoreChangeFactor)); uint64_t bestMoveNodes = thread->rootMoves[0].nodes; double pctNodesNotBest = 1.0 - (double) bestMoveNodes / thread->nodes; double nodeCountFactor = Max(TM_NODES_MIN, pctNodesNotBest * TM_NODES_SCALE + TM_NODES_BASE); if (bestScore >= TB_WIN_BOUND) nodeCountFactor = 0.5; if (elapsed > Limits.alloc * stabilityFactor * scoreChangeFactor * nodeCountFactor) { if (Threads.ponder) Threads.stopOnPonderHit = 1; else break; } } previousBestMove = bestMove; scores[thread->depth] = bestScore; } } static Score Negamax(Score alpha, Score beta, Depth depth, Bool cutnode, ThreadData* thread, PV* pv, SearchStack* ss) { Board* board = &thread->board; PV childPv; pv->count = 0; Bool isPV = beta - alpha != 1; // pv node when doing a full window Bool isRoot = !ss->ply; // Score score = -CHECKMATE; // initially assume the worst case Score bestScore = -CHECKMATE; // Score maxScore = CHECKMATE; // best possible Score origAlpha = alpha; // remember first alpha for tt storage Bool inCheck = !!board->checkers; Bool improving = 0; Score eval = ss->staticEval; Score rawEval = eval; Move bestMove = NULL_MOVE; Move hashMove = NULL_MOVE; Move move = NULL_MOVE; if (!isRoot && board->fmr >= 3 && alpha < 0 && HasCycle(board, ss->ply)) { alpha = 2 - (thread->nodes & 0x3); if (alpha >= beta) return alpha; } // drop into noisy moves only if (depth <= 0) return Quiesce(alpha, beta, 0, thread, ss); if (LoadRlx(Threads.stop) || (!thread->idx && CheckLimits(thread))) return 0; if (isPV && thread->seldepth < ss->ply + 1) thread->seldepth = ss->ply + 1; if (!isRoot) { // draw if (IsDraw(board, ss->ply)) return 2 - (thread->nodes & 0x3); // Prevent overflows if (ss->ply >= MAX_SEARCH_PLY - 1) return inCheck ? 0 : Evaluate(board, thread); // Mate distance pruning alpha = Max(alpha, -CHECKMATE + ss->ply); beta = Min(beta, CHECKMATE - ss->ply - 1); if (alpha >= beta) return alpha; } // check the transposition table for previous info // we ignore the tt on singular extension searches Bool ttHit = 0; Score ttScore = UNKNOWN; Score ttEval = EVAL_UNKNOWN; Depth ttDepth = DEPTH_OFFSET; HashBound ttBound = BOUND_UNKNOWN; Bool ttPv = isPV; TTEntry* tt = ss->skip ? NULL : TTProbe(board->zobrist, ss->ply, &ttHit, &hashMove, &ttScore, &ttEval, &ttDepth, &ttBound, &ttPv); hashMove = isRoot ? thread->rootMoves[thread->multiPV].move : hashMove; // if the TT has a value that fits our position and has been searched to an // equal or greater depth, then we accept this score and prune if (!isPV && ttScore != UNKNOWN && ttDepth >= depth && (cutnode || ttScore <= alpha) && (ttBound & (ttScore >= beta ? BOUND_LOWER : BOUND_UPPER))) return ttScore; // tablebase - we do not do this at root if (!isRoot && !ss->skip) { unsigned tbResult = TBProbe(board); if (tbResult != TB_RESULT_FAILED) { IncRlx(thread->tbhits); score = tbResult == TB_WIN ? TB_WIN_SCORE - ss->ply : tbResult == TB_LOSS ? -TB_WIN_SCORE + ss->ply : 0; HashBound bound = tbResult == TB_WIN ? BOUND_LOWER : tbResult == TB_LOSS ? BOUND_UPPER : BOUND_EXACT; // if the tablebase gives us what we want, then we accept it's score and // return if ((bound == BOUND_EXACT) || (bound == BOUND_LOWER ? score >= beta : score <= alpha)) { TTPut(tt, board->zobrist, depth, score, bound, NULL_MOVE, ss->ply, ttEval, ttPv); return score; } // for pv node searches we adjust our a/b search accordingly if (isPV) { if (bound == BOUND_LOWER) { bestScore = score; alpha = Max(alpha, score); } else maxScore = score; } } } if (inCheck) { rawEval = eval = ss->staticEval = EVAL_UNKNOWN; } else { // a singular search (ss->skip) has no TT entry and keeps the eval of the node it re-searches if (ttHit || !ss->skip) eval = StaticEval(thread, ss, tt, ttHit, ttEval, ttScore, ttBound, ttPv, &rawEval); // Improving improving = ss->ply >= 2 && (ss->staticEval > (ss - 2)->staticEval || (ss - 2)->staticEval == EVAL_UNKNOWN); } // reset moves to moves related to 1 additional ply (ss + 1)->skip = NULL_MOVE; (ss + 1)->killers[0] = NULL_MOVE; (ss + 1)->killers[1] = NULL_MOVE; ss->de = (ss - 1)->de; // IIR by Ed Schroder // http://talkchess.com/forum3/viewtopic.php?f=7&t=74769&sid=64085e3396554f0fba414404445b3120 if (!(ss->skip || inCheck)) { if ((isPV || cutnode) && depth >= IIR_DEPTH && !hashMove) depth--; } MovePicker mp; if (!isPV && !inCheck) { const Bool opponentHasEasyCapture = !!OpponentsEasyCaptures(board); const Bool opponentDeclining = ss->staticEval + (ss - 1)->staticEval > 1; if ((ss - 1)->reduction >= 3 && !opponentDeclining) depth++; if ((ss - 1)->reduction >= 1 && depth >= 2 && ss->staticEval + (ss - 1)->staticEval > DECLINE_MARGIN) depth--; // Reverse Futility Pruning // i.e. the static eval is so far above beta we prune if (depth <= RFP_DEPTH && !ss->skip && eval < TB_WIN_BOUND && eval >= beta && eval - RFP_MARGIN * depth + RFP_IMPROVING * (improving && !opponentHasEasyCapture) + RFP_DECLINING * opponentDeclining >= beta && (!hashMove || GetHistory(ss, thread, hashMove) > RFP_HISTORY)) return (eval + beta) / 2; // Razoring if (depth <= RAZOR_DEPTH && eval + RAZOR_MARGIN * depth <= alpha) { score = Quiesce(alpha, beta, 0, thread, ss); if (LoadRlx(Threads.stop)) return 0; if (score <= alpha) return score; } // Null move pruning // i.e. Our position is so good we can give our opponnent a free move and // they still can't catch up (this is usually countered by captures or mate // threats) if (depth >= NMP_DEPTH && (ss - 1)->move != NULL_MOVE && !ss->skip && !opponentHasEasyCapture && eval >= beta && HasNonPawn(board, board->stm) && (ss->ply >= thread->nmpMinPly || board->stm != thread->npmColor)) { Depth R = NMP_BASE + NMP_DEPTH_SCALE * depth / 1024 + Min(NMP_EVAL_SCALE * (eval - beta) / 1024, NMP_EVAL_MAX); PlayNullMove(thread, ss); score = -Negamax(-beta, -beta + 1, depth - R, !cutnode, thread, &childPv, ss + 1); UndoNullMove(board); if (LoadRlx(Threads.stop)) return 0; if (score >= beta) { if (score >= TB_WIN_BOUND) score = beta; if (thread->nmpMinPly || (abs(beta) < TB_WIN_BOUND && depth < NMP_VERIFY_DEPTH)) return score; thread->nmpMinPly = ss->ply + 3 * (depth - R) / 4; thread->npmColor = board->stm; Score verify = Negamax(beta - 1, beta, depth - R, 0, thread, pv, ss); thread->nmpMinPly = 0; if (LoadRlx(Threads.stop)) return 0; if (verify >= beta) return score; } } // Prob cut // If a relatively deep search from our TT doesn't say this node is // less than beta + margin, then we run a shallow search to look Score probBeta = beta + PROBCUT_MARGIN; if (depth >= PROBCUT_DEPTH && !ss->skip && abs(beta) < TB_WIN_BOUND && !(ttHit && ttDepth >= depth - 3 && ttScore < probBeta)) { InitPCMovePicker(&mp, thread, probBeta > eval); while ((move = NextMove(&mp, board, 1))) { if (!IsLegal(move, board)) continue; PlayMove(thread, ss, move); // qsearch to quickly check score = -Quiesce(-probBeta, -probBeta + 1, 0, thread, ss + 1); // if it's still above our cutoff, revalidate if (score >= probBeta) score = -Negamax(-probBeta, -probBeta + 1, depth - 4, !cutnode, thread, pv, ss + 1); UndoMove(move, board); if (LoadRlx(Threads.stop)) return 0; if (score >= probBeta) return score; } } } int numQuiets = 0, numCaptures = 0; Move quiets[64], captures[32]; int legalMoves = 0, playedMoves = 0, skipQuiets = 0; InitNormalMovePicker(&mp, hashMove, thread, ss); while ((move = NextMove(&mp, board, skipQuiets))) { if (ss->skip == move) continue; if (isRoot && !ValidRootMove(thread, move)) continue; if (!isRoot && !IsLegal(move, board)) continue; uint64_t startingNodeCount = thread->nodes; legalMoves++; Depth extension = 0; Bool killerOrCounter = move == mp.killer1 || move == mp.killer2 || move == mp.counter; int history = GetHistory(ss, thread, move); // reduction in 1/1024 plies int R = LMR[Min(depth, 63)][Min(legalMoves, 63)]; R -= LMR_HISTORY * history / 65536; // adjust reduction based on historical score R += LMR_NOISY_HASH * (IsCap(hashMove) || IsPromo(hashMove)); // increase reduction if hash move is noisy if (bestScore > -TB_WIN_BOUND) { if (!isRoot && legalMoves >= LMP[improving][depth]) skipQuiets = 1; if (!IsCap(move) && PromoPT(move) != QUEEN) { Depth lmrDepth = Max(1, depth - ReductionPlies(R)); if (!killerOrCounter && lmrDepth < HP_DEPTH && history < -HP_MARGIN * (depth - 1)) { skipQuiets = 1; continue; } if (!inCheck && lmrDepth < FP_DEPTH && eval + FP_BASE + FP_SCALE * lmrDepth <= alpha) skipQuiets = 1; if (!SEE(board, move, STATIC_PRUNE[0][lmrDepth])) continue; } else { if (!SEE(board, move, STATIC_PRUNE[1][depth])) continue; } } playedMoves++; if (isRoot && !thread->idx && GetTimeMS() - Limits.start > 2500) PrintCurrMove(thread->depth, move, playedMoves + thread->multiPV, board); if (!IsCap(move) && numQuiets < 64) quiets[numQuiets++] = move; else if (IsCap(move) && numCaptures < 32) captures[numCaptures++] = move; // singular extension // if one move is better than all the rest, then we consider this singular // and look at it more (extend). Singular is determined by checking all // other moves at a shallow depth on a nullwindow that is somewhere below // the tt evaluation implemented using "skip move" recursion like in SF // (allows for reductions when doing singular search) if (!isRoot && ss->ply < thread->depth * 2) { // ttHit is implied for move == hashMove to ever be true if (depth >= SE_DEPTH && move == hashMove && ttDepth >= depth - 3 && (ttBound & BOUND_LOWER) && abs(ttScore) < TB_WIN_BOUND) { Score sBeta = Max(ttScore - SE_MARGIN * depth / 8, -CHECKMATE); Depth sDepth = (depth - 1) / 2; ss->skip = move; score = Negamax(sBeta - 1, sBeta, sDepth, cutnode, thread, pv, ss); ss->skip = NULL_MOVE; if (LoadRlx(Threads.stop)) return 0; // no score failed above sBeta, so this is singular if (score < sBeta) { if (!isPV && score < sBeta - SE_TRIPLE_MARGIN && ss->de <= SE_TRIPLE_LIMIT && !IsCap(move)) { extension = 3; ss->de = (ss - 1)->de + 1; } else if (!isPV && score < sBeta - SE_DOUBLE_MARGIN && ss->de <= SE_DOUBLE_LIMIT) { extension = 2; ss->de = (ss - 1)->de + 1; } else { extension = 1; } } else if (sBeta >= beta) return sBeta; else if (ttScore >= beta) extension = -2 + isPV; else if (cutnode) extension = -2; else if (ttScore <= alpha) extension = -1; } } PlayMove(thread, ss, move); // apply extensions Depth newDepth = depth + extension; // Late move reductions if (depth > 1 && legalMoves > 1 && !(isPV && IsCap(move))) { // increase reduction on non-pv if (!ttPv) R += LMR_NOT_PV; // increase reduction if our eval is declining if (!improving) R += LMR_NOT_IMPROVING; // reduce these special quiets less if (killerOrCounter) R -= LMR_KILLER; // move GAVE check if (board->checkers) R -= LMR_CHECK; // Reduce more on expected cut nodes // idea from komodo/sf, explained by Don Daily here // https://talkchess.com/forum3/viewtopic.php?f=7&t=47577&start=10#p519741 // and https://www.chessprogramming.org/Node_Types if (cutnode) R += LMR_CUTNODE + LMR_CUTNODE_QUIET * !IsCap(move); if (ttDepth >= depth) R -= LMR_TT_DEPTH; // prevent dropping into QS, extending, or reducing all extensions R = Min(newDepth, Max(ReductionPlies(R), 1)); ss->reduction = R; Depth lmrDepth = newDepth - R; score = -Negamax(-alpha - 1, -alpha, lmrDepth, 1, thread, &childPv, ss + 1); ss->reduction = 0; if (score > alpha && R > 1) { // Credit to Viz (and lonfom) for the following modification of the zws // re-search depth. They can be found in SF as doDeeperSearch + doShallowerSearch newDepth += (score > bestScore + DEEPER_MARGIN); newDepth -= (score < bestScore + newDepth); if (newDepth - 1 > lmrDepth) score = -Negamax(-alpha - 1, -alpha, newDepth - 1, !cutnode, thread, &childPv, ss + 1); int bonus = score <= alpha ? -HistoryBonus(newDepth - 1) : score >= beta ? HistoryBonus(newDepth - 1) : 0; UpdateCH(ss, move, bonus); } } else if (!isPV || playedMoves > 1) { score = -Negamax(-alpha - 1, -alpha, newDepth - 1, !cutnode, thread, &childPv, ss + 1); } if (isPV && (playedMoves == 1 || (score > alpha && (isRoot || score < beta)))) score = -Negamax(-beta, -alpha, newDepth - 1, 0, thread, &childPv, ss + 1); UndoMove(move, board); // if a stop occurred the score cannot be trusted, so return immediately without // updating the best move, pv, root moves, histories or tt if (LoadRlx(Threads.stop)) return 0; if (isRoot) { RootMove* rm = thread->rootMoves; for (int i = 1; i < thread->numRootMoves; i++) if (thread->rootMoves[i].move == move) { rm = &thread->rootMoves[i]; break; } rm->nodes += thread->nodes - startingNodeCount; rm->avgScore = rm->avgScore == -CHECKMATE ? score : (rm->avgScore + score) / 2; if (playedMoves == 1 || score > alpha) { rm->score = score; rm->seldepth = thread->seldepth; rm->pv.count = childPv.count + 1; rm->pv.moves[0] = move; memcpy(rm->pv.moves + 1, childPv.moves, childPv.count * sizeof(Move)); } else { rm->score = -CHECKMATE; } } if (score > bestScore) { bestScore = score; if (isPV && !isRoot && score > alpha) { pv->count = childPv.count + 1; pv->moves[0] = move; memcpy(pv->moves + 1, childPv.moves, childPv.count * sizeof(Move)); } if (score > alpha) { bestMove = move; alpha = score; if (alpha < beta && score > -TB_WIN_BOUND) depth -= (depth >= 2 && depth <= 11); } // we're failing high if (alpha >= beta) { UpdateHistories(ss, thread, move, depth + (bestScore > beta + HIST_BETA_MARGIN), quiets, numQuiets, captures, numCaptures); break; } } } // Checkmate detection using movecount if (!legalMoves) return ss->skip ? alpha : inCheck ? -CHECKMATE + ss->ply : 0; // don't let our score inflate too high (tb) bestScore = Min(bestScore, maxScore); // prevent saving when in singular search HashBound bound = bestScore >= beta ? BOUND_LOWER : bestScore <= origAlpha ? BOUND_UPPER : BOUND_EXACT; if (!ss->skip && !(isRoot && thread->multiPV > 0)) TTPut(tt, board->zobrist, depth, bestScore, bound, bestMove, ss->ply, rawEval, ttPv); if (!inCheck && !IsCap(bestMove) && (bound & (bestScore >= ss->staticEval ? BOUND_LOWER : BOUND_UPPER))) { UpdateCorrection(ss->staticEval, bestScore, depth, board); UpdateContCorrection(ss->staticEval, bestScore, depth, ss); } return bestScore; } static Score Quiesce(Score alpha, Score beta, Depth depth, ThreadData* thread, SearchStack* ss) { Board* board = &thread->board; Score score = -CHECKMATE; Score futility = -CHECKMATE; Score bestScore = -CHECKMATE + ss->ply; Bool isPV = beta - alpha != 1; Bool inCheck = !!board->checkers; Score eval = ss->staticEval; Score rawEval = eval; Move hashMove = NULL_MOVE; Move bestMove = NULL_MOVE; Move move = NULL_MOVE; if (LoadRlx(Threads.stop) || (!thread->idx && CheckLimits(thread))) return 0; // draw check if (IsDraw(board, ss->ply)) return 0; // prevent overflows if (ss->ply >= MAX_SEARCH_PLY - 1) return inCheck ? 0 : Evaluate(board, thread); // check the transposition table for previous info Bool ttHit = 0; Score ttScore = UNKNOWN; Score ttEval = EVAL_UNKNOWN; Depth ttDepth = DEPTH_OFFSET; HashBound ttBound = BOUND_UNKNOWN; Bool ttPv = isPV; TTEntry* tt = TTProbe(board->zobrist, ss->ply, &ttHit, &hashMove, &ttScore, &ttEval, &ttDepth, &ttBound, &ttPv); // TT score pruning, ttHit implied with adjusted score if (!isPV && ttScore != UNKNOWN && (ttBound & (ttScore >= beta ? BOUND_LOWER : BOUND_UPPER))) return ttScore; if (inCheck) { rawEval = eval = ss->staticEval = EVAL_UNKNOWN; } else { eval = StaticEval(thread, ss, tt, ttHit, ttEval, ttScore, ttBound, ttPv, &rawEval); // stand pat if (eval >= beta) return eval; if (eval > alpha) alpha = eval; bestScore = eval; futility = bestScore + QS_FUTILITY; } (ss + 1)->killers[0] = NULL_MOVE; (ss + 1)->killers[1] = NULL_MOVE; int numQuiets = 0, numCaptures = 0; Move quiets[64], captures[32]; MovePicker mp; if (!inCheck) InitQSMovePicker(&mp, thread, depth >= -1); else InitQSEvasionsPicker(&mp, hashMove, thread, ss); int legalMoves = 0, skipQuiets = !inCheck; while ((move = NextMove(&mp, board, skipQuiets))) { if (!IsLegal(move, board)) continue; legalMoves++; if (bestScore > -TB_WIN_BOUND) { if (!inCheck && mp.phase != QS_PLAY_QUIET_CHECKS && futility <= alpha && !SEE(board, move, 1)) { bestScore = Max(bestScore, futility); continue; } if (!SEE(board, move, 0)) continue; } if (!IsCap(move) && numQuiets < 64) quiets[numQuiets++] = move; else if (IsCap(move) && numCaptures < 32) captures[numCaptures++] = move; PlayMove(thread, ss, move); score = -Quiesce(-beta, -alpha, depth - 1, thread, ss + 1); UndoMove(move, board); if (LoadRlx(Threads.stop)) return 0; if (score > -TB_WIN_BOUND) skipQuiets = 1; if (score > bestScore) { bestScore = score; if (score > alpha) { bestMove = move; alpha = score; } // failed high if (alpha >= beta) { UpdateHistories(ss, thread, move, 1, quiets, numQuiets, captures, numCaptures); break; } } } if (!legalMoves && inCheck) return -CHECKMATE + ss->ply; if (bestScore >= beta && abs(bestScore) < TB_WIN_BOUND) bestScore = (bestScore + beta) / 2; HashBound bound = bestScore >= beta ? BOUND_LOWER : BOUND_UPPER; TTPut(tt, board->zobrist, 0, bestScore, bound, bestMove, ss->ply, rawEval, ttPv); return bestScore; } static void SortRootMoves(ThreadData* thread, int offset) { for (int i = offset; i < thread->numRootMoves; i++) { int best = i; for (int j = i + 1; j < thread->numRootMoves; j++) if (thread->rootMoves[j].score > thread->rootMoves[best].score) best = j; if (best != i) { RootMove temp = thread->rootMoves[best]; thread->rootMoves[best] = thread->rootMoves[i]; thread->rootMoves[i] = temp; } } } static Bool ValidRootMove(ThreadData* thread, Move move) { for (int i = thread->multiPV; i < thread->numRootMoves; i++) if (move == thread->rootMoves[i].move) return 1; return 0; } void SearchClearThread(ThreadData* thread) { memset(&thread->counters, 0, sizeof(thread->counters)); memset(&thread->hh, 0, sizeof(thread->hh)); memset(&thread->ch, 0, sizeof(thread->ch)); memset(&thread->caph, 0, sizeof(thread->caph)); CorrectionClearPart(thread->idx, Threads.count); memset(&thread->contCorrection, 0, sizeof(thread->contCorrection)); thread->board.accumulators = thread->accumulators; thread->previousScore = UNKNOWN; }