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_list_score(Move move) {

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

120 if (move.is_capture()) {

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

122 return score::get(type, captured) + 10000;

123 }

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

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

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

127 }

128

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

130 static std::vector<int> score(256);

131

132 bool best_found = false;

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

134 score[i] = move_list_score(list[i]);

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

136 score[i] = 30000;

137 best_found = true;

138 }

139 }

140

141 if (!best_found && ply && follow_pv) {

142 follow_pv = false;

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

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

145 score[i] = 20000;

146 follow_pv = true;

147 break;

148 }

149 }

150 }

151

152 std::vector<int> index(list.size());

153 std::iota(begin(index), end(index), 0);

154 sort(begin(index), end(index), [&](int a, int b) { return score[a] > score[b]; });

155 return index;

156 }

157

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

159 copy = board;

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

161 board = copy;

162 return 0;

163 }

164 ply++;

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

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

167 return 1;

168 }

169

170 void stats_move_make_pruning(Board &copy) {

171 copy = board;

172 board.switch_side();

173 board.set_enpassant(square::no_sq);

174 ply++;

175 }

176

177 void stats_move_unmake_pruning(Board &copy) {

178 board = copy;

179 ply--;

180 }

181

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

183 board = copy;

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

185 rtable.pop();

186 ply--;

187 }

188

189 int16_t quiescence(int16_t alpha, int16_t beta) {

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

191 uci::communicate(settings);

192 if (settings->stopped) return 0;

193 }

194 pvtable.start(ply);

195 nodes++;

196

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

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

199 if (score >= beta) return beta;

200 if (score > alpha) alpha = score;

201

202 Board copy;

203 MoveList list(board, true);

204 for (int idx : move_list_sort(list, Move())) {

205 const Move move = list[idx];

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

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

208 stats_move_unmake(copy, move);

209

210 if (score > alpha) {

211 alpha = score;

212 pvtable.store(move, ply);

213 if (score >= beta) return beta;

214 }

215

216 if (settings->stopped) return 0;

217 }

218

219 return alpha;

220 }

221

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

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

224 Hashe::Flag flag = Hashe::Flag::Alpha;

225 int futility = 0;

226 Move bestMove;

227 Board copy;

228

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

230 uci::communicate(settings);

231 if (settings->stopped) return 0;

232 }

233 pvtable.start(ply);

234

235 // && fifty >= 100

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

237

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

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

240

241 bool isCheck = board.is_check();

242 if (isCheck) depth++;

243

244 if (depth == 0) {

245 nodes++;

246 int16_t score = quiescence(alpha, beta);

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

248 return score;

249 }

250

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

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

253 if (alpha >= beta) return alpha;

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

255

256 if (!pv_node && !isCheck) {

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

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

259

260 // evaluation pruning

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

262 int16_t marginEval = score_pawn * depth;

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

264 }

265

266 if (settings->stopped) return 0;

267

268 if (null) {

269 // null move pruning

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

271 stats_move_make_pruning(copy);

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

273 stats_move_unmake_pruning(copy);

274 if (score >= beta) return beta;

275 }

276

277 // razoring

278 score = staticEval + score_pawn;

279 int16_t scoreNew = quiescence(alpha, beta);

280

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

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

283 }

284

285 score += score_pawn;

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

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

288 }

289 }

290

291 // futility pruning condition

292 static constexpr const int16_t margin[] = {

293 0,

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

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

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

297 };

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

299 }

300

301 uint8_t legal_moves = 0;

302 uint8_t searched = 0;

303

304 MoveList list(board);

305 for (int idx : move_list_sort(list, bestMove)) {

306 const Move move = list[idx];

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

308 legal_moves++;

309

310 // futility pruning

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

312 stats_move_unmake(copy, move);

313 continue;

314 }

315

316 if (!searched) {

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

318 } else {

319 // Late Move Reduction

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

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

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

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

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

325 } else

326 score = alpha + 1;

327

328 // Principal Variation Search

329 if (score > alpha) {

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

331

332 // if fail research

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

334 }

335 }

336

337 stats_move_unmake(copy, move);

338 searched++;

339

340 if (settings->stopped) return 0;

341 if (score > alpha) {

342 if (!move.is_capture()) {

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

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

345 }

346

347 alpha = score;

348 flag = Hashe::Flag::Exact;

349 bestMove = move;

350 pvtable.store(move, ply);

351

352 if (score >= beta) {

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

354

355 if (!move.is_capture()) {

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

357 killer[0][ply] = move;

358 }

359

360 return beta;

361 }

362 }

363 }

364

365 if (legal_moves == 0) {

366 if (isCheck) return -MATE_VALUE + ply;

367 else

368 return 0;

369 }

370

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

372 return alpha;

373 }

374

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

376 int16_t alpha = -SCORE_INFINITY, beta = SCORE_INFINITY;

377 settings = &settingsr;

378

379 if (settings->newgame) {

380 ttable = TTable(C64(0x1000000));

381 }

382

383 rtable.clear();

384 board = settings->board;

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

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

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

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

389 }

390

391 ply = 0;

392 nodes = 0;

393 settings->stopped = false;

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

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

396 rtable = repetition::Table();

397

398 Move lastBest;

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

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

401 lastBest = pvtable.best();

402 follow_pv = 1;

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

404

405 uci::communicate(settings);

406 if (settings->stopped) break;

407

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

409 alpha = -SCORE_INFINITY;

410 beta = SCORE_INFINITY;

411 depth--;

412 continue;

413 }

414

415 alpha = score - WINDOW;

416 beta = score + WINDOW;

417

418 uint8_t mate_ply = 0xFF;

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

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

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

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

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

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

425 } else {

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

427 }

428

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

430 std::cout << " nodes " << nodes;

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

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

433

434 if (depth >= mate_ply) break;

435 }

436

437 settings->board = board;

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

439 }

440 } // namespace engine

441

442 int main(void) {

443 uci::loop();

444 return 0;

445 }