Why is my move generator so slow ?

[Paul JF]

Hello everyone !

Quite new to C++ and magic bitboards. I am developing a new engine (actually working but quite weak yet), but my move generator is slow, event if it correctly passes all the perft tests. For example, my previous engine in JavaScript with mailbox has a faster move generation … Can someone explains why is my implementation slow ? For the is_square_attacked and the gen_moves functions, I used the BBC tutorial on youtube. Here is the relevant code regarding move generation :

Code: Select all

static inline U64 get_bishop_attacks(int square, U64 occupancy) {
    __uint128_t occ = occupancy & BISHOP_MASKS[square];
    occ *= BISHOP_MAGICS[square];
    occ >>= 64 - BISHOP_RELEVANT_BITS[square];
    return BISHOP_ATTACKS[square][occ % 512];
}

static inline U64 get_rook_attacks(int square, U64 occupancy) {
    __uint128_t occ = occupancy & ROOK_MASKS[square];
    occ *= ROOK_MAGICS[square];
    occ >>= 64 - ROOK_RELEVANT_BITS[square];
    return ROOK_ATTACKS[square][occ % 4096];
}

U64 get_queen_attacks(int square, U64 occupancy) {
    return get_bishop_attacks(square, occupancy) | get_rook_attacks(square, occupancy);
}

class Move {
    public :

        int from_sq;
        int to_sq;
        int captured;
        int promoted;
        bool is_ep;

        Move(int from_sq=no_sq, int to_sq=no_sq, int captured=None, int promoted=None, bool is_ep=false) {
            this->from_sq = from_sq;
            this->to_sq = to_sq;
            this->captured = captured;
            this->promoted = promoted;
            this->is_ep = is_ep;
        }

        string to_string() const {
            string move_str = SQUARES_NAMES[from_sq] + SQUARES_NAMES[to_sq];
            if (promoted != None) {
                move_str += std::tolower(pieces_char[promoted]);
            }
            if (move_str == string("NONENONE")) {
                return string("0000");
            }
            return move_str;
        }

        bool operator==(const Move other) const {
            return from_sq == other.from_sq &&
                   to_sq == other.to_sq &&
                   captured == other.captured &&
                   promoted == other.promoted &&
                   is_ep == other.is_ep;
        }
};

const Move nullmove;

struct State {
    int en_passant;
    int castle;
    int movecount[2];

    State(int en_passant, int castle, int movecount[2]) {
        this->en_passant = en_passant;
        this->castle = castle;
        this->movecount[0] = movecount[0];
        this->movecount[1] = movecount[1];
    }
};


class Board {
    public :

        U64 bitboards[12];
        U64 occupancy[3];
        U64 hash_key;
        int side;
        int en_passant;
        int castle;
        int move_count[2];
        vector<State> state_history;
        vector<Move> move_stack;
        vector<U64> hash_history;

        void update_occupancy() {
            occupancy[WHITE] = bitboards[WKING] | bitboards[WQUEEN] | bitboards[WROOK] | bitboards[WBISHOP] | bitboards[WKNIGHT] | bitboards[WPAWN];
            occupancy[BLACK] = bitboards[BKING] | bitboards[BQUEEN] | bitboards[BROOK] | bitboards[BBISHOP] | bitboards[BKNIGHT] | bitboards[BPAWN];
            occupancy[BOTH]  = occupancy[WHITE] | occupancy[BLACK];
        }

        int get_piece(int square) {
            if (square < 0 || square >= 64) {
                return None;
            }
            for (int piece = WPAWN; piece <= BKING; piece++) {
                if (contains_square(bitboards[piece], square)) {
                    return piece;
                }
            }
            return None;
        }

