stellarUCI Chess engine written in C++20 |
| git clone git://git.dimitrijedobrota.com/stellar.git |
| Log | Files | Refs | README | LICENSE | |
engine.cpp (13887B)
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_score(const Move move) { 120 static constexpr const uint16_t capture[6][6] = { 121 // clang-format off 122 {105, 205, 305, 405, 505, 605}, 123 {104, 204, 304, 404, 504, 604}, 124 {103, 203, 303, 403, 503, 603}, 125 {102, 202, 302, 402, 502, 602}, 126 {101, 201, 301, 401, 501, 601}, 127 {100, 200, 300, 400, 500, 600}, 128 // clang-format on 129 }; 130 131 const piece::Type type = board.get_square_piece_type(move.source()); 132 if (move.is_capture()) { 133 const piece::Type captured = board.get_square_piece_type(move.target()); 134 return capture[to_underlying(type)][to_underlying(captured)] + 10000; 135 } 136 if (killer[0][ply] == move) return 9000; 137 if (killer[1][ply] == move) return 8000; 138 return history[piece::get_index(type, board.get_side())][to_underlying(move.target())]; 139 } 140 141 void move_list_sort(MoveList &list, std::vector<int> &score, int crnt) { 142 for (int i = crnt + 1; i < list.size(); i++) { 143 if (score[crnt] < score[i]) { 144 std::swap(list[crnt], list[i]); 145 std::swap(score[crnt], score[i]); 146 } 147 } 148 } 149 150 std::vector<int> move_list_score(MoveList &list, const Move best) { 151 std::vector<int> score(list.size(), 0); 152 153 bool best_found = false; 154 for (int i = 0; i < list.size(); i++) { 155 score[i] = move_score(list[i]); 156 if (list[i] == best) { 157 score[i] = 30000; 158 best_found = true; 159 } 160 } 161 162 if (best_found) return score; 163 164 if (ply && follow_pv) { 165 follow_pv = false; 166 for (int i = 0; i < list.size(); i++) { 167 if (list[i] == pvtable.best(ply)) { 168 score[i] = 20000; 169 follow_pv = true; 170 break; 171 } 172 } 173 } 174 175 return score; 176 } 177 178 int stats_move_make(Board ©, const Move move) { 179 copy = board; 180 if (!move.make(board)) { 181 board = copy; 182 return 0; 183 } 184 ply++; 185 rtable.push_hash(copy.get_hash()); 186 if (!move.is_repeatable()) rtable.push_null(); 187 return 1; 188 } 189 190 void stats_move_make_pruning(Board ©) { 191 copy = board; 192 board.switch_side(); 193 board.set_enpassant(square::no_sq); 194 ply++; 195 } 196 197 void stats_move_unmake_pruning(Board ©) { 198 board = copy; 199 ply--; 200 } 201 202 void stats_move_unmake(Board ©, const Move move) { 203 board = copy; 204 if (!move.is_repeatable()) rtable.pop(); 205 rtable.pop(); 206 ply--; 207 } 208 209 int16_t quiescence(int16_t alpha, int16_t beta) { 210 pvtable.start(ply); 211 if ((nodes & 2047) == 0) { 212 uci::communicate(settings); 213 if (settings->stopped) return 0; 214 } 215 nodes++; 216 217 int score = evaluate::score_position(board); 218 if (ply > MAX_PLY - 1) return score; 219 if (score >= beta) return beta; 220 if (score > alpha) alpha = score; 221 222 Board copy; 223 MoveList list(board, true); 224 std::vector<int> listScore = move_list_score(list, Move()); 225 for (int i = 0; i < list.size(); i++) { 226 move_list_sort(list, listScore, i); 227 const Move move = list[i]; 228 if (!stats_move_make(copy, move)) continue; 229 score = -quiescence(-beta, -alpha); 230 stats_move_unmake(copy, move); 231 232 if (settings->stopped) return 0; 233 if (score > alpha) { 234 alpha = score; 235 pvtable.store(move, ply); 236 if (score >= beta) return beta; 237 } 238 } 239 240 return alpha; 241 } 242 243 int16_t negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { 244 int pv_node = (beta - alpha) > 1; 245 Hashe::Flag flag = Hashe::Flag::Alpha; 246 int futility = 0; 247 Move bestMove; 248 Board copy; 249 250 pvtable.start(ply); 251 if ((nodes & 2047) == 0) { 252 uci::communicate(settings); 253 if (settings->stopped) return 0; 254 } 255 256 // && fifty >= 100 257 if (ply && rtable.is_repetition(board.get_hash())) return 0; 258 259 int16_t score = ttable.read(board, ply, &bestMove, alpha, beta, depth); 260 if (ply && score != TTable::unknown && !pv_node) return score; 261 262 bool isCheck = board.is_check(); 263 if (isCheck) depth++; 264 265 if (depth == 0) { 266 nodes++; 267 int16_t score = quiescence(alpha, beta); 268 // ttable_write(board, ply, bestMove, score, depth, HasheFlag::Exact); 269 return score; 270 } 271 272 if (alpha < -MATE_VALUE) alpha = -MATE_VALUE; 273 if (beta > MATE_VALUE - 1) beta = MATE_VALUE - 1; 274 if (alpha >= beta) return alpha; 275 // if (ply > MAX_PLY - 1) return evaluate::score_position(board); 276 277 if (!pv_node && !isCheck) { 278 static constexpr const U32 score_pawn = score::get(piece::Type::PAWN); 279 int16_t staticEval = evaluate::score_position(board); 280 281 // evaluation pruning 282 if (depth < 3 && abs(beta - 1) > -MATE_VALUE + 100) { 283 int16_t marginEval = score_pawn * depth; 284 if (staticEval - marginEval >= beta) return staticEval - marginEval; 285 } 286 287 if (settings->stopped) return 0; 288 289 if (null) { 290 // null move pruning 291 if (ply && depth > 2 && staticEval >= beta) { 292 stats_move_make_pruning(copy); 293 score = -negamax(-beta, -beta + 1, depth - 1 - REDUCTION_MOVE, false); 294 stats_move_unmake_pruning(copy); 295 if (score >= beta) return beta; 296 } 297 298 // razoring 299 score = staticEval + score_pawn; 300 int16_t scoreNew = quiescence(alpha, beta); 301 302 if (score < beta && depth == 1) { 303 return (scoreNew > score) ? scoreNew : score; 304 } 305 306 score += score_pawn; 307 if (score < beta && depth < 4) { 308 if (scoreNew < beta) return (scoreNew > score) ? scoreNew : score; 309 } 310 } 311 312 // futility pruning condition 313 static constexpr const int16_t margin[] = { 314 0, 315 score::get(piece::Type::PAWN), 316 score::get(piece::Type::KNIGHT), 317 score::get(piece::Type::ROOK), 318 }; 319 if (depth < 4 && abs(alpha) < MATE_SCORE && staticEval + margin[depth] <= alpha) futility = 1; 320 } 321 322 uint8_t legal_moves = 0; 323 uint8_t searched = 0; 324 325 MoveList list(board); 326 std::vector<int> listScore = move_list_score(list, bestMove); 327 for (int i = 0; i < list.size(); i++) { 328 move_list_sort(list, listScore, i); 329 const Move move = list[i]; 330 if (!stats_move_make(copy, move)) continue; 331 legal_moves++; 332 333 // futility pruning 334 if (futility && searched && !move.is_capture() && !move.is_promote() && !board.is_check()) { 335 stats_move_unmake(copy, move); 336 continue; 337 } 338 339 if (!searched) { 340 score = -negamax(-beta, -alpha, depth - 1, true); 341 } else { 342 // Late Move Reduction 343 if (!pv_node && searched >= FULL_DEPTH && depth >= REDUCTION_LIMIT && !isCheck && 344 !move.is_capture() && !move.is_promote() && 345 (move.source() != killer[0][ply].source() || move.target() != killer[0][ply].target()) && 346 (move.source() != killer[1][ply].source() || move.target() != killer[1][ply].target())) { 347 score = -negamax(-alpha - 1, -alpha, depth - 2, true); 348 } else 349 score = alpha + 1; 350 351 // Principal Variation Search 352 if (score > alpha) { 353 score = -negamax(-alpha - 1, -alpha, depth - 1, true); 354 355 // if fail research 356 if ((score > alpha) && (score < beta)) score = -negamax(-beta, -alpha, depth - 1, true); 357 } 358 } 359 360 stats_move_unmake(copy, move); 361 searched++; 362 363 if (settings->stopped) return 0; 364 if (score > alpha) { 365 if (!move.is_capture()) { 366 const piece::Type piece = board.get_square_piece_type(move.source()); 367 history[piece::get_index(piece, board.get_side())][to_underlying(move.target())] += depth; 368 } 369 370 alpha = score; 371 flag = Hashe::Flag::Exact; 372 bestMove = move; 373 pvtable.store(move, ply); 374 375 if (score >= beta) { 376 ttable.write(board, ply, bestMove, beta, depth, Hashe::Flag::Beta); 377 378 if (!move.is_capture()) { 379 killer[1][ply] = killer[0][ply]; 380 killer[0][ply] = move; 381 } 382 383 return beta; 384 } 385 } 386 } 387 388 if (legal_moves == 0) { 389 if (isCheck) return -MATE_VALUE + ply; 390 else 391 return 0; 392 } 393 394 ttable.write(board, ply, bestMove, alpha, depth, flag); 395 return alpha; 396 } 397 398 Move search_position(const uci::Settings &settingsr) { 399 int16_t alpha = -SCORE_INFINITY, beta = SCORE_INFINITY; 400 settings = &settingsr; 401 402 if (settings->newgame) { 403 ttable = TTable(C64(0x2FB4377)); 404 } 405 406 rtable.clear(); 407 board = settings->board; 408 for (int i = 0; i < settings->madeMoves.size(); i++) { 409 rtable.push_hash(board.get_hash()); 410 settings->madeMoves[i].make(board); 411 if (!settings->madeMoves[i].is_repeatable()) rtable.clear(); 412 } 413 414 ply = 0; 415 nodes = 0; 416 settings->stopped = false; 417 memset(killer, 0x00, sizeof(killer)); 418 memset(history, 0x00, sizeof(history)); 419 rtable = repetition::Table(); 420 421 Move lastBest; 422 423 uint64_t time_last = timer::get_ms(); 424 uint8_t max_depth = settings->depth ? settings->depth : MAX_PLY; 425 for (uint8_t depth = 1; depth <= max_depth; depth++) { 426 lastBest = pvtable.best(); 427 follow_pv = 1; 428 int16_t score = negamax(alpha, beta, depth, true); 429 430 uci::communicate(settings); 431 if (settings->stopped) break; 432 433 if ((score <= alpha) || (score >= beta)) { 434 alpha = -SCORE_INFINITY; 435 beta = SCORE_INFINITY; 436 depth--; 437 continue; 438 } 439 440 alpha = score - WINDOW; 441 beta = score + WINDOW; 442 443 uint8_t mate_ply = 0xFF; 444 if (score > -MATE_VALUE && score < -MATE_SCORE) { 445 mate_ply = (score + MATE_VALUE) / 2 + 1; 446 std::cout << "info score mate -" << (int)mate_ply; 447 } else if (score > MATE_SCORE && score < MATE_VALUE) { 448 mate_ply = (MATE_VALUE - score) / 2 + 1; 449 std::cout << "info score mate " << (int)mate_ply; 450 } else { 451 std::cout << "info score cp " << score; 452 } 453 454 std::cout << " depth " << (unsigned)depth; 455 std::cout << " nodes " << nodes; 456 std::cout << " time " << timer::get_ms() - settings->starttime; 457 std::cout << " pv " << pvtable << std::endl; 458 459 if (depth >= mate_ply) break; 460 461 uint64_t time_crnt = timer::get_ms(); 462 if (!settings->depth && 2 * time_crnt - time_last > settings->stoptime) break; 463 time_last = time_crnt; 464 } 465 466 settings->board = board; 467 return !settings->stopped ? pvtable.best() : lastBest; 468 } 469 } // namespace engine 470 471 int main(void) { 472 uci::loop(); 473 return 0; 474 }