bb.cpp

//
// Created by Vincent on 22/09/2017.
//

#include <stdexcept>

#include "bb.h"

/*
 * Sliding move generation using 'magic' bitboards.
 *
 * This code uses kogge-stone shifts in namespace bb_shifts to initialise a lookup table.
 * Lookup code is in namespace bb_sliders
 */
namespace bb_sliders {
    constexpr U64 outer_files = 0x8181818181818181ull;
    constexpr U64 outer_ranks = 0xff000000000000ffull;
    constexpr U64 edge = outer_files | outer_ranks;

    sq_entry_t b_table[64];
    sq_entry_t r_table[64];

    struct magic_init_t {
        uint64_t factor;
        int position;
    };

    // <editor-fold desc="Magic multipliers generated by Volker Annuss">
    magic_init_t bishop_magics[64] = {
            {0x007fbfbfbfbfbfffu, 5378},
            {0x0000a060401007fcu, 4093},
            {0x0001004008020000u, 4314},
            {0x0000806004000000u, 6587},
            {0x0000100400000000u, 6491},
            {0x000021c100b20000u, 6330},
            {0x0000040041008000u, 5609},
            {0x00000fb0203fff80u, 22236},
            {0x0000040100401004u, 6106},
            {0x0000020080200802u, 5625},
            {0x0000004010202000u, 16785},
            {0x0000008060040000u, 16817},
            {0x0000004402000000u, 6842},
            {0x0000000801008000u, 7003},
            {0x000007efe0bfff80u, 4197},
            {0x0000000820820020u, 7356},
            {0x0000400080808080u, 4602},
            {0x00021f0100400808u, 4538},
            {0x00018000c06f3fffu, 29531},
            {0x0000258200801000u, 45393},
            {0x0000240080840000u, 12420},
            {0x000018000c03fff8u, 15763},
            {0x00000a5840208020u, 5050},
            {0x0000020008208020u, 4346},
            {0x0000804000810100u, 6074},
            {0x0001011900802008u, 7866},
            {0x0000804000810100u, 32139},
            {0x000100403c0403ffu, 57673},
            {0x00078402a8802000u, 55365},
            {0x0000101000804400u, 15818},
            {0x0000080800104100u, 5562},
            {0x00004004c0082008u, 6390},
            {0x0001010120008020u, 7930},
            {0x000080809a004010u, 13329},
            {0x0007fefe08810010u, 7170},
            {0x0003ff0f833fc080u, 27267},
            {0x007fe08019003042u, 53787},
            {0x003fffefea003000u, 5097},
            {0x0000101010002080u, 6643},
            {0x0000802005080804u, 6138},
            {0x0000808080a80040u, 7418},
            {0x0000104100200040u, 7898},
            {0x0003ffdf7f833fc0u, 42012},
            {0x0000008840450020u, 57350},
            {0x00007ffc80180030u, 22813},
            {0x007fffdd80140028u, 56693},
            {0x00020080200a0004u, 5818},
            {0x0000101010100020u, 7098},
            {0x0007ffdfc1805000u, 4451},
            {0x0003ffefe0c02200u, 4709},
            {0x0000000820806000u, 4794},
            {0x0000000008403000u, 13364},
            {0x0000000100202000u, 4570},
            {0x0000004040802000u, 4282},
            {0x0004010040100400u, 14964},
            {0x00006020601803f4u, 4026},
            {0x0003ffdfdfc28048u, 4826},
            {0x0000000820820020u, 7354},
            {0x0000000008208060u, 4848},
            {0x0000000000808020u, 15946},
            {0x0000000001002020u, 14932},
            {0x0000000401002008u, 16588},
            {0x0000004040404040u, 6905},
            {0x007fff9fdf7ff813u, 16076}
    };
    magic_init_t rook_magics[64] = {
            {0x00280077ffebfffeu, 26304},
            {0x2004010201097fffu, 35520},
            {0x0010020010053fffu, 38592},
            {0x0040040008004002u, 8026},
            {0x7fd00441ffffd003u, 22196},
            {0x4020008887dffffeu, 80870},
            {0x004000888847ffffu, 76747},
            {0x006800fbff75fffdu, 30400},
            {0x000028010113ffffu, 11115},
            {0x0020040201fcffffu, 18205},
            {0x007fe80042ffffe8u, 53577},
            {0x00001800217fffe8u, 62724},
            {0x00001800073fffe8u, 34282},
            {0x00001800e05fffe8u, 29196},
            {0x00001800602fffe8u, 23806},
            {0x000030002fffffa0u, 49481},
            {0x00300018010bffffu, 2410},
            {0x0003000c0085fffbu, 36498},
            {0x0004000802010008u, 24478},
            {0x0004002020020004u, 10074},
            {0x0001002002002001u, 79315},
            {0x0001001000801040u, 51779},
            {0x0000004040008001u, 13586},
            {0x0000006800cdfff4u, 19323},
            {0x0040200010080010u, 70612},
            {0x0000080010040010u, 83652},
            {0x0004010008020008u, 63110},
            {0x0000040020200200u, 34496},
            {0x0002008010100100u, 84966},
            {0x0000008020010020u, 54341},
            {0x0000008020200040u, 60421},
            {0x0000820020004020u, 86402},
            {0x00fffd1800300030u, 50245},
            {0x007fff7fbfd40020u, 76622},
            {0x003fffbd00180018u, 84676},
            {0x001fffde80180018u, 78757},
            {0x000fffe0bfe80018u, 37346},
            {0x0001000080202001u, 370},
            {0x0003fffbff980180u, 42182},
            {0x0001fffdff9000e0u, 45385},
            {0x00fffefeebffd800u, 61659},
            {0x007ffff7ffc01400u, 12790},
            {0x003fffbfe4ffe800u, 16762},
            {0x001ffff01fc03000u, 0},
            {0x000fffe7f8bfe800u, 38380},
            {0x0007ffdfdf3ff808u, 11098},
            {0x0003fff85fffa804u, 21803},
            {0x0001fffd75ffa802u, 39189},
            {0x00ffffd7ffebffd8u, 58628},
            {0x007fff75ff7fbfd8u, 44116},
            {0x003fff863fbf7fd8u, 78357},
            {0x001fffbfdfd7ffd8u, 44481},
            {0x000ffff810280028u, 64134},
            {0x0007ffd7f7feffd8u, 41759},
            {0x0003fffc0c480048u, 1394},
            {0x0001ffffafd7ffd8u, 40910},
            {0x00ffffe4ffdfa3bau, 66516},
            {0x007fffef7ff3d3dau, 3897},
            {0x003fffbfdfeff7fau, 3930},
            {0x001fffeff7fbfc22u, 72934},
            {0x0000020408001001u, 72662},
            {0x0007fffeffff77fdu, 56325},
            {0x0003ffffbf7dfeecu, 66501},
            {0x0001ffff9dffa333u, 14826}
    };
    // </editor-fold>