        bool is_square_attacked(int square, int by_side) {

            if ((by_side == WHITE) && (PAWN_ATTACKS[BLACK][square] & bitboards[WPAWN])) {
                return true;
            } else if ((by_side == BLACK) && (PAWN_ATTACKS[WHITE][square] & bitboards[BPAWN])) {
                return true;
            } else if (KNIGHT_ATTACKS[square] & (by_side == WHITE ? bitboards[WKNIGHT] : bitboards[BKNIGHT])) {
                return true;
            } else if (KING_ATTACKS[square] & (by_side == WHITE ? bitboards[WKING] : bitboards[BKING])) {
                return true;
            } else if (get_bishop_attacks(square, occupancy[BOTH]) & (by_side == WHITE ? bitboards[WBISHOP] | bitboards[WQUEEN] : bitboards[BBISHOP] | bitboards[BQUEEN])) {
                return true;
            } else if (get_rook_attacks(square, occupancy[BOTH]) & (by_side == WHITE ? bitboards[WROOK] | bitboards[WQUEEN] : bitboards[BROOK] | bitboards[BQUEEN])) {
                return true;
            }
            return false;
        }

        vector<Move> generate_moves() {

            vector<Move> movelist;
            U64 bitboard;
            U64 attacks;
            int from_square;
            int to_square;

            for (int piece = WPAWN; piece <= BKING; piece++) {
                bitboard = bitboards[piece] & occupancy[side];

                if (side == WHITE) {
                    
                    if (piece == WPAWN) {
                        while (bitboard) {
                            from_square = ls1b_index(bitboard);

                            // quiet moves
                            to_square = from_square - 8;
                            if (!contains_square(occupancy[BOTH], to_square)) {
                                if ((to_square >= A8) && (to_square <= H8)) { // pawn promotion
                                    movelist.push_back(Move(from_square, to_square, None, WQUEEN));
                                    movelist.push_back(Move(from_square, to_square, None, WROOK));
                                    movelist.push_back(Move(from_square, to_square, None, WBISHOP));
                                    movelist.push_back(Move(from_square, to_square, None, WKNIGHT));
                                } else { // pawn push
                                    movelist.push_back(Move(from_square, to_square)); // single push
                                    if ((from_square >= A2) && (from_square <= H2) && !contains_square(occupancy[BOTH], to_square-8)) {
                                        movelist.push_back(Move(from_square, to_square-8)); // double push
                                    }
                                }
                            }

                            // capture moves
                            attacks = PAWN_ATTACKS[WHITE][from_square] & occupancy[BLACK];
                            while (attacks) {
                                to_square = ls1b_index(attacks);
                                if ((to_square >= A8) && (to_square <= H8)) { // capture promotion
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), WQUEEN));
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), WROOK));
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), WBISHOP));
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), WKNIGHT));
                                } else { // normal capture
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square)));
                                }
                                attacks = remove_square(attacks, to_square);
                            }

                            // en passant
                            if (en_passant != no_sq) {
                                attacks = PAWN_ATTACKS[WHITE][from_square] & (1ULL << en_passant);
                                if (attacks) { 
                                    movelist.push_back(Move(from_square, en_passant, BPAWN, None, true));
                                }
                            }

                            bitboard = remove_square(bitboard, from_square);
                        }
                    } else if (piece == WKING) { // castling move
                        if (castle & WK) { // kingside
                            if (!contains_square(occupancy[BOTH], F1) && !contains_square(occupancy[BOTH], G1)) {
                                if (!is_square_attacked(E1, BLACK) && ! is_square_attacked(F1, BLACK)) {
                                    movelist.push_back(Move(E1, G1));
                                }
                            }
                        }
                        if (castle & WQ) { // queenside
                            if (!contains_square(occupancy[BOTH], B1) && !contains_square(occupancy[BOTH], C1) && !contains_square(occupancy[BOTH], D1)) {
                                if (!is_square_attacked(E1, BLACK) && ! is_square_attacked(D1, BLACK)) {
                                    movelist.push_back(Move(E1, C1));
                                }
                            }
                        }
                    }
                
                } else if (side == BLACK) {

                    if (piece == BPAWN) {
                        while (bitboard) {
                            from_square = ls1b_index(bitboard);

                            // quiet moves
                            to_square = from_square + 8;
                            if (!contains_square(occupancy[BOTH], to_square)) {
                                if ((to_square >= A1) && (to_square <= H1)) { // pawn promotion
                                    movelist.push_back(Move(from_square, to_square, None, BQUEEN));
                                    movelist.push_back(Move(from_square, to_square, None, BROOK));
                                    movelist.push_back(Move(from_square, to_square, None, BBISHOP));
                                    movelist.push_back(Move(from_square, to_square, None, BKNIGHT));
                                } else { // pawn push
                                    movelist.push_back(Move(from_square, to_square)); // single push
                                    if ((from_square >= A7) && (from_square <= H7) && !contains_square(occupancy[BOTH], to_square+8)) {
                                        movelist.push_back(Move(from_square, to_square+8)); // double push
                                    }
                                }
                            }

                            // capture moves
                            attacks = PAWN_ATTACKS[BLACK][from_square] & occupancy[WHITE];
                            while (attacks) {
                                to_square = ls1b_index(attacks);
                                if ((to_square >= A1) && (to_square <= H1)) { // capture promotion
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), BQUEEN));
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), BROOK));
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), BBISHOP));
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square), BKNIGHT));
                                } else { // normal capture
                                    movelist.push_back(Move(from_square, to_square, get_piece(to_square)));
                                }
                                attacks = remove_square(attacks, to_square);
                            }

                            // en passant
                            if (en_passant != no_sq) {
                                attacks = PAWN_ATTACKS[BLACK][from_square] & (1ULL << en_passant);
                                if (attacks) { 
                                    movelist.push_back(Move(from_square, en_passant, WPAWN, None, true));
                                }
                            }

                            bitboard = remove_square(bitboard, from_square);
                        }
                    } else if (piece == BKING) { // castling move
                        if (castle & BK) { // kingside
                            if (!contains_square(occupancy[BOTH], F8) && !contains_square(occupancy[BOTH], G8)) {
                                if (!is_square_attacked(E8, WHITE) && !is_square_attacked(F8, WHITE)) {
                                    movelist.push_back(Move(E8, G8));
                                }
                            }
                        }
                        if (castle & BQ) { // queenside
                            if (!contains_square(occupancy[BOTH], B8) && !contains_square(occupancy[BOTH], C8) && !contains_square(occupancy[BOTH], D8)) {
                                if (!is_square_attacked(E8, WHITE) && ! is_square_attacked(D8, WHITE)) {
                                    movelist.push_back(Move(E8, C8));
                                }
                            }
                        }
                    }
                }

                // knight
                if (((piece == WKNIGHT) && (side == WHITE)) || ((piece == BKNIGHT) && (side == BLACK))) {
                    while (bitboard) {
                        from_square = ls1b_index(bitboard);
                        attacks = KNIGHT_ATTACKS[from_square] & (~occupancy[side]);

                        while (attacks) {
                            to_square = ls1b_index(attacks);

                            if (contains_square(occupancy[BOTH], to_square)) { // capture
                                movelist.push_back(Move(from_square, to_square, get_piece(to_square)));    
                            } else { // quiet move
                                movelist.push_back(Move(from_square, to_square));
                            }

                            attacks = remove_square(attacks, to_square);
                        }

                        bitboard = remove_square(bitboard, from_square);
                    }
                }

                // bishop
                else if (((piece == WBISHOP) && (side == WHITE)) || ((piece == BBISHOP) && (side == BLACK))) {
                    while (bitboard) {
                        from_square = ls1b_index(bitboard);
                        attacks = get_bishop_attacks(from_square, occupancy[BOTH]) & (~occupancy[side]);

                        while (attacks) {
                            to_square = ls1b_index(attacks);

                            if (contains_square(occupancy[BOTH], to_square)) { // capture
                                movelist.push_back(Move(from_square, to_square, get_piece(to_square)));    
                            } else { // quiet move
                                movelist.push_back(Move(from_square, to_square));
                            }

                            attacks = remove_square(attacks, to_square);
                        }

                        bitboard = remove_square(bitboard, from_square);
                    }
                }

                // rook
                else if (((piece == WROOK) && (side == WHITE)) || ((piece == BROOK) && (side == BLACK))) {
                    while (bitboard) {
                        from_square = ls1b_index(bitboard);
                        attacks = get_rook_attacks(from_square, occupancy[BOTH]) & (~occupancy[side]);

                        while (attacks) {
                            to_square = ls1b_index(attacks);

                            if (contains_square(occupancy[BOTH], to_square)) { // capture
                                movelist.push_back(Move(from_square, to_square, get_piece(to_square)));    
                            } else { // quiet move
                                movelist.push_back(Move(from_square, to_square));
                            }

                            attacks = remove_square(attacks, to_square);
                        }

                        bitboard = remove_square(bitboard, from_square);
                    }
                }

                // rook
                else if (((piece == WQUEEN) && (side == WHITE)) || ((piece == BQUEEN) && (side == BLACK))) {
                    while (bitboard) {
                        from_square = ls1b_index(bitboard);
                        attacks = get_queen_attacks(from_square, occupancy[BOTH]) & (~occupancy[side]);

                        while (attacks) {
                            to_square = ls1b_index(attacks);

                            if (contains_square(occupancy[BOTH], to_square)) { // capture
                                movelist.push_back(Move(from_square, to_square, get_piece(to_square)));    
                            } else { // quiet move
                                movelist.push_back(Move(from_square, to_square));
                            }

                            attacks = remove_square(attacks, to_square);
                        }

                        bitboard = remove_square(bitboard, from_square);
                    }
                }

                // king
                else if (((piece == WKING) && (side == WHITE)) || ((piece == BKING) && (side == BLACK))) {
                    while (bitboard) {
                        from_square = ls1b_index(bitboard);
                        attacks = KING_ATTACKS[from_square] & (~occupancy[side]);

                        while (attacks) {
                            to_square = ls1b_index(attacks);

                            if (contains_square(occupancy[BOTH], to_square)) { // capture
                                movelist.push_back(Move(from_square, to_square, get_piece(to_square)));    
                            } else { // quiet move
                                movelist.push_back(Move(from_square, to_square));
                            }

                            attacks = remove_square(attacks, to_square);
                        }

                        bitboard = remove_square(bitboard, from_square);
                    }
                }
            }

            return movelist;
        }

        bool make(Move move) {

            int piece = get_piece(move.from_sq);

            state_history.push_back(State(en_passant, castle, move_count));
            move_stack.push_back(move);
            hash_history.push_back(hash_key);

            move_count[0] += 1;
            if (side == BLACK) {
                move_count[1] += 1;
            }

            hash_key ^= castlingKey[castle];
            if (en_passant != no_sq) {
                hash_key ^= RANDOM_ARRAY[772 + square_file(en_passant)];
            }

            int from_file = square_file(move.from_sq);
            int from_rank = square_rank(move.from_sq);
            int to_file   = square_file(move.to_sq);
            int to_rank   = square_rank(move.to_sq);

            castle &= castle_mask[move.from_sq] & castle_mask[move.to_sq];

            if (piece == WKING) {
                castle &= BK|BQ;
                if ((move.from_sq == E1) && (move.to_sq == G1)) {
                    bitboards[WROOK] = remove_square(bitboards[WROOK], H1);
                    bitboards[WROOK] = add_square(bitboards[WROOK], F1);
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[WROOK] + 8 * square_rank(H1) + square_file(H1)];
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[WROOK] + 8 * square_rank(F1) + square_file(F1)];
                } else if ((move.from_sq == E1) && (move.to_sq == C1)) {
                    bitboards[WROOK] = remove_square(bitboards[WROOK], A1);
                    bitboards[WROOK] = add_square(bitboards[WROOK], D1);
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[WROOK] + 8 * square_rank(A1) + square_file(A1)];
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[WROOK] + 8 * square_rank(D1) + square_file(D1)];
                }
            } else if (piece == BKING) {
                castle &= WK|WQ;
                if ((move.from_sq == E8) && (move.to_sq == G8)) {
                    bitboards[BROOK] = remove_square(bitboards[BROOK], H8);
                    bitboards[BROOK] = add_square(bitboards[BROOK], F8);
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[BROOK] + 8 * square_rank(H8) + square_file(H8)];
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[BROOK] + 8 * square_rank(F8) + square_file(F8)];
                } else if ((move.from_sq == E8) && (move.to_sq == C8)) {
                    bitboards[BROOK] = remove_square(bitboards[BROOK], A8);
                    bitboards[BROOK] = add_square(bitboards[BROOK], D8);
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[BROOK] + 8 * square_rank(A8) + square_file(A8)];
                    hash_key ^= RANDOM_ARRAY[64 * hash_piece[BROOK] + 8 * square_rank(D8) + square_file(D8)];
                }
            }

            if (move.is_ep) {
                bitboards[move.captured] = remove_square(bitboards[move.captured], side == WHITE ? en_passant+8 : en_passant-8);
                hash_key ^= RANDOM_ARRAY[64 * hash_piece[move.captured] + 8 * square_rank(side == WHITE ? en_passant+8 : en_passant-8) + square_file(side == WHITE ? en_passant+8 : en_passant-8)];
            }
            
            else if (move.captured != None) {
                move_count[0] = 0;
                bitboards[move.captured] = remove_square(bitboards[move.captured], move.to_sq);
                hash_key ^= RANDOM_ARRAY[64 * hash_piece[move.captured] + 8 * to_rank + to_file];
            }

            if (move.promoted != None) {
                bitboards[move.promoted] = add_square(bitboards[move.promoted], move.to_sq);
                bitboards[piece] = remove_square(bitboards[piece], move.from_sq);
                hash_key ^= RANDOM_ARRAY[64 * hash_piece[move.promoted] + 8 * to_rank + to_file];
                hash_key ^= RANDOM_ARRAY[64 * hash_piece[piece] + 8 * from_rank + from_file];
            }
            
            else {
                bitboards[piece] = remove_square(bitboards[piece], move.from_sq);
                bitboards[piece] = add_square(bitboards[piece], move.to_sq);
                hash_key ^= RANDOM_ARRAY[64 * hash_piece[piece] + 8 * from_rank + from_file];
                hash_key ^= RANDOM_ARRAY[64 * hash_piece[piece] + 8 * to_rank + to_file];
            }

            en_passant = no_sq;
            if (piece == WPAWN or piece == BPAWN) {
                move_count[0] = 0;
                if (abs(move.from_sq - move.to_sq) == 16) {
                    en_passant = side == WHITE ? move.from_sq - 8 : move.from_sq + 8;
                    hash_key ^= RANDOM_ARRAY[772 + square_file(en_passant)];
                }
            }

            update_occupancy();
            side ^= 1;
            hash_key ^= castlingKey[castle];
            hash_key ^= RANDOM_ARRAY[780]; // side

            // legality check-up
            bool illegal = is_square_attacked(ls1b_index(bitboards[side == BLACK ? WKING : BKING]), side);
            if (illegal) {
                unmake();
                return false;
            }
            return true;
        }

        void unmake() {

            Move move = move_stack.back();
            move_stack.pop_back();
            State state = state_history.back();
            state_history.pop_back();
            en_passant = state.en_passant;
            castle = state.castle;
            move_count[0] = state.movecount[0];
            move_count[1] = state.movecount[1];
            hash_key = hash_history.back();
            hash_history.pop_back();
            side ^= 1;

            int captured = move.captured;
            int piece = get_piece(move.to_sq);

            if (move.promoted != None) {
                bitboards[piece] = remove_square(bitboards[piece], move.to_sq);
                bitboards[side == WHITE ? WPAWN : BPAWN] = add_square(bitboards[side == WHITE ? WPAWN : BPAWN], move.from_sq);
                if (move.captured != None) {
                    bitboards[captured] = add_square(bitboards[captured], move.to_sq);
                }
                update_occupancy();
                return;
            }

            bitboards[piece] = remove_square(bitboards[piece], move.to_sq);
            bitboards[piece] = add_square(bitboards[piece], move.from_sq);

            if (move.is_ep) {
                if (side == WHITE) {
                    bitboards[BPAWN] = add_square(bitboards[BPAWN], en_passant+8);
                } else {
                    bitboards[WPAWN] = add_square(bitboards[WPAWN], en_passant-8);
                }
            } else if (move.captured != None) {
                bitboards[captured] = add_square(bitboards[captured], move.to_sq);
            }

            if (piece == WKING) {
                if ((move.from_sq == E1) && (move.to_sq == G1)) {
                    bitboards[WROOK] = add_square(bitboards[WROOK], H1);
                    bitboards[WROOK] = remove_square(bitboards[WROOK], F1);
                } else if ((move.from_sq == E1) && (move.to_sq == C1)) {
                    bitboards[WROOK] = add_square(bitboards[WROOK], A1);
                    bitboards[WROOK] = remove_square(bitboards[WROOK], D1);
                }
            } else if (piece == BKING) {
                if ((move.from_sq == E8) && (move.to_sq == G8)) {
                    bitboards[BROOK] = add_square(bitboards[BROOK], H8);
                    bitboards[BROOK] = remove_square(bitboards[BROOK], F8);
                } else if ((move.from_sq == E8) && (move.to_sq == C8)) {
                    bitboards[BROOK] = add_square(bitboards[BROOK], A8);
                    bitboards[BROOK] = remove_square(bitboards[BROOK], D8);
                }
            }

            update_occupancy();
            
        }

        
};

