1
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ I don't expect the MagicBitboards class to be the problem either, but without it we can't actually run the code, which would have been useful \$\endgroup\$
    – harold
    Mar 4 at 11:35
  • \$\begingroup\$ @harold Well for the code to run, you actually need half my codebase, I think that would be way too much for a single question. \$\endgroup\$
    – Tom Gebel
    Mar 4 at 17:21
  • \$\begingroup\$ Maybe, but now no one else can run a profiler over the code (and potential improvements), that makes it difficult to give useful advice.. For example I could suggest that allowed_pinned_move_path_for_index be turned into an array, but I don't know that that will help. \$\endgroup\$
    – harold
    Mar 4 at 17:37

1 Answer 1

3
\$\begingroup\$
  • check_for_legality is indeed overcomplicated. It seems (can't say for sure without profiling) that blindly making the pseudo-legal move and testing for a King's exposure afterwards should be faster. Castling is a special case of course.

    In any case, a method with 11 parameters is a sure indication that something is wrong with the design.

  • Legality of castling doesn't look correct. b1 (or b8) square being attacked does not invalidate Queenside castling.

    Also, testing for king_in_check here is redundant. It is already known that king is not in check.

  • I don't see why add_*_moves should care about capture_attacks vs quiet_attacks.

  • all_attack_paths_blocked implementation is anti-idiomatic.

      if (condition) {
          return true;
      }
      return false;
    

    is a long way to say

      return condition;
    
  • generate_pseudo_legal_moves feels like it should be private.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your answer. 1. I agree, do you have any suggestions on how to improve the design here? 2. You are right, b1/b8 being attacked does not invalidate queenside castling, but my logic is correct. I just "misuse" the method is_attacked() a bit by passing all piece positions as threat board. Also, testing for king_in_check is not redundant, because castling counts as a king move, so it is not necessarily tested above. \$\endgroup\$
    – Tom Gebel
    Mar 4 at 22:15
  • \$\begingroup\$ 3. add_*_moves cares about whether the move is a capture or not because the created move needs to have the correct move type property. 4. generate_pseudo_legal_moves needs to be public, because it gets called somewhere else independently. \$\endgroup\$
    – Tom Gebel
    Mar 4 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.