    U64 attacks[88772];

    // Use kogge-stone occluded shifts to (slowly) generate bishop moves for the lookup table
    U64 compute_bishop_moves(int sq, U64 occupancy) {
        U64 open = ~occupancy;
        return bb_shifts::shift<D_NE>(bb_shifts::fill_occluded<D_NE>(single_bit(sq), open))
               | bb_shifts::shift<D_NW>(bb_shifts::fill_occluded<D_NW>(single_bit(sq), open))
               | bb_shifts::shift<D_SE>(bb_shifts::fill_occluded<D_SE>(single_bit(sq), open))
               | bb_shifts::shift<D_SW>(bb_shifts::fill_occluded<D_SW>(single_bit(sq), open));
    }

    // Use kogge-stone occluded shifts to (slowly) generate rook moves for the lookup table
    U64 compute_rook_moves(int sq, U64 occupancy) {
        U64 open = ~occupancy;
        return bb_shifts::shift<D_N>(bb_shifts::fill_occluded<D_N>(single_bit(sq), open))
               | bb_shifts::shift<D_E>(bb_shifts::fill_occluded<D_E>(single_bit(sq), open))
               | bb_shifts::shift<D_S>(bb_shifts::fill_occluded<D_S>(single_bit(sq), open))
               | bb_shifts::shift<D_W>(bb_shifts::fill_occluded<D_W>(single_bit(sq), open));
    }

