Created
April 15, 2025 19:34
-
-
Save nocturn9x/fcede86abd5b8cfef8c5d3060ce5791c to your computer and use it in GitHub Desktop.
Heimdall search (no comments)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import heimdall/see | |
| import heimdall/eval | |
| import heimdall/board | |
| import heimdall/movegen | |
| import heimdall/util/logs | |
| import heimdall/util/limits | |
| import heimdall/util/shared | |
| import heimdall/util/aligned | |
| import heimdall/util/tunables | |
| import heimdall/transpositions | |
| import std/math | |
| import std/times | |
| import std/options | |
| import std/atomics | |
| import std/strutils | |
| import std/monotimes | |
| import std/strformat | |
| import std/heapqueue | |
| export shared | |
| const | |
| NUM_KILLERS* = 1 | |
| NMP_VERIFICATION_THRESHOLD = 14 | |
| MVV_MULTIPLIER = 10 | |
| TTMOVE_OFFSET = 700_000 | |
| GOOD_CAPTURE_OFFSET = 600_000 | |
| KILLERS_OFFSET = 500_000 | |
| COUNTER_OFFSET = 400_000 | |
| QUIET_OFFSET = 200_000 | |
| BAD_CAPTURE_OFFSET = 50_000 | |
| HISTORY_SCORE_CAP = 16384 | |
| func computeLMRTable: array[MAX_DEPTH + 1, array[MAX_MOVES + 1, int]] {.compileTime.} = | |
| for i in 1..result.high(): | |
| for j in 1..result[0].high(): | |
| result[i][j] = round(0.8 + ln(i.float) * ln(j.float) * 0.4).int | |
| const LMR_TABLE = computeLMRTable() | |
| type | |
| ThreatHistoryTable* = array[White..Black, array[Square(0)..Square(63), array[Square(0)..Square(63), array[bool, array[bool, Score]]]]] | |
| CaptHistTable* = array[White..Black, array[Square(0)..Square(63), array[Square(0)..Square(63), array[Pawn..Queen, Score]]]] | |
| CountersTable* = array[Square(0)..Square(63), array[Square(0)..Square(63), Move]] | |
| KillersTable* = array[MAX_DEPTH, array[NUM_KILLERS, Move]] | |
| ContinuationHistory* = array[White..Black, array[PieceKind.Pawn..PieceKind.King, | |
| array[Square(0)..Square(63), array[White..Black, array[PieceKind.Pawn..PieceKind.King, | |
| array[Square(0)..Square(63), int16]]]]]] | |
| SearchStackEntry = object | |
| staticEval: Score | |
| move: Move | |
| piece: Piece | |
| inCheck: bool | |
| reduction: int | |
| SearchStack = array[MAX_DEPTH + 1, SearchStackEntry] | |
| SearchManager* = object | |
| state*: SearchState | |
| stack*: SearchStack | |
| statistics*: SearchStatistics | |
| logger*: SearchLogger | |
| limiter*: SearchLimiter | |
| parameters*: SearchParameters | |
| board: Chessboard | |
| searchMoves: seq[Move] | |
| transpositionTable: ptr TTable | |
| quietHistory: ptr ThreatHistoryTable | |
| captureHistory: ptr CaptHistTable | |
| killers: ptr KillersTable | |
| counters: ptr CountersTable | |
| continuationHistory: ptr ContinuationHistory | |
| workerPool: WorkerPool | |
| workerCount: int | |
| pvMoves: array[MAX_DEPTH + 1, array[MAX_DEPTH + 1, Move]] | |
| evalState: EvalState | |
| clockStarted: bool | |
| expired: bool | |
| minNmpPly: int | |
| previousScores*: array[MAX_MOVES, Score] | |
| previousLines*: array[MAX_MOVES, array[MAX_DEPTH + 1, Move]] | |
| WorkerCommand = enum | |
| Shutdown, Reset, Setup, Go, Ping | |
| WorkerResponse = enum | |
| Ok, SetupMissing, SetupAlready, NotSetUp, Pong | |
| SearchWorker* = ref object | |
| workerId: int | |
| thread: Thread[SearchWorker] | |
| manager: SearchManager | |
| channels: tuple[command: Channel[WorkerCommand], response: Channel[WorkerResponse]] | |
| isSetUp: Atomic[bool] | |
| evalState: EvalState | |
| positions: seq[Position] | |
| transpositionTable: ptr TTable | |
| quietHistory: ptr ThreatHistoryTable | |
| captureHistory: ptr CaptHistTable | |
| killers: ptr KillersTable | |
| counters: ptr CountersTable | |
| continuationHistory: ptr ContinuationHistory | |
| parameters: SearchParameters | |
| WorkerPool* = ref object | |
| workers: seq[SearchWorker] | |
| func resetHeuristicTables*(quietHistory: ptr ThreatHistoryTable, captureHistory: ptr CaptHistTable, killerMoves: ptr KillersTable, | |
| counterMoves: ptr CountersTable, continuationHistory: ptr ContinuationHistory) = | |
| for color in White..Black: | |
| for i in Square(0)..Square(63): | |
| for j in Square(0)..Square(63): | |
| quietHistory[color][i][j][true][false] = Score(0) | |
| quietHistory[color][i][j][false][true] = Score(0) | |
| quietHistory[color][i][j][true][true] = Score(0) | |
| quietHistory[color][i][j][false][false] = Score(0) | |
| for piece in Pawn..Queen: | |
| captureHistory[color][i][j][piece] = Score(0) | |
| for i in 0..<MAX_DEPTH: | |
| for j in 0..<NUM_KILLERS: | |
| killerMoves[i][j] = nullMove() | |
| for fromSq in Square(0)..Square(63): | |
| for toSq in Square(0)..Square(63): | |
| counterMoves[fromSq][toSq] = nullMove() | |
| for sideToMove in White..Black: | |
| for piece in PieceKind.all(): | |
| for to in Square(0)..Square(63): | |
| for prevColor in White..Black: | |
| for prevPiece in PieceKind.all(): | |
| for prevTo in Square(0)..Square(63): | |
| continuationHistory[sideToMove][piece][to][prevColor][prevPiece][prevTo] = 0 | |
| proc search*(self: var SearchManager, searchMoves: seq[Move] = @[], silent=false, ponder=false, minimal=false, variations=1): seq[ref array[MAX_DEPTH + 1, Move]] {.gcsafe.} | |
| proc setBoardState*(self: SearchManager, state: seq[Position]) {.gcsafe.} | |
| func createWorkerPool: WorkerPool = | |
| new(result) | |
| proc newSearchManager*(positions: seq[Position], transpositions: ptr TTable, | |
| quietHistory: ptr ThreatHistoryTable, captureHistory: ptr CaptHistTable, | |
| killers: ptr KillersTable, counters: ptr CountersTable, | |
| continuationHistory: ptr ContinuationHistory, | |
| parameters=getDefaultParameters(), mainWorker=true, chess960=false, | |
| evalState=newEvalState(), state=newSearchState(), | |
| statistics=newSearchStatistics(), normalizeScore: bool = true): SearchManager {.gcsafe.} = | |
| result = SearchManager(transpositionTable: transpositions, quietHistory: quietHistory, | |
| captureHistory: captureHistory, killers: killers, counters: counters, | |
| continuationHistory: continuationHistory, parameters: parameters, | |
| state: state, statistics: statistics, evalState: evalState) | |
| new(result.board) | |
| result.state.normalizeScore.store(normalizeScore) | |
| result.state.chess960.store(chess960) | |
| result.state.isMainThread.store(mainWorker) | |
| if mainWorker: | |
| result.workerPool = createWorkerPool() | |
| result.limiter = newSearchLimiter(result.state, result.statistics) | |
| result.logger = createSearchLogger(result.state, result.statistics, result.board, transpositions) | |
| result.setBoardState(positions) | |
| else: | |
| result.limiter = newDummyLimiter() | |
| proc workerLoop(self: SearchWorker) {.thread.} = | |
| while true: | |
| let msg = self.channels.command.recv() | |
| case msg: | |
| of Ping: | |
| self.channels.response.send(Pong) | |
| of Shutdown: | |
| if self.isSetUp.load(): | |
| self.isSetUp.store(false) | |
| freeHeapAligned(self.killers) | |
| freeHeapAligned(self.quietHistory) | |
| freeHeapAligned(self.captureHistory) | |
| freeHeapAligned(self.continuationHistory) | |
| freeHeapAligned(self.counters) | |
| self.channels.response.send(Ok) | |
| break | |
| of Reset: | |
| if not self.isSetUp.load(): | |
| self.channels.response.send(NotSetUp) | |
| continue | |
| resetHeuristicTables(self.quietHistory, self.captureHistory, self.killers, self.counters, self.continuationHistory) | |
| self.channels.response.send(Ok) | |
| of Go: | |
| if not self.isSetUp.load(): | |
| self.channels.response.send(SetupMissing) | |
| continue | |
| self.channels.response.send(Ok) | |
| discard self.manager.search(@[], true, false, false, 1) | |
| of Setup: | |
| if self.isSetUp.load(): | |
| self.channels.response.send(SetupAlready) | |
| continue | |
| self.quietHistory = allocHeapAligned(ThreatHistoryTable, 64) | |
| self.continuationHistory = allocHeapAligned(ContinuationHistory, 64) | |
| self.captureHistory = allocHeapAligned(CaptHistTable, 64) | |
| self.killers = allocHeapAligned(KillersTable, 64) | |
| self.counters = allocHeapAligned(CountersTable, 64) | |
| self.isSetUp.store(true) | |
| self.manager = newSearchManager(self.positions, self.transpositionTable, | |
| self.quietHistory, self.captureHistory, | |
| self.killers, self.counters, self.continuationHistory, | |
| self.parameters, false, false, self.evalState) | |
| self.channels.response.send(Ok) | |
| proc cmd(self: SearchWorker, cmd: WorkerCommand, expected: WorkerResponse = Ok) {.inline.} = | |
| self.channels.command.send(cmd) | |
| let response = self.channels.response.recv() | |
| doAssert response == expected, &"sent {cmd} to worker #{self.workerId} and expected {expected}, got {response} instead" | |
| proc ping(self: SearchWorker) {.inline.} = | |
| self.cmd(Ping, Pong) | |
| proc setup(self: SearchWorker) {.inline.} = | |
| self.cmd(Setup) | |
| proc go(self: SearchWorker) {.inline.} = | |
| self.cmd(Go) | |
| proc shutdown(self: SearchWorker) {.inline.} = | |
| self.cmd(Shutdown) | |
| joinThread(self.thread) | |
| self.channels.command.close() | |
| self.channels.response.close() | |
| proc reset(self: SearchWorker) {.inline.} = | |
| self.cmd(Reset) | |
| proc create(self: WorkerPool): SearchWorker {.inline, discardable.} = | |
| result = SearchWorker(workerId: self.workers.len()) | |
| self.workers.add(result) | |
| result.channels.command.open(0) | |
| result.channels.response.open(0) | |
| createThread(result.thread, workerLoop, result) | |
| result.ping() | |
| proc reset(self: WorkerPool) {.inline.} = | |
| for worker in self.workers: | |
| worker.reset() | |
| proc shutdown(self: WorkerPool) {.inline.} = | |
| for worker in self.workers: | |
| worker.shutdown() | |
| self.workers.setLen(0) | |
| proc setupWorkers(self: var SearchManager) {.inline.} = | |
| for i in 0..<self.workerCount: | |
| var worker = self.workerPool.workers[i] | |
| worker.positions = self.board.positions.deepCopy() | |
| worker.evalState = self.evalState.deepCopy() | |
| worker.parameters = self.parameters | |
| worker.transpositionTable = self.transpositionTable | |
| worker.setup() | |
| self.state.childrenStats.add(worker.manager.statistics) | |
| proc createWorkers(self: var SearchManager, workerCount: int) {.inline.} = | |
| for i in 0..<workerCount: | |
| self.workerPool.create() | |
| self.setupWorkers() | |
| proc shutdownWorkers*(self: var SearchManager) {.inline.} = | |
| self.workerPool.shutdown() | |
| self.state.childrenStats.setLen(0) | |
| proc resetWorkers*(self: var SearchManager) {.inline.} = | |
| self.workerPool.reset() | |
| proc restartWorkers*(self: var SearchManager) {.inline.} = | |
| self.shutdownWorkers() | |
| self.createWorkers(self.workerCount) | |
| proc startSearch(self: WorkerPool) {.inline.} = | |
| for worker in self.workers: | |
| worker.go() | |
| proc setWorkerCount*(self: var SearchManager, workerCount: int) {.inline.} = | |
| doAssert workerCount >= 0 | |
| if workerCount != self.workerCount: | |
| self.workerCount = workerCount | |
| self.shutdownWorkers() | |
| self.createWorkers(self.workerCount) | |
| func getWorkerCount*(self: SearchManager): int {.inline.} = self.workerCount | |
| proc setBoardState*(self: SearchManager, state: seq[Position]) {.gcsafe.} = | |
| self.board.positions.setLen(0) | |
| for position in state: | |
| self.board.positions.add(position.clone()) | |
| self.evalState.init(self.board) | |
| if self.state.isMainThread.load(): | |
| for worker in self.workerPool.workers: | |
| worker.manager.setBoardState(state) | |
| func getCurrentPosition*(self: SearchManager): lent Position {.inline.} = | |
| return self.board.position | |
| proc setNetwork*(self: var SearchManager, path: string) = | |
| self.evalState = newEvalState(path) | |
| self.evalState.init(self.board) | |
| proc setUCIMode*(self: SearchManager, value: bool) = | |
| self.state.uciMode.store(value) | |
| func isSearching*(self: SearchManager): bool {.inline.} = | |
| result = self.state.searching.load() | |
| func stop*(self: SearchManager) {.inline.} = | |
| if not self.isSearching(): | |
| return | |
| self.state.stop.store(true) | |
| if self.state.isMainThread.load(): | |
| for child in self.workerPool.workers: | |
| child.manager.stop() | |
| func isKillerMove(self: SearchManager, move: Move, ply: int): bool {.inline.} = | |
| for killer in self.killers[ply]: | |
| if killer == move: | |
| return true | |
| proc getMainHistScore(self: SearchManager, sideToMove: PieceColor, move: Move): Score {.inline.} = | |
| assert move.isCapture() or move.isQuiet() | |
| if move.isQuiet(): | |
| let startAttacked = self.board.position.threats.contains(move.startSquare) | |
| let targetAttacked = self.board.position.threats.contains(move.targetSquare) | |
| result = self.quietHistory[sideToMove][move.startSquare][move.targetSquare][startAttacked][targetAttacked] | |
| else: | |
| let victim = self.board.getPiece(move.targetSquare).kind | |
| result = self.captureHistory[sideToMove][move.startSquare][move.targetSquare][victim] | |
| func getOnePlyContHistScore(self: SearchManager, sideToMove: PieceColor, piece: Piece, target: Square, ply: int): int16 {.inline.} = | |
| var prevPiece = self.stack[ply - 1].piece | |
| result += self.continuationHistory[sideToMove][piece.kind][target][prevPiece.color][prevPiece.kind][self.stack[ply - 1].move.targetSquare] | |
| func getTwoPlyContHistScore(self: SearchManager, sideToMove: PieceColor, piece: Piece, target: Square, ply: int): int16 {.inline.} = | |
| var prevPiece = self.stack[ply - 2].piece | |
| result += self.continuationHistory[sideToMove][piece.kind][target][prevPiece.color][prevPiece.kind][self.stack[ply - 2].move.targetSquare] | |
| func getFourPlyContHistScore(self: SearchManager, sideToMove: PieceColor, piece: Piece, target: Square, ply: int): int16 {.inline.} = | |
| var prevPiece = self.stack[ply - 4].piece | |
| result += self.continuationHistory[sideToMove][piece.kind][target][prevPiece.color][prevPiece.kind][self.stack[ply - 4].move.targetSquare] | |
| func getContHistScore(self: SearchManager, sideToMove: PieceColor, piece: Piece, target: Square, ply: int): Score {.inline.} = | |
| if ply > 0: | |
| result += self.getOnePlyContHistScore(sideToMove, piece, target, ply) | |
| if ply > 1: | |
| result += self.getTwoPlyContHistScore(sideToMove, piece, target, ply) | |
| if ply > 3: | |
| result += self.getFourPlyContHistScore(sideToMove, piece, target, ply) | |
| proc updateHistories(self: SearchManager, sideToMove: PieceColor, move: Move, piece: Piece, depth, ply: int, good: bool) {.inline.} = | |
| assert move.isCapture() or move.isQuiet() | |
| var bonus: int | |
| if move.isQuiet(): | |
| bonus = (if good: self.parameters.moveBonuses.quiet.good else: -self.parameters.moveBonuses.quiet.bad) * depth | |
| if ply > 0 and not self.board.positions[^2].fromNull: | |
| let prevPiece = self.stack[ply - 1].piece | |
| self.continuationHistory[sideToMove][piece.kind][move.targetSquare][prevPiece.color][prevPiece.kind][self.stack[ply - 1].move.targetSquare] += (bonus - abs(bonus) * self.getOnePlyContHistScore(sideToMove, piece, move.targetSquare, ply) div HISTORY_SCORE_CAP).int16 | |
| if ply > 1 and not self.board.positions[^3].fromNull: | |
| let prevPiece = self.stack[ply - 2].piece | |
| self.continuationHistory[sideToMove][piece.kind][move.targetSquare][prevPiece.color][prevPiece.kind][self.stack[ply - 2].move.targetSquare] += (bonus - abs(bonus) * self.getTwoPlyContHistScore(sideToMove, piece, move.targetSquare, ply) div HISTORY_SCORE_CAP).int16 | |
| if ply > 3 and not self.board.positions[^5].fromNull: | |
| let prevPiece = self.stack[ply - 4].piece | |
| self.continuationHistory[sideToMove][piece.kind][move.targetSquare][prevPiece.color][prevPiece.kind][self.stack[ply - 4].move.targetSquare] += (bonus - abs(bonus) * self.getFourPlyContHistScore(sideToMove, piece, move.targetSquare, ply) div HISTORY_SCORE_CAP).int16 | |
| let startAttacked = self.board.position.threats.contains(move.startSquare) | |
| let targetAttacked = self.board.position.threats.contains(move.targetSquare) | |
| self.quietHistory[sideToMove][move.startSquare][move.targetSquare][startAttacked][targetAttacked] += Score(bonus) - abs(bonus.int32) * self.getMainHistScore(sideToMove, move) div HISTORY_SCORE_CAP | |
| elif move.isCapture(): | |
| bonus = (if good: self.parameters.moveBonuses.capture.good else: -self.parameters.moveBonuses.capture.bad) * depth | |
| let victim = self.board.getPiece(move.targetSquare).kind | |
| self.captureHistory[sideToMove][move.startSquare][move.targetSquare][victim] += Score(bonus) - abs(bonus.int32) * self.getMainHistScore(sideToMove, move) div HISTORY_SCORE_CAP | |
| proc getEstimatedMoveScore(self: SearchManager, hashMove: Move, move: Move, ply: int): int {.inline.} = | |
| if move == hashMove: | |
| return TTMOVE_OFFSET | |
| if ply > 0: | |
| if self.isKillerMove(move, ply): | |
| return KILLERS_OFFSET | |
| let prevMove = self.stack[ply - 1].move | |
| if move == self.counters[prevMove.startSquare][prevMove.targetSquare]: | |
| return COUNTER_OFFSET | |
| let sideToMove = self.board.sideToMove | |
| if move.isTactical(): | |
| let winning = self.board.position.see(move, 0) | |
| if move.isCapture(): | |
| result += self.getMainHistScore(sideToMove, move) | |
| if not winning: | |
| if move.isCapture(): | |
| result += MVV_MULTIPLIER * self.board.getPiece(move.targetSquare).getStaticPieceScore() | |
| return BAD_CAPTURE_OFFSET + result | |
| else: | |
| return GOOD_CAPTURE_OFFSET + result | |
| if move.isQuiet(): | |
| result = QUIET_OFFSET + self.getMainHistScore(sideToMove, move) + self.getContHistScore(sideToMove, self.board.getPiece(move.startSquare), move.targetSquare, ply) | |
| iterator pickMoves(self: SearchManager, hashMove: Move, ply: int, qsearch: bool = false): Move = | |
| var moves {.noinit.} = newMoveList() | |
| self.board.generateMoves(moves, capturesOnly=qsearch) | |
| var scores {.noinit.}: array[MAX_MOVES, int] | |
| for i in 0..moves.high(): | |
| scores[i] = self.getEstimatedMoveScore(hashMove, moves[i], ply) | |
| for startIndex in 0..<moves.len(): | |
| var | |
| bestMoveIndex = moves.len() | |
| bestScore = int.low() | |
| for i in startIndex..<moves.len(): | |
| if scores[i] > bestScore: | |
| bestScore = scores[i] | |
| bestMoveIndex = i | |
| if bestMoveIndex == moves.len(): | |
| break | |
| yield moves[bestMoveIndex] | |
| let move = moves[startIndex] | |
| let score = scores[startIndex] | |
| moves.data[startIndex] = moves[bestMoveIndex] | |
| scores[startIndex] = scores[bestMoveIndex] | |
| moves.data[bestMoveIndex] = move | |
| scores[bestMoveIndex] = score | |
| func isPondering*(self: SearchManager): bool {.inline.} = self.state.pondering.load() | |
| func cancelled(self: SearchManager): bool {.inline.} = self.state.stop.load() | |
| proc stopPondering*(self: var SearchManager) {.inline.} = | |
| assert self.state.isMainThread.load() | |
| self.state.pondering.store(false) | |
| self.limiter.enable(true) | |
| func nodes*(self: SearchManager): uint64 {.inline.} = | |
| result = self.statistics.nodeCount.load() | |
| for child in self.state.childrenStats: | |
| result += child.nodeCount.load() | |
| proc shouldStop*(self: var SearchManager, inTree=true): bool {.inline.} = | |
| if self.cancelled(): | |
| return true | |
| if not self.state.isMainThread.load(): | |
| return | |
| if self.expired: | |
| return true | |
| result = self.limiter.expired(inTree) | |
| self.expired = result | |
| proc getReduction(self: SearchManager, move: Move, depth, ply, moveNumber: int, isPV: static bool, wasPV, ttCapture, cutNode: bool): int {.inline.} = | |
| let moveCount = when isPV: self.parameters.lmrMoveNumber.pv else: self.parameters.lmrMoveNumber.nonpv | |
| if moveNumber > moveCount and depth >= self.parameters.lmrMinDepth: | |
| result = LMR_TABLE[depth][moveNumber] | |
| when isPV: | |
| dec(result) | |
| if cutNode: | |
| inc(result, 2) | |
| if self.stack[ply].inCheck: | |
| dec(result) | |
| if ttCapture and move.isQuiet(): | |
| inc(result) | |
| if move.isQuiet(): | |
| inc(result) | |
| if move.isQuiet() or move.isCapture(): | |
| let stm = self.board.sideToMove | |
| let piece = self.board.getPiece(move.startSquare) | |
| var score: int = self.getMainHistScore(stm, move) | |
| if move.isQuiet(): | |
| score += self.getContHistScore(stm, piece, move.targetSquare, ply) | |
| score = score div self.parameters.historyLmrDivisor.quiet | |
| else: | |
| score = score div self.parameters.historyLmrDivisor.noisy | |
| dec(result, score) | |
| if ply > 0 and moveNumber >= self.parameters.previousLmrMinimum: | |
| result -= self.stack[ply - 1].reduction div self.parameters.previousLmrDivisor | |
| if wasPV: | |
| dec(result) | |
| result = result.clamp(-1, depth - 1) | |
| proc staticEval(self: SearchManager): Score = | |
| result = self.board.evaluate(self.evalState) | |
| let | |
| knights = self.board.getBitboard(Knight, White) or self.board.getBitboard(Knight, Black) | |
| bishops = self.board.getBitboard(Bishop, White) or self.board.getBitboard(Bishop, Black) | |
| pawns = self.board.getBitboard(Pawn, White) or self.board.getBitboard(Pawn, Black) | |
| rooks = self.board.getBitboard(Rook, White) or self.board.getBitboard(Rook, Black) | |
| queens = self.board.getBitboard(Queen, White) or self.board.getBitboard(Queen, Black) | |
| let material = Score(Knight.getStaticPieceScore() * knights.countSquares() + | |
| Bishop.getStaticPieceScore() * bishops.countSquares() + | |
| Pawn.getStaticPieceScore() * pawns.countSquares() + | |
| Rook.getStaticPieceScore() * rooks.countSquares() + | |
| Queen.getStaticPieceScore() * queens.countSquares()) | |
| result = result * (material + Score(self.parameters.materialScalingOffset)) div Score(self.parameters.materialScalingDivisor) | |
| proc qsearch(self: var SearchManager, ply: int, alpha, beta: Score, isPV: static bool): Score = | |
| if self.shouldStop() or ply >= MAX_DEPTH: | |
| return Score(0) | |
| self.statistics.selectiveDepth.store(max(self.statistics.selectiveDepth.load(), ply)) | |
| if self.board.isDrawn(ply): | |
| return Score(0) | |
| let | |
| query = self.transpositionTable[].get(self.board.zobristKey) | |
| ttHit = query.isSome() | |
| hashMove = if ttHit: query.get().bestMove else: nullMove() | |
| var wasPV = isPV | |
| if not wasPV and ttHit: | |
| wasPV = query.get().flag.wasPV() | |
| if ttHit: | |
| let entry = query.get() | |
| var score = entry.score | |
| if score.isMateScore(): | |
| score -= int16(score.int.sgn() * ply) | |
| case entry.flag.bound(): | |
| of NoBound: | |
| discard | |
| of Exact: | |
| return score | |
| of LowerBound: | |
| if score >= beta: | |
| return score | |
| of UpperBound: | |
| if score <= alpha: | |
| return score | |
| let staticEval = if not ttHit: self.staticEval() else: query.get().staticEval | |
| self.stack[ply].staticEval = staticEval | |
| self.stack[ply].inCheck = self.board.inCheck() | |
| if staticEval >= beta: | |
| let bestScore = (staticEval + beta) div 2 | |
| if not ttHit: | |
| self.transpositionTable.store(0, staticEval, self.board.zobristKey, nullMove(), LowerBound, bestScore.int16, wasPV) | |
| return bestScore | |
| var | |
| bestScore = staticEval | |
| alpha = max(alpha, staticEval) | |
| bestMove = hashMove | |
| for move in self.pickMoves(hashMove, ply, qsearch=true): | |
| let winning = self.board.position.see(move, 0) | |
| if not winning: | |
| continue | |
| let | |
| previous = if ply > 0: self.stack[ply - 1].move else: nullMove() | |
| recapture = previous != nullMove() and previous.targetSquare == move.targetSquare | |
| if not recapture and not self.stack[ply].inCheck and staticEval + self.parameters.qsearchFpEvalMargin <= alpha and not self.board.position.see(move, 1): | |
| continue | |
| let kingSq = self.board.getBitboard(King, self.board.sideToMove).toSquare() | |
| self.stack[ply].move = move | |
| self.stack[ply].piece = self.board.getPiece(move.startSquare) | |
| self.stack[ply].reduction = 0 | |
| self.evalState.update(move, self.board.sideToMove, self.stack[ply].piece.kind, self.board.getPiece(move.targetSquare).kind, kingSq) | |
| self.board.doMove(move) | |
| self.statistics.nodeCount.atomicInc() | |
| prefetch(addr self.transpositionTable.data[getIndex(self.transpositionTable[], self.board.zobristKey)], cint(0), cint(3)) | |
| let score = -self.qsearch(ply + 1, -beta, -alpha, isPV) | |
| self.board.unmakeMove() | |
| self.evalState.undo() | |
| if self.shouldStop(): | |
| return Score(0) | |
| bestScore = max(score, bestScore) | |
| if score >= beta: | |
| break | |
| if score > alpha: | |
| alpha = score | |
| bestMove = move | |
| if self.shouldStop(): | |
| return Score(0) | |
| if self.statistics.currentVariation.load() == 1: | |
| let nodeType = if bestScore >= beta: LowerBound else: UpperBound | |
| var storedScore = bestScore | |
| if storedScore.isMateScore(): | |
| storedScore += Score(storedScore.int.sgn()) * Score(ply) | |
| self.transpositionTable.store(0, storedScore, self.board.zobristKey, bestMove, nodeType, staticEval.int16, wasPV) | |
| return bestScore | |
| proc storeKillerMove(self: SearchManager, ply: int, move: Move) {.inline.} = | |
| let first = self.killers[ply][0] | |
| if first == move: | |
| return | |
| var j = self.killers[ply].len() - 2 | |
| while j >= 0: | |
| self.killers[ply][j + 1] = self.killers[ply][j]; | |
| dec(j) | |
| self.killers[ply][0] = move | |
| func clearPV(self: var SearchManager, ply: int) {.inline.} = | |
| for i in 0..self.pvMoves[ply].high(): | |
| self.pvMoves[ply][i] = nullMove() | |
| func clearKillers(self: SearchManager, ply: int) {.inline.} = | |
| for i in 0..self.killers[ply].high(): | |
| self.killers[ply][i] = nullMove() | |
| proc search(self: var SearchManager, depth, ply: int, alpha, beta: Score, isPV: static bool, cutNode: bool, excluded=nullMove()): Score {.discardable, gcsafe.} = | |
| assert alpha < beta | |
| assert isPV or alpha + 1 == beta | |
| if self.shouldStop() or ply >= MAX_DEPTH: | |
| return | |
| self.clearPV(ply) | |
| if ply < self.killers[].high(): | |
| self.clearKillers(ply + 1) | |
| let originalAlpha = alpha | |
| self.statistics.selectiveDepth.store(max(self.statistics.selectiveDepth.load(), ply)) | |
| if self.board.isDrawn(ply): | |
| return Score(0) | |
| let sideToMove = self.board.sideToMove | |
| self.stack[ply].inCheck = self.board.inCheck() | |
| self.stack[ply].reduction = 0 | |
| var depth = min(depth, MAX_DEPTH) | |
| if self.stack[ply].inCheck: | |
| depth = clamp(depth + 1, 1, MAX_DEPTH) | |
| if depth <= 0: | |
| return self.qsearch(ply, alpha, beta, isPV) | |
| let | |
| isSingularSearch = excluded != nullMove() | |
| query = self.transpositionTable.get(self.board.zobristKey) | |
| ttHit = query.isSome() | |
| ttDepth = if ttHit: query.get().depth.int else: 0 | |
| hashMove = if not ttHit: nullMove() else: query.get().bestMove | |
| ttCapture = ttHit and hashMove.isCapture() | |
| staticEval = if not ttHit: self.staticEval() else: query.get().staticEval | |
| expectFailHigh = ttHit and query.get().flag.bound() in [LowerBound, Exact] | |
| root = ply == 0 | |
| var ttScore = if ttHit: query.get().score else: 0 | |
| var wasPV = isPV | |
| if not wasPV and ttHit: | |
| wasPV = query.get().flag.wasPV() | |
| self.stack[ply].staticEval = staticEval | |
| var improving = false | |
| if ply > 2 and not self.stack[ply].inCheck: | |
| improving = staticEval > self.stack[ply - 2].staticEval | |
| var ttPrune = false | |
| if ttHit and not isSingularSearch: | |
| let entry = query.get() | |
| if ttDepth >= depth: | |
| if ttScore.isMateScore(): | |
| ttScore -= int16(ttScore.int.sgn() * ply) | |
| case entry.flag.bound(): | |
| of NoBound: | |
| discard | |
| of Exact: | |
| ttPrune = true | |
| of LowerBound: | |
| ttPrune = ttScore >= beta | |
| of UpperBound: | |
| ttPrune = ttScore <= alpha | |
| if ttPrune: | |
| when not isPV: | |
| return ttScore | |
| else: | |
| depth = clamp(depth - 1, 1, MAX_DEPTH) | |
| if not root and depth >= self.parameters.iirMinDepth and (not ttHit or ttDepth + self.parameters.iirDepthDifference < depth): | |
| depth = clamp(depth - 1, 1, MAX_DEPTH) | |
| when not isPV: | |
| if self.stack[ply - 1].reduction > 0 and not self.stack[ply - 1].inCheck and not self.stack[ply - 1].move.isTactical() and | |
| (-self.stack[ply - 1].staticEval > self.stack[ply].staticEval) and self.stack[ply].staticEval < alpha: | |
| depth = clamp(depth + 1, 1, MAX_DEPTH) | |
| if not wasPV and not self.stack[ply].inCheck and depth <= self.parameters.rfpDepthLimit and staticEval - self.parameters.rfpEvalThreshold * (depth - improving.int) >= beta: | |
| return beta + (staticEval - beta) div 3 | |
| if not wasPV and depth > self.parameters.nmpDepthThreshold and staticEval >= beta and ply >= self.minNmpPly and | |
| (not ttHit or expectFailHigh or ttScore >= beta) and self.board.canNullMove(): | |
| let | |
| friendlyPawns = self.board.getBitboard(Pawn, sideToMove) | |
| friendlyKing = self.board.getBitboard(King, sideToMove) | |
| friendlyPieces = self.board.getOccupancyFor(sideToMove) | |
| if (friendlyPieces and not (friendlyKing or friendlyPawns)) != 0: | |
| self.statistics.nodeCount.atomicInc() | |
| self.board.makeNullMove() | |
| var reduction = self.parameters.nmpBaseReduction + depth div self.parameters.nmpDepthReduction | |
| reduction += min((staticEval - beta) div self.parameters.nmpEvalDivisor, self.parameters.nmpEvalMaximum) | |
| let score = -self.search(depth - reduction, ply + 1, -beta - 1, -beta, isPV=false, cutNode=not cutNode) | |
| self.board.unmakeMove() | |
| if self.shouldStop(): | |
| return Score(0) | |
| if score >= beta: | |
| if depth <= NMP_VERIFICATION_THRESHOLD or self.minNmpPly > 0: | |
| return score | |
| self.minNmpPly = ply + (depth - reduction) * 3 div 4 | |
| let verifiedScore = self.search(depth - reduction, ply, beta - 1, beta, isPV=false, cutNode=true) | |
| self.minNmpPly = 0 | |
| if verifiedScore >= beta: | |
| return verifiedScore | |
| var | |
| bestMove = hashMove | |
| bestScore = lowestEval() | |
| playedMoves = 0 | |
| i = 0 | |
| alpha = alpha | |
| failedQuiets {.noinit.} = newMoveList() | |
| failedQuietPieces {.noinit.}: array[MAX_MOVES, Piece] | |
| failedCaptures {.noinit.} = newMoveList() | |
| for move in self.pickMoves(hashMove, ply): | |
| if root and self.searchMoves.len() > 0 and move notin self.searchMoves: | |
| continue | |
| if move == excluded: | |
| continue | |
| let | |
| nodesBefore = self.statistics.nodeCount.load() | |
| isNotMated = bestScore > -mateScore() + MAX_DEPTH | |
| lmrDepth = depth - LMR_TABLE[depth][i] | |
| when not isPV: | |
| if move.isQuiet() and lmrDepth <= self.parameters.fpDepthLimit and | |
| (staticEval + self.parameters.fpEvalOffset) + self.parameters.fpEvalMargin * (depth + improving.int) <= alpha and isNotMated: | |
| inc(i) | |
| continue | |
| if not root and move.isQuiet() and isNotMated and playedMoves >= (self.parameters.lmpDepthOffset + self.parameters.lmpDepthMultiplier * depth * depth) div (2 - improving.int): | |
| inc(i) | |
| continue | |
| if not root and isNotMated and lmrDepth <= self.parameters.seePruningMaxDepth and (move.isQuiet() or move.isCapture() or move.isEnPassant()): | |
| let margin = -depth * (if move.isQuiet(): self.parameters.seePruningMargin.quiet else: self.parameters.seePruningMargin.capture) | |
| if not self.board.positions[^1].see(move, margin): | |
| inc(i) | |
| continue | |
| var singular = 0 | |
| if not root and not isSingularSearch and depth > self.parameters.seMinDepth and expectFailHigh and move == hashMove and ttDepth + self.parameters.seDepthOffset >= depth: | |
| let newBeta = Score(ttScore - self.parameters.seDepthMultiplier * depth) | |
| let newAlpha = Score(newBeta - 1) | |
| let newDepth = (depth - self.parameters.seReductionOffset) div self.parameters.seReductionDivisor | |
| let singularScore = self.search(newDepth, ply, newAlpha, newBeta, isPV=false, cutNode=cutNode, excluded=hashMove) | |
| if singularScore < newBeta: | |
| inc(singular) | |
| when not isPV: | |
| if singularScore <= newAlpha - self.parameters.doubleExtMargin: | |
| inc(singular) | |
| if singularScore <= newAlpha - self.parameters.tripleExtMargin: | |
| inc(singular) | |
| elif ttScore >= beta or cutNode: | |
| singular = -2 | |
| self.stack[ply].move = move | |
| self.stack[ply].piece = self.board.getPiece(move.startSquare) | |
| let kingSq = self.board.getBitboard(King, self.board.sideToMove).toSquare() | |
| self.evalState.update(move, self.board.sideToMove, self.stack[ply].piece.kind, self.board.getPiece(move.targetSquare).kind, kingSq) | |
| let reduction = self.getReduction(move, depth, ply, i, isPV, wasPV, ttCapture, cutNode) | |
| self.stack[ply].reduction = reduction | |
| self.board.doMove(move) | |
| self.statistics.nodeCount.atomicInc() | |
| var score: Score | |
| prefetch(addr self.transpositionTable.data[getIndex(self.transpositionTable[], self.board.zobristKey)], cint(0), cint(3)) | |
| if i == 0: | |
| score = -self.search(depth - 1 + singular, ply + 1, -beta, -alpha, isPV, when isPV: false else: not cutNode) | |
| elif reduction > 0: | |
| score = -self.search(depth - 1 - reduction, ply + 1, -alpha - 1, -alpha, isPV=false, cutNode=true) | |
| if score > alpha: | |
| score = -self.search(depth - 1, ply + 1, -alpha - 1, -alpha, isPV=false, cutNode=not cutNode) | |
| else: | |
| score = -self.search(depth - 1, ply + 1, -alpha - 1, -alpha, isPV=false, cutNode=not cutNode) | |
| if i > 0 and score > alpha and score < beta: | |
| score = -self.search(depth - 1, ply + 1, -beta, -alpha, isPV, cutNode=false) | |
| if self.shouldStop(): | |
| self.evalState.undo() | |
| self.board.unmakeMove() | |
| return Score(0) | |
| inc(i) | |
| inc(playedMoves) | |
| if root: | |
| let nodesAfter = self.statistics.nodeCount.load() | |
| self.statistics.spentNodes[move.startSquare][move.targetSquare].atomicInc(nodesAfter - nodesBefore) | |
| self.board.unmakeMove() | |
| self.evalState.undo() | |
| bestScore = max(score, bestScore) | |
| if score >= beta: | |
| if not root and not (move.isCapture() or move.isEnPassant()): | |
| let prevMove = self.stack[ply - 1].move | |
| self.counters[prevMove.startSquare][prevMove.targetSquare] = move | |
| if move.isQuiet(): | |
| if not bestMove.isTactical(): | |
| self.updateHistories(sideToMove, move, self.stack[ply].piece, depth, ply, true) | |
| for i, quiet in failedQuiets: | |
| self.updateHistories(sideToMove, quiet, failedQuietPieces[i], depth, ply, false) | |
| self.storeKillerMove(ply, move) | |
| if move.isCapture(): | |
| if bestMove.isCapture(): | |
| self.updateHistories(sideToMove, move, nullPiece(), depth, ply, true) | |
| for capture in failedCaptures: | |
| self.updateHistories(sideToMove, capture, nullPiece(), depth, ply, false) | |
| break | |
| if score > alpha: | |
| alpha = score | |
| bestMove = move | |
| if root: | |
| self.statistics.bestRootScore.store(score) | |
| self.statistics.bestMove.store(bestMove) | |
| when isPV: | |
| for i, pv in self.pvMoves[ply + 1]: | |
| if pv == nullMove(): | |
| self.pvMoves[ply][i + 1] = nullMove() | |
| break | |
| self.pvMoves[ply][i + 1] = pv | |
| self.pvMoves[ply][0] = move | |
| else: | |
| if move.isQuiet(): | |
| failedQuiets.add(move) | |
| failedQuietPieces[failedQuiets.high()] = self.stack[ply].piece | |
| elif move.isCapture(): | |
| failedCaptures.add(move) | |
| if i == 0: | |
| if self.stack[ply].inCheck: | |
| return Score(ply) - mateScore() | |
| return if not isSingularSearch: Score(0) else: alpha | |
| if self.shouldStop(): | |
| return Score(0) | |
| if not isSingularSearch and (not root or self.statistics.currentVariation.load() == 1) and not self.expired and not self.cancelled(): | |
| let nodeType = if bestScore >= beta: LowerBound elif bestScore <= originalAlpha: UpperBound else: Exact | |
| var storedScore = bestScore | |
| if storedScore.isMateScore(): | |
| storedScore += Score(storedScore.int.sgn()) * Score(ply) | |
| self.transpositionTable.store(depth.uint8, storedScore, self.board.zobristKey, bestMove, nodeType, staticEval.int16, wasPV) | |
| return bestScore | |
| proc startClock*(self: var SearchManager) = | |
| self.state.searchStart.store(getMonoTime()) | |
| self.clockStarted = true | |
| proc search*(self: var SearchManager, searchMoves: seq[Move] = @[], silent=false, ponder=false, minimal=false, variations=1): seq[ref array[MAX_DEPTH + 1, Move]] = | |
| if self.state.isMainThread.load(): | |
| self.workerPool.startSearch() | |
| if ponder: | |
| self.limiter.disable() | |
| else: | |
| self.limiter.enable() | |
| if silent: | |
| self.logger.disable() | |
| else: | |
| self.logger.enable() | |
| self.state.pondering.store(ponder) | |
| self.searchMoves = searchMoves | |
| self.statistics.nodeCount.store(0) | |
| self.statistics.highestDepth.store(0) | |
| self.statistics.selectiveDepth.store(0) | |
| self.statistics.bestRootScore.store(0) | |
| self.statistics.bestMove.store(nullMove()) | |
| self.statistics.currentVariation.store(0) | |
| for i in Square(0)..Square(63): | |
| for j in Square(0)..Square(63): | |
| self.statistics.spentNodes[i][j].store(0) | |
| var score = Score(0) | |
| var bestMoves: seq[Move] = @[] | |
| var legalMoves {.noinit.} = newMoveList() | |
| var variations = min(MAX_MOVES, variations) | |
| var heap = initHeapQueue[tuple[score: Score, line: int]]() | |
| var messages = newSeqOfCap[tuple[score: Score, line: int]](32) | |
| if variations > 1: | |
| self.board.generateMoves(legalMoves) | |
| if searchMoves.len() > 0: | |
| variations = min(variations, searchMoves.len()) | |
| var lines = newSeqOfCap[array[MAX_DEPTH + 1, Move]](variations) | |
| var lastInfoLine = false | |
| result = newSeqOfCap[ref array[MAX_DEPTH + 1, Move]](variations) | |
| for i in 0..<variations: | |
| result.add(new(array[MAX_DEPTH + 1, Move])) | |
| for j in 0..MAX_DEPTH: | |
| self.previousLines[i][j] = nullMove() | |
| for i in 0..<MAX_MOVES: | |
| self.previousScores[i] = Score(0) | |
| block search: | |
| self.state.stop.store(false) | |
| self.state.searching.store(true) | |
| self.expired = false | |
| if not self.clockStarted and self.state.isMainThread.load(): | |
| self.startClock() | |
| for depth in 1..MAX_DEPTH: | |
| if self.shouldStop(false): | |
| break | |
| self.limiter.scale(self.parameters) | |
| heap.clear() | |
| messages.setLen(0) | |
| lines.setLen(0) | |
| for i in 1..variations: | |
| self.statistics.selectiveDepth.store(0) | |
| self.statistics.currentVariation.store(i) | |
| if depth < self.parameters.aspWindowDepthThreshold: | |
| score = self.search(depth, 0, lowestEval(), highestEval(), true, false) | |
| else: | |
| var | |
| delta = Score(self.parameters.aspWindowInitialSize) | |
| alpha = max(lowestEval(), score - delta) | |
| beta = min(highestEval(), score + delta) | |
| reduction = 0 | |
| while true: | |
| score = self.search(depth - reduction, 0, alpha, beta, true, false) | |
| if self.shouldStop(false): | |
| break | |
| if score <= alpha: | |
| alpha = max(lowestEval(), score - delta) | |
| beta = (alpha + beta) div 2 | |
| reduction = 0 | |
| elif score >= beta: | |
| beta = min(highestEval(), score + delta) | |
| reduction += 1 | |
| else: | |
| break | |
| delta += delta | |
| if delta >= Score(self.parameters.aspWindowMaxSize): | |
| delta = highestEval() | |
| let variation = self.pvMoves[0] | |
| lines.add(variation) | |
| bestMoves.add(variation[0]) | |
| let stopping = self.shouldStop(false) | |
| if variation[0] != nullMove() and not stopping: | |
| self.previousLines[i - 1] = variation | |
| result[i - 1][] = variation | |
| if not silent: | |
| if not stopping: | |
| heap.push((score, lines.high())) | |
| else: | |
| let isIncompleteSearch = self.limiter.expired(false) or self.cancelled() | |
| if not isIncompleteSearch: | |
| self.previousScores[i - 1] = score | |
| else: | |
| lastInfoLine = true | |
| break search | |
| self.previousScores[i - 1] = score | |
| self.statistics.highestDepth.store(depth) | |
| if variations > 1: | |
| self.searchMoves = searchMoves | |
| for move in legalMoves: | |
| if move in bestMoves: | |
| continue | |
| if searchMoves.len() > 0 and move notin searchMoves: | |
| continue | |
| self.searchMoves.add(move) | |
| bestMoves.setLen(0) | |
| while heap.len() > 0: | |
| messages.add(heap.pop()) | |
| var i = 1 | |
| for j in countdown(messages.high(), 0): | |
| let message = messages[j] | |
| if not minimal: | |
| self.logger.log(lines[message.line], i, some(message.score)) | |
| inc(i) | |
| var stats = self.statistics | |
| var finalScore = self.previousScores[0] | |
| if self.state.isMainThread.load(): | |
| self.stop() | |
| var bestSearcher = addr self | |
| for worker in self.workerPool.workers: | |
| worker.ping() | |
| let | |
| bestDepth = bestSearcher.statistics.highestDepth.load() | |
| bestScore = bestSearcher.statistics.bestRootScore.load() | |
| currentDepth = worker.manager.statistics.highestDepth.load() | |
| currentScore = worker.manager.statistics.bestRootScore.load() | |
| if (bestDepth == currentDepth and currentScore > bestScore) or (currentScore.isMateScore() and currentScore > bestScore): | |
| bestSearcher = addr worker.manager | |
| if currentDepth > bestDepth and (currentScore > bestScore or not bestScore.isMateScore()): | |
| bestSearcher = addr worker.manager | |
| if not bestSearcher.state.isMainThread.load(): | |
| lastInfoLine = true | |
| stats = bestSearcher.statistics | |
| finalScore = bestSearcher.statistics.bestRootScore.load() | |
| result[0][] = bestSearcher.previousLines[0] | |
| if not silent and (lastInfoLine or minimal): | |
| self.logger.log(result[0][], 1, some(finalScore), some(stats)) | |
| self.state.searching.store(false) | |
| self.state.pondering.store(false) | |
| self.clockStarted = false |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment