stellarUCI Chess engine written in C++20 |
| git clone git://git.dimitrijedobrota.com/stellar.git |
| Log | Files | Refs | README | LICENSE | |
engine.cpp (12978B)
1 #include <algorithm> 2 #include <ctype.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 7 #include "attack.hpp" 8 #include "board.hpp" 9 #include "evaluate.hpp" 10 #include "move.hpp" 11 #include "movelist.hpp" 12 #include "piece.hpp" 13 #include "repetition.hpp" 14 #include "score.hpp" 15 #include "timer.hpp" 16 #include "uci.hpp" 17 #include "utils.hpp" 18 19 #define FULL_DEPTH 4 20 #define REDUCTION_LIMIT 3 21 #define REDUCTION_MOVE 2 22 23 #define WINDOW 50 24 25 namespace engine { 26 27 struct Hashe { 28 enum class Flag : uint8_t { 29 Exact, 30 Alpha, 31 Beta 32 }; 33 U64 key; 34 Move best; 35 uint8_t depth; 36 int16_t score; 37 Flag flag; 38 }; 39 40 class TTable { 41 public: 42 static inline constexpr const int16_t unknown = 32500; 43 44 TTable() {} 45 TTable(U64 size) : table(size, {0}) {} 46 47 void clear() { table.clear(); }; 48 int16_t read(const Board &board, int ply, Move *best, int16_t alpha, int16_t beta, uint8_t depth) const { 49 U64 hash = board.get_hash(); 50 const Hashe &phashe = table[hash % table.size()]; 51 if (phashe.key == hash) { 52 if (phashe.depth >= depth) { 53 int16_t score = phashe.score; 54 55 if (score < -MATE_SCORE) score += ply; 56 if (score > MATE_SCORE) score -= ply; 57 58 if (phashe.flag == Hashe::Flag::Exact) return score; 59 if ((phashe.flag == Hashe::Flag::Alpha) && (score <= alpha)) return alpha; 60 if ((phashe.flag == Hashe::Flag::Beta) && (score >= beta)) return beta; 61 } 62 *best = phashe.best; 63 } 64 return unknown; 65 } 66 67 void write(const Board &board, int ply, Move best, int16_t score, uint8_t depth, Hashe::Flag flag) { 68 U64 hash = board.get_hash(); 69 Hashe &phashe = table[hash % table.size()]; 70 71 if (score < -MATE_SCORE) score += ply; 72 if (score > MATE_SCORE) score -= ply; 73 74 phashe = {hash, best, depth, score, flag}; 75 } 76 77 private: 78 std::vector<Hashe> table; 79 }; 80 81 class PVTable { 82 public: 83 Move best(uint8_t ply = 0) { return table[0][ply]; } 84 85 void start(uint8_t ply) { length[ply] = ply; } 86 void store(Move move, uint8_t ply) { 87 table[ply][ply] = move; 88 for (uint8_t i = ply + 1; i < length[ply + 1]; i++) 89 table[ply][i] = table[ply + 1][i]; 90 length[ply] = length[ply + 1]; 91 } 92 93 friend std::ostream &operator<<(std::ostream &os, const PVTable &pvtable); 94 95 private: 96 Move table[MAX_PLY][MAX_PLY] = {{}}; 97 uint8_t length[MAX_PLY] = {0}; 98 }; 99 100 std::ostream &operator<<(std::ostream &os, const PVTable &pvtable) { 101 for (uint8_t i = 0; i < pvtable.length[0]; i++) 102 os << pvtable.table[0][i] << " "; 103 return os; 104 } 105 106 static const uci::Settings *settings = nullptr; 107 static Board board; 108 static TTable ttable; 109 static repetition::Table rtable; 110 111 static PVTable pvtable; 112 113 static Move killer[2][MAX_PLY]; 114 static U32 history[12][64]; 115 static bool follow_pv; 116 static U64 nodes; 117 static uint8_t ply; 118 119 U32 inline move_list_score(Move move) { 120 const piece::Type type = board.get_square_piece_type(move.source()); 121 if (move.is_capture()) { 122 const piece::Type captured = board.get_square_piece_type(move.target()); 123 return score::get(type, captured) + 10000; 124 } 125 if (killer[0][ply] == move) return 9000; 126 if (killer[1][ply] == move) return 8000; 127 return history[piece::get_index(type, board.get_side())][to_underlying(move.target())]; 128 } 129 130 std::vector<int> move_list_sort(MoveList &list, const Move best) { 131 static std::vector<int> score(256); 132 133 bool best_found = false; 134 for (int i = 0; i < list.size(); i++) { 135 score[i] = move_list_score(list[i]); 136 if (list[i] == best) { 137 score[i] = 30000; 138 best_found = true; 139 } 140 } 141 142 if (!best_found && ply && follow_pv) { 143 follow_pv = false; 144 for (int i = 0; i < list.size(); i++) { 145 if (list[i] == pvtable.best(ply)) { 146 score[i] = 20000; 147 follow_pv = true; 148 break; 149 } 150 } 151 } 152 153 std::vector<int> index(list.size()); 154 std::iota(begin(index), end(index), 0); 155 sort(begin(index), end(index), [&](int a, int b) { return score[a] > score[b]; }); 156 return index; 157 } 158 159 int stats_move_make(Board ©, const Move move) { 160 copy = board; 161 if (!move.make(board)) { 162 board = copy; 163 return 0; 164 } 165 ply++; 166 rtable.push_hash(copy.get_hash()); 167 if (!move.is_repeatable()) rtable.push_null(); 168 return 1; 169 } 170 171 void stats_move_make_pruning(Board ©) { 172 copy = board; 173 board.switch_side(); 174 board.set_enpassant(square::no_sq); 175 ply++; 176 } 177 178 void stats_move_unmake_pruning(Board ©) { 179 board = copy; 180 ply--; 181 } 182 183 void stats_move_unmake(Board ©, const Move move) { 184 board = copy; 185 if (!move.is_repeatable()) rtable.pop(); 186 rtable.pop(); 187 ply--; 188 } 189 190 int16_t quiescence(int16_t alpha, int16_t beta) { 191 if ((nodes & 2047) == 0) { 192 uci::communicate(settings); 193 if (settings->stopped) return 0; 194 } 195 pvtable.start(ply); 196 nodes++; 197 198 int score = evaluate::score_position(board); 199 if (ply > MAX_PLY - 1) return score; 200 if (score >= beta) return beta; 201 if (score > alpha) alpha = score; 202 203 Board copy; 204 MoveList list(board, true); 205 for (int idx : move_list_sort(list, Move())) { 206 const Move move = list[idx]; 207 if (!stats_move_make(copy, move)) continue; 208 score = -quiescence(-beta, -alpha); 209 stats_move_unmake(copy, move); 210 211 if (score > alpha) { 212 alpha = score; 213 pvtable.store(move, ply); 214 if (score >= beta) return beta; 215 } 216 217 if (settings->stopped) return 0; 218 } 219 220 return alpha; 221 } 222 223 int16_t negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { 224 int pv_node = (beta - alpha) > 1; 225 Hashe::Flag flag = Hashe::Flag::Alpha; 226 int futility = 0; 227 Move bestMove; 228 Board copy; 229 230 if ((nodes & 2047) == 0) { 231 uci::communicate(settings); 232 if (settings->stopped) return 0; 233 } 234 pvtable.start(ply); 235 236 // && fifty >= 100 237 if (ply && rtable.is_repetition(board.get_hash())) return 0; 238 239 int16_t score = ttable.read(board, ply, &bestMove, alpha, beta, depth); 240 if (ply && score != TTable::unknown && !pv_node) return score; 241 242 bool isCheck = board.is_check(); 243 if (isCheck) depth++; 244 245 if (depth == 0) { 246 nodes++; 247 int16_t score = quiescence(alpha, beta); 248 // ttable_write(board, ply, bestMove, score, depth, HasheFlag::Exact); 249 return score; 250 } 251 252 if (alpha < -MATE_VALUE) alpha = -MATE_VALUE; 253 if (beta > MATE_VALUE - 1) beta = MATE_VALUE - 1; 254 if (alpha >= beta) return alpha; 255 // if (ply > MAX_PLY - 1) return evaluate::score_position(board); 256 257 if (!pv_node && !isCheck) { 258 static constexpr const U32 score_pawn = score::get(piece::Type::PAWN); 259 int16_t staticEval = evaluate::score_position(board); 260 261 // evaluation pruning 262 if (depth < 3 && abs(beta - 1) > -MATE_VALUE + 100) { 263 int16_t marginEval = score_pawn * depth; 264 if (staticEval - marginEval >= beta) return staticEval - marginEval; 265 } 266 267 if (settings->stopped) return 0; 268 269 if (null) { 270 // null move pruning 271 if (ply && depth > 2 && staticEval >= beta) { 272 stats_move_make_pruning(copy); 273 score = -negamax(-beta, -beta + 1, depth - 1 - REDUCTION_MOVE, false); 274 stats_move_unmake_pruning(copy); 275 if (score >= beta) return beta; 276 } 277 278 // razoring 279 score = staticEval + score_pawn; 280 int16_t scoreNew = quiescence(alpha, beta); 281 282 if (score < beta && depth == 1) { 283 return (scoreNew > score) ? scoreNew : score; 284 } 285 286 score += score_pawn; 287 if (score < beta && depth < 4) { 288 if (scoreNew < beta) return (scoreNew > score) ? scoreNew : score; 289 } 290 } 291 292 // futility pruning condition 293 static constexpr const int16_t margin[] = { 294 0, 295 score::get(piece::Type::PAWN), 296 score::get(piece::Type::KNIGHT), 297 score::get(piece::Type::ROOK), 298 }; 299 if (depth < 4 && abs(alpha) < MATE_SCORE && staticEval + margin[depth] <= alpha) futility = 1; 300 } 301 302 uint8_t legal_moves = 0; 303 uint8_t searched = 0; 304 305 MoveList list(board); 306 for (int idx : move_list_sort(list, bestMove)) { 307 const Move move = list[idx]; 308 if (!stats_move_make(copy, move)) continue; 309 legal_moves++; 310 311 // futility pruning 312 if (futility && searched && !move.is_capture() && !move.is_promote() && !board.is_check()) { 313 stats_move_unmake(copy, move); 314 continue; 315 } 316 317 if (!searched) { 318 score = -negamax(-beta, -alpha, depth - 1, true); 319 } else { 320 // Late Move Reduction 321 if (!pv_node && searched >= FULL_DEPTH && depth >= REDUCTION_LIMIT && !isCheck && 322 !move.is_capture() && !move.is_promote() && 323 (move.source() != killer[0][ply].source() || move.target() != killer[0][ply].target()) && 324 (move.source() != killer[1][ply].source() || move.target() != killer[1][ply].target())) { 325 score = -negamax(-alpha - 1, -alpha, depth - 2, true); 326 } else 327 score = alpha + 1; 328 329 // Principal Variation Search 330 if (score > alpha) { 331 score = -negamax(-alpha - 1, -alpha, depth - 1, true); 332 333 // if fail research 334 if ((score > alpha) && (score < beta)) score = -negamax(-beta, -alpha, depth - 1, true); 335 } 336 } 337 338 stats_move_unmake(copy, move); 339 searched++; 340 341 if (settings->stopped) return 0; 342 if (score > alpha) { 343 if (!move.is_capture()) { 344 const piece::Type piece = board.get_square_piece_type(move.source()); 345 history[piece::get_index(piece, board.get_side())][to_underlying(move.target())] += depth; 346 } 347 348 alpha = score; 349 flag = Hashe::Flag::Exact; 350 bestMove = move; 351 pvtable.store(move, ply); 352 353 if (score >= beta) { 354 ttable.write(board, ply, bestMove, beta, depth, Hashe::Flag::Beta); 355 356 if (!move.is_capture()) { 357 killer[1][ply] = killer[0][ply]; 358 killer[0][ply] = move; 359 } 360 361 return beta; 362 } 363 } 364 } 365 366 if (legal_moves == 0) { 367 if (isCheck) return -MATE_VALUE + ply; 368 else 369 return 0; 370 } 371 372 ttable.write(board, ply, bestMove, alpha, depth, flag); 373 return alpha; 374 } 375 376 Move search_position(const uci::Settings &settingsr) { 377 int16_t alpha = -SCORE_INFINITY, beta = SCORE_INFINITY; 378 settings = &settingsr; 379 380 if (settings->newgame) { 381 ttable = TTable(C64(0x1000000)); 382 } 383 384 rtable.clear(); 385 board = settings->board; 386 for (int i = 0; i < settings->madeMoves.size(); i++) { 387 rtable.push_hash(board.get_hash()); 388 settings->madeMoves[i].make(board); 389 if (!settings->madeMoves[i].is_repeatable()) rtable.clear(); 390 } 391 392 ply = 0; 393 nodes = 0; 394 settings->stopped = false; 395 memset(killer, 0x00, sizeof(killer)); 396 memset(history, 0x00, sizeof(history)); 397 rtable = repetition::Table(); 398 399 Move lastBest; 400 uint8_t max_depth = settings->depth ? settings->depth : MAX_PLY; 401 for (uint8_t depth = 1; depth <= max_depth; depth++) { 402 lastBest = pvtable.best(); 403 follow_pv = 1; 404 int16_t score = negamax(alpha, beta, depth, true); 405 406 uci::communicate(settings); 407 if (settings->stopped) break; 408 409 if ((score <= alpha) || (score >= beta)) { 410 alpha = -SCORE_INFINITY; 411 beta = SCORE_INFINITY; 412 depth--; 413 continue; 414 } 415 416 alpha = score - WINDOW; 417 beta = score + WINDOW; 418 419 uint8_t mate_ply = 0xFF; 420 if (score > -MATE_VALUE && score < -MATE_SCORE) { 421 mate_ply = (score + MATE_VALUE) / 2 + 1; 422 std::cout << "info score mate -" << (int)mate_ply; 423 } else if (score > MATE_SCORE && score < MATE_VALUE) { 424 mate_ply = (MATE_VALUE - score) / 2 + 1; 425 std::cout << "info score mate " << (int)mate_ply; 426 } else { 427 std::cout << "info score cp " << score; 428 } 429 430 std::cout << " depth " << (unsigned)depth; 431 std::cout << " nodes " << nodes; 432 std::cout << " time " << timer::get_ms() - settings->starttime; 433 std::cout << " pv " << pvtable << std::endl; 434 435 if (depth >= mate_ply) break; 436 } 437 438 settings->board = board; 439 return !settings->stopped ? pvtable.best() : lastBest; 440 } 441 } // namespace engine 442 443 int main(void) { 444 uci::loop(); 445 return 0; 446 }