stellar

Attack only move generation, general refactor

11 files changed, 132 insertions(+), 125 deletions(-)

diff --git a/ CMakeLists.txt b/ CMakeLists.txt

@@ -3,7 +3,7 @@ set(CMAKE_EXPORT_COMPILE_COMMANDS ON) project( Stellar

VERSION 0.0.28

VERSION 0.0.29

DESCRIPTION "Chess engine written in C" HOMEPAGE_URL https://git.dimitrijedobrota.com/stellar.git LANGUAGES C CXX

diff --git a/ src/engine/engine.cpp b/ src/engine/engine.cpp

@@ -13,7 +13,6 @@ #include "uci.hpp" #include "utils.hpp"

#define MAX_PLY 64

#define FULL_DEPTH 4 #define REDUCTION_LIMIT 3 #define REDUCTION_MOVE 2

@@ -37,7 +36,7 @@ struct Hashe { class TTable { public:

static inline constexpr const uint16_t unknown = 32500;

static inline constexpr const int16_t unknown = 32500;

TTable() {} TTable(U64 size) : table(size, {0}) {}

@@ -112,7 +111,7 @@ 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 uint8_t pv_length[MAX_PLY];

static bool follow_pv; static U64 nodes; static U32 ply;

@@ -157,14 +156,14 @@ std::vector<int> move_list_sort(MoveList &list, const Move best) { return index; }

int evaluate(const Board &board) {

int16_t evaluate(const Board &board) {

Color side = board.get_side(); Color sideOther = (side == Color::BLACK) ? Color::WHITE : Color::BLACK; U64 occupancy = board.get_bitboard_color(side); uint8_t square_i;

int score = 0;

int16_t score = 0;

for (const piece::Type type : piece::TypeIter()) { U64 bitboard = board.get_bitboard_piece(type); bitboard_for_each_bit(square_i, bitboard) {

@@ -182,9 +181,9 @@ int evaluate(const Board &board) { return score; }

int stats_move_make(Board &copy, const Move move, int flag) {

int stats_move_make(Board &copy, const Move move) {

copy = board;

if (!move.make(board, flag)) {

if (!move.make(board)) {

board = copy; return 0; }

@@ -221,7 +220,7 @@ void stats_pv_store(Move move) { pv_length[ply] = pv_length[ply + 1]; }

int quiescence(int16_t alpha, int16_t beta) {

int16_t quiescence(int16_t alpha, int16_t beta) {

if ((nodes & 2047) == 0) { uci::communicate(settings); if (settings->stopped) return 0;

@@ -235,11 +234,10 @@ int quiescence(int16_t alpha, int16_t beta) { if (score > alpha) alpha = score; Board copy;

MoveList list(board);

MoveList list(board, true);

for (int idx : move_list_sort(list, Move())) { const Move move = list[idx];

if (!stats_move_make(copy, list[idx], 1)) continue;

if (!stats_move_make(copy, move)) continue;

score = -quiescence(-beta, -alpha); stats_move_unmake(copy, move);

@@ -255,7 +253,7 @@ int quiescence(int16_t alpha, int16_t beta) { return alpha; }

int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {

int16_t negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) {

int pv_node = (beta - alpha) > 1; Hashe::Flag flag = Hashe::Flag::Alpha; int futility = 0;

@@ -268,14 +266,18 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { } pv_length[ply] = ply;

int score = ttable.read(board, ply, &bestMove, alpha, beta, depth);

if (ply && score != TTable::unknown && !pv_node) return score;

// && fifty >= 100 if (ply && rtable.is_repetition(board.get_hash())) return 0;

int16_t score = ttable.read(board, ply, &bestMove, alpha, beta, depth);

if (ply && score != TTable::unknown && !pv_node) return score;

bool isCheck = board.is_check();

if (isCheck) depth++;

if (depth == 0) { nodes++;

int score = quiescence(alpha, beta);

int16_t score = quiescence(alpha, beta);

// ttable_write(board, ply, bestMove, score, depth, HasheFlag::Exact); return score; }

@@ -285,16 +287,13 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { if (alpha >= beta) return alpha; // if (ply > MAX_PLY - 1) return evaluate(board);

int isCheck = board.is_check();

if (isCheck) depth++;

if (!pv_node && !isCheck) { static constexpr const U32 score_pawn = piece::score(piece::Type::PAWN);

int staticEval = evaluate(board);

int16_t staticEval = evaluate(board);

// evaluation pruning if (depth < 3 && abs(beta - 1) > -MATE_VALUE + 100) {

int marginEval = score_pawn * depth;

int16_t marginEval = score_pawn * depth;

if (staticEval - marginEval >= beta) return staticEval - marginEval; }

@@ -311,7 +310,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { // razoring score = staticEval + score_pawn;

int scoreNew = quiescence(alpha, beta);

int16_t scoreNew = quiescence(alpha, beta);

if (score < beta && depth == 1) { return (scoreNew > score) ? scoreNew : score;

@@ -324,7 +323,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { } // futility pruning condition

static constexpr const int margin[] = {

static constexpr const int16_t margin[] = {

0, piece::score(piece::Type::PAWN), piece::score(piece::Type::KNIGHT),

@@ -333,13 +332,13 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { if (depth < 4 && abs(alpha) < MATE_SCORE && staticEval + margin[depth] <= alpha) futility = 1; }

int legal_moves = 0;

int searched = 0;

uint8_t legal_moves = 0;

uint8_t searched = 0;

MoveList list(board); for (int idx : move_list_sort(list, bestMove)) { const Move move = list[idx];

if (!stats_move_make(copy, move, 0)) continue;

if (!stats_move_make(copy, move)) continue;

legal_moves++; // futility pruning

@@ -408,7 +407,7 @@ int negamax(int16_t alpha, int16_t beta, uint8_t depth, bool null) { return alpha; }

void search_position(const uci::Settings &settingsr) {

Move search_position(const uci::Settings &settingsr) {

int16_t alpha = -SCORE_INFINITY, beta = SCORE_INFINITY; settings = &settingsr;

@@ -421,7 +420,7 @@ void search_position(const uci::Settings &settingsr) { 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();

if (!settings->madeMoves[i].is_repetable()) rtable.clear();

} ply = 0;

@@ -432,45 +431,27 @@ void search_position(const uci::Settings &settingsr) { memset(pv_table, 0x00, sizeof(pv_table)); memset(pv_length, 0x00, sizeof(pv_length));

for (uint8_t depth_crnt = 1; depth_crnt <= settings->depth;) {

for (uint8_t depth = 1; depth <= settings->depth; depth++) {

uci::communicate(settings); if (settings->stopped) break; follow_pv = 1;

int score = negamax(alpha, beta, depth_crnt, true);

int16_t score = negamax(alpha, beta, depth, true);

if ((score <= alpha) || (score >= beta)) { alpha = -SCORE_INFINITY; beta = SCORE_INFINITY;

depth--;

continue; } alpha = score - WINDOW; beta = score + WINDOW;

if (pv_length[0]) {

if (score > -MATE_VALUE && score < -MATE_SCORE) {

std::cout << "info score mate " << -(score + MATE_VALUE) / 2 - 1;

} else if (score > MATE_SCORE && score < MATE_VALUE) {

std::cout << "info score mate " << (MATE_VALUE - score) / 2 + 1;

} else {

std::cout << "info score cp " << score;

}

std::cout << " depth " << (unsigned)depth_crnt;

std::cout << " nodes " << nodes;

std::cout << " pv ";

for (int i = 0; i < pv_length[0]; i++) {

uci::move_print(board, pv_table[0][i]);

std::cout << " ";

}

std::cout << "\n";

}

depth_crnt++;

if (pv_length[0]) uci::pv_print(score, depth, nodes, pv_length, pv_table, board);

}

std::cout << "bestmove ";

uci::move_print(board, pv_table[0][0]);

std::cout << "\n";

settings->board = board;

return pv_table[0][0];

} } // namespace engine

diff --git a/ src/engine/engine.hpp b/ src/engine/engine.hpp

@@ -2,10 +2,13 @@ #define STELLAR_ENGINE_H #include "engine/uci.hpp"

#include "move.hpp"

#include "uci.hpp" namespace engine {

void search_position(const uci::Settings &setting);

Move search_position(const uci::Settings &setting);

} #endif

diff --git a/ src/engine/score.hpp b/ src/engine/score.hpp

@@ -1,6 +1,8 @@ #ifndef STELLAR_SCORE_H #define STELLAR_SCORE_H

#define MAX_PLY 64

#define SCORE_INFINITY 32000 #define MATE_VALUE 31000 #define MATE_SCORE 30000

diff --git a/ src/engine/uci.cpp b/ src/engine/uci.cpp

@@ -20,18 +20,31 @@ void move_print(const Board &board, Move move) { if (move.is_promote()) std::cout << piece::get_code(move.promoted(), board.get_side()); }

void communicate(const uci::Settings *settings) {

if (!settings->infinite && uci::get_time_ms() > settings->stoptime) settings->stopped = true;

void pv_print(int16_t score, uint8_t depth, uint64_t nodes, uint8_t pv_length[MAX_PLY],

Move pv_table[MAX_PLY][MAX_PLY], const Board &board) {

if (score > -MATE_VALUE && score < -MATE_SCORE) {

std::cout << "info score mate " << -(score + MATE_VALUE) / 2 - 1;

} else if (score > MATE_SCORE && score < MATE_VALUE) {

std::cout << "info score mate " << (MATE_VALUE - score) / 2 + 1;

} else {

std::cout << "info score cp " << score;

}

/*

if (std::cin.peek() == EOF || std::cin.peek() == '\n') {

std::cin.clear();

std::cout << " depth " << (unsigned)depth;

std::cout << " nodes " << nodes;

std::cout << " pv ";

for (int i = 0; i < pv_length[0]; i++) {

uci::move_print(board, pv_table[0][i]);

std::cout << " ";

}

std::cout << "\n";

}

void communicate(const uci::Settings *settings) {

if (!settings->infinite && uci::get_time_ms() > settings->stoptime) {

settings->stopped = true;

return; }

std::string command;

std::cin >> command;

if (command == "stop" || command == "quit") settings->stopped = true;

*/

} inline bool parse_move(const Board &board, Move &move, const std::string &move_string) {

@@ -148,8 +161,11 @@ void loop(void) { if (!time) settings.infinite = true;

// std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

engine::search_position(settings);

const Move best = engine::search_position(settings);

std::cout << "bestmove ";

uci::move_print(settings.board, best);

std::cout << "\n";

settings.newgame = false; } }

diff --git a/ src/engine/uci.hpp b/ src/engine/uci.hpp

@@ -4,15 +4,17 @@ #include "board.hpp" #include "move.hpp" #include "movelist.hpp"

#include "score.hpp"

#include "utils.hpp" namespace uci { struct Settings {

mutable Board board;

MoveList searchMoves; MoveList madeMoves;

Board board;

uint32_t starttime; uint32_t stoptime; uint16_t depth = 64;

@@ -28,6 +30,8 @@ struct Settings { }; void loop(void);

void pv_print(int16_t score, uint8_t depth, uint64_t nodes, uint8_t pv_length[MAX_PLY],

Move pv_table[MAX_PLY][MAX_PLY], const Board &board);

void move_print(const Board &board, Move move); void communicate(const uci::Settings *settings); uint32_t get_time_ms(void);

diff --git a/ src/move/move.cpp b/ src/move/move.cpp

@@ -22,7 +22,7 @@ void Move::piece_move(Board &board, piece::Type type, Color color, Square source using piece::Type::PAWN; using piece::Type::ROOK;

bool Move::make(Board &board, bool attack_only) const {

bool Move::make(Board &board) const {

static constexpr const int castling_rights[64] = { // clang-format off 13, 15, 15, 15, 12, 15, 15, 14,

@@ -36,63 +36,58 @@ bool Move::make(Board &board, bool attack_only) const { // clang-format on };

if (attack_only) {

if (is_capture()) return make(board, false);

return 0;

const Color color = board.get_side();

const Color colorOther = color == Color::BLACK ? Color::WHITE : Color::BLACK;

const Square source = this->source();

const Square target = this->target();

const Square ntarget =

static_cast<Square>(to_underlying(this->target()) + (color == Color::WHITE ? -8 : +8));

const piece::Type piece = board.get_square_piece_type(source);

if (!is_capture()) {

if (is_promote()) {

piece_remove(board, piece, color, source);

piece_set(board, promoted(), color, target);

} else {

piece_move(board, piece, color, source, target);

}

} else {

const Color color = board.get_side();

const Color colorOther = color == Color::BLACK ? Color::WHITE : Color::BLACK;

const Square source = this->source();

const Square target = this->target();

const Square ntarget =

static_cast<Square>(to_underlying(this->target()) + (color == Color::WHITE ? -8 : +8));

const piece::Type piece = board.get_square_piece_type(source);

if (!is_capture()) {

if (is_promote()) {

piece_remove(board, piece, color, source);

piece_set(board, promoted(), color, target);

} else {

piece_move(board, piece, color, source, target);

}

const piece::Type captured = board.get_square_piece_type(target);

if (is_enpassant()) {

piece_move(board, piece, color, source, target);

piece_remove(board, PAWN, colorOther, ntarget);

} else if (is_promote()) {

piece_remove(board, piece, color, source);

piece_remove(board, captured, colorOther, target);

piece_set(board, promoted(), color, target);

} else {

const piece::Type captured = board.get_square_piece_type(target);

if (is_enpassant()) {

piece_move(board, piece, color, source, target);

piece_remove(board, PAWN, colorOther, ntarget);

} else if (is_promote()) {

piece_remove(board, piece, color, source);

piece_remove(board, captured, colorOther, target);

piece_set(board, promoted(), color, target);

} else {

piece_remove(board, captured, colorOther, target);

piece_move(board, piece, color, source, target);

}

piece_remove(board, captured, colorOther, target);

piece_move(board, piece, color, source, target);

}

}

board.set_enpassant(is_double() ? ntarget : Square::no_sq);

board.set_enpassant(is_double() ? ntarget : Square::no_sq);

if (is_castle()) {

if (color == Color::WHITE) {

if (is_castle_king()) piece_move(board, ROOK, Color::WHITE, Square::h1, Square::f1);

if (is_castle_queen()) piece_move(board, ROOK, Color::WHITE, Square::a1, Square::d1);

} else {

if (is_castle_king()) piece_move(board, ROOK, Color::BLACK, Square::h8, Square::f8);

if (is_castle_queen()) piece_move(board, ROOK, Color::BLACK, Square::a8, Square::d8);

}

if (is_castle()) {

if (color == Color::WHITE) {

if (is_castle_king()) piece_move(board, ROOK, Color::WHITE, Square::h1, Square::f1);

if (is_castle_queen()) piece_move(board, ROOK, Color::WHITE, Square::a1, Square::d1);

} else {

if (is_castle_king()) piece_move(board, ROOK, Color::BLACK, Square::h8, Square::f8);

if (is_castle_queen()) piece_move(board, ROOK, Color::BLACK, Square::a8, Square::d8);

}

}

board.and_castle(castling_rights[to_underlying(this->source())] &

castling_rights[to_underlying(this->target())]);

board.and_castle(castling_rights[to_underlying(this->source())] &

castling_rights[to_underlying(this->target())]);

if (!board.is_check()) {

board.switch_side();

return 1;

}

return 0;

if (!board.is_check()) {

board.switch_side();

return 1;

}

return 0;

} std::ostream &operator<<(std::ostream &os, Move move) {

diff --git a/ src/move/move.hpp b/ src/move/move.hpp

@@ -53,7 +53,7 @@ struct Move { const piece::Type promoted(void) const { return static_cast<piece::Type>((flags_i & 0x3) + 1); }

bool make(Board &board, bool attack_only = false) const;

bool make(Board &board) const;

friend std::ostream &operator<<(std::ostream &os, Move move);

diff --git a/ src/move/movelist.cpp b/ src/move/movelist.cpp

@@ -12,7 +12,7 @@ using piece::Type::PAWN;

void MoveList::generate(const Board &board) {

void MoveList::generate(const Board &board, bool attacks_only) {

uint8_t src_i, tgt_i; Color color = board.get_side();

@@ -25,7 +25,7 @@ void MoveList::generate(const Board &board) { bitboard_for_each_bit(src_i, bitboard) { const Square src = static_cast<Square>(src_i); const Square tgt = static_cast<Square>(tgt_i = src_i + add);

if (!board.is_square_occupied(tgt)) {

if (!attacks_only && !board.is_square_occupied(tgt)) {

if (pawn_canPromote(color, src)) { list.push_back({src, tgt, Move::PKNIGHT}); list.push_back({src, tgt, Move::PBISHOP});

@@ -70,11 +70,18 @@ void MoveList::generate(const Board &board) { U64 attack = board.get_bitboard_piece_moves(type, color, src); bitboard_for_each_bit(tgt_i, attack) { const Square tgt = static_cast<Square>(tgt_i);

list.push_back({src, tgt, board.is_square_occupied(tgt) ? Move::CAPTURE : Move::QUIET});

if (board.is_square_occupied(tgt)) {

list.push_back({src, tgt, Move::CAPTURE});

} else {

if (attacks_only) continue;

list.push_back({src, tgt, Move::QUIET});

}

} } }

if (attacks_only) return;

// Castling if (color == Color::WHITE) { if (!board.is_square_attacked(Square::e1, Color::BLACK)) {

diff --git a/ src/move/movelist.hpp b/ src/move/movelist.hpp

@@ -12,13 +12,12 @@ class MoveList { private: using list_t = std::vector<Move>;

using index_t = std::vector<int>;

public: MoveList() : list(){};

MoveList(const Board &board) : list() {

MoveList(const Board &board, bool attacks_only = false) : list() {

list.reserve(256);

generate(board);

generate(board, attacks_only);

} void clear() { list.clear(); }

@@ -30,7 +29,7 @@ class MoveList { friend std::ostream &operator<<(std::ostream &os, const MoveList &list); private:

void generate(const Board &board);

void generate(const Board &board, bool attacks_only);

list_t list; };

diff --git a/ src/perft/perft.cpp b/ src/perft/perft.cpp

@@ -18,7 +18,7 @@ class Perft { Perft(semaphore_t &sem) : sem(sem) {} void operator()(const Board &board_start, Move move, int depth) { Board board = board_start;

if (!move.make(board, 0)) return;

if (!move.make(board)) return;

sem.acquire(); // debug(board_start, move, board);

@@ -63,7 +63,7 @@ class Perft { const MoveList list(board); for (int i = 0; i < list.size(); i++) { Board copy = board;

if (!list[i].make(copy, 0)) continue;

if (!list[i].make(copy)) continue;

// debug(board, list[i], copy); if (depth != 1) test(copy, depth - 1);