I'm writing (or at least trying to write) a chess engine in C++. This is the first time I write code in C++, and I use this project to practice. Anyway, I'm following the general guidelines of a tutorial from YouTube and chess programming wiki page but I'm trying to come with improvements on my own.
At the moment I'm at a stage where I try to pre-calculate all the possible attacks before hand to get better results later in-game. In order to precalculate I use a method called magic bitboards (a kind of hashing technique) and in order to generate the keys I use a dumb brute force algorithm which take relatively long time.
I came up with this solution (with the assistance of others of course) where when the program is running I check if the "magic numbers" were produced already; if yes, then initialise from the file, otherwise generate them now.
Is the way I did it decent?
And if not, what could I do better?
The main goal is to improve the time it takes until the program is ready to start a game.
I'm adding a snippet of the relevant code for review; the entire project (incomplete) is in a GitHub repo.
Here is the part from attack.cpp. The purpose of this part is to create and initialize possible attacks of the sliding pieces (rook, bishop)
- generating the attack "on the fly"
- generating occupancy maps
- using magic bitboards to hash the attacks.
- using the magic bitboards to get the attacks in-game with
get_bishop_attack()&get_rook_attack().
The part I've asked the question for is the part where I generate the magic number which takes the most because it is a simple brute force algorithm.
board.h
#ifndef __BOARD__H_
#define __BOARD__H_
#include <stdint.h>
#include <array>
#include <string_view>
#include <string>
enum Color{White, Black, Both};
enum Sliders {rook, bishop};
/* Bit manipulations */
#define get_bit(bit_board, square) ((bit_board) & (1ULL << (square)))
#define set_bit(bit_board, square) ((bit_board) |= (1ULL << (square)))
#define clear_bit(bit_board, square) ((bit_board) &= ~(1ULL << (square)))
int count_bits(uint64_t bitboard);
int get_lsb_index(uint64_t bitboard);
enum squares {
a8 = 0, 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 = -1
};
constexpr std::array<std::string_view, 64> index_to_square = {
"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"
};
class Bitboards{
public:
enum Castling {WKS = 1, WQS = 2, BKS = 4, BQS = 8};
enum Pieces {P, N, B, R, Q, K, p, n, b, r, q, k};
/*** Constructors ***/
Bitboards();
/*** Methods ***/
void print_board();
void attacked_squares();
bool is_square_attacked(int square, Color color);
private:
/*** Variables ***/
std::array<uint64_t, 12> bitboards{};
std::array<uint64_t, 3> occ_bitboards{};
static constexpr std::string_view ascii_pieces{"PNBRQKpnbrqk"};
int en_passant_sq = no_sq;
int castle;
int side = Color::White;
std::string starting_pos{"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1"};
/*** Methods ***/
int piece_to_int(char);
void parse_fen(std::string);
};
// Constants masking the A, H, GH and AB files.
constexpr uint64_t NOT_FILE_A = 18374403900871474942UL;
constexpr uint64_t NOT_FILE_H = 9187201950435737471UL;
constexpr uint64_t NOT_FILE_GH = 4557430888798830399UL;
constexpr uint64_t NOT_FILE_AB = 18229723555195321596UL;
void print_board(uint64_t bit_board);
#endif
board.cpp
#include "board.h"
#include <iostream>
#include <array>
/****** Constructors ******/
Bitboards::Bitboards(){
parse_fen(this->starting_pos);
}
void print_board(uint64_t bit_board){
for (int rank = 0; rank < 8; rank++){
for (int file = 0; file < 8; file++){
if (file == 0){
std::cout << 8 - rank << " ";
}
int square = rank * 8 + file;
std::cout << ((bit_board & (1ULL << square)) ? " 1" : " 0");
}
std::cout << std::endl;
}
std::cout << " a b c d e f g h" << std::endl;
printf("\n Bitboard: %lud\n\n", bit_board);
}
int count_bits(uint64_t bitboard){
int counter = 0;
while(bitboard){
counter++;
bitboard &= bitboard - 1;
}
return counter;
}
int get_lsb_index(uint64_t bitboard){
if (!bitboard)
return -1;
else
return count_bits((bitboard & -bitboard) -1);
}
void Bitboards::print_board(){
for(int rank = 0; rank < 8; rank ++){
for(int file = 0; file < 8; file++){
if(file == 0)
std::cout << 8 - rank << " ";
int square = rank * 8 + file;
bool piece_found = false;
for(int piece = P; piece <= k; piece++){
if (this->bitboards[piece] & (1ULL << square)){
std::cout << " " << ascii_pieces[piece];
piece_found = true;
break;
}
}
if(!piece_found){
std::cout << " .";
}
}
std::cout << std::endl;
}
std::cout << " a b c d e f g h" << std::endl;
std::cout << std::endl << std::endl;
std::cout << " Side: " << ((this->side == Color::White) ? "White" : "Black") << std::endl;
std::cout << " Enpassant: " << ((this->en_passant_sq == no_sq) ? "no" : index_to_square[this->en_passant_sq]) << std::endl;
std::cout << " Castling: " << ((this->castle & WKS) ? 'K': '-') << ((this->castle & WQS) ? 'Q': '-') <<
((this->castle & BKS) ? 'k': '-') << ((this->castle & BQS) ? 'q': '-') << std::endl;
}
void Bitboards::parse_fen(std::string fen_string){
/*** Setting boards && board state to empty ***/
this->bitboards = {};
this->occ_bitboards = {};
this->side = Color::White;
this->en_passant_sq = no_sq;
this->castle = 0;
/*** Parsing the pieces location ***/
auto it = fen_string.begin();
for(int rank = 0; rank < 8; rank++){
for(int file = 0; file < 8; file++){
int square = rank * 8 + file;
if(isalpha(*it)){
int bb = piece_to_int(*it);
set_bit(this->bitboards[bb], square);
std::advance(it, 1);
}
if(isdigit(*it)){
file += (*it - '0');
// If the square is empty fix shift
int piece = -1;
for(int bb_piece = Bitboards::P; bb_piece <= Bitboards::k; bb_piece++){
if(get_bit(bitboards[bb_piece],square)){
piece = bb_piece;
}
}
if(piece == -1)
file--;
std::advance(it,1);
}
if(*it == '/'){
std::advance(it,1);
}
}
}
/*** Parsing board state ***/
while(isspace(*it))
std::advance(it,1);
this->side = (*it == 'w') ? Color::White : Color::Black; // Side to move
std::advance(it,1);
while(isspace(*it))
std::advance(it,1);
// Getting castling rights
while(!isspace(*it)){
switch (*it){
case 'K':
this->castle |= WKS; break;
case 'Q':
this->castle |= WQS; break;
case 'k':
this->castle |= BKS; break;
case 'q':
this->castle |= BQS; break;
case '-': break;
}
std::advance(it,1);
}
while(isspace(*it))
std::advance(it,1);
if(*it != '-'){
int f = (*it - 'a');
int r = 8 - ((*(it+1)) -'0');
this->en_passant_sq = r * 8 + f;
}
/*** Init occupancy boards ***/
for(int piece = P; piece <= K; piece++){
this->occ_bitboards[White] |= this->bitboards[piece];
this->occ_bitboards[Both] |= this->bitboards[piece];
}
for(int piece = p; piece <= k; piece++){
this->occ_bitboards[Black] |= this->bitboards[piece];
this->occ_bitboards[Both] |= this->bitboards[piece];
}
}
int Bitboards::piece_to_int(char c){
std::array<std::array<char, 2> ,12> pieces_to_int{
{{'P', Bitboards::P}, {'N', Bitboards::N},{'B', Bitboards::B},
{'R', Bitboards::R},{'Q', Bitboards::Q},{'K', Bitboards::K},
{'p', Bitboards::p},{'n', Bitboards::n},{'b', Bitboards::b},
{'r', Bitboards::r},{'q', Bitboards::q},{'k', Bitboards::k}}
};
for(const auto& piece: pieces_to_int){
if(piece[0] == c)
return piece[1];
}
return -1;
}
int get_lsb_index(uint64_t bitboard){
if (!bitboard)
return -1;
else
return count_bits((bitboard & -bitboard) -1);
}
attacks.h
#ifndef __ATTACKS__H_
#define __ATTACKS__H_
#include <stdint.h>
#include <array>
/****** INITIALIZE ATTACKS ******/
// The engige pre-computes all possible attacks in order to be faster in-game.
// Leaping pieces: pawn, knight, king.
void init_pawn_attack();
void init_knight_attack();
void init_king_attack();
// Sliding pieces: rook, bishop.
void init_magic_numbers();
void init_sliders_attack(Sliders slider);
/****** GETTERS ******/
// Getting the pieces attack in-game.
uint64_t get_pawn_attack(Color color, int square);
uint64_t get_knight_attack(int square);
uint64_t get_king_attack(int square);
uint64_t get_bishop_attack(int square, uint64_t block);
uint64_t get_rook_attack(int square, uint64_t block);
uint64_t get_queen_attack(int square, uint64_t block);
// TESTS
// uint64_t get_bishop_attack_on_the_fly(int square, uint64_t block);
// uint64_t get_bishop_attack(int square, uint64_t block);
#endif
attacks.cpp
#include <iostream>
#include "board.h"
#include "xorshift_random.h" //XOR32SHIFT Algorithm to create a pseudo random number
#include <istream>
#include <fstream>
/****** LEAPING PIECES ATTACKS ******/
// Leaping pieces precomputed attacks (pawn, knight, king)
static std::array<std::array<uint64_t, 64>, 2> pawn_attack;
static std::array<uint64_t, 64> knight_attack;
static std::array<uint64_t, 64> king_attack;
static uint64_t get_pawn_attack_mask(Color color, int square){
uint64_t attack = 0;
uint64_t bit = 1ULL << square;
if (color == Color::White){
attack |= ((bit >> 7) & NOT_FILE_A);
attack |= ((bit >> 9) & NOT_FILE_H);
} else {
attack |= (bit << 7) & NOT_FILE_H;
attack |= (bit << 9) & NOT_FILE_A;
}
return attack;
}
void init_pawn_attack(){
for(int i = 0; i < 64; i++){
pawn_attack[Color::White][i] = get_pawn_attack_mask(Color::White, i);
pawn_attack[Color::Black][i] = get_pawn_attack_mask(Color::Black, i);
}
}
uint64_t get_pawn_attack(Color color, int square){
return pawn_attack[color][square];
}
static uint64_t get_knight_attack_mask(int square){
uint64_t attack = 0UL;
uint64_t bit = 1ULL << square;
if ((bit >> 6) & NOT_FILE_AB) attack |= bit >> 6;
if ((bit >> 10) & NOT_FILE_GH) attack |= bit >> 10;
if ((bit >> 15) & NOT_FILE_A) attack |= bit >> 15;
if ((bit >> 17) & NOT_FILE_H) attack |= bit >> 17;
if ((bit << 6) & NOT_FILE_GH) attack |= bit << 6;
if ((bit << 10) & NOT_FILE_AB) attack |= bit << 10;
if ((bit << 15) & NOT_FILE_H) attack |= bit << 15;
if ((bit << 17) & NOT_FILE_A) attack |= bit << 17;
return attack;
}
void init_knight_attack(){
for(int i = 0; i < 64; i++){
knight_attack[i] = get_knight_attack_mask(i);
}
}
uint64_t get_knight_attack(int square){
return knight_attack[square];
}
static uint64_t get_king_attack_mask(int square){
uint64_t attack = 0UL;
uint64_t bit = 1ULL << square;
if ((bit >> 1) & NOT_FILE_H) attack |= bit >> 1;
if ((bit << 1) & NOT_FILE_A) attack |= bit << 1;
if ((bit >> 7) & NOT_FILE_A) attack |= bit >> 7;
if ((bit << 7) & NOT_FILE_H) attack |= bit << 7;
if ((bit >> 9) & NOT_FILE_H) attack |= bit >> 9;
if ((bit << 9) & NOT_FILE_A) attack |= bit << 9;
attack |= bit >> 8;
attack |= bit << 8;
return attack;
}
void init_king_attack(){
for (int i = 0; i < 64; i++){
king_attack[i] = get_king_attack_mask(i);
}
}
uint64_t get_king_attack(int square){
return king_attack[square];
}
/****** SLIDING PIECES ATTACKS ******/
// Sliding pieces precomputed attack, for every possible occupancy.
static std::array<std::array<uint64_t, 512> ,64>bishop_attacks;
static std::array<std::array<uint64_t, 4096> ,64>rook_attacks;
// Magic numbers to get fast access to the sliding pieces attacks
std::array<uint64_t,64> bishop_magic_numbers;
std::array<uint64_t,64> rook_magic_numbers;
// Sliding pieces attack masks
std::array<uint64_t, 64>bishop_masks;
std::array<uint64_t, 64> rook_masks;
// Mapping the number of relevant bits in an occupancy board of bishop attack from each square.
const std::array<int, 64> bishop_relevant_bits = {
6, 5, 5, 5, 5, 5, 5, 6,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 5, 5, 5, 5, 5, 5, 6
};
// Mapping the number of relevant bits in an occupancy board of rook attack from each square.
const std::array<int, 64> rook_relevant_bits = {
12, 11, 11, 11, 11, 11, 11, 12,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
12, 11, 11, 11, 11, 11, 11, 12
};
static uint64_t mask_bishop_occupancy(int square){
uint64_t occupancy = 0;
int t_file = square % 8;
int t_rank = square / 8;
for(int f = t_file + 1, r = t_rank + 1; f <=6 && r<=6; f++, r++) occupancy |= (1ULL << (r * 8 + f));
for(int f = t_file + 1, r = t_rank - 1; f <=6 && r>=1; f++, r--) occupancy |= (1ULL << (r * 8 + f));
for(int f = t_file - 1, r = t_rank + 1; f >=1 && r<=6; f--, r++) occupancy |= (1ULL << (r * 8 + f));
for(int f = t_file - 1, r = t_rank - 1; f >=1 && r>=1; f--, r--) occupancy |= (1ULL << (r * 8 + f));
return occupancy;
}
static uint64_t get_bishop_attack_on_the_fly(int square, uint64_t block){
uint64_t attacks = 0;
int t_file = square % 8;
int t_rank = square / 8;
for(int f = t_file + 1, r = t_rank + 1; f <=7 && r<=7; f++, r++){
attacks |= (1ULL << (r * 8 + f));
if(((1ULL << (r * 8 + f)) & block)){
break;
}
}
for(int f = t_file + 1, r = t_rank - 1; f <=7 && r>=0; f++, r--){
attacks |= (1ULL << (r * 8 + f));
if(((1ULL << (r * 8 + f)) & block)){
break;
}
}
for(int f = t_file - 1, r = t_rank + 1; f >=0 && r<=7; f--, r++){
attacks |= (1ULL << (r * 8 + f));
if(((1ULL << (r * 8 + f)) & block)){
break;
}
}
for(int f = t_file - 1, r = t_rank - 1; f >=0 && r>=0; f--, r--){
attacks |= (1ULL << (r * 8 + f));
if(((1ULL << (r * 8 + f)) & block)){
break;
}
}
return attacks;
}
static uint64_t mask_rook_occupancy(int square){
uint64_t occupancy = 0;
int t_file = square % 8;
int t_rank = square / 8;
for(int f = t_file + 1; f <= 6; f++) occupancy |= (1ULL << (t_rank * 8 + f));
for(int f = t_file - 1; f >= 1; f--) occupancy |= (1ULL << (t_rank * 8 + f));
for(int r = t_rank + 1; r <= 6; r++) occupancy |= (1ULL << (r * 8 + t_file));
for(int r = t_rank - 1; r >= 1; r--) occupancy |= (1ULL << (r * 8 + t_file));
return occupancy;
}
static uint64_t get_rook_attack_on_the_fly(int square, uint64_t block){
uint64_t attacks = 0;
int t_file = square % 8;
int t_rank = square / 8;
for(int f = t_file + 1; f <=7; f++){
attacks |= (1ULL << (t_rank * 8 + f));
if(((1ULL << (t_rank * 8 + f)) & block)){
break;
}
}
for(int f = t_file - 1; f >= 0 ; f--){
attacks |= (1ULL << (t_rank * 8 + f));
if(((1ULL << (t_rank * 8 + f)) & block)){
break;
}
}
for(int r = t_rank + 1; r<=7;r++){
attacks |= (1ULL << (r * 8 + t_file));
if(((1ULL << (r * 8 + t_file)) & block)){
break;
}
}
for(int r = t_rank - 1; r>=0;r--){
attacks |= (1ULL << (r * 8 + t_file));
if(((1ULL << (r * 8 + t_file)) & block)){
break;
}
}
return attacks;
}
static uint64_t set_occupanacies(int index, int bits_in_mask, uint64_t attack_mask){
uint64_t occupancy = 0ULL;
for (int count = 0; count < bits_in_mask; count++){
int square = get_lsb_index(attack_mask);
clear_bit(attack_mask, square);
if (index & (1 << count))
occupancy |= (1ULL << square);
}
return occupancy;
}
uint64_t generate_magic_number(){
return get_random_U64_number() & get_random_U64_number() & get_random_U64_number();
}
uint64_t find_magic_number(int square, int relevant_bits, Sliders slider){
std::array<uint64_t, 4096> occupancies;
std::array<uint64_t, 4096> attacks;
std::array<uint64_t, 4096> used_attacks;
uint64_t attack_mask = (slider == Sliders::bishop) ? mask_bishop_occupancy(square) : mask_rook_occupancy(square);
int occupancy_indices = 1 << relevant_bits;
for(int index = 0; index < occupancy_indices; index ++){
occupancies[index] = set_occupanacies(index, relevant_bits, attack_mask);
attacks[index] = (slider == Sliders::bishop) ? get_bishop_attack_on_the_fly(square, occupancies[index]) : get_rook_attack_on_the_fly(square, occupancies[index]);
}
// Test magic numbers
for(int random_count = 0; random_count < 100000000; random_count++){
uint64_t magic_number = generate_magic_number();
if(count_bits((attack_mask * magic_number) & 0xFF00000000000000) < 6) continue;
used_attacks = {};
int index, fail;
for(index = 0, fail = 0; !fail && index < occupancy_indices; index++){
int magic_index = (int)((occupancies[index] * magic_number) >> (64 - relevant_bits));
if(used_attacks[magic_index] == 0ULL)
used_attacks[magic_index] = attacks[index];
else if(used_attacks[magic_index] != attacks[index])
fail = 1;
}
if (!fail)
return magic_number;
}
std::cout << "Magic number failed!" << std::endl;
return 0ULL;
}
void get_magic_numbers(){
std::ofstream file("../magic_numbers.txt");
for(int square = 0; square < 64; square++){
rook_magic_numbers[square] = find_magic_number(square, rook_relevant_bits[square], Sliders::rook);
file << rook_magic_numbers[square] << std::endl;
}
for(int square = 0; square < 64; square++){
bishop_magic_numbers[square] = find_magic_number(square, bishop_relevant_bits[square], Sliders::bishop);
file << bishop_magic_numbers[square] << std::endl;
}
}
void init_magic_numbers(){
std::ifstream file("../magic_numbers.txt");
if (!file.is_open()) {
get_magic_numbers();
return;
}
std::string line;
for(int i=0; i<64; i++){
if (std::getline(file, line)) {
rook_magic_numbers[i] = std::stoull(line);
}
}
for(int i=0; i<64; i++){
if(std::getline(file, line)) {
bishop_magic_numbers[i] = std::stoull(line);
}
}
file.close();
}
void init_sliders_attack(Sliders slider){
for(int square = 0; square < 64; square++){
bishop_masks[square] = mask_bishop_occupancy(square);
rook_masks[square] = mask_rook_occupancy(square);
uint64_t attack_mask = (slider == Sliders::bishop) ? bishop_masks[square] : rook_masks[square];
int relevant_bits = count_bits(attack_mask);
uint64_t occupancy_indices = (1 << relevant_bits);
for(int index = 0; index < occupancy_indices; index++){
// Rook
if(slider == Sliders::rook){
uint64_t occupancy = set_occupanacies(index, relevant_bits, attack_mask);
int magic_index = (occupancy * rook_magic_numbers[square]) >> (64 - rook_relevant_bits[square]);
rook_attacks[square][magic_index] = get_rook_attack_on_the_fly(square, occupancy);
}
// Bishop
else if(slider == Sliders::bishop){
uint64_t occupancy = set_occupanacies(index, relevant_bits, attack_mask);
int magic_index = (occupancy * bishop_magic_numbers[square]) >> (64 - bishop_relevant_bits[square]);
bishop_attacks[square][magic_index] = get_bishop_attack_on_the_fly(square, occupancy);
}
}
}
}
uint64_t get_bishop_attack(int square, uint64_t block){
block &= bishop_masks[square];
block *= bishop_magic_numbers[square];
block >>= 64 - bishop_relevant_bits[square];
return bishop_attacks[square][block];
}
uint64_t get_rook_attack(int square, uint64_t block){
block &= rook_masks[square];
block *= rook_magic_numbers[square];
block >>= 64 - rook_relevant_bits[square];
return rook_attacks[square][block];
}
uint64_t get_queen_attack(int square ,uint64_t block){
uint64_t queen_att = 0ULL;
queen_att |= get_bishop_attack(square, block);
queen_att |= get_rook_attack(square, block);
return queen_att;
}
constexprexpressions, and store them as variables in your program. It will be much more efficient to load these from memory than to read and parse them from a text file. \$\endgroup\$constexpr, is to have a program generate a source file with the results that you can compile and link with your program. \$\endgroup\$