stellar

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 &copy, 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 &copy) {

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 &copy) {

262 board = copy;

263 ply--;

264 }

265

266 void stats_move_unmake(Board &copy, 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 }