commit 67d1edbf1daf0345b19c76305a4f6bd88bb70493
parent 230f52919827bd8671fd340e5cbcbb753e37140a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 5 Aug 2023 14:29:43 +0200
Sort PV moves, and general improvement
Diffstat:
8 files changed, 98 insertions(+), 102 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -3,7 +3,7 @@ set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
project(
Stellar
- VERSION 0.0.9
+ VERSION 0.0.10
DESCRIPTION "Chess engine written in C"
HOMEPAGE_URL https://git.dimitrijedobrota.com/stellar.git
LANGUAGES C
diff --git a/src/board/board.c b/src/board/board.c
@@ -7,14 +7,6 @@
#include "board.h"
-struct Board {
- U64 color[2];
- U64 piece[6];
- eColor side;
- Square enpassant;
- eCastle castle;
-};
-
Board *board_new(void) {
Board *p;
NEW0(p);
@@ -23,7 +15,7 @@ Board *board_new(void) {
void board_free(Board **p) { FREE(*p); }
-void board_copy(Board *self, Board *dest) { *dest = *self; }
+void board_copy(const Board *self, Board *dest) { *dest = *self; }
Square board_enpassant(const Board *self) { return self->enpassant; }
eCastle board_castle(const Board *self) { return self->castle; }
@@ -38,7 +30,7 @@ U64 board_piece_get_internal(const Board *self, ePiece piece, Square target) {
return bit_get(self->piece[piece], target);
}
-U64 board_pieceSet(Board *self, Piece piece) {
+U64 board_pieceSet(const Board *self, Piece piece) {
return self->piece[piece_piece(piece)] & self->color[piece_color(piece)];
}
@@ -79,7 +71,7 @@ void board_piece_move(Board *self, Piece Piece, Square source, Square target) {
board_piece_set(self, Piece, target);
}
-U64 board_piece_attacks(Board *self, Piece piece, Square src) {
+U64 board_piece_attacks(const Board *self, Piece piece, Square src) {
return piece_attacks(piece)(src, board_occupancy(self));
}
diff --git a/src/engine/engine.c b/src/engine/engine.c
@@ -23,6 +23,7 @@ struct Stats {
Move pv_table[MAX_PLY][MAX_PLY];
Move killer_moves[2][MAX_PLY];
U32 history_moves[16][64];
+ int follow_pv, score_pv;
};
Stats *Stats_new(void) {
@@ -34,43 +35,55 @@ Stats *Stats_new(void) {
void Stats_free(Stats **p) { FREE(*p); }
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;
+ }
+ }
+
if (move_capture(move)) {
return Score_capture(piece_piece(move_piece(move)),
piece_piece(move_piece_capture(move)));
- } else {
- if (move_cmp(stats->killer_moves[0][stats->ply], move))
- return 9000;
- else if (move_cmp(stats->killer_moves[1][stats->ply], move))
- return 8000;
- else
- return stats->history_moves[piece_index(move_piece(move))]
- [move_target(move)];
}
+ if (move_cmp(stats->killer_moves[0][stats->ply], move))
+ return 9000;
+ else if (move_cmp(stats->killer_moves[1][stats->ply], move))
+ return 8000;
+ else
+ return stats
+ ->history_moves[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) {
- int score[list->count];
- for (int i = 0; i < list->count; i++)
- score[i] = move_score(stats, list->moves[i]);
-
- for (int i = 0; i < list->count; i++)
- for (int j = i + 1; j < list->count; j++)
- if (score[i] < score[j]) {
- Move t = list->moves[i];
- list->moves[i] = list->moves[j];
- list->moves[j] = t;
-
- int s = score[i];
- score[i] = score[j];
- score[j] = s;
- }
+ move_list_stats = stats;
+ qsort(list->moves, list->count, sizeof(Move), move_list_cmp);
}
/* SEARCHING */
-int evaluate(Board *board) {
+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) {
Square square;
eColor side = board_side(board);
U64 occupancy = board_color(board, side);
@@ -92,82 +105,64 @@ int evaluate(Board *board) {
return score;
}
-int quiescence(Stats *stats, Board *board, int alpha, int beta) {
- MoveList *moves;
- Board *copy;
-
+int quiescence(Stats *stats, const Board *board, int alpha, int beta) {
int eval = evaluate(board);
stats->nodes++;
- if (eval >= beta) {
- return beta;
- }
-
- if (eval > alpha) {
- alpha = eval;
- }
+ if (eval >= beta) return beta;
+ if (eval > alpha) alpha = eval;
- copy = board_new();
- moves = move_list_generate(NULL, board);
- move_list_sort(stats, moves);
+ Board copy;
+ MoveList moves;
+ move_list_generate(&moves, board);
+ move_list_sort(stats, &moves);
- for (int i = 0; i < move_list_size(moves); i++) {
- board_copy(board, copy);
+ for (int i = 0; i < move_list_size(&moves); i++) {
+ board_copy(board, ©);
- if (move_make(move_list_move(moves, i), copy, 1) == 0) continue;
+ if (move_make(move_list_move(&moves, i), ©, 1) == 0) continue;
stats->ply++;
- int score = -quiescence(stats, copy, -beta, -alpha);
+ int score = -quiescence(stats, ©, -beta, -alpha);
stats->ply--;
- if (score >= beta) {
- move_list_free(&moves);
- board_free(©);
- return beta;
- }
-
- if (score > alpha) {
- alpha = score;
- }
+ if (score >= beta) return beta;
+ if (score > alpha) alpha = score;
}
- move_list_free(&moves);
- board_free(©);
return alpha;
}
-int negamax(Stats *stats, Board *board, int alpha, int beta, int depth) {
- MoveList *list;
- Board *copy;
- int isCheck = 0;
+int negamax(Stats *stats, const Board *board, int alpha, int beta, int depth) {
int ply = stats->ply;
-
stats->pv_length[ply] = ply;
if (depth == 0) return quiescence(stats, board, alpha, beta);
-
if (ply > MAX_PLY - 1) return evaluate(board);
stats->nodes++;
- copy = board_new();
- list = move_list_generate(NULL, board);
- isCheck = board_isCheck(board);
-
+ int isCheck = board_isCheck(board);
if (isCheck) depth++;
+ Board copy;
+ MoveList list;
+ move_list_generate(&list, board);
+
+ if (stats->follow_pv) enable_pv_scoring(stats, &list);
+
+ move_list_sort(stats, &list);
int legal_moves = 0;
- move_list_sort(stats, list);
- for (int i = 0; i < move_list_size(list); i++) {
- Move move = move_list_move(list, i);
+ for (int i = 0; i < move_list_size(&list); i++) {
+ Move move = move_list_move(&list, i);
- board_copy(board, copy);
- if (move_make(move, copy, 0) == 0) {
+ board_copy(board, ©);
+ if (move_make(move, ©, 0) == 0) {
continue;
}
stats->ply++;
- int score = -negamax(stats, copy, -beta, -alpha, depth - 1);
+ int score = -negamax(stats, ©, -beta, -alpha, depth - 1);
stats->ply--;
legal_moves++;
@@ -176,8 +171,6 @@ int negamax(Stats *stats, Board *board, int alpha, int beta, int depth) {
stats->killer_moves[1][ply] = stats->killer_moves[0][ply];
stats->killer_moves[0][ply] = move;
}
- move_list_free(&list);
- board_free(©);
return beta;
}
@@ -201,8 +194,6 @@ int negamax(Stats *stats, Board *board, int alpha, int beta, int depth) {
return 0;
}
- move_list_free(&list);
- board_free(©);
return alpha;
}
@@ -212,27 +203,28 @@ void move_print_UCI(Move move) {
if (move_promote(move)) printf(" %c", piece_asci(move_piece_promote(move)));
}
-void search_position(Board *board, int depth) {
- Stats *stats = Stats_new();
+void search_position(const Board *board, int depth) {
+ Stats stats = {0};
for (int crnt = 1; crnt <= depth; crnt++) {
- int score = negamax(stats, board, -50000, 50000, crnt);
+ stats.follow_pv = 1;
+ stats.nodes = 0;
+
+ int score = negamax(&stats, board, -50000, 50000, crnt);
printf("info score cp %d depth %d nodes %ld pv ", score, crnt,
- stats->nodes);
+ stats.nodes);
- for (int i = 0; i < stats->pv_length[0]; i++) {
- move_print_UCI(stats->pv_table[0][i]);
+ for (int i = 0; i < stats.pv_length[0]; i++) {
+ move_print_UCI(stats.pv_table[0][i]);
printf(" ");
}
printf("\n");
}
printf("bestmove ");
- move_print_UCI(stats->pv_table[0][0]);
+ move_print_UCI(stats.pv_table[0][0]);
printf("\n");
-
- Stats_free(&stats);
}
void print_info(void) {
diff --git a/src/include/board.h b/src/include/board.h
@@ -12,10 +12,17 @@ enum enumCastle {
typedef enum enumCastle eCastle;
typedef struct Board Board;
+struct Board {
+ U64 color[2];
+ U64 piece[6];
+ eColor side;
+ Square enpassant;
+ eCastle castle;
+};
Board *board_new(void);
void board_free(Board **p);
-void board_copy(Board *self, Board *dest);
+void board_copy(const Board *self, Board *dest);
U64 board_color(const Board *self, eColor color);
U64 board_occupancy(const Board *self);
@@ -26,8 +33,8 @@ Square board_enpassant(const Board *self);
void board_enpassant_set(Board *self, Square target);
-U64 board_pieceSet(Board *self, Piece piece);
-U64 board_piece_attacks(Board *self, Piece piece, Square src);
+U64 board_pieceSet(const Board *self, Piece piece);
+U64 board_piece_attacks(const Board *self, Piece piece, Square src);
void board_piece_capture(Board *self, Piece piece, Piece taken, Square source,
Square target);
diff --git a/src/include/moves.h b/src/include/moves.h
@@ -37,7 +37,7 @@ 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);
-MoveList *move_list_generate(MoveList *moves, Board *board);
+MoveList *move_list_generate(MoveList *moves, const Board *board);
int move_make(Move move, Board *board, int flag);
#define move_source(move) (move.source)
diff --git a/src/include/utils.h b/src/include/utils.h
@@ -23,11 +23,13 @@ extern const U64 notHFile;
#define bit_get(bitboard, square) (((bitboard) >> (square)) & C64(1))
#define bit_set(bitboard, square) ((bitboard) |= C64(1) << (square))
#define bit_pop(bitboard, square) ((bitboard) &= ~(C64(1) << (square)))
+
uint8_t bit_count(U64 bitboard);
uint8_t bit_lsb_index(U64 bitboard);
+#define bit_lsb_pop(bitboard) ((bitboard) &= (bitboard) & ((bitboard)-1))
#define bitboard_for_each_bit(var, bb) \
- for (var = bit_lsb_index(bb); bb; bit_pop(bb, var), var = bit_lsb_index(bb))
+ for (var = bit_lsb_index(bb); bb; bit_lsb_pop(bb), var = bit_lsb_index(bb))
// squares
// clang-format off
diff --git a/src/moves/moves.c b/src/moves/moves.c
@@ -76,12 +76,15 @@ void move_list_print(const MoveList *self) {
move_list_add(moves, move); \
}
-MoveList *move_list_generate(MoveList *moves, Board *board) {
+MoveList *move_list_generate(MoveList *moves, const Board *board) {
Move move;
Square src, tgt;
eColor color = board_side(board);
- if (!moves) moves = move_list_new();
+ if (!moves)
+ moves = move_list_new();
+ else
+ move_list_reset(moves);
// pawn moves
Piece piece = piece_get(PAWN, color);
diff --git a/src/score/score.c b/src/score/score.c
@@ -7,7 +7,7 @@ struct Score_T {
int capture[6];
};
-struct Score_T Scores[] = {
+const struct Score_T Scores[] = {
[PAWN] = {
.value = 100,
.position = {
