commit 97eeac5b570b67e3fa6e327ec142ea0c5f135d49
parent 8bab42ac758595bc29cfc1ae86398a57e72cd963
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 30 Aug 2023 22:15:26 +0200
Prevent move repetition
Diffstat:
8 files changed, 93 insertions(+), 34 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -3,7 +3,7 @@ set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
project(
Stellar
- VERSION 0.0.26
+ VERSION 0.0.28
DESCRIPTION "Chess engine written in C"
HOMEPAGE_URL https://git.dimitrijedobrota.com/stellar.git
LANGUAGES C CXX
diff --git a/src/board/board.cpp b/src/board/board.cpp
@@ -23,7 +23,7 @@ Board::Board(const std::string &fen) {
file = 0;
rank--;
} else {
- throw std::exception();
+ throw std::runtime_error("Invalid piece position");
}
}
@@ -33,7 +33,7 @@ Board::Board(const std::string &fen) {
else if (fen[i] == 'b')
side = Color::BLACK;
else
- throw std::exception();
+ throw std::runtime_error("Invalid player char");
for (i += 2; fen[i] != ' '; i++) {
if (fen[i] == 'K')
@@ -47,9 +47,10 @@ Board::Board(const std::string &fen) {
else if (fen[i] == '-')
break;
else
- throw std::exception();
+ throw std::runtime_error("Invalid castle rights");
}
+ i++;
if (fen[++i] != '-') enpassant = square_from_coordinates(fen.data() + i);
hash = Zobrist::hash(*this);
}
diff --git a/src/engine/engine.cpp b/src/engine/engine.cpp
@@ -76,16 +76,46 @@ class TTable {
std::vector<Hashe> table;
};
-const uci::Settings *settings = nullptr;
-Board board;
-TTable ttable;
-Move pv_table[MAX_PLY][MAX_PLY];
-Move killer[2][MAX_PLY];
-U32 history[12][64];
-int pv_length[MAX_PLY];
-bool follow_pv;
-U64 nodes;
-U32 ply;
+class RTable {
+ public:
+ RTable() = default;
+
+ bool is_repetition(const U64 hash) const {
+ for (int i = repetitions.size() - 1; i >= 0; i--) {
+ if (repetitions[i] == hash) return true;
+ if (repetitions[i] == hashNull) return false;
+ }
+ return false;
+ }
+
+ void pop(void) { repetitions.pop_back(); }
+ void clear(void) { repetitions.clear(); }
+ void push_null(void) { repetitions.push_back(hashNull); }
+ void push_hash(U64 hash) { repetitions.push_back(hash); }
+
+ friend std::ostream &operator<<(std::ostream &os, const RTable &rtable) {
+ for (const U64 hash : rtable.repetitions)
+ os << hash << " ";
+ return os;
+ }
+
+ private:
+ std::vector<U64> repetitions;
+
+ const static int hashNull = 0;
+};
+
+static const uci::Settings *settings = nullptr;
+static Board board;
+static TTable ttable;
+static RTable rtable;
+static Move pv_table[MAX_PLY][MAX_PLY];
+static Move killer[2][MAX_PLY];
+static U32 history[12][64];
+static int pv_length[MAX_PLY];
+static bool follow_pv;
+static U64 nodes;
+static U32 ply;
U32 inline move_list_score(Move move) {
const piece::Type type = board.get_square_piece_type(move.source());
@@ -152,15 +182,15 @@ int evaluate(const Board &board) {
return score;
}
-int is_repetition() { return 0; }
-
-int stats_move_make(Board ©, Move move, int flag) {
+int stats_move_make(Board ©, const Move move, int flag) {
copy = board;
if (!move.make(board, flag)) {
board = copy;
return 0;
}
ply++;
+ rtable.push_hash(copy.get_hash());
+ if (!move.is_repetable()) rtable.push_null();
return 1;
}
@@ -171,8 +201,15 @@ void stats_move_make_pruning(Board ©) {
ply++;
}
-void stats_move_unmake(Board ©) {
+void stats_move_unmake_pruning(Board ©) {
+ board = copy;
+ ply--;
+}
+
+void stats_move_unmake(Board ©, const Move move) {
board = copy;
+ if (!move.is_repetable()) rtable.pop();
+ rtable.pop();
ply--;
}
@@ -201,13 +238,14 @@ int quiescence(int16_t alpha, int16_t beta) {
MoveList list(board);
for (int idx : move_list_sort(list, Move())) {
+ const Move move = list[idx];
if (!stats_move_make(copy, list[idx], 1)) continue;
score = -quiescence(-beta, -alpha);
- stats_move_unmake(copy);
+ stats_move_unmake(copy, move);
if (score > alpha) {
alpha = score;
- stats_pv_store(list[idx]);
+ stats_pv_store(move);
if (score >= beta) return beta;
}
@@ -234,7 +272,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {
if (ply && score != TTable::unknown && !pv_node) return score;
// && fifty >= 100
- if (ply && is_repetition()) return 0;
+ if (ply && rtable.is_repetition(board.get_hash())) return 0;
if (depth == 0) {
nodes++;
int score = quiescence(alpha, beta);
@@ -267,7 +305,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {
if (ply && depth > 2 && staticEval >= beta) {
stats_move_make_pruning(copy);
score = -negamax(-beta, -beta + 1, depth - 1 - REDUCTION_MOVE, false);
- stats_move_unmake(copy);
+ stats_move_unmake_pruning(copy);
if (score >= beta) return beta;
}
@@ -306,7 +344,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {
// futility pruning
if (futility && searched && !move.is_capture() && !move.is_promote() && !board.is_check()) {
- stats_move_unmake(copy);
+ stats_move_unmake(copy, move);
continue;
}
@@ -331,7 +369,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {
}
}
- stats_move_unmake(copy);
+ stats_move_unmake(copy, move);
searched++;
if (settings->stopped) return 0;
@@ -378,9 +416,16 @@ void search_position(const uci::Settings &settingsr) {
ttable = TTable(C64(0x1000000));
}
+ rtable.clear();
+ board = settings->board;
+ for (int i = 0; i < settings->madeMoves.size(); i++) {
+ rtable.push_hash(board.get_hash());
+ settings->madeMoves[i].make(board);
+ if (!settings->madeMoves[i].is_repetable()) rtable.push_null();
+ }
+
ply = 0;
nodes = 0;
- board = settings->board;
settings->stopped = false;
memset(killer, 0x00, sizeof(killer));
memset(history, 0x00, sizeof(history));
diff --git a/src/engine/uci.cpp b/src/engine/uci.cpp
@@ -76,19 +76,26 @@ void loop(void) {
settings = Settings();
settings.board = Board(start_position);
} else if (command == "position") {
+ settings.madeMoves.clear();
iss >> command;
if (command == "startpos") {
settings.board = Board(start_position);
} else if (command == "fen") {
iss >> command;
- settings.board = Board(command);
+ settings.board = Board(line.substr(13));
}
- iss >> command;
+
+ while (iss >> command)
+ if (command == "moves") break;
+
+ Board board = settings.board;
while (iss >> command) {
- if (!parse_move(settings.board, move, command)) break;
- move.make(settings.board);
+ if (!parse_move(board, move, command)) break;
+ settings.madeMoves.push(move);
+ move.make(board);
}
} else if (command == "go") {
+ settings.searchMoves.clear();
uint32_t wtime = 0, btime = 0, movetime = 0;
uint16_t winc = 0, binc = 0, movestogo = 30;
@@ -118,7 +125,7 @@ void loop(void) {
else if (command == "searchmoves") {
while (iss >> command) {
if (!parse_move(settings.board, move, command)) break;
- settings.searchmoves.push(move);
+ settings.searchMoves.push(move);
}
}
}
diff --git a/src/engine/uci.hpp b/src/engine/uci.hpp
@@ -9,7 +9,9 @@
namespace uci {
struct Settings {
- MoveList searchmoves;
+ MoveList searchMoves;
+ MoveList madeMoves;
+
Board board;
uint32_t starttime;
uint32_t stoptime;
diff --git a/src/move/move.hpp b/src/move/move.hpp
@@ -16,6 +16,7 @@ struct Move {
CASTLEQ,
CAPTURE,
ENPASSANT,
+ PQUIET,
PKNIGHT = 8,
PBISHOP,
PROOK,
@@ -37,11 +38,12 @@ struct Move {
Square source(void) const { return static_cast<Square>(source_i); }
Square target(void) const { return static_cast<Square>(target_i); }
- bool is_capture(void) const { return flags_i & CAPTURE; }
+ bool is_capture(void) const { return flags_i != PQUIET && (flags_i & CAPTURE); }
bool is_promote(void) const { return flags_i & 0x8; }
- bool is_quiet(void) const { return flags_i == QUIET; }
bool is_double(void) const { return flags_i == DOUBLE; }
+ bool is_repetable(void) const { return flags_i == QUIET; }
+ bool is_quiet(void) const { return flags_i == QUIET || flags_i == PQUIET; }
bool is_castle(void) const { return flags_i == CASTLEK || flags_i == CASTLEQ; }
bool is_castle_king(void) const { return flags_i == CASTLEK; }
diff --git a/src/move/movelist.cpp b/src/move/movelist.cpp
@@ -32,7 +32,7 @@ void MoveList::generate(const Board &board) {
list.push_back({src, tgt, Move::PROOK});
list.push_back({src, tgt, Move::PQUEEN});
} else {
- list.push_back({src, tgt, Move::QUIET});
+ list.push_back({src, tgt, Move::PQUIET});
// two ahead
const Square tgt = static_cast<Square>(tgt_i + add);
diff --git a/src/move/movelist.hpp b/src/move/movelist.hpp
@@ -21,7 +21,9 @@ class MoveList {
generate(board);
}
+ void clear() { list.clear(); }
int size() const { return list.size(); }
+
const Move operator[](size_t idx) const { return list[idx]; }
void push(const Move move) { list.push_back(move); }