    // Squares that are relevant when looking up bishop moves
    U64 compute_bishop_mask(int sq) {
        return compute_bishop_moves(sq, 0) & ~edge;
    }

    // Squares that are relevant when looking up rook moves
    U64 compute_rook_mask(int sq) {
        // Can't use (compute_rook_moves(sq, 0) & ~edge) because rooks can be on the edge of the board
        return ((bb_shifts::shift<D_E>(bb_shifts::fill_occluded<D_E>(single_bit(sq), ~0ull))
                 | bb_shifts::shift<D_W>(bb_shifts::fill_occluded<D_W>(single_bit(sq), ~0ull))) & ~outer_files)
               | ((bb_shifts::shift<D_N>(bb_shifts::fill_occluded<D_N>(single_bit(sq), ~0ull))
                   | bb_shifts::shift<D_S>(bb_shifts::fill_occluded<D_S>(single_bit(sq), ~0ull))) & ~outer_ranks);
    }

    // Initialisation code
    void init_sliders() {
        for (int sq = 0; sq < 64; sq++) {
            sq_entry_t entry = {};
            unsigned bits;

            entry = {compute_bishop_mask(sq), bishop_magics[sq].factor, attacks + bishop_magics[sq].position};
            bits = pop_count(entry.mask);
            for (U64 dense_occ = 0; dense_occ < (1u << bits); dense_occ++) {
                U64 occ = bb_intrin::pdep(dense_occ, entry.mask); // pdep an incrementing bitfield for all relevant bitboards
                entry.base[(occ * entry.magic) >> (64u - 9u)] = compute_bishop_moves(sq, occ);
            }
            b_table[sq] = entry;

            entry = {compute_rook_mask(sq), rook_magics[sq].factor, attacks + rook_magics[sq].position};
            bits = pop_count(entry.mask);
            for (U64 dense_occ = 0; dense_occ < (1u << bits); dense_occ++) {
                U64 occ = bb_intrin::pdep(dense_occ, entry.mask);
                entry.base[(occ * entry.magic) >> (64u - 12u)] = compute_rook_moves(sq, occ);
            }
            r_table[sq] = entry;
        }
    }
}

/*
 * Initialisation of various utility bitboards
 */
namespace bb_util {
    U64 between[64][64];
    U64 line[64][64];
    U64 ray[64][64];
    U64 file[8];

    void init_util() {
        for (uint8_t a = 0; a < 64; a++) {
            // File
            {
                file[file_index(a)] |= single_bit(a);
            }

            for (uint8_t b = 0; b < 64; b++) {
                // Between
                {
                    U64 occupied = single_bit(a) | single_bit(b);
                    if (bb_sliders::bishop_moves(a, 0) & single_bit(b)) {
                        between[a][b] = bb_sliders::bishop_moves(a, occupied) &
                                        bb_sliders::bishop_moves(b, occupied);
                    } else if (bb_sliders::rook_moves(a, 0) & single_bit(b)) {
                        between[a][b] = bb_sliders::rook_moves(a, occupied) &
                                        bb_sliders::rook_moves(b, occupied);
                    }
                }

                // Line
                {
                    if (bb_sliders::bishop_moves(a, 0) & single_bit(b)) {
                        line[a][b] = bb_sliders::bishop_moves(a, 0) &
                                     bb_sliders::bishop_moves(b, 0);
                    } else if (bb_sliders::rook_moves(a, 0) & single_bit(b)) {
                        line[a][b] = bb_sliders::rook_moves(a, 0) &
                                     bb_sliders::rook_moves(b, 0);
                    }
                }

                // Ray
                {
                    U64 occupied = single_bit(a);
                    if (bb_sliders::bishop_moves(a, 0) & single_bit(b)) {
                        ray[a][b] = bb_sliders::bishop_moves(a, occupied) &
                                    bb_sliders::bishop_moves(b, occupied);
                    } else if (bb_sliders::rook_moves(a, 0) & single_bit(b)) {
                        ray[a][b] = bb_sliders::rook_moves(a, occupied) &
                                    bb_sliders::rook_moves(b, occupied);
                    }
                }
            }
        }
    }
}

