commit b3231023f2f855d0f1b27d7e834bba800bb6da5a
parent 66c57a8231fc90d5e7a02763af8b5388968b3836
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 14 Aug 2023 14:53:10 +0200
Rework sorting as a list of indexes
Diffstat:
7 files changed, 71 insertions(+), 82 deletions(-)
diff --git a/src/engine/engine.cpp b/src/engine/engine.cpp
@@ -38,33 +38,32 @@ U32 inline move_list_score(Move move) {
return history[to_underlying(type)][to_underlying(move.target())];
}
-void move_list_sort(MoveList &list, bool check_best = true) {
- for (auto &[move, score] : list)
- score = move_list_score(move);
+void move_list_sort(MoveList &list, std::vector<int> &index, bool bestCheck = true) {
+ static std::vector<int> score(256);
bool best = false;
- if (check_best) {
- for (auto &[move, score] : list) {
- if (move == move_list_best_move) {
- score = 30000;
- best = true;
- break;
- }
+ for (int i = 0; i < list.size(); i++) {
+ score[i] = move_list_score(list[i]);
+ index[i] = i;
+ if (bestCheck && list[i] == move_list_best_move) {
+ score[i] = 30000;
+ bestCheck = false;
+ best = true;
}
}
if (!best && ply && follow_pv) {
follow_pv = false;
- for (auto &[move, score] : list) {
- if (move == pv_table[0][ply]) {
- score = 20000;
+ for (int i = 0; i < list.size(); i++) {
+ if (list[i] == pv_table[0][ply]) {
+ score[i] = 20000;
follow_pv = true;
break;
}
}
}
- sort(list.begin(), list.end());
+ sort(index.begin(), index.begin() + list.size(), [&](int a, int b) { return score[a] > score[b]; });
}
int evaluate(const Board &board) {
@@ -136,15 +135,16 @@ int quiescence(int alpha, int beta) {
Board copy;
MoveList list(board);
- move_list_sort(list, false);
- for (const auto [move, _] : list) {
- if (!stats_move_make(copy, move, 1)) continue;
+ std::vector<int> index(list.size());
+ move_list_sort(list, index, false);
+ for (int idx : index) {
+ if (!stats_move_make(copy, list[idx], 1)) continue;
score = -quiescence(-beta, -alpha);
stats_move_unmake(copy);
if (score > alpha) {
alpha = score;
- stats_pv_store(move);
+ stats_pv_store(list[idx]);
if (score >= beta) return beta;
}
}
@@ -229,8 +229,10 @@ int negamax(int alpha, int beta, int depth, bool null) {
move_list_best_move = bestMove;
MoveList list(board);
- move_list_sort(list);
- for (const auto [move, _] : list) {
+ std::vector<int> index(list.size());
+ move_list_sort(list, index);
+ for (int idx : index) {
+ const Move move = list[idx];
if (!stats_move_make(copy, move, 0)) continue;
legal_moves++;
@@ -406,7 +408,9 @@ Move parse_move(char *move_string) {
Square source = square_from_coordinates(move_string);
Square target = square_from_coordinates(move_string + 2);
- for (const auto [move, _] : MoveList(board)) {
+ const MoveList list(board);
+ for (int i = 0; i < list.size(); i++) {
+ const Move move = list[i];
if (move.source() == source && move.target() == target) {
if (move_string[4]) {
if (tolower(move.piece_promote().code) != move_string[4]) continue;
diff --git a/src/include/board.hpp b/src/include/board.hpp
@@ -7,7 +7,6 @@
#include <iostream>
#include <string>
-typedef struct Board Board;
class Board {
public:
enum class Castle : uint8_t {
diff --git a/src/include/move.hpp b/src/include/move.hpp
@@ -38,9 +38,9 @@ struct Move {
friend std::ostream &operator<<(std::ostream &os, Move move);
private:
- void piece_remove(Board &board, const piece::Piece &piece, Square square) const;
- void piece_set(Board &board, const piece::Piece &piece, Square square) const;
- void piece_move(Board &board, const piece::Piece &piece, Square source, Square target) const;
+ inline void piece_remove(Board &board, const piece::Piece &piece, Square square) const;
+ inline void piece_set(Board &board, const piece::Piece &piece, Square square) const;
+ inline void piece_move(Board &board, const piece::Piece &piece, Square source, Square target) const;
unsigned source_i : 6;
unsigned target_i : 6;
diff --git a/src/include/movelist.hpp b/src/include/movelist.hpp
@@ -5,21 +5,14 @@
#include "move.hpp"
#include "utils_cpp.hpp"
-#include <functional>
#include <iostream>
+#include <numeric>
#include <vector>
class MoveList {
- public:
- struct MoveListE {
- Move move;
- U32 score;
-
- auto operator<=>(const MoveListE &mle) { return mle.score <=> score; }
- };
-
private:
- using list_t = std::vector<MoveListE>;
+ using list_t = std::vector<Move>;
+ using index_t = std::vector<int>;
public:
MoveList(const Board &board) : list() {
@@ -27,29 +20,13 @@ class MoveList {
generate(board);
}
- auto size() const { return list.size(); }
-
- MoveListE &operator[](size_t idx) { return list[idx]; }
- const MoveListE &operator[](size_t idx) const { return list[idx]; }
+ int size() const { return list.size(); }
+ const Move operator[](size_t idx) const { return list[idx]; }
friend std::ostream &operator<<(std::ostream &os, const MoveList &list);
- using iterator = list_t::iterator;
- using const_iterator = list_t::const_iterator;
-
- iterator begin() { return list.begin(); }
- iterator end() { return list.end(); }
-
- const_iterator begin() const { return list.begin(); }
- const_iterator end() const { return list.end(); }
- const_iterator cbegin() const { return list.cbegin(); }
- const_iterator cend() const { return list.cend(); }
-
private:
- void push_back(const Move &&move) { list.push_back({move, 0}); }
-
void generate(const Board &board);
-
void clear() { list.clear(); }
list_t list;
diff --git a/src/include/piece.hpp b/src/include/piece.hpp
@@ -109,7 +109,7 @@ constexpr const Piece &get_from_code(char code) {
constexpr const Piece &get_from_index(uint8_t index) { return table[index / 6][index % 6]; }
-static inline constexpr const Square mirror[65] = {
+inline constexpr const Square mirror[65] = {
// clang-format off
Square::a8, Square::b8, Square::c8, Square::d8, Square::e8, Square::f8, Square::g8, Square::h8,
Square::a7, Square::b7, Square::c7, Square::d7, Square::e7, Square::f7, Square::g7, Square::h7,
@@ -122,8 +122,8 @@ static inline constexpr const Square mirror[65] = {
// clang-format on
};
-static constexpr inline const uint16_t value[6] = {100, 300, 350, 500, 1000, 10000};
-static constexpr inline const uint16_t capture[6][6] = {
+constexpr inline const uint16_t value[6] = {100, 300, 350, 500, 1000, 10000};
+constexpr inline const uint16_t capture[6][6] = {
// clang-format off
{105, 205, 305, 405, 505, 605},
{104, 204, 304, 404, 504, 604},
@@ -133,7 +133,7 @@ static constexpr inline const uint16_t capture[6][6] = {
{100, 200, 300, 400, 500, 600},
// clang-format on
};
-static constexpr inline const int8_t position[6][64] = {
+constexpr inline const int8_t position[6][64] = {
// clang-format off
{
0, 0, 0, 0, 0, 0, 0, 0,
diff --git a/src/move/movelist.cpp b/src/move/movelist.cpp
@@ -27,17 +27,21 @@ void MoveList::generate(const Board &board) {
const Square tgt = static_cast<Square>(tgt_i = src_i + add);
if (!board.is_square_occupied(tgt)) {
if (pawn_canPromote(color, src)) {
- push_back(Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::KNIGHT, color), 0, 0, 0));
- push_back(Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::BISHOP, color), 0, 0, 0));
- push_back(Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::ROOK, color), 0, 0, 0));
- push_back(Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::QUEEN, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::KNIGHT, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::BISHOP, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::ROOK, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, nullptr, &piece::get(piece::Type::QUEEN, color), 0, 0, 0));
} else {
- push_back(Move(src, tgt, &pawn, 0, 0, 0, 0, 0));
+ list.push_back(Move(src, tgt, &pawn, 0, 0, 0, 0, 0));
// two ahead
const Square tgt = static_cast<Square>(tgt_i + add);
if (pawn_onStart(color, src) && !board.is_square_occupied(tgt))
- push_back(Move(src, tgt, &pawn, 0, 0, 1, 0, 0));
+ list.push_back(Move(src, tgt, &pawn, 0, 0, 1, 0, 0));
}
}
@@ -47,19 +51,24 @@ void MoveList::generate(const Board &board) {
const Square tgt = static_cast<Square>(tgt_i);
const piece::Piece *capture = board.get_square_piece(tgt);
if (pawn_canPromote(color, src)) {
- push_back(Move(src, tgt, &pawn, capture, &piece::get(piece::Type::KNIGHT, color), 0, 0, 0));
- push_back(Move(src, tgt, &pawn, capture, &piece::get(piece::Type::BISHOP, color), 0, 0, 0));
- push_back(Move(src, tgt, &pawn, capture, &piece::get(piece::Type::ROOK, color), 0, 0, 0));
- push_back(Move(src, tgt, &pawn, capture, &piece::get(piece::Type::QUEEN, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, capture, &piece::get(piece::Type::KNIGHT, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, capture, &piece::get(piece::Type::BISHOP, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, capture, &piece::get(piece::Type::ROOK, color), 0, 0, 0));
+ list.push_back(
+ Move(src, tgt, &pawn, capture, &piece::get(piece::Type::QUEEN, color), 0, 0, 0));
} else {
- push_back(Move(src, tgt, &pawn, capture, 0, 0, 0, 0));
+ list.push_back(Move(src, tgt, &pawn, capture, 0, 0, 0, 0));
}
}
// en passant
const Square enpassant = board.get_enpassant();
if (enpassant != Square::no_sq && board.is_piece_attack_square(pawn, src, enpassant))
- push_back(Move(src, enpassant, &pawn, &piece::get(piece::Type::PAWN, colorOther), 0, 0, 1, 0));
+ list.push_back(
+ Move(src, enpassant, &pawn, &piece::get(piece::Type::PAWN, colorOther), 0, 0, 1, 0));
}
// All piece move
@@ -71,7 +80,7 @@ void MoveList::generate(const Board &board) {
U64 attack = board.get_bitboard_piece_moves(piece, src);
bitboard_for_each_bit(tgt_i, attack) {
const Square tgt = static_cast<Square>(tgt_i);
- push_back(Move(src, tgt, &piece, board.get_square_piece(tgt), 0, 0, 0, 0));
+ list.push_back(Move(src, tgt, &piece, board.get_square_piece(tgt), 0, 0, 0, 0));
}
}
}
@@ -83,14 +92,14 @@ void MoveList::generate(const Board &board) {
if (board.get_castle() & to_underlying(Board::Castle::WK)) {
if (!board.is_square_occupied(Square::f1) && !board.is_square_occupied(Square::g1) &&
!board.is_square_attacked(Square::f1, Color::BLACK))
- push_back(Move(Square::e1, Square::g1, &piece, 0, 0, 0, 0, 1));
+ list.push_back(Move(Square::e1, Square::g1, &piece, 0, 0, 0, 0, 1));
}
if (board.get_castle() & to_underlying(Board::Castle::WQ)) {
if (!board.is_square_occupied(Square::d1) && !board.is_square_occupied(Square::c1) &&
!board.is_square_occupied(Square::b1) &&
!board.is_square_attacked(Square::d1, Color::BLACK) &&
!board.is_square_attacked(Square::c1, Color::BLACK))
- push_back(Move(Square::e1, Square::c1, &piece, 0, 0, 0, 0, 1));
+ list.push_back(Move(Square::e1, Square::c1, &piece, 0, 0, 0, 0, 1));
}
}
} else {
@@ -99,14 +108,14 @@ void MoveList::generate(const Board &board) {
if (board.get_castle() & to_underlying(Board::Castle::BK)) {
if (!board.is_square_occupied(Square::f8) && !board.is_square_occupied(Square::g8) &&
!board.is_square_attacked(Square::f8, Color::WHITE))
- push_back(Move(Square::e8, Square::g8, &piece, 0, 0, 0, 0, 1));
+ list.push_back(Move(Square::e8, Square::g8, &piece, 0, 0, 0, 0, 1));
}
if (board.get_castle() & to_underlying(Board::Castle::BQ)) {
if (!board.is_square_occupied(Square::d8) && !board.is_square_occupied(Square::c8) &&
!board.is_square_occupied(Square::b8) &&
!board.is_square_attacked(Square::d8, Color::WHITE) &&
!board.is_square_attacked(Square::c8, Color::WHITE))
- push_back(Move(Square::e8, Square::c8, &piece, 0, 0, 0, 0, 1));
+ list.push_back(Move(Square::e8, Square::c8, &piece, 0, 0, 0, 0, 1));
}
}
}
@@ -114,8 +123,8 @@ void MoveList::generate(const Board &board) {
std::ostream &operator<<(std::ostream &os, const MoveList &list) {
os << "Size: " << std::dec << list.size() << "\n";
- for (const auto &moveE : list.list) {
- os << moveE.score << ": " << moveE.move << "\n";
+ for (const Move move : list.list) {
+ os << move << "\n";
}
return os;
}
diff --git a/src/perft/perft.cpp b/src/perft/perft.cpp
@@ -57,14 +57,14 @@ class Perft {
private:
void test(const Board &board, int depth) {
- for (const auto [move, _] : MoveList(board)) {
+ const MoveList list(board);
+ for (int i = 0; i < list.size(); i++) {
Board copy = board;
- if (!move.make(copy, 0)) continue;
-
+ if (!list[i].make(copy, 0)) continue;
if (depth != 1)
test(copy, depth - 1);
else
- score(copy, move);
+ score(copy, list[i]);
}
}
void score(const Board &board, Move move) {
@@ -94,8 +94,8 @@ void perft_test(const char *fen, int depth, int thread_num) {
Perft::semaphore_t sem(thread_num);
int index = 0;
- for (const auto &[move, _] : list)
- threads[index++] = std::thread(Perft(sem), board, move, depth);
+ for (int i = 0; i < list.size(); i++)
+ threads[index++] = std::thread(Perft(sem), board, list[i], depth);
for (auto &thread : threads)
thread.join();