int perft(Board board, int depth) {
    
    int nodes = 0;

    if (depth == 0) {
        return 1;
    }

    for (const Move move : board.generate_moves()) {
        if (!board.make(move)) {
            continue;
        }
        nodes += perft(board, depth - 1);
        board.unmake();
    }
    return nodes;
}

Also, my use of the magic bitboards is the following :

Code: Select all

static inline U64 get_bishop_attacks(int square, U64 occupancy) {
    __uint128_t occ = occupancy & BISHOP_MASKS[square];
    occ *= BISHOP_MAGICS[square];
    occ >>= 64 - BISHOP_RELEVANT_BITS[square];
    return BISHOP_ATTACKS[square][occ % 512];
}

static inline U64 get_rook_attacks(int square, U64 occupancy) {
    __uint128_t occ = occupancy & ROOK_MASKS[square];
    occ *= ROOK_MAGICS[square];
    occ >>= 64 - ROOK_RELEVANT_BITS[square];
    return ROOK_ATTACKS[square][occ % 4096];
}

But most engines seems to use the following :

Code: Select all

static inline U64 get_bishop_attacks(int square, U64 occupancy) {
    occupancy &= bishop_masks[square];
    occupancy *= bishop_magic_numbers[square];
    occupancy >>= 64 - bishop_relevant_bits[square];
    return bishop_attacks[square][occupancy];
}

