| | | 1 | | using Rudim.Board; |
| | | 2 | | using Rudim.Common; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using System.Threading; |
| | | 5 | | |
| | | 6 | | namespace Rudim.Search |
| | | 7 | | { |
| | | 8 | | public static partial class Negamax |
| | | 9 | | { |
| | | 10 | | public static int Nodes; |
| | | 11 | | private static int _searchDepth; |
| | | 12 | | |
| | | 13 | | public static int Search(BoardState boardState, int depth, CancellationToken cancellationToken) |
| | | 14 | | { |
| | 43 | 15 | | _searchDepth = depth; |
| | 43 | 16 | | Nodes = 0; |
| | 43 | 17 | | Quiescence.ResetNodes(); |
| | 43 | 18 | | int score = Search(boardState, depth, int.MinValue + 1, int.MaxValue - 1, true, cancellationToken); |
| | 43 | 19 | | return score; |
| | | 20 | | } |
| | | 21 | | |
| | | 22 | | private static int Search(BoardState boardState, int depth, int alpha, int beta, bool allowNullMove,Cancellation |
| | | 23 | | { |
| | 1840423 | 24 | | int ply = _searchDepth - depth; |
| | 1840423 | 25 | | bool isPvNode = beta - alpha > 1; |
| | 1840423 | 26 | | Nodes++; |
| | | 27 | | |
| | 1840423 | 28 | | if (boardState.IsDraw()) |
| | 0 | 29 | | return 0; |
| | | 30 | | |
| | 1840423 | 31 | | (bool hasValue, int ttScore, Move ttBest) = TranspositionTable.GetEntry(boardState.BoardHash, alpha, beta, d |
| | 1840423 | 32 | | if (hasValue) |
| | | 33 | | { |
| | | 34 | | // TODO: This doesn't seem right - revisit TT impl |
| | 77597 | 35 | | boardState.BestMove = ttBest; |
| | 77597 | 36 | | return TranspositionTable.RetrieveScore(ttScore, ply); |
| | | 37 | | } |
| | | 38 | | |
| | 1762826 | 39 | | if (depth <= 0) |
| | 1238187 | 40 | | return Quiescence.Search(boardState, alpha, beta, cancellationToken); |
| | | 41 | | |
| | 524639 | 42 | | if (CanPruneNullMove(isPvNode, boardState, allowNullMove, depth)) |
| | | 43 | | { |
| | 120436 | 44 | | boardState.MakeNullMove(); |
| | 120436 | 45 | | int score = -Search(boardState, depth - 1 - 2, -beta, -beta + 1, false, cancellationToken); |
| | 120436 | 46 | | boardState.UndoNullMove(); |
| | 120436 | 47 | | if (score >= beta) |
| | 87437 | 48 | | return beta; // TODO : Store in TT |
| | | 49 | | } |
| | | 50 | | |
| | | 51 | | int originalAlpha = alpha; |
| | 437202 | 52 | | bool foundPv = false; |
| | 437202 | 53 | | TranspositionEntryType entryType = TranspositionEntryType.Alpha; |
| | | 54 | | |
| | 437202 | 55 | | boardState.GenerateMoves(); |
| | 437202 | 56 | | PopulateMoveScores(boardState, ply); |
| | | 57 | | |
| | 437202 | 58 | | int numberOfLegalMoves = 0; |
| | 437202 | 59 | | List<Move> moves = boardState.Moves; |
| | 4059350 | 60 | | for(int i = 0; i < moves.Count; ++i) |
| | | 61 | | { |
| | 1977296 | 62 | | MoveOrdering.SortNextBestMove(moves, i); |
| | 1977296 | 63 | | Move move = moves[i]; |
| | 1977296 | 64 | | if (cancellationToken.IsCancellationRequested) |
| | | 65 | | break; |
| | 1977292 | 66 | | boardState.MakeMove(move); |
| | 1977292 | 67 | | if (boardState.IsInCheck(boardState.SideToMove.Other())) |
| | | 68 | | { |
| | 258212 | 69 | | boardState.UnmakeMove(move); |
| | 258212 | 70 | | continue; |
| | | 71 | | } |
| | | 72 | | |
| | 1719080 | 73 | | int score = SearchDeeper(boardState, depth, alpha, beta, cancellationToken, foundPv, allowNullMove); |
| | | 74 | | |
| | 1719080 | 75 | | numberOfLegalMoves++; |
| | | 76 | | |
| | 1719080 | 77 | | boardState.UnmakeMove(move); |
| | 1719080 | 78 | | if (score >= beta) |
| | | 79 | | { |
| | 384819 | 80 | | return BetaCutoff(beta, move, ply, boardState, depth); |
| | | 81 | | } |
| | 1334261 | 82 | | if (score > alpha) |
| | | 83 | | { |
| | 1970 | 84 | | AlphaUpdate(score, move, boardState, depth, out alpha, out foundPv, out entryType); |
| | | 85 | | } |
| | | 86 | | } |
| | | 87 | | |
| | 52383 | 88 | | if (numberOfLegalMoves == 0) |
| | | 89 | | { |
| | 103 | 90 | | if (boardState.IsInCheck(boardState.SideToMove)) |
| | 103 | 91 | | return -Constants.MaxCentipawnEval + ply; |
| | 0 | 92 | | return 0; |
| | | 93 | | } |
| | | 94 | | |
| | 52280 | 95 | | TranspositionTable.SubmitEntry(boardState.BoardHash, TranspositionTable.AdjustScore(alpha, ply), depth, boar |
| | | 96 | | |
| | 52280 | 97 | | return alpha; |
| | | 98 | | } |
| | | 99 | | |
| | | 100 | | private static int SearchDeeper(BoardState boardState, int depth, int alpha, int beta, |
| | | 101 | | CancellationToken cancellationToken, bool foundPv, bool allowNullMove) |
| | | 102 | | { |
| | | 103 | | int score; |
| | 1719080 | 104 | | if (foundPv) |
| | | 105 | | { |
| | 25568 | 106 | | score = PrincipalVariationSearch(boardState, depth, alpha, beta, allowNullMove, cancellationToken); |
| | | 107 | | } |
| | | 108 | | else |
| | | 109 | | { |
| | 1693512 | 110 | | score = -Search(boardState, depth - 1, -beta, -alpha, allowNullMove, cancellationToken); |
| | | 111 | | } |
| | 1719080 | 112 | | return score; |
| | | 113 | | } |
| | | 114 | | } |
| | | 115 | | } |