stellar

Stellar - UCI Chess engine written in C++20
git clone git://git.dimitrijedobrota.com/stellar.git
Log | Files | Refs | README | LICENSE

commit ff9e899cbc8545891ed223f9d75cc0546621ac50
parent bb9fc007ecf818bf2899b0f8426dc087de918273
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  8 Aug 2023 19:45:10 +0200

Improve move scoring

Diffstat:
MCMakeLists.txt | 2+-
Msrc/engine/CMakeLists.txt | 2+-
Msrc/engine/engine.c | 95++++++++++++++++++++++++++++++++++++++-----------------------------------------
Asrc/engine/score.c | 141+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/engine/score.h | 13+++++++++++++
Msrc/engine/stats.h | 2+-
Msrc/include/moves.h | 18+++++++++++++++---
Dsrc/include/score.h | 10----------
Msrc/moves/moves.c | 32+++++++++++++++++++++++++-------
Msrc/perft/CMakeLists.txt | 1-
Msrc/perft/perft.c | 4++--
Dsrc/score/CMakeLists.txt | 7-------
Dsrc/score/score.c | 119-------------------------------------------------------------------------------
13 files changed, 245 insertions(+), 201 deletions(-)

diff --git a/CMakeLists.txt b/CMakeLists.txt @@ -3,7 +3,7 @@ set(CMAKE_EXPORT_COMPILE_COMMANDS ON) project( Stellar - VERSION 0.0.17 + VERSION 0.0.18 DESCRIPTION "Chess engine written in C" HOMEPAGE_URL https://git.dimitrijedobrota.com/stellar.git LANGUAGES C diff --git a/src/engine/CMakeLists.txt b/src/engine/CMakeLists.txt @@ -1,5 +1,6 @@ add_executable(engine engine.c + score.c transposition.c ) @@ -8,7 +9,6 @@ target_link_libraries(engine PRIVATE board PRIVATE moves PRIVATE piece - PRIVATE score PRIVATE utils PRIVATE random ) diff --git a/src/engine/engine.c b/src/engine/engine.c @@ -23,55 +23,35 @@ #define WINDOW 50 -int move_score(Stats *stats, Move move) { - if (stats->score_pv) { - if (move_cmp(stats->pv_table[0][stats->ply], move)) { - stats->score_pv = 0; - return 20000; +void move_list_sort_pv(MoveList *list, Stats *stats, Move best) { + assert(list && stats); + + for (int i = 0; i < move_list_size(list); i++) { + const Move move = move_list_index_move(list, i); + if (move_cmp(best, move)) { + move_list_index_score_set(list, i, 30000); + return; } } - if (move_capture(move)) { - return Score_capture(piece_piece(move_piece(move)), - piece_piece(move_piece_capture(move))); + if (stats->ply && stats->follow_pv) { + stats->follow_pv = 0; + for (int i = 0; i < move_list_size(list); i++) { + const Move move = move_list_index_move(list, i); + if (move_cmp(stats->pv_table[0][stats->ply], move)) { + move_list_index_score_set(list, i, 20000); + stats->follow_pv = 1; + break; + } + } } - - if (move_cmp(stats->killer[0][stats->ply], move)) - return 9000; - else if (move_cmp(stats->killer[1][stats->ply], move)) - return 8000; - else - return stats->history[piece_index(move_piece(move))][move_target(move)]; - - return 0; -} - -static Stats *move_list_stats = NULL; -int move_list_cmp(const void *a, const void *b) { - return move_score(move_list_stats, *(Move *)a) <= - move_score(move_list_stats, *(Move *)b); -} - -void move_list_sort(Stats *stats, MoveList *list) { - move_list_stats = stats; - qsort(list->moves, list->count, sizeof(Move), move_list_cmp); } /* SEARCHING */ -void enable_pv_scoring(Stats *stats, MoveList *list) { - stats->follow_pv = 0; - - for (int i = 0; i < list->count; i++) { - if (move_cmp(stats->pv_table[0][stats->ply], move_list_move(list, i))) { - stats->score_pv = 1; - stats->follow_pv = 1; - return; - } - } -} - int evaluate(const Board *board) { + assert(board); + Square square; eColor side = board_side(board); U64 occupancy = board_color(board, side); @@ -96,6 +76,8 @@ int evaluate(const Board *board) { int is_repetition() { return 0; } int stats_move_make(Stats *self, Board *copy, Move move, int flag) { + assert(self && copy); + board_copy(self->board, copy); if (!move_make(move, self->board, flag)) { board_copy(copy, self->board); @@ -106,6 +88,8 @@ int stats_move_make(Stats *self, Board *copy, Move move, int flag) { } void stats_move_make_pruning(Stats *self, Board *copy) { + assert(self && copy); + board_copy(self->board, copy); board_side_switch(self->board); board_enpassant_set(self->board, no_sq); @@ -113,11 +97,15 @@ void stats_move_make_pruning(Stats *self, Board *copy) { } void stats_move_unmake(Stats *self, Board *copy) { + assert(self && copy); + board_copy(copy, self->board); self->ply--; } void stats_pv_store(Stats *self, Move move) { + assert(self); + const int ply = self->ply; self->pv_table[ply][ply] = move; for (int i = ply + 1; i < self->pv_length[ply + 1]; i++) { @@ -127,6 +115,8 @@ void stats_pv_store(Stats *self, Move move) { } int quiescence(Stats *stats, int alpha, int beta) { + assert(stats); + stats->pv_length[stats->ply] = stats->ply; stats->nodes++; @@ -136,12 +126,14 @@ int quiescence(Stats *stats, int alpha, int beta) { if (score > alpha) alpha = score; Board copy; - MoveList moves; - move_list_generate(&moves, stats->board); - move_list_sort(stats, &moves); + MoveList list; + move_list_generate(&list, stats->board); + Score_move_list(stats, &list); + move_list_sort_pv(&list, stats, (Move){0}); + move_list_sort(&list); - for (int i = 0; i < move_list_size(&moves); i++) { - Move move = move_list_move(&moves, i); + for (int i = 0; i < move_list_size(&list); i++) { + Move move = move_list_index_move(&list, i); if (!stats_move_make(stats, &copy, move, 1)) continue; score = -quiescence(stats, -beta, -alpha); stats_move_unmake(stats, &copy); @@ -157,6 +149,8 @@ int quiescence(Stats *stats, int alpha, int beta) { } int negamax(Stats *stats, int alpha, int beta, int depth, bool null) { + assert(stats); + int pv_node = (beta - alpha) > 1; HasheFlag flag = flagAlpha; Move bestMove = {0}; @@ -228,13 +222,14 @@ int negamax(Stats *stats, int alpha, int beta, int depth, bool null) { MoveList list; move_list_generate(&list, stats->board); - if (stats->follow_pv) enable_pv_scoring(stats, &list); - move_list_sort(stats, &list); + Score_move_list(stats, &list); + move_list_sort_pv(&list, stats, bestMove); + move_list_sort(&list); int legal_moves = 0; int searched = 0; for (int i = 0; i < move_list_size(&list); i++) { - const Move move = move_list_move(&list, i); + const Move move = move_list_index_move(&list, i); if (!stats_move_make(stats, &copy, move, 0)) continue; legal_moves++; @@ -321,6 +316,8 @@ void move_print_UCI(Move move) { TTable *ttable = NULL; void search_position(Board *board, int depth) { + assert(board); + Stats stats = {.ttable = ttable, .board = board, 0}; int alpha = -INFINITY, beta = INFINITY; @@ -435,7 +432,7 @@ Move parse_move(Board *board, char *move_string) { moves = move_list_generate(NULL, board); for (int i = 0; i < moves->count; i++) { - Move move = moves->moves[i]; + Move move = move_list_index_move(moves, i); if (move_source(move) == source && move_target(move) == target) { if (move_string[4]) { if (tolower(piece_code(move_piece_promote(move))) != diff --git a/src/engine/score.c b/src/engine/score.c @@ -0,0 +1,141 @@ +#include "score.h" +#include "moves.h" +#include "stats.h" + +// clang-format off +struct Score_T { + int value; + int position[64]; + int capture[6]; +}; + +static const struct Score_T Scores[] = { +[PAWN] = { +.value = 100, +.position = { + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, -10, -10, 0, 0, 0, + 0, 0, 0, 5, 5, 0, 0, 0, + 5, 5, 10, 20, 20, 5, 5, 5, + 10, 10, 10, 20, 20, 10, 10, 10, + 20, 20, 20, 30, 30, 30, 20, 20, + 30, 30, 30, 40, 40, 30, 30, 30, + 90, 90, 90, 90, 90, 90, 90, 90, }, +.capture = { [PAWN] = 105, [KNIGHT] = 205, + [BISHOP] = 305, [ROOK] = 405, + [QUEEN] = 505, [KING] = 605} }, +[KNIGHT] = { +.value = 300, +.position = { + -5, -10 , 0, 0, 0, 0, -10, -5, + -5, 0, 0, 0, 0, 0, 0, -5, + -5, 5, 20, 10, 10, 20, 5, -5, + -5, 10, 20, 30, 30, 20, 10, -5, + -5, 10, 20, 30, 30, 20, 10, -5, + -5, 5, 20, 20, 20, 20, 5, -5, + -5, 0, 0, 10, 10, 0, 0, -5, + -5, 0, 0, 0, 0, 0, 0, -5, }, +.capture = { [PAWN] = 104, [KNIGHT] = 204, + [BISHOP] = 304, [ROOK] = 404, + [QUEEN] = 504, [KING] = 604} }, +[BISHOP] = { +.value = 350, +.position = { + 0, 0, -10, 0, 0, -10, 0, 0, + 0, 30, 0, 0, 0, 0, 30, 0, + 0, 10, 0, 0, 0, 0, 10, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 0, 0, 0, 10, 10, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, }, +.capture = { [PAWN] = 103, [KNIGHT] = 203, + [BISHOP] = 303, [ROOK] = 403, + [QUEEN] = 503, [KING] = 603} }, +[ROOK] = { +.value = 500, +.position = { + 0, 0, 0, 20, 20, 0, 0, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 0, 0, 10, 20, 20, 10, 0, 0, + 50, 50, 50, 50, 50, 50, 50, 50, + 50, 50, 50, 50, 50, 50, 50, 50, }, +.capture = { [PAWN] = 102, [KNIGHT] = 202, + [BISHOP] = 302, [ROOK] = 402, + [QUEEN] = 502, [KING] = 602} }, +[QUEEN] = { +.value = 1000, +.position = { + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, }, +.capture = { [PAWN] = 101, [KNIGHT] = 201, + [BISHOP] = 301, [ROOK] = 401, + [QUEEN] = 501, [KING] = 601} }, +[KING] = { +.value = 10000, +.position = { + 0, 0, 5, 0, -15, 0, 10, 0, + 0, 5, 5, -5, -5, 0, 5, 0, + 0, 0, 5, 10, 10, 5, 0, 0, + 0, 5, 10, 20, 20, 10, 5, 0, + 0, 5, 10, 20, 20, 10, 5, 0, + 0, 5, 5, 10, 10, 5, 5, 0, + 0, 0, 5, 5, 5, 5, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, }, +.capture = { [PAWN] = 100, [KNIGHT] = 200, + [BISHOP] = 300, [ROOK] = 400, + [QUEEN] = 500, [KING] = 600} }, +}; + +const int mirror_score[128] = +{ + a8, b8, c8, d8, e8, f8, g8, h8, + a7, b7, c7, d7, e7, f7, g7, h7, + a6, b6, c6, d6, e6, f6, g6, h6, + a5, b5, c5, d5, e5, f5, g5, h5, + a4, b4, c4, d4, e4, f4, g4, h4, + a3, b3, c3, d3, e3, f3, g3, h3, + a2, b2, c2, d2, e2, f2, g2, h2, + a1, b1, c1, d1, e1, f1, g1, h1, no_sq, +}; +// clang-format on + +int Score_value(ePiece piece) { return Scores[piece].value; } + +int Score_position(ePiece piece, eColor color, Square square) { + if (color == BLACK) square = mirror_score[square]; + return Scores[piece].position[square]; +} + +int Score_capture(ePiece src, ePiece tgt) { + return Scores[src].capture[tgt] + 10000; +} + +int Score_move(const Stats *stats, Move move) { + if (move_capture(move)) { + return Score_capture(piece_piece(move_piece(move)), + piece_piece(move_piece_capture(move))); + } + + if (move_cmp(stats->killer[0][stats->ply], move)) + return 9000; + else if (move_cmp(stats->killer[1][stats->ply], move)) + return 8000; + + return stats->history[piece_index(move_piece(move))][move_target(move)]; +} + +void Score_move_list(const Stats *stats, MoveList *list) { + for (int i = 0; i < move_list_size(list); i++) { + list->moves[i].score = Score_move(stats, move_list_index_move(list, i)); + } +} diff --git a/src/engine/score.h b/src/engine/score.h @@ -0,0 +1,13 @@ +#ifndef STELLAR_SCORE_H +#define STELLAR_SCORE_H + +#include "board.h" +#include "moves.h" +#include "stats.h" + +int Score_position(ePiece piece, eColor color, Square square); +void Score_move_list(const Stats *stats, MoveList *list); +int Score_capture(ePiece src, ePiece tgt); +int Score_value(ePiece piece); + +#endif diff --git a/src/engine/stats.h b/src/engine/stats.h @@ -14,7 +14,7 @@ struct Stats { int pv_length[MAX_PLY]; struct TTable *ttable; Board *board; - int follow_pv, score_pv; + int follow_pv; long nodes; int ply; }; diff --git a/src/include/moves.h b/src/include/moves.h @@ -21,9 +21,14 @@ struct Move { }; typedef struct MoveList MoveList; +typedef struct MoveE MoveE; + struct MoveList { - Move moves[256]; int count; + struct MoveE { + Move move; + int score; + } moves[256]; }; int move_cmp(Move a, Move b); @@ -31,14 +36,21 @@ Move move_encode(Square src, Square tgt, Piece piece, Piece capture, Piece promote, int dbl, int enpassant, int castle); void move_print(Move move); MoveList *move_list_new(void); + void move_list_free(MoveList **p); -Move move_list_move(const MoveList *self, int index); +Move move_list_index_move(const MoveList *self, int index); +int move_list_index_score(const MoveList *self, int index); +void move_list_index_score_set(MoveList *self, int index, int score); + +int move_make(Move move, Board *board, int flag); + int move_list_size(const MoveList *self); void move_list_reset(MoveList *self); void move_list_add(MoveList *self, Move move); void move_list_print(const MoveList *self); +void move_list_sort(MoveList *list); + MoveList *move_list_generate(MoveList *moves, const Board *board); -int move_make(Move move, Board *board, int flag); #define move_source(move) (move.source) #define move_target(move) (move.target) diff --git a/src/include/score.h b/src/include/score.h @@ -1,10 +0,0 @@ -#ifndef STELLAR_SCORE_H -#define STELLAR_SCORE_H - -#include "board.h" - -int Score_capture(ePiece src, ePiece tgt); -int Score_position(ePiece piece, eColor color, Square square); -int Score_value(ePiece piece); - -#endif diff --git a/src/moves/moves.c b/src/moves/moves.c @@ -4,7 +4,6 @@ #include <cul/assert.h> #include <cul/mem.h> -#include "board.h" #include "moves.h" int move_cmp(Move a, Move b) { return *(uint32_t *)&a == *(uint32_t *)&b; } @@ -45,19 +44,38 @@ MoveList *move_list_new(void) { void move_list_free(MoveList **p) { FREE(*p); } -Move move_list_move(const MoveList *self, int index) { - return self->moves[index]; +Move move_list_index_move(const MoveList *self, int index) { + return self->moves[index].move; } + +int move_list_index_score(const MoveList *self, int index) { + return self->moves[index].score; +} + +void move_list_index_score_set(MoveList *self, int index, int score) { + self->moves[index].score = score; +} + int move_list_size(const MoveList *self) { return self->count; } void move_list_reset(MoveList *self) { self->count = 0; } void move_list_add(MoveList *self, Move move) { - self->moves[self->count++] = move; + self->moves[self->count++].move = move; +} + +int move_list_cmp(const void *a, const void *b) { + return ((MoveE *)a)->score <= ((MoveE *)b)->score; +} + +void move_list_sort(MoveList *list) { + qsort(list->moves, list->count, sizeof(MoveE), move_list_cmp); } void move_list_print(const MoveList *self) { - printf(" From To Pi Cap Prmt Dbl Enp Cst C P\n"); - for (int i = 0; i < self->count; i++) - move_print(self->moves[i]); + printf("Score From To Pi Cap Prmt Dbl Enp Cst C P\n"); + for (int i = 0; i < self->count; i++) { + printf("%5d: ", self->moves[i].score); + move_print(self->moves[i].move); + } printf("Total: %d\n", self->count); } diff --git a/src/perft/CMakeLists.txt b/src/perft/CMakeLists.txt @@ -17,7 +17,6 @@ target_link_libraries(perft PRIVATE board PRIVATE moves PRIVATE piece - PRIVATE score PRIVATE utils PRIVATE random ) diff --git a/src/perft/perft.c b/src/perft/perft.c @@ -58,7 +58,7 @@ void perft_driver(Board *board, struct MoveList *moveList, int depth, Board *copy = board_new(); for (int i = 0; i < move_list_size(list); i++) { - Move move = move_list_move(list, i); + Move move = move_list_index_move(list, i); board_copy(board, copy); if (!move_make(move, copy, 0)) continue; @@ -105,7 +105,7 @@ void *perft_thread(void *arg) { pthread_mutex_unlock(&shared->mutex); break; } - Move move = move_list_move(shared->list, shared->index++); + Move move = move_list_index_move(shared->list, shared->index++); pthread_mutex_unlock(&shared->mutex); result = (PerftResult){0}; diff --git a/src/score/CMakeLists.txt b/src/score/CMakeLists.txt @@ -1,7 +0,0 @@ -add_library(score OBJECT - score.c -) - -target_include_directories(score - PUBLIC "${PROJECT_SOURCE_DIR}/src/include" -) diff --git a/src/score/score.c b/src/score/score.c @@ -1,119 +0,0 @@ -#include "score.h" - -// clang-format off -struct Score_T { - int value; - int position[64]; - int capture[6]; -}; - -static const struct Score_T Scores[] = { -[PAWN] = { -.value = 100, -.position = { - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, -10, -10, 0, 0, 0, - 0, 0, 0, 5, 5, 0, 0, 0, - 5, 5, 10, 20, 20, 5, 5, 5, - 10, 10, 10, 20, 20, 10, 10, 10, - 20, 20, 20, 30, 30, 30, 20, 20, - 30, 30, 30, 40, 40, 30, 30, 30, - 90, 90, 90, 90, 90, 90, 90, 90, }, -.capture = { [PAWN] = 105, [KNIGHT] = 205, - [BISHOP] = 305, [ROOK] = 405, - [QUEEN] = 505, [KING] = 605} }, -[KNIGHT] = { -.value = 300, -.position = { - -5, -10 , 0, 0, 0, 0, -10, -5, - -5, 0, 0, 0, 0, 0, 0, -5, - -5, 5, 20, 10, 10, 20, 5, -5, - -5, 10, 20, 30, 30, 20, 10, -5, - -5, 10, 20, 30, 30, 20, 10, -5, - -5, 5, 20, 20, 20, 20, 5, -5, - -5, 0, 0, 10, 10, 0, 0, -5, - -5, 0, 0, 0, 0, 0, 0, -5, }, -.capture = { [PAWN] = 104, [KNIGHT] = 204, - [BISHOP] = 304, [ROOK] = 404, - [QUEEN] = 504, [KING] = 604} }, -[BISHOP] = { -.value = 350, -.position = { - 0, 0, -10, 0, 0, -10, 0, 0, - 0, 30, 0, 0, 0, 0, 30, 0, - 0, 10, 0, 0, 0, 0, 10, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 0, 0, 0, 10, 10, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, }, -.capture = { [PAWN] = 103, [KNIGHT] = 203, - [BISHOP] = 303, [ROOK] = 403, - [QUEEN] = 503, [KING] = 603} }, -[ROOK] = { -.value = 500, -.position = { - 0, 0, 0, 20, 20, 0, 0, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 0, 0, 10, 20, 20, 10, 0, 0, - 50, 50, 50, 50, 50, 50, 50, 50, - 50, 50, 50, 50, 50, 50, 50, 50, }, -.capture = { [PAWN] = 102, [KNIGHT] = 202, - [BISHOP] = 302, [ROOK] = 402, - [QUEEN] = 502, [KING] = 602} }, -[QUEEN] = { -.value = 1000, -.position = { - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, }, -.capture = { [PAWN] = 101, [KNIGHT] = 201, - [BISHOP] = 301, [ROOK] = 401, - [QUEEN] = 501, [KING] = 601} }, -[KING] = { -.value = 10000, -.position = { - 0, 0, 5, 0, -15, 0, 10, 0, - 0, 5, 5, -5, -5, 0, 5, 0, - 0, 0, 5, 10, 10, 5, 0, 0, - 0, 5, 10, 20, 20, 10, 5, 0, - 0, 5, 10, 20, 20, 10, 5, 0, - 0, 5, 5, 10, 10, 5, 5, 0, - 0, 0, 5, 5, 5, 5, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, }, -.capture = { [PAWN] = 100, [KNIGHT] = 200, - [BISHOP] = 300, [ROOK] = 400, - [QUEEN] = 500, [KING] = 600} }, -}; - -const int mirror_score[128] = -{ - a8, b8, c8, d8, e8, f8, g8, h8, - a7, b7, c7, d7, e7, f7, g7, h7, - a6, b6, c6, d6, e6, f6, g6, h6, - a5, b5, c5, d5, e5, f5, g5, h5, - a4, b4, c4, d4, e4, f4, g4, h4, - a3, b3, c3, d3, e3, f3, g3, h3, - a2, b2, c2, d2, e2, f2, g2, h2, - a1, b1, c1, d1, e1, f1, g1, h1, no_sq, -}; -// clang-format on - -int Score_value(ePiece piece) { return Scores[piece].value; } - -int Score_position(ePiece piece, eColor color, Square square) { - if (color == BLACK) square = mirror_score[square]; - return Scores[piece].position[square]; -} - -int Score_capture(ePiece src, ePiece tgt) { - return Scores[src].capture[tgt] + 10000; -}