I am currently writing a bitboard-based Chess Engine in C++, and I recently finished the move generation. I am using move-lookup-tables that get pre-calculated at application startup for sliding and non-sliding pieces. For the sliding pieces I implemented magic bitboards, which get handled in the MagicBitboards class (should be pretty irrelevant here, so I did not include them in the question).
The move generator now successfully passes multiple perft() test positions, but it is still pretty slow and I feel like the implementation is all over the place code-wise (and much longer than it should probably be). I tried to summarize and generalize functions as much as possible, but somehow there always is a justification for all the extra functions to exist on their own (most of the time, I feel like the code would just get completely un-readable if I packed more similar but different functionality in the same function).
Most of the CPU calls get wasted in the check_for_legality() function, because everything else is basically just looking up moves in pre-calculated arrays and a few bit-wise operations.
If you have any suggestions how my code could be made more readable or performant, please share your insight! Thank you very much!
perft() results for the initial position at depth 5:
a2a4: 1
a2a3: 1
b1a3: 1
b1c3: 1
b2b4: 1
b2b3: 1
c2c3: 1
c2c4: 1
d2d3: 1
d2d4: 1
e2e4: 1
e2e3: 1
f2f4: 1
f2f3: 1
g2g4: 1
g1h3: 1
g1f3: 1
g2g3: 1
h2h3: 1
h2h4: 1
Depth: 1
Total nodes: 20
Total time: 1ms/0.001s
a2a4: 20
a2a3: 20
b1a3: 20
b1c3: 20
b2b4: 20
b2b3: 20
c2c3: 20
c2c4: 20
d2d3: 20
d2d4: 20
e2e4: 20
e2e3: 20
f2f4: 20
f2f3: 20
g2g4: 20
g1h3: 20
g1f3: 20
g2g3: 20
h2h3: 20
h2h4: 20
Depth: 2
Total nodes: 400
Total time: 1ms/0.001s
a2a4: 420
a2a3: 380
b1a3: 400
b1c3: 440
b2b4: 421
b2b3: 420
c2c3: 420
c2c4: 441
d2d3: 539
d2d4: 560
e2e4: 600
e2e3: 599
f2f4: 401
f2f3: 380
g2g4: 421
g1h3: 400
g1f3: 440
g2g3: 420
h2h3: 380
h2h4: 420
Depth: 3
Total nodes: 8902
Total time: 15ms/0.015s
a2a4: 9329
a2a3: 8457
b1a3: 8885
b1c3: 9755
b2b4: 9332
b2b3: 9345
c2c3: 9272
c2c4: 9744
d2d3: 11959
d2d4: 12435
e2e4: 13160
e2e3: 13134
f2f4: 8929
f2f3: 8457
g2g4: 9328
g1h3: 8881
g1f3: 9748
g2g3: 9345
h2h3: 8457
h2h4: 9329
Depth: 4
Total nodes: 197281
Total time: 291ms/0.291s
a2a4: 217832
a2a3: 181046
b1a3: 198572
b1c3: 234656
b2b4: 216145
b2b3: 215255
c2c3: 222861
c2c4: 240082
d2d3: 328511
d2d4: 361790
e2e4: 405385
e2e3: 402988
f2f4: 198473
f2f3: 178889
g2g4: 214048
g1h3: 198502
g1f3: 233491
g2g3: 217210
h2h3: 181044
h2h4: 218829
Depth: 5
Total nodes: 4865609
Total time: 6752ms/6.752s
MoveGenerator.h:
#ifndef MOVEGENERATOR_H
#define MOVEGENERATOR_H
#include "Bitboard.h"
#include "globals.h"
#include "GameState.h"
#include "MagicBitboards.h"
#include <array>
#include <vector>
namespace Chess_Engine
{
class MoveGenerator
{
using NonMagicAttackTable = std::array<Bitboard, 64>;
using BishopAttackTable = std::array<std::array<Bitboard, 512>, 64>;
using RookAttackTable = std::array<std::array<Bitboard, 4096>, 64>;
public:
MoveGenerator();
virtual ~MoveGenerator();
std::vector<Move> generate_legal_moves(const GameState& game_state); // returns all legal moves for a given position
std::vector<Move> generate_pseudo_legal_moves(const GameState& game_state); // returns all pseudo-legal moves for a given position
private:
// checks a single move for legality and returns result
bool check_for_legality(const GameState& game_state, Move move, BoardState board_state, const Bitboard& all_enemy_attacks, const Bitboard& king_position, const Bitboard& king_attack_paths, const Bitboard& direct_king_attackers, const Bitboard& pinned, const Bitboard& pinners, std::unordered_map<int32_t, Bitboard>* allowed_pinned_move_path_for_index, bool king_in_check);
bool all_attackers_captured(Move move, const Bitboard& direct_king_attackers, bool white_to_move);
bool all_attack_paths_blocked(Move move, const Bitboard& king_attack_paths);
// methods for filling move vector
void add_king_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, bool castle_short, bool castle_long);
void add_knight_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces);
void add_pawn_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, bool is_white_to_move, bool en_passant_possible, uint32_t en_passant_target_square);
void add_bishop_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces);
void add_rook_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces);
// methods for filling threat bitboard
void add_king_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces);
// -> also adds knights to direct_king_attackers if necessary
void add_knight_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, Bitboard* direct_king_attackers, const Bitboard& king_position);
// -> also adds pawns to direct_king_attackers if necessary
void add_pawn_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, Bitboard* direct_king_attackers, const Bitboard& king_position, bool is_white_to_move);
void add_bishop_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, const Bitboard& king_position);
void add_rook_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, const Bitboard& king_position);
// returns a bitboard of all attacks threatened by the opponent (ignoring the king for sliding pieces)
Bitboard get_enemy_attack_bitboard(const GameState& game_state, Bitboard* direct_king_attackers);
// methods for getting king attack info for sliding pieces
void get_bishop_king_attack_info(const GameState& game_state, const Bitboard& bishop_positions, const Bitboard& enemy_pieces, const Bitboard& allied_pieces, const Bitboard& king_position, Bitboard* attack_paths, Bitboard* direct_attackers, Bitboard* pinned, Bitboard* pinners);
void get_rook_king_attack_info(const GameState& game_state, const Bitboard& bishop_positions, const Bitboard& enemy_pieces, const Bitboard& allied_pieces, const Bitboard& king_position, Bitboard* attack_paths, Bitboard* direct_attackers, Bitboard* pinned, Bitboard* pinners);
// gets information on where the king gets attacked from and where the attackers and pinned pieces are
void get_attack_on_king_info(const GameState& game_state, Bitboard* attack_paths, Bitboard* attackers, Bitboard* pinned, Bitboard* pinners);
void initialise_king_attack_table();
void initialise_pawn_move_table_white();
void initialise_pawn_attack_table_white();
void initialise_pawn_move_table_black();
void initialise_pawn_attack_table_black();
void initialise_knight_attack_table();
NonMagicAttackTable king_attack_table;
NonMagicAttackTable pawn_move_table_white;
NonMagicAttackTable pawn_attack_table_white;
NonMagicAttackTable pawn_move_table_black;
NonMagicAttackTable pawn_attack_table_black;
NonMagicAttackTable knight_attack_table;
MagicBitboards sliding_attack_generator;
};
}
#endif
MoveGenerator.cpp:
#include "MoveGenerator.h"
#include "GameState.h"
#include "Bitboard.h"
#include "Move.h"
#include "globals.h"
#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <functional>
namespace Chess_Engine
{
using NonMagicAttackTable = std::array<Bitboard, 64>;
MoveGenerator::MoveGenerator()
{
// this is where the static lookup tables get initialised
// non-sliding
initialise_king_attack_table();
initialise_pawn_move_table_white();
initialise_pawn_attack_table_white();
initialise_pawn_move_table_black();
initialise_pawn_attack_table_black();
initialise_knight_attack_table();
}
MoveGenerator::~MoveGenerator()
{
}
std::vector<Move> MoveGenerator::generate_legal_moves(const GameState& game_state)
{
std::vector<Move> pseudo_legal_moves = generate_pseudo_legal_moves(game_state);
std::vector<Move> legal_moves;
Bitboard attack_paths, direct_king_attackers, pinned, pinners;
std::unordered_map<int32_t, Bitboard> allowed_pinned_move_path_for_index;
BoardState board_state = game_state.get_board_state();
Bitboard all_enemy_attacks = get_enemy_attack_bitboard(game_state, &direct_king_attackers);
Bitboard king_position = game_state.is_white_to_move() ? board_state.king_position_white : board_state.king_position_black;
bool king_in_check = all_enemy_attacks & king_position;
get_attack_on_king_info(game_state, &attack_paths, &direct_king_attackers, &pinned, &pinners);
// test all pseudo legal moves for legality
for (const Move& move : pseudo_legal_moves)
{
if (check_for_legality(game_state, move, board_state, all_enemy_attacks, king_position, attack_paths, direct_king_attackers, pinned, pinners, &allowed_pinned_move_path_for_index, king_in_check))
{
legal_moves.push_back(move);
}
}
return legal_moves;
}
bool MoveGenerator::check_for_legality(const GameState& game_state, Move move, BoardState board_state, const Bitboard& all_enemy_attacks, const Bitboard& king_position, const Bitboard& king_attack_paths, const Bitboard& direct_king_attackers, const Bitboard& pinned, const Bitboard& pinners, std::unordered_map<int32_t, Bitboard>* allowed_pinned_move_path_for_index, bool king_in_check)
{
int32_t from_index = move.get_from_index();
int32_t to_index = move.get_to_index();
bool is_king_move = Bitboard(1UL << from_index) & king_position;
bool is_pinned = Bitboard(1UL << from_index) & pinned;
bool white_to_move = game_state.is_white_to_move();
int32_t flags = move.get_flags();
// is the moving piece a king?
if (is_king_move)
{
// is the destination square attacked by the opponent?
if (Bitboard::is_attacked(to_index, all_enemy_attacks))
{
return false;
}
}
// is the king in check?
else if (king_in_check)
{
// if the king is in check and the moving piece is pinned, the move is invalid
if (is_pinned)
{
return false;
}
// in the case of a double-check, all non-king moves are unvalid
if (direct_king_attackers.bit_count() > 1)
{
return false;
}
// are neither all pieces attacking the king getting captured, nor all attack paths getting blocked?
if (!(all_attackers_captured(move, direct_king_attackers, white_to_move)) && !(all_attack_paths_blocked(move, king_attack_paths)))
{
return false;
}
}
// is the moving piece pinned?
else if (is_pinned)
{
// if allowed_pinned_move_path for given origin square is not already calculated
if (allowed_pinned_move_path_for_index->find(from_index) == allowed_pinned_move_path_for_index->end())
{
Bitboard allowed_pinned_move_path = 0;
int32_t direction = 0;
bool same_file = (king_position.get_index() % 8) == (from_index % 8);
bool same_rank = (king_position.get_index() / 8) == (from_index / 8);
// rook movement
if (same_file || same_rank)
{
if (same_file) // on the same file
{
direction = from_index > king_position.get_index() ? 8 : -8;
}
else // on the same rank
{
direction = from_index > king_position.get_index() ? 1 : -1;
}
}
// bishop movement
else
{
int32_t horizontal_direction = ((king_position.get_index() % 8) < (from_index % 8)) ? 1 : -1; // horizontal index shift
int32_t vertical_direction = ((king_position.get_index() / 8) > (from_index / 8)) ? -8 : 8; // vertical index shift
direction = horizontal_direction + vertical_direction; // total shift
}
// contruct allowed_pinned_move_path
for (int32_t index = king_position.get_index() + direction; !(Bitboard(1UL << (index - direction)) & pinners) ; index += direction)
{
allowed_pinned_move_path |= Bitboard(1UL << index);
}
allowed_pinned_move_path_for_index->insert({from_index, allowed_pinned_move_path});
}
// if the pinned piece is moving outside of the allowed path, the move is invalid
if (!(Bitboard(1UL << to_index) & allowed_pinned_move_path_for_index->at(from_index)))
{
return false;
}
}
// castling
if (move.get_flags() == Move::KINGSIDE_CASTLE)
{
Bitboard castling_blockers = all_enemy_attacks | game_state.get_board_state().get_all_positions();
if (Bitboard::is_attacked(king_position.get_index() - 1, castling_blockers) ||
Bitboard::is_attacked(king_position.get_index() - 2, castling_blockers) ||
king_in_check)
{
return false;
}
}
else if (flags == Move::QUEENSIDE_CASTLE)
{
Bitboard castling_blockers = all_enemy_attacks | game_state.get_board_state().get_all_positions();
if (Bitboard::is_attacked(king_position.get_index() + 1, castling_blockers) ||
Bitboard::is_attacked(king_position.get_index() + 2, castling_blockers) ||
Bitboard::is_attacked(king_position.get_index() + 3, game_state.get_board_state().get_all_positions()) ||
king_in_check)
{
return false;
}
}
// make sure en-passant captures do not expose the king by capturing the last enemy piece blocking the attack (very rare)
if (flags == Move::EN_PASSANT_CAPTURE && !((to_index % 8 == 0) || (to_index % 8 == 7)))
{
Bitboard nearest_horizontal_pieces;
int32_t capture_shift = white_to_move ? -8 : 8;
// all pieces, except the moving pawn
Bitboard all_pieces = board_state.get_all_positions() & ~Bitboard(1UL << from_index);
// search to the right
for (int32_t index = to_index + capture_shift - 1; (index % 8) != 7; --index)
{
if (Bitboard(1UL << index) & all_pieces)
{
nearest_horizontal_pieces |= Bitboard(1UL << index);
break;
}
}
// search to the left
for (int32_t index = to_index + capture_shift + 1; (index % 8) != 0; ++index)
{
if (Bitboard(1UL << index) & all_pieces)
{
nearest_horizontal_pieces |= Bitboard(1UL << index);
break;
}
}
Bitboard enemy_rooks = white_to_move ? board_state.rook_positions_black : board_state.rook_positions_white;
Bitboard enemy_queens = white_to_move ? board_state.queen_positions_black : board_state.queen_positions_white;
Bitboard enemy_horizontal_attackers = enemy_rooks | enemy_queens;
// if one nearest horizontal piece is the own king and the other is an enemy horizontal attacker, the capture exposes the king
if ((nearest_horizontal_pieces & king_position) && (nearest_horizontal_pieces & enemy_horizontal_attackers))
{
return false;
}
}
return true;
}
bool MoveGenerator::all_attackers_captured(Move move, const Bitboard& direct_king_attackers, bool white_to_move)
{
if (Bitboard(1UL << move.get_to_index()) & direct_king_attackers)
{
return true;
}
if (move.get_flags() == Move::EN_PASSANT_CAPTURE)
{
int32_t capture_shift = white_to_move ? -8 : 8;
int32_t capture_index = move.get_to_index() + capture_shift;
if (Bitboard(1UL << capture_index) & direct_king_attackers)
{
return true;
}
}
return false;
}
bool MoveGenerator::all_attack_paths_blocked(Move move, const Bitboard& king_attack_paths)
{
if (Bitboard(1UL << move.get_to_index()) & king_attack_paths)
{
return true;
}
return false;
}
std::vector<Move> MoveGenerator::generate_pseudo_legal_moves(const GameState& game_state)
{
std::vector<Move> pseudo_legal_moves;
BoardState board_state = game_state.get_board_state();
bool white_to_move = game_state.is_white_to_move();
Bitboard allied_pieces = white_to_move ? board_state.get_all_positions_white() : board_state.get_all_positions_black();
Bitboard enemy_pieces = white_to_move ? board_state.get_all_positions_black() : board_state.get_all_positions_white();
std::array<Bitboard*, 6> allied_bitboards = white_to_move ? board_state.white_bitboards : board_state.black_bitboards;
// process king attacks
bool castle_short = white_to_move ? game_state.get_white_castle_short() : game_state.get_black_castle_short();
bool castle_long = white_to_move ? game_state.get_white_castle_long() : game_state.get_black_castle_long();
Bitboard king_position = *allied_bitboards[5];
add_king_moves(&pseudo_legal_moves, king_position, allied_pieces, enemy_pieces, castle_short, castle_long);
// process pawn attacks
Bitboard pawn_positions = *allied_bitboards[0];
add_pawn_moves(&pseudo_legal_moves, pawn_positions, allied_pieces, enemy_pieces, white_to_move, game_state.is_en_passant_possible(), game_state.get_en_passant_square());
// process knight attacks
Bitboard knight_positions = *allied_bitboards[2];
add_knight_moves(&pseudo_legal_moves, knight_positions, allied_pieces, enemy_pieces);
// process bishop attacks
Bitboard bishop_positions = *allied_bitboards[3];
add_bishop_moves(&pseudo_legal_moves, bishop_positions, allied_pieces, enemy_pieces);
// process rook attacks
Bitboard rook_positions = *allied_bitboards[1];
add_rook_moves(&pseudo_legal_moves, rook_positions, allied_pieces, enemy_pieces);
// process queen attacks (a queen moves like rook + bishop, so she doesn't need her own method)
Bitboard queen_attacks = *allied_bitboards[4];
add_bishop_moves(&pseudo_legal_moves, queen_attacks, allied_pieces, enemy_pieces);
add_rook_moves(&pseudo_legal_moves, queen_attacks, allied_pieces, enemy_pieces);
return pseudo_legal_moves;
}
void MoveGenerator::add_king_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, bool castle_short, bool castle_long)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = king_attack_table[from_index];
attacks &= ~allied_pieces;
Bitboard capture_attacks = attacks & enemy_pieces;
Bitboard quiet_attacks = attacks & ~enemy_pieces;
while (capture_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(capture_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::CAPTURE));
capture_attacks.reset_LS1B();
}
while (quiet_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(quiet_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::QUIET));
quiet_attacks.reset_LS1B();
}
if (castle_short)
{
move_list->push_back(Move(from_index, from_index - 2, Move::KINGSIDE_CASTLE));
}
if (castle_long)
{
move_list->push_back(Move(from_index, from_index + 2, Move::QUEENSIDE_CASTLE));
}
attacking.reset_LS1B();
}
}
void MoveGenerator::add_knight_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = knight_attack_table[from_index];
attacks &= ~allied_pieces;
Bitboard capture_attacks = attacks & enemy_pieces;
Bitboard quiet_attacks = attacks & ~enemy_pieces;
while (capture_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(capture_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::CAPTURE));
capture_attacks.reset_LS1B();
}
while (quiet_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(quiet_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::QUIET));
quiet_attacks.reset_LS1B();
}
attacking.reset_LS1B();
}
}
void MoveGenerator::add_pawn_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, bool is_white_to_move, bool en_passant_possible, uint32_t en_passant_target_square)
{
Bitboard attacking = attacking_pieces;
NonMagicAttackTable pawn_move_table = is_white_to_move ? pawn_move_table_white : pawn_move_table_black;
NonMagicAttackTable pawn_attack_table = is_white_to_move ? pawn_attack_table_white : pawn_attack_table_black;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard moves = pawn_move_table[from_index]; // get quiet forward moves
moves &= (~allied_pieces & ~enemy_pieces);
int32_t move_index_shift = is_white_to_move ? 8 : -8;
while (moves)
{
int32_t to_index = Bitboard::isolate_LS1B(moves).get_index();
// if pawn is moving two squares
if (to_index == (from_index + 2*move_index_shift))
{
// if in between square is empty
if (!(Bitboard(1UL << (from_index + move_index_shift)) & Bitboard(allied_pieces | enemy_pieces)))
{
move_list->push_back(Move(from_index, to_index, Move::DOUBLE_PAWN_PUSH));
}
}
// if pawn moves to top or bottom rank
else if ((to_index >= 56 && to_index <= 63) || (to_index >= 0 && to_index <= 7))
{
move_list->push_back(Move(from_index, to_index, Move::KNIGHT_PROMOTION));
move_list->push_back(Move(from_index, to_index, Move::BISHOP_PROMOTION));
move_list->push_back(Move(from_index, to_index, Move::ROOK_PROMOTION));
move_list->push_back(Move(from_index, to_index, Move::QUEEN_PROMOTION));
}
else
{
move_list->push_back(Move(from_index, to_index, Move::QUIET));
}
moves.reset_LS1B();
}
Bitboard attacks = pawn_attack_table[from_index]; // get diagonal capture moves
// en-passant
if (en_passant_possible)
{
if (Bitboard(1UL << en_passant_target_square) & attacks)
{
move_list->push_back(Move(from_index, en_passant_target_square, Move::EN_PASSANT_CAPTURE));
}
}
attacks &= enemy_pieces;
while (attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(attacks).get_index();
if ((to_index >= 56 && to_index <= 63) || (to_index >= 0 && to_index <= 7))
{
move_list->push_back(Move(from_index, to_index, Move::KNIGHT_PROMOTION_CAPTURE));
move_list->push_back(Move(from_index, to_index, Move::BISHOP_PROMOTION_CAPTURE));
move_list->push_back(Move(from_index, to_index, Move::ROOK_PROMOTION_CAPTURE));
move_list->push_back(Move(from_index, to_index, Move::QUEEN_PROMOTION_CAPTURE));
}
else
{
move_list->push_back(Move(from_index, to_index, Move::CAPTURE));
}
attacks.reset_LS1B();
}
attacking.reset_LS1B();
}
}
void MoveGenerator::add_bishop_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = sliding_attack_generator.get_bishop_attacks(from_index, allied_pieces | enemy_pieces);
attacks &= ~allied_pieces;
Bitboard capture_attacks = attacks & enemy_pieces;
Bitboard quiet_attacks = attacks & ~enemy_pieces;
while (capture_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(capture_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::CAPTURE));
capture_attacks.reset_LS1B();
}
while (quiet_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(quiet_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::QUIET));
quiet_attacks.reset_LS1B();
}
attacking.reset_LS1B();
}
}
void MoveGenerator::add_rook_moves(std::vector<Move>* move_list, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = sliding_attack_generator.get_rook_attacks(from_index, allied_pieces | enemy_pieces);
attacks &= ~allied_pieces;
Bitboard capture_attacks = attacks & enemy_pieces;
Bitboard quiet_attacks = attacks & ~enemy_pieces;
while (capture_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(capture_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::CAPTURE));
capture_attacks.reset_LS1B();
}
while (quiet_attacks)
{
int32_t to_index = Bitboard::isolate_LS1B(quiet_attacks).get_index();
move_list->push_back(Move(from_index, to_index, Move::QUIET));
quiet_attacks.reset_LS1B();
}
attacking.reset_LS1B();
}
}
void MoveGenerator::add_king_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = king_attack_table[from_index];
*enemy_attacks |= attacks;
attacking.reset_LS1B();
}
}
void MoveGenerator::add_knight_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, Bitboard* direct_king_attackers, const Bitboard& king_position)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = knight_attack_table[from_index];
if (attacks & king_position)
{
*direct_king_attackers |= Bitboard(1UL << from_index);
}
*enemy_attacks |= attacks;
attacking.reset_LS1B();
}
}
void MoveGenerator::add_pawn_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, Bitboard* direct_king_attackers, const Bitboard& king_position, bool is_white_to_move)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks;
if (is_white_to_move)
{
attacks |= pawn_attack_table_black[from_index];
}
else
{
attacks |= pawn_attack_table_white[from_index];
}
if (attacks & king_position)
{
*direct_king_attackers |= Bitboard(1UL << from_index);
}
*enemy_attacks |= attacks;
attacking.reset_LS1B();
}
}
void MoveGenerator::add_bishop_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, const Bitboard& king_position)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = sliding_attack_generator.get_bishop_attacks(from_index, (allied_pieces ^ king_position) | enemy_pieces);
*enemy_attacks |= attacks;
attacking.reset_LS1B();
}
}
void MoveGenerator::add_rook_attacks(Bitboard* enemy_attacks, const Bitboard& attacking_pieces, const Bitboard& allied_pieces, const Bitboard& enemy_pieces, const Bitboard& king_position)
{
Bitboard attacking = attacking_pieces;
while (attacking)
{
int32_t from_index = Bitboard::isolate_LS1B(attacking).get_index();
Bitboard attacks = sliding_attack_generator.get_rook_attacks(from_index, (allied_pieces ^ king_position) | enemy_pieces);
*enemy_attacks |= attacks;
attacking.reset_LS1B();
}
}
Bitboard MoveGenerator::get_enemy_attack_bitboard(const GameState& game_state, Bitboard* direct_king_attackers)
{
Bitboard all_attacks;
BoardState board_state = game_state.get_board_state();
bool white_to_move = game_state.is_white_to_move();
Bitboard allied_pieces = white_to_move ? board_state.get_all_positions_white() : board_state.get_all_positions_black();
Bitboard enemy_pieces = white_to_move ? board_state.get_all_positions_black() : board_state.get_all_positions_white();
Bitboard king_position = white_to_move ? board_state.king_position_white : board_state.king_position_black;
Bitboard enemy_king_position = white_to_move ? board_state.king_position_black : board_state.king_position_white;
add_king_attacks(&all_attacks, enemy_king_position);
Bitboard enemy_pawn_positions = white_to_move ? board_state.pawn_positions_black : board_state.pawn_positions_white;
add_pawn_attacks(&all_attacks, enemy_pawn_positions, direct_king_attackers, king_position, white_to_move);
Bitboard enemy_knight_positions = white_to_move ? board_state.knight_positions_black : board_state.knight_positions_white;
add_knight_attacks(&all_attacks, enemy_knight_positions, direct_king_attackers, king_position);
Bitboard enemy_bishop_positions = white_to_move ? board_state.bishop_positions_black : board_state.bishop_positions_white;
add_bishop_attacks(&all_attacks, enemy_bishop_positions, allied_pieces, enemy_pieces, king_position);
Bitboard enemy_rook_positions = white_to_move ? board_state.rook_positions_black : board_state.rook_positions_white;
add_rook_attacks(&all_attacks, enemy_rook_positions, allied_pieces, enemy_pieces, king_position);
Bitboard enemy_queen_positions = white_to_move ? board_state.queen_positions_black : board_state.queen_positions_white;
add_bishop_attacks(&all_attacks, enemy_queen_positions, allied_pieces, enemy_pieces, king_position);
add_rook_attacks(&all_attacks, enemy_queen_positions, allied_pieces, enemy_pieces, king_position);
return all_attacks;
}
void MoveGenerator::get_attack_on_king_info(const GameState& game_state, Bitboard* attack_paths, Bitboard* direct_attackers, Bitboard* pinned, Bitboard* pinners)
{
BoardState board_state = game_state.get_board_state();
bool white_to_move = game_state.is_white_to_move();
Bitboard allied_pieces = white_to_move ? board_state.get_all_positions_white() : board_state.get_all_positions_black();
Bitboard enemy_pieces = white_to_move ? board_state.get_all_positions_black() : board_state.get_all_positions_white();
Bitboard king_position = white_to_move ? board_state.king_position_white : board_state.king_position_black;
Bitboard enemy_bishop_positions = white_to_move ? board_state.bishop_positions_black : board_state.bishop_positions_white;
get_bishop_king_attack_info(game_state, enemy_bishop_positions, enemy_pieces, allied_pieces, king_position, attack_paths, direct_attackers, pinned, pinners);
Bitboard enemy_rook_positions = white_to_move ? board_state.rook_positions_black : board_state.rook_positions_white;
get_rook_king_attack_info(game_state, enemy_rook_positions, enemy_pieces, allied_pieces, king_position, attack_paths, direct_attackers, pinned, pinners);
Bitboard enemy_queen_positions = white_to_move ? board_state.queen_positions_black : board_state.queen_positions_white;
get_bishop_king_attack_info(game_state, enemy_queen_positions, enemy_pieces, allied_pieces, king_position, attack_paths, direct_attackers, pinned, pinners);
get_rook_king_attack_info(game_state, enemy_queen_positions, enemy_pieces, allied_pieces, king_position, attack_paths, direct_attackers, pinned, pinners);
}
void MoveGenerator::get_bishop_king_attack_info(const GameState& game_state, const Bitboard& bishop_positions, const Bitboard& enemy_pieces, const Bitboard& allied_pieces, const Bitboard& king_position, Bitboard* attack_paths, Bitboard* direct_attackers, Bitboard* pinned, Bitboard* pinners)
{
Bitboard enemy_bishop_positions = bishop_positions;
while (enemy_bishop_positions)
{
int32_t from_index = Bitboard::isolate_LS1B(enemy_bishop_positions).get_index();
Bitboard attacks = sliding_attack_generator.get_bishop_attacks(from_index, enemy_pieces);
Bitboard king_attack_path;
// if king is theoretically attacked
if (attacks & king_position)
{
// calculate attack path
int32_t horizontal_direction = ((king_position.get_index() % 8) < (from_index % 8)) ? -1 : +1; // horizontal index shift
int32_t vertical_direction = ((king_position.get_index() / 8) > (from_index / 8)) ? +8 : -8; // vertical index shift
int32_t direction = horizontal_direction + vertical_direction; // total shift
// loop through attack path and save it
for (int32_t index = from_index + direction; index != king_position.get_index(); index += direction)
{
king_attack_path |= (1UL << index);
}
Bitboard blockers = king_attack_path & allied_pieces; // all allied pieces blocking the path
if (blockers.bit_count() == 0)
{
*direct_attackers |= Bitboard(1UL << from_index); // add attacker to all direct attackers
*attack_paths |= king_attack_path; // add attack path to all attack paths
}
else if (blockers.bit_count() == 1)
{
*pinned |= blockers; // add blocker to pinned pieces
*pinners |= Bitboard(1UL << from_index); // add attacker to pinning pieces
}
}
enemy_bishop_positions.reset_LS1B();
}
}
void MoveGenerator::get_rook_king_attack_info(const GameState& game_state, const Bitboard& rook_positions, const Bitboard& enemy_pieces, const Bitboard& allied_pieces, const Bitboard& king_position, Bitboard* attack_paths, Bitboard* direct_attackers, Bitboard* pinned, Bitboard* pinners)
{
Bitboard enemy_rook_positions = rook_positions;
while (enemy_rook_positions)
{
int32_t from_index = Bitboard::isolate_LS1B(enemy_rook_positions).get_index();
Bitboard attacks = sliding_attack_generator.get_rook_attacks(from_index, enemy_pieces);
Bitboard king_attack_path;
// if king is theoretically attacked
if (attacks & king_position)
{
int32_t direction = 0;
// calculate attack path
if ((from_index % 8) == (king_position.get_index() % 8)) // on the same file
{
if (from_index > king_position.get_index())
{
direction = -8;
}
else
{
direction = 8;
}
}
else // on the same rank
{
if (from_index > king_position.get_index())
{
direction = -1;
}
else
{
direction = 1;
}
}
// loop through attack path and save it
for (int32_t index = from_index + direction; index != king_position.get_index(); index += direction)
{
king_attack_path |= Bitboard(1UL << index);
}
Bitboard blockers = king_attack_path & allied_pieces; // all allied pieces blocking the path
if (blockers.bit_count() == 0)
{
*direct_attackers |= Bitboard(1UL << from_index); // add attacker to all direct attackers
*attack_paths |= king_attack_path; // add attack path to all attack paths
}
else if (blockers.bit_count() == 1)
{
*pinned |= blockers; // add blocker to pinned pieces
*pinners |= Bitboard(1UL << from_index); // add attacker to pinning pieces
}
}
enemy_rook_positions.reset_LS1B();
}
}
void MoveGenerator::initialise_king_attack_table()
{
for (int32_t square = 0; square < 64; ++square)
{
Bitboard attacks;
attacks |= Bitboard(1UL << (square + 9)) & Bitboard::mask_rank[0] & Bitboard::mask_file[7]; // up -> left
attacks |= Bitboard(1UL << (square + 8)) & Bitboard::mask_rank[0]; // up
attacks |= Bitboard(1UL << (square + 7)) & Bitboard::mask_rank[0] & Bitboard::mask_file[0]; // up -> right
attacks |= Bitboard(1UL << (square + 1)) & Bitboard::mask_file[7]; // left
attacks |= Bitboard(1UL << (square - 1)) & Bitboard::mask_file[0]; // right
attacks |= Bitboard(1UL << (square - 7)) & Bitboard::mask_rank[7] & Bitboard::mask_file[7]; // down -> left
attacks |= Bitboard(1UL << (square - 8)) & Bitboard::mask_rank[7]; // down
attacks |= Bitboard(1UL << (square - 9)) & Bitboard::mask_rank[7] & Bitboard::mask_file[0]; // down -> right
king_attack_table[square] = attacks;
}
}
void MoveGenerator::initialise_pawn_move_table_white()
{
for (int32_t square = 0; square < 64; ++square)
{
Bitboard attacks;
attacks |= Bitboard(1UL << (square + 8)) & Bitboard::mask_rank[0]; // up by one
if (square <= 15 && square >= 8)
{
attacks |= (1UL << (square + 16)); // up by two
}
pawn_move_table_white[square] = attacks;
}
}
void MoveGenerator::initialise_pawn_attack_table_white()
{
for (int32_t square = 0; square < 64; ++square)
{
Bitboard attacks;
attacks |= Bitboard(1UL << (square + 9)) & Bitboard::mask_file[7] & Bitboard::mask_rank[0]; // diagonal left
attacks |= Bitboard(1UL << (square + 7)) & Bitboard::mask_file[0] & Bitboard::mask_rank[0]; // diagonal right
pawn_attack_table_white[square] = attacks;
}
}
void MoveGenerator::initialise_pawn_move_table_black()
{
for (int32_t square = 0; square < 64; ++square)
{
Bitboard attacks;
attacks |= Bitboard(1UL << (square - 8)) & Bitboard::mask_rank[7]; // up by one
if (square <= 55 && square >= 48)
{
attacks |= (1UL << (square - 16)); // up by two
}
pawn_move_table_black[square] = attacks;
}
}
void MoveGenerator::initialise_pawn_attack_table_black()
{
for (int32_t square = 0; square < 64; ++square)
{
Bitboard attacks;
attacks |= Bitboard(1UL << (square - 9)) & Bitboard::mask_file[0] & Bitboard::mask_rank[7]; // diagonal right
attacks |= Bitboard(1UL << (square - 7)) & Bitboard::mask_file[7] & Bitboard::mask_rank[7]; // diagonal left
pawn_attack_table_black[square] = attacks;
}
}
void MoveGenerator::initialise_knight_attack_table()
{
for (int32_t square = 0; square < 64; ++square)
{
Bitboard attacks;
attacks |= Bitboard(1UL << (square + 17)) & Bitboard::mask_rank[0] & Bitboard::mask_rank[1] & Bitboard::mask_file[7]; // 2 up -> 1 left
attacks |= Bitboard(1UL << (square + 15)) & Bitboard::mask_rank[0] & Bitboard::mask_rank[1] & Bitboard::mask_file[0]; // 2 up -> 1 right
attacks |= Bitboard(1UL << (square + 10)) & Bitboard::mask_file[6] & Bitboard::mask_file[7] & Bitboard::mask_rank[0]; // 2 left -> 1 up
attacks |= Bitboard(1UL << (square - 6)) & Bitboard::mask_file[6] & Bitboard::mask_file[7] & Bitboard::mask_rank[7]; // 2 left -> 1 down
attacks |= Bitboard(1UL << (square - 15)) & Bitboard::mask_rank[6] & Bitboard::mask_rank[7] & Bitboard::mask_file[7]; // 2 down -> 1 left
attacks |= Bitboard(1UL << (square - 17)) & Bitboard::mask_rank[6] & Bitboard::mask_rank[7] & Bitboard::mask_file[0]; // 2 down -> 1 right
attacks |= Bitboard(1UL << (square + 6)) & Bitboard::mask_file[0] & Bitboard::mask_file[1] & Bitboard::mask_rank[0]; // 2 right -> 1 up
attacks |= Bitboard(1UL << (square - 10)) & Bitboard::mask_file[0] & Bitboard::mask_file[1] & Bitboard::mask_rank[7]; // 2 right -> 1 down
knight_attack_table[square] = attacks;
}
}
}
MagicBitboardsclass to be the problem either, but without it we can't actually run the code, which would have been useful \$\endgroup\$allowed_pinned_move_path_for_indexbe turned into an array, but I don't know that that will help. \$\endgroup\$