stellar

0 #include <algorithm>

1 #include <ctype.h>

2 #include <stdio.h>

3 #include <stdlib.h>

4 #include <string.h>

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 #define FULL_DEPTH 4

19 #define REDUCTION_LIMIT 3

20 #define REDUCTION_MOVE 2

21

22 #define WINDOW 50

23

24 namespace engine {

25

26 struct Hashe {

27 enum class Flag : uint8_t {

28 Exact,

29 Alpha,

30 Beta

31 };

32 U64 key;

33 Move best;

34 uint8_t depth;

35 int16_t score;

36 Flag flag;

37 };

38

39 class TTable {

40 public:

41 static inline constexpr const int16_t unknown = 32500;

42

43 TTable() {}

44 TTable(U64 size) : table(size, {0}) {}

45

46 void clear() { table.clear(); };

47 int16_t read(const Board &board, int ply, Move *best, int16_t alpha, int16_t beta, uint8_t depth) const {

48 U64 hash = board.get_hash();

49 const Hashe &phashe = table[hash % table.size()];

50 if (phashe.key == hash) {

51 if (phashe.depth >= depth) {

52 int16_t score = phashe.score;

53

54 if (score < -MATE_SCORE) score += ply;

55 if (score > MATE_SCORE) score -= ply;

56

57 if (phashe.flag == Hashe::Flag::Exact) return score;

58 if ((phashe.flag == Hashe::Flag::Alpha) && (score <= alpha)) return alpha;

59 if ((phashe.flag == Hashe::Flag::Beta) && (score >= beta)) return beta;

60 }

61 *best = phashe.best;

62 }

63 return unknown;

64 }

65

66 void write(const Board &board, int ply, Move best, int16_t score, uint8_t depth, Hashe::Flag flag) {

67 U64 hash = board.get_hash();

68 Hashe &phashe = table[hash % table.size()];

69

70 if (score < -MATE_SCORE) score += ply;

71 if (score > MATE_SCORE) score -= ply;

72

73 phashe = {hash, best, depth, score, flag};

74 }

75

76 private:

77 std::vector<Hashe> table;

78 };

79

80 class PVTable {

81 public:

82 Move best(uint8_t ply = 0) { return table[0][ply]; }

83

84 void start(uint8_t ply) { length[ply] = ply; }

85 void store(Move move, uint8_t ply) {

86 table[ply][ply] = move;

87 for (uint8_t i = ply + 1; i < length[ply + 1]; i++)

88 table[ply][i] = table[ply + 1][i];

89 length[ply] = length[ply + 1];

90 }

91

92 friend std::ostream &operator<<(std::ostream &os, const PVTable &pvtable);

93

94 private:

95 Move table[MAX_PLY][MAX_PLY] = {{}};

96 uint8_t length[MAX_PLY] = {0};

97 };

98

99 std::ostream &operator<<(std::ostream &os, const PVTable &pvtable) {

100 for (uint8_t i = 0; i < pvtable.length[0]; i++)

101 os << pvtable.table[0][i] << " ";

102 return os;

103 }

104

105 static const uci::Settings *settings = nullptr;

106 static Board board;

107 static TTable ttable;

108 static repetition::Table rtable;

109

110 static PVTable pvtable;

111

112 static Move killer[2][MAX_PLY];

113 static U32 history[12][64];

114 static bool follow_pv;

115 static U64 nodes;

116 static uint8_t ply;

117

118 U32 inline move_score(const Move move) {

119 static constexpr const uint16_t capture[6][6] = {

120 // clang-format off

121 {105, 205, 305, 405, 505, 605},

122 {104, 204, 304, 404, 504, 604},

123 {103, 203, 303, 403, 503, 603},

124 {102, 202, 302, 402, 502, 602},

125 {101, 201, 301, 401, 501, 601},

126 {100, 200, 300, 400, 500, 600},

127 // clang-format on

128 };

129

130 const piece::Type type = board.get_square_piece_type(move.source());

131 if (move.is_capture()) {

132 const piece::Type captured = board.get_square_piece_type(move.target());

133 return capture[to_underlying(type)][to_underlying(captured)] + 10000;

134 }

135 if (killer[0][ply] == move) return 9000;

136 if (killer[1][ply] == move) return 8000;

137 return history[piece::get_index(type, board.get_side())][to_underlying(move.target())];

138 }

139

140 void move_list_sort(MoveList &list, std::vector<int> &score, int crnt) {

141 for (int i = crnt + 1; i < list.size(); i++) {

142 if (score[crnt] < score[i]) {

143 std::swap(list[crnt], list[i]);

144 std::swap(score[crnt], score[i]);

145 }

146 }

147 }

148

149 std::vector<int> move_list_score(MoveList &list, const Move best) {

150 std::vector<int> score(list.size(), 0);

151

152 bool best_found = false;

153 for (int i = 0; i < list.size(); i++) {

154 score[i] = move_score(list[i]);

155 if (list[i] == best) {

156 score[i] = 30000;

157 best_found = true;

158 }

159 }

160

161 if (best_found) return score;

162

163 if (ply && follow_pv) {

164 follow_pv = false;

165 for (int i = 0; i < list.size(); i++) {

166 if (list[i] == pvtable.best(ply)) {

167 score[i] = 20000;

168 follow_pv = true;

169 break;

170 }

171 }

172 }

173

174 return score;

175 }

176

177 int stats_move_make(Board &copy, const Move move) {

178 copy = board;

179 if (!move.make(board)) {

180 board = copy;

181 return 0;

182 }

183 ply++;

184 rtable.push_hash(copy.get_hash());

185 if (!move.is_repeatable()) rtable.push_null();

186 return 1;

187 }

188

189 void stats_move_make_pruning(Board &copy) {

190 copy = board;

191 board.switch_side();

192 board.set_enpassant(square::no_sq);

193 ply++;

194 }

195

196 void stats_move_unmake_pruning(Board &copy) {

197 board = copy;

198 ply--;

199 }

200

201 void stats_move_unmake(Board &copy, const Move move) {

202 board = copy;

203 if (!move.is_repeatable()) rtable.pop();

204 rtable.pop();

205 ply--;

206 }

207

208 int16_t quiescence(int16_t alpha, int16_t beta) {

209 pvtable.start(ply);

210 if ((nodes & 2047) == 0) {

211 uci::communicate(settings);

212 if (settings->stopped) return 0;

213 }

214 nodes++;

215

216 int score = evaluate::score_position(board);

217 if (ply > MAX_PLY - 1) return score;

218 if (score >= beta) return beta;

219 if (score > alpha) alpha = score;

220

221 Board copy;

222 MoveList list(board, true);

223 std::vector<int> listScore = move_list_score(list, Move());

224 for (int i = 0; i < list.size(); i++) {

225 move_list_sort(list, listScore, i);

226 const Move move = list[i];

227 if (!stats_move_make(copy, move)) continue;

228 score = -quiescence(-beta, -alpha);

229 stats_move_unmake(copy, move);

230

231 if (settings->stopped) return 0;

232 if (score > alpha) {

233 alpha = score;

234 pvtable.store(move, ply);

235 if (score >= beta) return beta;

236 }

237 }

238

239 return alpha;

240 }

241

242 int16_t negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {

243 int pv_node = (beta - alpha) > 1;

244 Hashe::Flag flag = Hashe::Flag::Alpha;

245 int futility = 0;

246 Move bestMove;

247 Board copy;

248

249 pvtable.start(ply);

250 if ((nodes & 2047) == 0) {

251 uci::communicate(settings);

252 if (settings->stopped) return 0;

253 }

254

255 // && fifty >= 100

256 if (ply && rtable.is_repetition(board.get_hash())) return 0;

257

258 int16_t score = ttable.read(board, ply, &bestMove, alpha, beta, depth);

259 if (ply && score != TTable::unknown && !pv_node) return score;

260

261 bool isCheck = board.is_check();

262 if (isCheck) depth++;

263

264 if (depth == 0) {

265 nodes++;

266 int16_t score = quiescence(alpha, beta);

267 // ttable_write(board, ply, bestMove, score, depth, HasheFlag::Exact);

268 return score;

269 }

270

271 if (alpha < -MATE_VALUE) alpha = -MATE_VALUE;

272 if (beta > MATE_VALUE - 1) beta = MATE_VALUE - 1;

273 if (alpha >= beta) return alpha;

274 // if (ply > MAX_PLY - 1) return evaluate::score_position(board);

275

276 if (!pv_node && !isCheck) {

277 static constexpr const U32 score_pawn = score::get(piece::Type::PAWN);

278 int16_t staticEval = evaluate::score_position(board);

279

280 // evaluation pruning

281 if (depth < 3 && abs(beta - 1) > -MATE_VALUE + 100) {

282 int16_t marginEval = score_pawn * depth;

283 if (staticEval - marginEval >= beta) return staticEval - marginEval;

284 }

285

286 if (settings->stopped) return 0;

287

288 if (null) {

289 // null move pruning

290 if (ply && depth > 2 && staticEval >= beta) {

291 stats_move_make_pruning(copy);

292 score = -negamax(-beta, -beta + 1, depth - 1 - REDUCTION_MOVE, false);

293 stats_move_unmake_pruning(copy);

294 if (score >= beta) return beta;

295 }

296

297 // razoring

298 score = staticEval + score_pawn;

299 int16_t scoreNew = quiescence(alpha, beta);

300

301 if (score < beta && depth == 1) {

302 return (scoreNew > score) ? scoreNew : score;

303 }

304

305 score += score_pawn;

306 if (score < beta && depth < 4) {

307 if (scoreNew < beta) return (scoreNew > score) ? scoreNew : score;

308 }

309 }

310

311 // futility pruning condition

312 static constexpr const int16_t margin[] = {

313 0,

314 score::get(piece::Type::PAWN),

315 score::get(piece::Type::KNIGHT),

316 score::get(piece::Type::ROOK),

317 };

318 if (depth < 4 && abs(alpha) < MATE_SCORE && staticEval + margin[depth] <= alpha) futility = 1;

319 }

320

321 uint8_t legal_moves = 0;

322 uint8_t searched = 0;

323

324 MoveList list(board);

325 std::vector<int> listScore = move_list_score(list, bestMove);

326 for (int i = 0; i < list.size(); i++) {

327 move_list_sort(list, listScore, i);

328 const Move move = list[i];

329 if (!stats_move_make(copy, move)) continue;

330 legal_moves++;

331

332 // futility pruning

333 if (futility && searched && !move.is_capture() && !move.is_promote() && !board.is_check()) {

334 stats_move_unmake(copy, move);

335 continue;

336 }

337

338 if (!searched) {

339 score = -negamax(-beta, -alpha, depth - 1, true);

340 } else {

341 // Late Move Reduction

342 if (!pv_node && searched >= FULL_DEPTH && depth >= REDUCTION_LIMIT && !isCheck &&

343 !move.is_capture() && !move.is_promote() &&

344 (move.source() != killer[0][ply].source() || move.target() != killer[0][ply].target()) &&

345 (move.source() != killer[1][ply].source() || move.target() != killer[1][ply].target())) {

346 score = -negamax(-alpha - 1, -alpha, depth - 2, true);

347 } else

348 score = alpha + 1;

349

350 // Principal Variation Search

351 if (score > alpha) {

352 score = -negamax(-alpha - 1, -alpha, depth - 1, true);

353

354 // if fail research

355 if ((score > alpha) && (score < beta)) score = -negamax(-beta, -alpha, depth - 1, true);

356 }

357 }

358

359 stats_move_unmake(copy, move);

360 searched++;

361

362 if (settings->stopped) return 0;

363 if (score > alpha) {

364 if (!move.is_capture()) {

365 const piece::Type piece = board.get_square_piece_type(move.source());

366 history[piece::get_index(piece, board.get_side())][to_underlying(move.target())] += depth;

367 }

368

369 alpha = score;

370 flag = Hashe::Flag::Exact;

371 bestMove = move;

372 pvtable.store(move, ply);

373

374 if (score >= beta) {

375 ttable.write(board, ply, bestMove, beta, depth, Hashe::Flag::Beta);

376

377 if (!move.is_capture()) {

378 killer[1][ply] = killer[0][ply];

379 killer[0][ply] = move;

380 }

381

382 return beta;

383 }

384 }

385 }

386

387 if (legal_moves == 0) {

388 if (isCheck) return -MATE_VALUE + ply;

389 else

390 return 0;

391 }

392

393 ttable.write(board, ply, bestMove, alpha, depth, flag);

394 return alpha;

395 }

396

397 Move search_position(const uci::Settings &settingsr) {

398 int16_t alpha = -SCORE_INFINITY, beta = SCORE_INFINITY;

399 settings = &settingsr;

400

401 if (settings->newgame) {

402 ttable = TTable(C64(0x2FB4377));

403 }

404

405 rtable.clear();

406 board = settings->board;

407 for (int i = 0; i < settings->madeMoves.size(); i++) {

408 rtable.push_hash(board.get_hash());

409 settings->madeMoves[i].make(board);

410 if (!settings->madeMoves[i].is_repeatable()) rtable.clear();

411 }

412

413 ply = 0;

414 nodes = 0;

415 settings->stopped = false;

416 memset(killer, 0x00, sizeof(killer));

417 memset(history, 0x00, sizeof(history));

418 rtable = repetition::Table();

419

420 Move lastBest;

421

422 uint64_t time_last = timer::get_ms();

423 uint8_t max_depth = settings->depth ? settings->depth : MAX_PLY;

424 for (uint8_t depth = 1; depth <= max_depth; depth++) {

425 lastBest = pvtable.best();

426 follow_pv = 1;

427 int16_t score = negamax(alpha, beta, depth, true);

428

429 uci::communicate(settings);

430 if (settings->stopped) break;

431

432 if ((score <= alpha) || (score >= beta)) {

433 alpha = -SCORE_INFINITY;

434 beta = SCORE_INFINITY;

435 depth--;

436 continue;

437 }

438

439 alpha = score - WINDOW;

440 beta = score + WINDOW;

441

442 uint8_t mate_ply = 0xFF;

443 if (score > -MATE_VALUE && score < -MATE_SCORE) {

444 mate_ply = (score + MATE_VALUE) / 2 + 1;

445 std::cout << "info score mate -" << (int)mate_ply;

446 } else if (score > MATE_SCORE && score < MATE_VALUE) {

447 mate_ply = (MATE_VALUE - score) / 2 + 1;

448 std::cout << "info score mate " << (int)mate_ply;

449 } else {

450 std::cout << "info score cp " << score;

451 }

452

453 std::cout << " depth " << (unsigned)depth;

454 std::cout << " nodes " << nodes;

455 std::cout << " time " << timer::get_ms() - settings->starttime;

456 std::cout << " pv " << pvtable << std::endl;

457

458 if (depth >= mate_ply) break;

459

460 uint64_t time_crnt = timer::get_ms();

461 if (!settings->depth && 2 * time_crnt - time_last > settings->stoptime) break;

462 time_last = time_crnt;

463 }

464

465 settings->board = board;

466 return !settings->stopped ? pvtable.best() : lastBest;

467 }

468 } // namespace engine

469

470 int main(void) {

471 uci::loop();

472 return 0;

473 }