stellarUCI Chess engine written in C++20 |
| git clone git://git.dimitrijedobrota.com/stellar.git |
| Log | Files | Refs | README | LICENSE |
engine.cpp (15451B)
0 #include <algorithm> 1 #include <cctype> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 6 #include "attack.hpp" 7 #include "board.hpp" 8 #include "evaluate.hpp" 9 #include "move.hpp" 10 #include "movelist.hpp" 11 #include "piece.hpp" 12 #include "repetition.hpp" 13 #include "score.hpp" 14 #include "timer.hpp" 15 #include "uci.hpp" 16 #include "utils.hpp" 17 18 enum { 19 FULL_DEPTH = 4, 20 REDUCTION_LIMIT = 3, 21 REDUCTION_MOVE = 2 22 }; 23 24 enum { 25 WINDOW = 50 26 }; 27 28 namespace engine { 29 30 struct Hashe { 31 enum class Flag : uint8_t { 32 Exact, 33 Alpha, 34 Beta 35 }; 36 U64 key; 37 Move best; 38 uint8_t depth; 39 int16_t score; 40 Flag flag; 41 }; 42 43 template <U64 size> class TTable_internal { 44 public: 45 static inline constexpr const int16_t unknown = 32500; 46 47 static void clear() { 48 memset(table.data(), 0x00, size * sizeof(Hashe)); 49 #ifdef USE_STATS 50 accessed = 0, rewrite = 0, miss = 0; 51 #endif 52 }; 53 54 #ifdef USE_STATS 55 static void print() { 56 std::cout << "Transposition table: " << std::endl; 57 std::cout << "\tSize: " << size << " entries (" << sizeof(Hashe) << "B per entry)" << std::endl; 58 std::cout << "\tSize: " << std::fixed << std::setprecision(2) 59 << (double)size * sizeof(Hashe) / (1 << 20) << "MB" << std::endl; 60 std::cout << "\tReads: " << accessed << std::endl; 61 std::cout << "\tMisses: " << miss << "(" << (double)miss / accessed << "%)" << std::endl; 62 std::cout << "\tRewrite: " << rewrite << std::endl; 63 std::cout << "\tUsed " << (double)used() / size << "%" << std::endl; 64 } 65 66 static U64 used() { 67 U64 res = 0; 68 69 for (int i = 0; i < size; i++) { 70 if (table[i].key) res++; 71 } 72 73 return res; 74 } 75 #endif 76 77 static int16_t read(const Board &board, int ply, Move *best, int16_t alpha, int16_t beta, uint8_t depth) { 78 U64 hash = board.get_hash(); 79 const Hashe &phashe = table[hash % size]; 80 81 #ifdef USE_STATS 82 accessed++; 83 #endif 84 85 if (phashe.key == hash) { 86 if (phashe.depth >= depth) { 87 int16_t score = phashe.score; 88 89 if (score < -MATE_SCORE) score += ply; 90 if (score > MATE_SCORE) score -= ply; 91 92 if (phashe.flag == Hashe::Flag::Exact) return score; 93 if ((phashe.flag == Hashe::Flag::Alpha) && (score <= alpha)) return alpha; 94 if ((phashe.flag == Hashe::Flag::Beta) && (score >= beta)) return beta; 95 } 96 *best = phashe.best; 97 } 98 #ifdef USE_STATS 99 else { 100 miss++; 101 } 102 #endif 103 return unknown; 104 } 105 106 static void write(const Board &board, int ply, Move best, int16_t score, uint8_t depth, 107 Hashe::Flag flag) { 108 U64 hash = board.get_hash(); 109 Hashe &phashe = table[hash % size]; 110 111 if (score < -MATE_SCORE) score += ply; 112 if (score > MATE_SCORE) score -= ply; 113 114 if (phashe.key == hash) { 115 if (phashe.depth > depth) return; 116 } 117 #ifdef USE_STATS 118 else { 119 rewrite++; 120 } 121 #endif 122 123 phashe = {hash, best, depth, score, flag}; 124 } 125 126 private: 127 static std::array<Hashe, size> table; 128 129 #ifdef USE_STATS 130 static U64 accessed, rewrite, miss; 131 #endif 132 }; 133 134 template <U64 size> std::array<Hashe, size> TTable_internal<size>::table; 135 136 #ifdef USE_STATS 137 template <U64 size> U64 TTable_internal<size>::accessed = 0; 138 template <U64 size> U64 TTable_internal<size>::rewrite = 0; 139 template <U64 size> U64 TTable_internal<size>::miss = 0; 140 #endif 141 142 using TTable = TTable_internal<C64(0x2000023)>; 143 144 TTable ttable; 145 146 class PVTable { 147 public: 148 Move best(uint8_t ply = 0) { return table[0][ply]; } 149 150 void start(uint8_t ply) { length[ply] = ply; } 151 void store(Move move, uint8_t ply) { 152 table[ply][ply] = move; 153 for (uint8_t i = ply + 1; i < length[ply + 1]; i++) 154 table[ply][i] = table[ply + 1][i]; 155 length[ply] = length[ply + 1]; 156 } 157 158 friend std::ostream &operator<<(std::ostream &os, const PVTable &pvtable); 159 160 private: 161 Move table[MAX_PLY][MAX_PLY] = {{}}; 162 uint8_t length[MAX_PLY] = {0}; 163 }; 164 165 std::ostream &operator<<(std::ostream &os, const PVTable &pvtable) { 166 for (uint8_t i = 0; i < pvtable.length[0]; i++) 167 os << pvtable.table[0][i] << " "; 168 return os; 169 } 170 171 static const uci::Settings *settings = nullptr; 172 static Board board; 173 static repetition::Table rtable; 174 175 static PVTable pvtable; 176 177 static Move killer[2][MAX_PLY]; 178 static U32 history[12][64]; 179 static bool follow_pv; 180 static U64 nodes; 181 static uint8_t ply; 182 183 U32 inline move_score(const Move move) { 184 static constexpr const uint16_t capture[6][6] = { 185 // clang-format off 186 {105, 205, 305, 405, 505, 605}, 187 {104, 204, 304, 404, 504, 604}, 188 {103, 203, 303, 403, 503, 603}, 189 {102, 202, 302, 402, 502, 602}, 190 {101, 201, 301, 401, 501, 601}, 191 {100, 200, 300, 400, 500, 600}, 192 // clang-format on 193 }; 194 195 const Type type = board.get_square_piece_type(move.source()); 196 if (move.is_capture()) { 197 const Type captured = board.get_square_piece_type(move.target()); 198 return capture[type][captured] + 10000; 199 } 200 if (killer[0][ply] == move) return 9000; 201 if (killer[1][ply] == move) return 8000; 202 return history[piece::get_index(type, board.get_side())][move.target()]; 203 } 204 205 void move_list_sort(MoveList &list, std::vector<int> &score, int crnt) { 206 for (int i = crnt + 1; i < list.size(); i++) { 207 if (score[crnt] < score[i]) { 208 std::swap(list[crnt], list[i]); 209 std::swap(score[crnt], score[i]); 210 } 211 } 212 } 213 214 std::vector<int> move_list_score(MoveList &list, const Move best) { 215 std::vector<int> score(list.size(), 0); 216 217 bool best_found = false; 218 for (int i = 0; i < list.size(); i++) { 219 score[i] = move_score(list[i]); 220 if (list[i] == best) { 221 score[i] = 30000; 222 best_found = true; 223 } 224 } 225 226 if (best_found) return score; 227 228 if (ply && follow_pv) { 229 follow_pv = false; 230 for (int i = 0; i < list.size(); i++) { 231 if (list[i] == pvtable.best(ply)) { 232 score[i] = 20000; 233 follow_pv = true; 234 break; 235 } 236 } 237 } 238 239 return score; 240 } 241 242 int stats_move_make(Board ©, const Move move) { 243 copy = board; 244 if (!move.make(board)) { 245 board = copy; 246 return 0; 247 } 248 ply++; 249 rtable.push_hash(copy.get_hash()); 250 if (!move.is_repeatable()) rtable.push_null(); 251 return 1; 252 } 253 254 void stats_move_make_pruning(Board ©) { 255 copy = board; 256 board.switch_side(); 257 board.set_enpassant(Square::no_sq); 258 ply++; 259 } 260 261 void stats_move_unmake_pruning(Board ©) { 262 board = copy; 263 ply--; 264 } 265 266 void stats_move_unmake(Board ©, const Move move) { 267 board = copy; 268 if (!move.is_repeatable()) rtable.pop(); 269 rtable.pop(); 270 ply--; 271 } 272 273 int16_t quiescence(int16_t alpha, int16_t beta) { 274 pvtable.start(ply); 275 if ((nodes & 2047) == 0) { 276 uci::communicate(settings); 277 if (settings->stopped) return 0; 278 } 279 280 nodes++; 281 282 int score = evaluate::score_position(board); 283 if (ply > MAX_PLY - 1) return score; 284 if (score >= beta) return beta; 285 if (score > alpha) alpha = score; 286 287 Board copy; 288 MoveList list(board, true); 289 std::vector<int> listScore = move_list_score(list, Move()); 290 for (int i = 0; i < list.size(); i++) { 291 move_list_sort(list, listScore, i); 292 const Move move = list[i]; 293 if (!stats_move_make(copy, move)) continue; 294 score = -quiescence(-beta, -alpha); 295 stats_move_unmake(copy, move); 296 297 if (settings->stopped) return 0; 298 if (score > alpha) { 299 alpha = score; 300 pvtable.store(move, ply); 301 if (score >= beta) return beta; 302 } 303 } 304 305 return alpha; 306 } 307 308 int16_t negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { 309 int pv_node = (beta - alpha) > 1; 310 Hashe::Flag flag = Hashe::Flag::Alpha; 311 int futility = 0; 312 Move bestMove; 313 Board copy; 314 315 pvtable.start(ply); 316 if ((nodes & 2047) == 0) { 317 uci::communicate(settings); 318 if (settings->stopped) return 0; 319 } 320 321 // && fifty >= 100 322 if (ply && rtable.is_repetition(board.get_hash())) return 0; 323 324 int16_t score = ttable.read(board, ply, &bestMove, alpha, beta, depth); 325 if (ply && score != TTable::unknown && !pv_node) return score; 326 327 bool isCheck = board.is_check(); 328 if (isCheck) depth++; 329 330 if (depth == 0) { 331 nodes++; 332 int16_t score = quiescence(alpha, beta); 333 // ttable_write(board, ply, bestMove, score, depth, HasheFlag::Exact); 334 return score; 335 } 336 337 if (alpha < -MATE_VALUE) alpha = -MATE_VALUE; 338 if (beta > MATE_VALUE - 1) beta = MATE_VALUE - 1; 339 if (alpha >= beta) return alpha; 340 // if (ply > MAX_PLY - 1) return evaluate::score_position(board); 341 342 if (!pv_node && !isCheck) { 343 static constexpr const U32 score_pawn = score::get(PAWN); 344 int16_t staticEval = evaluate::score_position(board); 345 346 // evaluation pruning 347 if (depth < 3 && abs(beta - 1) > -MATE_VALUE + 100) { 348 int16_t marginEval = score_pawn * depth; 349 if (staticEval - marginEval >= beta) return staticEval - marginEval; 350 } 351 352 if (settings->stopped) return 0; 353 354 if (null) { 355 // null move pruning 356 if (ply && depth > 2 && staticEval >= beta) { 357 stats_move_make_pruning(copy); 358 score = -negamax(-beta, -beta + 1, depth - 1 - REDUCTION_MOVE, false); 359 stats_move_unmake_pruning(copy); 360 if (score >= beta) return beta; 361 } 362 363 // razoring 364 score = staticEval + score_pawn; 365 int16_t scoreNew = quiescence(alpha, beta); 366 367 if (score < beta && depth == 1) { 368 return (scoreNew > score) ? scoreNew : score; 369 } 370 371 score += score_pawn; 372 if (score < beta && depth < 4) { 373 if (scoreNew < beta) return (scoreNew > score) ? scoreNew : score; 374 } 375 } 376 377 // futility pruning condition 378 static constexpr const int16_t margin[] = { 379 0, 380 score::get(PAWN), 381 score::get(KNIGHT), 382 score::get(ROOK), 383 }; 384 if (depth < 4 && abs(alpha) < MATE_SCORE && staticEval + margin[depth] <= alpha) futility = 1; 385 } 386 387 uint8_t legal_moves = 0; 388 uint8_t searched = 0; 389 390 MoveList list(board); 391 std::vector<int> listScore = move_list_score(list, bestMove); 392 for (int i = 0; i < list.size(); i++) { 393 move_list_sort(list, listScore, i); 394 const Move move = list[i]; 395 if (!stats_move_make(copy, move)) continue; 396 legal_moves++; 397 398 // futility pruning 399 if (futility && searched && !move.is_capture() && !move.is_promote() && !board.is_check()) { 400 stats_move_unmake(copy, move); 401 continue; 402 } 403 404 if (!searched) { 405 score = -negamax(-beta, -alpha, depth - 1, true); 406 } else { 407 // Late Move Reduction 408 if (!pv_node && searched >= FULL_DEPTH && depth >= REDUCTION_LIMIT && !isCheck && 409 !move.is_capture() && !move.is_promote() && 410 (move.source() != killer[0][ply].source() || move.target() != killer[0][ply].target()) && 411 (move.source() != killer[1][ply].source() || move.target() != killer[1][ply].target())) { 412 score = -negamax(-alpha - 1, -alpha, depth - 2, true); 413 } else 414 score = alpha + 1; 415 416 // Principal Variation Search 417 if (score > alpha) { 418 score = -negamax(-alpha - 1, -alpha, depth - 1, true); 419 420 // if fail research 421 if ((score > alpha) && (score < beta)) score = -negamax(-beta, -alpha, depth - 1, true); 422 } 423 } 424 425 stats_move_unmake(copy, move); 426 searched++; 427 428 if (settings->stopped) return 0; 429 if (score > alpha) { 430 if (!move.is_capture()) { 431 const Type piece = board.get_square_piece_type(move.source()); 432 history[piece::get_index(piece, board.get_side())][move.target()] += depth; 433 } 434 435 alpha = score; 436 flag = Hashe::Flag::Exact; 437 bestMove = move; 438 pvtable.store(move, ply); 439 440 if (score >= beta) { 441 ttable.write(board, ply, bestMove, beta, depth, Hashe::Flag::Beta); 442 443 if (!move.is_capture()) { 444 killer[1][ply] = killer[0][ply]; 445 killer[0][ply] = move; 446 } 447 448 return beta; 449 } 450 } 451 } 452 453 if (legal_moves == 0) { 454 if (isCheck) return -MATE_VALUE + ply; 455 else 456 return 0; 457 } 458 459 ttable.write(board, ply, bestMove, alpha, depth, flag); 460 return alpha; 461 } 462 463 Move search_position(const uci::Settings &settingsr) { 464 int16_t alpha = -SCORE_INFINITY, beta = SCORE_INFINITY; 465 settings = &settingsr; 466 467 if (settings->newgame) ttable.clear(); 468 469 rtable.clear(); 470 board = settings->board; 471 for (int i = 0; i < settings->madeMoves.size(); i++) { 472 rtable.push_hash(board.get_hash()); 473 settings->madeMoves[i].make(board); 474 if (!settings->madeMoves[i].is_repeatable()) rtable.clear(); 475 } 476 477 ply = 0; 478 nodes = 0; 479 settings->stopped = false; 480 memset(killer, 0x00, sizeof(killer)); 481 memset(history, 0x00, sizeof(history)); 482 rtable = repetition::Table(); 483 484 Move lastBest; 485 486 uint64_t time_last = timer::get_ms(); 487 uint8_t max_depth = settings->depth ? settings->depth : MAX_PLY; 488 for (uint8_t depth = 1; depth <= max_depth; depth++) { 489 lastBest = pvtable.best(); 490 follow_pv = true; 491 int16_t score = negamax(alpha, beta, depth, true); 492 493 uci::communicate(settings); 494 if (settings->stopped) break; 495 496 if ((score <= alpha) || (score >= beta)) { 497 alpha = -SCORE_INFINITY; 498 beta = SCORE_INFINITY; 499 depth--; 500 continue; 501 } 502 503 alpha = score - WINDOW; 504 beta = score + WINDOW; 505 506 uint8_t mate_ply = 0xFF; 507 if (score > -MATE_VALUE && score < -MATE_SCORE) { 508 mate_ply = (score + MATE_VALUE) / 2 + 1; 509 std::cout << "info score mate -" << (int)mate_ply; 510 } else if (score > MATE_SCORE && score < MATE_VALUE) { 511 mate_ply = (MATE_VALUE - score) / 2 + 1; 512 std::cout << "info score mate " << (int)mate_ply; 513 } else { 514 std::cout << "info score cp " << score; 515 } 516 517 std::cout << " depth " << (unsigned)depth; 518 std::cout << " nodes " << nodes; 519 std::cout << " time " << timer::get_ms() - settings->starttime; 520 std::cout << " pv " << pvtable << std::endl; 521 522 if (depth >= mate_ply) break; 523 524 uint64_t time_crnt = timer::get_ms(); 525 if (!settings->depth && 2 * time_crnt - time_last > settings->stoptime) break; 526 time_last = time_crnt; 527 } 528 529 settings->board = board; 530 return !settings->stopped ? pvtable.best() : lastBest; 531 } 532 } // namespace engine 533 534 int main() { 535 attack::init(); 536 zobrist::init(); 537 uci::loop(); 538 #ifdef USE_STATS 539 engine::ttable.print(); 540 #endif 541 return 0; 542 }