stellar

commit f8a5dd96409dbbd8818aef7f6984dda121053c0a
parent 120c077931942c5cc5308bf9ccc62cc83cfd6c82
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 25 Sep 2023 19:45:53 +0000

Incremental sorting, fix quiescence timeout

Diffstat:
M
CMakeLists.txt
 | 
2
+-
M
src/engine/engine.cpp
 | 
41
++++++++++++++++++++++++++---------------
M
src/move/movelist.hpp
 | 
1
+

3 files changed, 28 insertions(+), 16 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -3,7 +3,7 @@ set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
 
 project(
     Stellar
-	VERSION 9.0.2
+	VERSION 9.0.3
     DESCRIPTION "Chess engine written in C++"
 	HOMEPAGE_URL https://git.dimitrijedobrota.com/stellar.git
     LANGUAGES CXX
diff --git a/src/engine/engine.cpp b/src/engine/engine.cpp
@@ -116,7 +116,7 @@ static bool follow_pv;
 static U64 nodes;
 static uint8_t ply;
 
-U32 inline move_list_score(Move move) {
+U32 inline move_score(const Move move) {
     static constexpr const uint16_t capture[6][6] = {
         // clang-format off
         {105, 205, 305, 405, 505, 605},
@@ -138,19 +138,30 @@ U32 inline move_list_score(Move move) {
     return history[piece::get_index(type, board.get_side())][to_underlying(move.target())];
 }
 
-std::vector<int> move_list_sort(MoveList &list, const Move best) {
-    static std::vector<int> score(256);
+void move_list_sort(MoveList &list, std::vector<int> &score, int crnt) {
+    for (int i = crnt + 1; i < list.size(); i++) {
+        if (score[crnt] < score[i]) {
+            std::swap(list[crnt], list[i]);
+            std::swap(score[crnt], score[i]);
+        }
+    }
+}
+
+std::vector<int> move_list_score(MoveList &list, const Move best) {
+    std::vector<int> score(list.size(), 0);
 
     bool best_found = false;
     for (int i = 0; i < list.size(); i++) {
-        score[i] = move_list_score(list[i]);
+        score[i] = move_score(list[i]);
         if (list[i] == best) {
             score[i] = 30000;
             best_found = true;
         }
     }
 
-    if (!best_found && ply && follow_pv) {
+    if (best_found) return score;
+
+    if (ply && follow_pv) {
         follow_pv = false;
         for (int i = 0; i < list.size(); i++) {
             if (list[i] == pvtable.best(ply)) {
@@ -161,10 +172,7 @@ std::vector<int> move_list_sort(MoveList &list, const Move best) {
         }
     }
 
-    std::vector<int> index(list.size());
-    std::iota(begin(index), end(index), 0);
-    sort(begin(index), end(index), [&](int a, int b) { return score[a] > score[b]; });
-    return index;
+    return score;
 }
 
 int stats_move_make(Board &copy, const Move move) {
@@ -213,19 +221,20 @@ int16_t quiescence(int16_t alpha, int16_t beta) {
 
     Board copy;
     MoveList list(board, true);
-    for (int idx : move_list_sort(list, Move())) {
-        const Move move = list[idx];
+    std::vector<int> listScore = move_list_score(list, Move());
+    for (int i = 0; i < list.size(); i++) {
+        move_list_sort(list, listScore, i);
+        const Move move = list[i];
         if (!stats_move_make(copy, move)) continue;
         score = -quiescence(-beta, -alpha);
         stats_move_unmake(copy, move);
 
+        if (settings->stopped) return 0;
         if (score > alpha) {
             alpha = score;
             pvtable.store(move, ply);
             if (score >= beta) return beta;
         }
-
-        if (settings->stopped) return 0;
     }
 
     return alpha;
@@ -314,8 +323,10 @@ int16_t negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {
     uint8_t searched = 0;
 
     MoveList list(board);
-    for (int idx : move_list_sort(list, bestMove)) {
-        const Move move = list[idx];
+    std::vector<int> listScore = move_list_score(list, bestMove);
+    for (int i = 0; i < list.size(); i++) {
+        move_list_sort(list, listScore, i);
+        const Move move = list[i];
         if (!stats_move_make(copy, move)) continue;
         legal_moves++;
 
diff --git a/src/move/movelist.hpp b/src/move/movelist.hpp
@@ -32,6 +32,7 @@ class MoveList {
     int size() const { return list.size(); }
 
     const Move operator[](size_t idx) const { return list[idx]; }
+    Move &operator[](size_t idx) { return list[idx]; }
     void push(const Move move) { list.push_back(move); }
 
     friend std::ostream &operator<<(std::ostream &os, const MoveList &list);