/**
 * =====================================================================================================================
 * GENERATION FOR NON-SLIDING PIECES
 * =====================================================================================================================
 */
namespace bb_normal_moves {
    U64 king_moves[64];
    U64 knight_moves[64];
    U64 pawn_moves_x1[2][64];
    U64 pawn_moves_x2[2][64];
    U64 pawn_caps[2][64];

    // We use this method (and signed integers) to not generate moves off the edge of the board (or which wrap around)
    inline bool valid_square(const int &file, const int &rank) {
        return file >= 0 && file < 8 && rank >= 0 && rank < 8;
    }

    // Check if move is valid and add to lookup table if it is
    inline void update_array(U64 *arr, const uint8_t &file, const uint8_t &rank,
                             int file_offset, int rank_offset) {
        if (valid_square(file + file_offset, rank + rank_offset)) {
            arr[square_index(file, rank)] |= single_bit(square_index(file + file_offset, rank + rank_offset));
        }
    }

    void init_normal_moves() {
        for (uint8_t file_from = 0; file_from < 8; file_from++) {
            for (uint8_t rank_from = 0; rank_from < 8; rank_from++) {
                // King moves
                update_array(king_moves, file_from, rank_from, -1, -1);
                update_array(king_moves, file_from, rank_from, -1, 0);
                update_array(king_moves, file_from, rank_from, -1, 1);
                update_array(king_moves, file_from, rank_from, 0, -1);
                update_array(king_moves, file_from, rank_from, 0, 1);
                update_array(king_moves, file_from, rank_from, 1, -1);
                update_array(king_moves, file_from, rank_from, 1, 0);
                update_array(king_moves, file_from, rank_from, 1, 1);

                // Knight moves
                update_array(knight_moves, file_from, rank_from, -2, -1);
                update_array(knight_moves, file_from, rank_from, -2, 1);
                update_array(knight_moves, file_from, rank_from, -1, -2);
                update_array(knight_moves, file_from, rank_from, -1, 2);
                update_array(knight_moves, file_from, rank_from, 1, -2);
                update_array(knight_moves, file_from, rank_from, 1, 2);
                update_array(knight_moves, file_from, rank_from, 2, -1);
                update_array(knight_moves, file_from, rank_from, 2, 1);

                // Pawn moves
                update_array(pawn_moves_x1[WHITE], file_from, rank_from, 0, 1);
                update_array(pawn_moves_x1[BLACK], file_from, rank_from, 0, -1);

                // Pawn double moves from 2nd of 7th rank (our ranks are 0 indexed)
                if (rank_from == 1) {
                    update_array(pawn_moves_x2[WHITE], file_from, rank_from, 0, 2);
                } else if (rank_from == 6) {
                    update_array(pawn_moves_x2[BLACK], file_from, rank_from, 0, -2);
                }

                // Pawn captures
                update_array(pawn_caps[WHITE], file_from, rank_from, 1, 1);
                update_array(pawn_caps[WHITE], file_from, rank_from, -1, 1);
                update_array(pawn_caps[BLACK], file_from, rank_from, 1, -1);
                update_array(pawn_caps[BLACK], file_from, rank_from, -1, -1);
            }
        }
    }
}

void init_tables() {
    bb_sliders::init_sliders();
    bb_util::init_util();
    bb_normal_moves::init_normal_moves();
}

uint8_t to_sq(char file, char rank) {
    if (file >= 'a' && file <= 'h' && rank >= '1' && rank <= '8') {
        return square_index(uint8_t(file - 'a'), uint8_t(rank - '1'));
    } else {
        throw std::runtime_error(std::string("invalid square descriptor: '") + file + rank + "'");
    }
}

std::string from_sq(uint8_t sq) {
    return std::string{(char) (file_index(sq) + 'a'), (char) (rank_index(sq) + '1')};
}