static inline U64 get_rook_attacks(int square, U64 occupancy) {
    occupancy &= rook_masks[square];
    occupancy *= rook_magic_numbers[square];
    occupancy >>= 64 - rook_relevant_bits[square];
    return rook_attacks[square][occupancy];
}

Why doesn't it works in my engine ? Removing the U128 to keep the U64 just causes my engine to generate illegal moves, and removing the modulo causes a segmentation fault.

Thanks in advance for any help,
Paul JF

[Aleks Peshkov]

I am not an expert in bitboard movegen, but I immediately see

Code: Select all

vector<Move> generate_moves() {
            vector<Move> movelist;

as one the obvious sources of slowdown. You start with empty vector, than vector resize itself many times as it grows. It means it reallocates heap memory and copy itself several times. At minimum you should declare initial vector size.

2) 8 * square_rank(A1) + square_file(A1) should be exact identical to just A1

[Bo Persson]

Code: Select all

class Move {
    public :

        int from_sq;
        int to_sq;
        int captured;
        int promoted;
        bool is_ep;

This is wasting lots of space. None of these values need 4 bytes each. Could be packed a lot better.

[Paul JF]

8 * square_rank(A1) + square_file(A1) should be exact identical to just A1

This is interesting. Unfortunately my board layout does not verify this property. I will try to change it to satisfy it, but this will took me some work as I will have to regenerate all my attack tables and magic numbers.

This is wasting lots of space. None of these values need 4 bytes each. Could be packed a lot better.

Yes I thought of that, but in my mind optimizing the types was some kind of fine-tuning that I would do at the end. I will try that !

You start with empty vector, than vector resize itself many times as it grows. It means it reallocates heap memory and copy itself several times. At minimum you should declare initial vector size.

I do not really understand this part. As I said, quite new to C++

Thanks a lot for the advice ! I still don't understand the need of the U128 for my sliding piece movegen. So appart those remarks, my movegen seems right ? I feel like the get_piece method is not efficient, maybe keeping a 8x8 board list would help ?

[Werner Taelemans]

Quite new to C++ and magic bitboards. I am developing a new engine (actually working but quite weak yet), but my move generator is slow, event if it correctly passes all the perft tests.

Code: Select all

int perft(Board board, int depth) {
    
    int nodes = 0;

    if (depth == 0) {
        return 1;
    }

    for (const Move move : board.generate_moves()) {
        if (!board.make(move)) {
            continue;
        }
        nodes += perft(board, depth - 1);
        board.unmake();
    }
    return nodes;
}

In all your functions you make a copy of your parameters instead of using references. For example when you change

Code: Select all

int perft(Board board, int depth) {

to

Code: Select all

int perft(Board& board, const int& depth) {

you should already see a big difference.

[syzygy]

I still don't understand the need of the U128 for my sliding piece movegen. So appart those remarks, my movegen seems right ?

No, you should not use U128 for magic move generation. Just use unsigned 64-bits ints.

[syzygy]

Why doesn't it works in my engine ? Removing the U128 to keep the U64 just causes my engine to generate illegal moves, and removing the modulo causes a segmentation fault.

You might want to spend some time trying to understand what magic move generation is doing.

Basically it takes the square of your bishop, extracts the bits (& mask) from the occupancy bitboard which are relevant to bishop moves from that square, and then uses a lookup table to find the valid bishop attacks. The trick is that the extracted bits are converted into an index into the lookup table by doing a multiplication of the (occ & mask) bitboard (as an U64) with a "magic" U64, followed by a right-shift which leaves you with just enough bits. The magic U64 has been chosen such that there happen to be no collisions (i.e. no two different occupancy patterns corresponding to different bishop attacks map to the same index in the lookup table).

The U64xU64->U64 multiplication overflows, but that is fine.

[syzygy]

You start with empty vector, than vector resize itself many times as it grows. It means it reallocates heap memory and copy itself several times. At minimum you should declare initial vector size.

I do not really understand this part. As I said, quite new to C++

You are doing lots and lots of memory allocations, which slow down your code.

Just pass your move generator an index into or a pointer to an array. Do not let it allocate an array.

[Paul JF]

you should already see a big difference.

Yes, I tried and there is. Thanks !

Just pass your move generator an index into or a pointer to an array. Do not let it allocate an array.

Understood. I'll try !

No, you should not use U128 for magic move generation. Just use unsigned 64-bits ints.

Yes I know, but I didn't understood why using 64 bits didn't worked (it actually caused illegal moves). Now I guess it is because I generated my magic numbers with Python, without restricting the things to 64 bits …

8 * square_rank(A1) + square_file(A1) should be exact identical to just A1

I will have to change my board layout for that.

This is wasting lots of space. None of these values need 4 bytes each. Could be packed a lot better.

Yes, I will try to optimize every type in my code.

Thank you everyone for pointing out all those mistakes/inacuracy in my code. So during the next month I will :

• Use reference to the bord;

• Change my board layout to Little-endian;

• Regenerate my magic numbers using C++ and the new board layout;

• Optimize the types.

Another question concerning my get_piece function : should I instead use a 8x8 board to get rid of the loops ?

I think I'll be back here when everything will be done.

[syzygy]

Yes I know, but I didn't understood why using 64 bits didn't worked (it actually caused illegal moves). Now I guess it is because I generated my magic numbers with Python, without restricting the things to 64 bits …

Yes, if you use a python script to find suitable magic numbers by trial and error, then the collision test that Python does has to be identical to what your engine does.

This is wasting lots of space. None of these values need 4 bytes each. Could be packed a lot better.

Yes, I will try to optimize every type in my code.[/quote]
I think most engines pack their moves into 32 or even 16 bits.
Note that you will want to store moves in the TT table in a compact format.

Another question concerning my get_piece function : should I instead use a 8x8 board to get rid of the loops ?

Probably.