4
\$\begingroup\$

In the last couple of days I have been programming a chess move generator in Rust from scratch. While it's intent is to be later used in a fully functional engine, where the speed of the move-generation isn't as important, I have had quite some fun optimizing the move-generator. Now, my engine reaches about 85 million nodes per second when testing it with perft, which is about half the speed popular engines like stockfish reach. Now I can't seem to optimize my engine any further. (The perft implementation is using bulk counting aswell)

Internally the board is represented with bitboards. For Move-Generation, magic bitboards are used for sliding pieces, while there is lookup-tables for knights and kings. The pawn's moves are calculated by bit-shifts. I am following this guide for legal move generation, which leaves me with a method generate_moves(g:&GameState)->(Vec<GameMove>,bool)to generate all moves of a given position and a boolean determining if the position is in check. Most of the methods used in the module magic.rs are only there to generate the magic numbers and the lookup-tables for the lookups, and therefor are only used in the beginning.

main.rs

#[macro_use]
extern crate lazy_static;
extern crate rand;

mod game_state;
mod misc;
mod bitboards;
mod movegen;

use self::game_state::GameState;
use std::time::Instant;

fn main() {
    let now = Instant::now();
    bitboards::init_all();
    println!("Should have initialized everything!");

    let new_now = Instant::now();
    println!("Initialization Time: {}ms", new_now.duration_since(now).as_secs() * 1000 + new_now.duration_since(now).subsec_millis() as u64);
    let now = Instant::now();

    let g = GameState::from_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
    //let g= GameState::from_fen("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1");
    let nodes = perft_div(&g, 6);
    println!("{}", nodes);
    //misc::STD_FEN);
    let new_now = Instant::now();
    let time_passed = new_now.duration_since(now).as_secs() as f64 + new_now.duration_since(now).subsec_millis() as f64 / 1000.0;
    println!("Time: {}ms", new_now.duration_since(now).as_secs() * 1000 + new_now.duration_since(now).subsec_millis() as u64);
    println!("NPS: {}", nodes as f64 / time_passed);
}

pub fn perft_div(g: &GameState, depth: usize) -> u64 {
    let mut count = 0u64;
    let (valid_moves, in_check) = movegen::generate_moves(&g);
    for mv in valid_moves {
        let next_g = movegen::make_move(&g, &mv);
        let res = perft(&next_g, depth - 1);
        println!("{:?}: {}", mv, res);
        count += res;
    }
    count
}

pub fn perft(g: &GameState, depth: usize) -> u64 {
    if depth == 1 {
        let (vm, _ic) = movegen::generate_moves(&g);
        return vm.len() as u64;
    } else {
        let mut res = 0;
        let (valid_moves, incheck) = movegen::generate_moves(&g);
        for mv in valid_moves {
            res += perft(&movegen::make_move(&g, &mv), depth - 1);
        }
        res
    }
}

The game_state file contains the simple structs and a method for parsing a FEN-String.

game_state.rs

use std::fmt::{Formatter, Display, Result, Debug};

#[derive(Clone)]
pub enum GameMoveType {
    Quiet,
    Capture,
    EnPassant,
    Castle,
    Promotion(PieceType),
}

#[derive(Clone, Debug)]
pub enum PieceType {
    King,
    Pawn,
    Knight,
    Bishop,
    Rook,
    Queen,
}

pub struct GameMove {
    pub from: usize,
    pub to: usize,
    pub move_type: GameMoveType,
    pub piece_type: PieceType,
}

impl Debug for GameMove {
    fn fmt(&self, formatter: &mut Formatter) -> Result {
        let mut res_str: String = String::new();
        res_str.push_str(&format!("{}{}{}{}", file_to_string(self.from % 8), self.from / 8 + 1, file_to_string(self.to % 8), self.to / 8 + 1));
        match &self.move_type {
            GameMoveType::Quiet => { res_str.push_str("") }
            _ => {}
        };
        write!(formatter, "{}", res_str)
    }
}

fn file_to_string(file: usize) -> &'static str {
    match file {
        0 => "a",
        1 => "b",
        2 => "c",
        3 => "d",
        4 => "e",
        5 => "f",
        6 => "g",
        7 => "h",
        _ => panic!("invalid file")
    }
}

pub struct GameState {
    // 0 = white
    // 1 = black
    pub color_to_move: usize,

    //Array saving all the bitboards
    //Index 1:
    // 0 -> Pawns
    // 1 -> Knights
    // 2 -> Bishops
    // 3 -> Rooks
    // 4 -> Queens
    // 5 -> King
    //Index 2:
    // 0 -> White
    // 1 -> Black
    pub pieces: [[u64; 2]; 6],

    //Castle flags
    pub castle_white_kingside: bool,
    pub castle_white_queenside: bool,
    pub castle_black_kingside: bool,
    pub castle_black_queenside: bool,

    //En passant flag
    pub en_passant: u64,
    //50 move draw counter
    pub half_moves: usize,
    pub full_moves: usize,
    //Move-Gen
    //King/Knight lookup
    //Sliding by magic
}

impl GameState {
    pub fn from_fen(fen: &str) -> GameState {
        let vec: Vec<&str> = fen.split(" ").collect();
        if vec.len() < 4 {
            panic!("Invalid FEN");
        }
        //Parse through FEN
        //Piecess
        let pieces: Vec<&str> = vec[0].split("/").collect();
        if pieces.len() != 8 {
            panic!("Invalid FEN");
        }
        //Iterate over all 8 ranks
        let mut pieces_arr: [[u64; 2]; 6] = [[0u64; 2]; 6];
        for rank in 0..8 {
            let rank_str = pieces[rank];
            let mut file: usize = 0;
            let mut rank_str_idx: usize = 0;
            while file < 8 {
                let idx = (7 - rank) * 8 + file;
                let next_char = rank_str.chars().nth(rank_str_idx);
                rank_str_idx += 1;
                match next_char {
                    Some(x) => {
                        match x {
                            'P' => {
                                pieces_arr[0][0] |= 1u64 << idx;
                                file += 1;
                            }
                            'p' => {
                                pieces_arr[0][1] |= 1u64 << idx;
                                file += 1;
                            }
                            'N' => {
                                pieces_arr[1][0] |= 1u64 << idx;
                                file += 1;
                            }
                            'n' => {
                                pieces_arr[1][1] |= 1u64 << idx;
                                file += 1;
                            }
                            'B' => {
                                pieces_arr[2][0] |= 1u64 << idx;
                                file += 1;
                            }
                            'b' => {
                                pieces_arr[2][1] |= 1u64 << idx;
                                file += 1;
                            }
                            'R' => {
                                pieces_arr[3][0] |= 1u64 << idx;
                                file += 1;
                            }
                            'r' => {
                                pieces_arr[3][1] |= 1u64 << idx;
                                file += 1;
                            }
                            'Q' => {
                                pieces_arr[4][0] |= 1u64 << idx;
                                file += 1;
                            }
                            'q' => {
                                pieces_arr[4][1] |= 1u64 << idx;
                                file += 1;
                            }
                            'K' => {
                                pieces_arr[5][0] |= 1u64 << idx;
                                file += 1;
                            }
                            'k' => {
                                pieces_arr[5][1] |= 1u64 << idx;
                                file += 1;
                            }
                            '1' => {
                                file += 1;
                            }
                            '2' => {
                                file += 2;
                            }
                            '3' => {
                                file += 3;
                            }
                            '4' => {
                                file += 4;
                            }
                            '5' => {
                                file += 5;
                            }
                            '6' => {
                                file += 6;
                            }
                            '7' => {
                                file += 7;
                            }
                            '8' => {
                                file += 8;
                            }
                            _ => {
                                panic!("Invalid FEN");
                            }
                        }
                    }
                    None => panic!("Invalid FEN"),
                }
            }
        }

        //Side to move
        let color_to_move = match vec[1] {
            "w" => 0,
            "b" => 1,
            _ => panic!("Invalid FEN!")
        };

        //CastlingAbilities
        let castle_white_kingside = vec[2].contains("K");
        let castle_white_queenside = vec[2].contains("Q");
        let castle_black_kingside = vec[2].contains("k");
        let castle_black_queenside = vec[2].contains("q");

        //En Passant target square //Ignore
        let mut en_passant: u64 = 0u64;
        if vec[3] != "-" {
            let mut idx: usize = 0usize;
            let file = vec[3].chars().nth(0);
            let rank = vec[3].chars().nth(1);
            match file {
                Some(x) => {
                    match x {
                        'a' | 'A' => {}
                        'b' | 'B' => {
                            idx += 1;
                        }
                        'c' | 'C' => {
                            idx += 2;
                        }
                        'd' | 'D' => {
                            idx += 3;
                        }
                        'e' | 'E' => {
                            idx += 4;
                        }
                        'f' | 'F' => {
                            idx += 5;
                        }
                        'g' | 'G' => {
                            idx += 6;
                        }
                        'h' | 'H' => {
                            idx += 7;
                        }
                        _ => {
                            panic!("Invalid FEN!");
                        }
                    }
                }
                None => { panic!("Invalid FEN!"); }
            }
            match rank {
                Some(x) => {
                    match x {
                        '1' => {}
                        '2' => {
                            idx += 8;
                        }
                        '3' => {
                            idx += 16;
                        }
                        '4' => {
                            idx += 24;
                        }
                        '5' => {
                            idx += 32;
                        }
                        '6' => {
                            idx += 40;
                        }
                        '7' => {
                            idx += 48;
                        }
                        '8' => {
                            idx += 56;
                        }
                        _ => {
                            panic!("Invalid FEN!");
                        }
                    }
                }
                None => {
                    panic!("Invalid FEN!");
                }
            }
            en_passant = 1u64 << idx;
        }
        let mut half_moves = 0;
        let mut full_moves = 0;
        if vec.len() > 4 {
            //HalfMoveClock
            half_moves = vec[4].parse().unwrap();

            full_moves = vec[5].parse().unwrap();
        }
        GameState {
            color_to_move,
            pieces: pieces_arr,
            castle_white_kingside,
            castle_white_queenside,
            castle_black_kingside,
            castle_black_queenside,
            half_moves,
            full_moves,
            en_passant,
        }
    }
    pub fn standard() -> GameState {
        GameState {
            color_to_move: 0usize,
            pieces: [[0xff00u64, 0xff000000000000u64], [0x42u64, 0x4200000000000000u64], [0x24u64, 0x2400000000000000u64], [0x81u64, 0x8100000000000000u64],
                [0x8u64, 0x800000000000000u64], [0x10u64, 0x1000000000000000u64]],
            castle_white_kingside: true,
            castle_white_queenside: true,
            castle_black_kingside: true,
            castle_black_queenside: true,
            en_passant: 0u64,
            half_moves: 0usize,
            full_moves: 1usize,
        }
    }
}

misc.rs

pub const STD_FEN:&str ="rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";

bitboards.rs

use rand::Rng;

static mut ROOK_BITS: [usize; 64] = [
    12, 11, 11, 11, 11, 11, 11, 12,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    12, 11, 11, 11, 11, 11, 11, 12
];
static mut BISHOP_BITS: [usize; 64] = [
    6, 5, 5, 5, 5, 5, 5, 6,
    5, 5, 5, 5, 5, 5, 5, 5,
    5, 5, 7, 7, 7, 7, 5, 5,
    5, 5, 7, 9, 9, 7, 5, 5,
    5, 5, 7, 9, 9, 7, 5, 5,
    5, 5, 7, 7, 7, 7, 5, 5,
    5, 5, 5, 5, 5, 5, 5, 5,
    6, 5, 5, 5, 5, 5, 5, 6
];
const MAGIC_NUMS_ROOKS: [u64; 64] = [
    0x2180028011204008u64, 0x21400190002000c0u64, 0x8480100020000b80u64, 0x80100080061800u64, 0xc100080004030010u64, 0x200084430120001u64, 0x1880110006800200u64, 0x100006200804100u64, 0x4084800280400020u64, 0x8400400050002000u64, 0xd001020010342u64, 0x20040102008040u64, 0x8000802400810800u64, 0x2922002804100a01u64, 0x4109002a0099000cu64, 0x40020000840e0841u64, 0x800848000204011u64, 0x900444000201008u64, 0x5201010020049142u64, 0x80620009c20030u64, 0x45310004080100u64, 0x808002001400u64, 0x1090840002100328u64, 0x8022000184085bu64, 0x401080028020u64, 0x4910400080802000u64, 0x1400403100200100u64, 0x910008080180450u64, 0x200040080800800u64, 0x1052000200100429u64, 0x2004e80c000a1110u64, 0x1423000100005282u64, 0x8088834000800aa0u64, 0x10080c000806000u64, 0x8010200082805002u64, 0x82101003000u64, 0x7040080280800400u64, 0x610c004100401200u64, 0x5700010804001002u64, 0x1000008042000904u64, 0x21049460c0008000u64, 0x410014020004002u64, 0x20100a001410013u64, 0x401000810010020u64, 0x4008012400808008u64, 0x808200440480110u64, 0x1b81040200010100u64, 0x8020040040820003u64, 0x80002108508100u64, 0x10242082b008200u64, 0x801004090200100u64, 0x4003002008100100u64, 0x8180080440080u64, 0x890c0004800a0080u64, 0x104020108102400u64, 0x41111040840200u64, 0x1010201601008042u64, 0x127002440013181u64, 0x102104209220082u64, 0xa011009001242009u64, 0x81000228001085u64, 0x5022001008011c02u64, 0x100821000810804u64, 0x100002280d601u64, ];
const MAGIC_NUMS_BISHOPS: [u64; 64] = [
    0x6040422a14086080u64, 0x4084800408020u64, 0x400c080210440010u64, 0x44042080000000u64, 0x2610882002100a00u64, 0x9030080c0080u64, 0xc140841048148004u64, 0x200844c100442u64, 0x40042004042682u64, 0x4200100608410a28u64, 0x802010052a202108u64, 0x800c080601410802u64, 0xc001011040020004u64, 0x488811002902400u64, 0xa008024210106808u64, 0x1004a100e9042004u64, 0x2030002102e20800u64, 0x510a5810210042u64, 0x68010408089830u64, 0x41c800802044200u64, 0x4004080a04000u64, 0x4004080203040a00u64, 0x830642382040u64, 0x8200401101c23040u64, 0x8400248108110u64, 0x4440020289080u64, 0x3008040408004050u64, 0x8004004004010002u64, 0x921004024044016u64, 0x201840802020a00u64, 0x20222c0000414811u64, 0x5802068602404810u64, 0x2791200810a29848u64, 0x2650821000081000u64, 0x415000480322u64, 0x2041401820060200u64, 0x1020200240104u64, 0x10802000c2212u64, 0xe002880a00005200u64, 0x2001062200402100u64, 0x52105044000850u64, 0x204590820800818u64, 0x1201410082a00u64, 0x440004200810800u64, 0x20080100442401u64, 0x200b200214100880u64, 0x2810108100400100u64, 0x8824640052011048u64, 0x4281040114400060u64, 0x988824040208001du64, 0x806081c40c040909u64, 0x20090084110014u64, 0x304006022440118u64, 0x1011400304010004u64, 0xa1020010410a048u64, 0x8110020809002809u64, 0x40010022100c0413u64, 0x2800020125011014u64, 0x46082400u64, 0x60408400840401u64, 0x8001020010021204u64, 0x4c00100812084200u64, 0x20000420440c1098u64, 0x802200c01120060u64, ];
lazy_static! {
    pub static ref FILES: [u64;8] = initialize_files();
    pub static ref NOT_FILES: [u64;8] = initialize_not_files();
    pub static ref RANKS: [u64;8] = initialize_ranks();
    pub static ref SQUARES: [u64;64]= initialize_squares();
    pub static ref NOT_SQUARES: [u64;64]= initialize_not_squares();
    pub static ref MAGICS_ROOKS: Vec<Magic>= init_magics_rooks();
    pub static ref MAGICS_BISHOPS:Vec<Magic>= init_magics_bishops();
    pub static ref KING_ATTACKS:[u64;64] = init_king_attacks();
    pub static ref KNIGHT_ATTACKS:[u64;64] = init_knight_attacks();
    pub static ref FILES_LESS_THAN:[u64;8]= init_files_less_than();
    pub static ref FILES_GREATER_THAN:[u64;8]= init_files_greater_than();
    pub static ref RANKS_LESS_THAN:[u64;8]= init_ranks_less_than();
    pub static ref RANKS_GREATER_THAN:[u64;8]= init_ranks_greater_than();
}
pub struct Magic {
    pub occupancy_mask: u64,
    pub shift: usize,
    pub magic_num: u64,
    pub lookup_table: Vec<u64>,
}

impl Magic {
    pub fn get_attacks(&self, all_pieces_board: u64) -> u64 {
        self.lookup_table[(((all_pieces_board & self.occupancy_mask).wrapping_mul(self.magic_num)) >> (64 - self.shift)) as usize]
    }
}

pub fn init_all() {
    FILES.len();
    NOT_FILES.len();
    RANKS.len();
    SQUARES.len();
    NOT_SQUARES.len();
    //Override Magics with better magic nums
    MAGICS_ROOKS.len();
    MAGICS_BISHOPS.len();
    KING_ATTACKS.len();
    KNIGHT_ATTACKS.len();
    FILES_LESS_THAN.len();
    FILES_GREATER_THAN.len();
    RANKS_LESS_THAN.len();
    RANKS_GREATER_THAN.len();
}

//Rook-specific magic
pub fn init_magics_rooks() -> Vec<Magic> {
    let mut res: Vec<Magic> = Vec::with_capacity(64);
    for square in 0..64 {
        let shift;
        unsafe {
            shift = ROOK_BITS[square];
        }
        let occupancy_mask = occupancy_mask_rooks(square);
        if occupancy_mask.count_ones() as usize != shift {
            panic!("Not good!");
        }
        let mut blockers_by_index: Vec<u64> = Vec::with_capacity(1 << shift);
        let mut attack_table: Vec<u64> = Vec::with_capacity(1 << shift);
        //Initialize lookup table
        for i in 0..(1 << shift) {
            //i is index of lookup table
            blockers_by_index.push(blockers_to_bitboard(i, shift, occupancy_mask));
            attack_table.push(rook_attacks_slow(square, blockers_by_index[i]));
        }
        let magic_num = MAGIC_NUMS_ROOKS[square];
        let mut lookup_table = Vec::with_capacity(1 << shift);
        for _i in 0..(1 << shift) {
            lookup_table.push(0u64);
        }
        //Calculate look-up table
        for i in 0..(1 << shift) {
            let j = transform(blockers_by_index[i], magic_num, shift);
            if lookup_table[j] == 0u64 {
                lookup_table[j] = attack_table[i];
            } else {
                panic!("Isn't valid num!")
            }
        }
        res.push(Magic {
            occupancy_mask,
            shift,
            magic_num,
            lookup_table,
        })
    }
    println!("Finished Initializing Rook Attacks!");
    res
}

pub fn occupancy_mask_rooks(square: usize) -> u64 {
    (((RANKS[square / 8] & !(FILES[0] | FILES[7])) | (FILES[square % 8] & !(RANKS[0] | RANKS[7]))) & NOT_SQUARES[square])
}

pub fn rook_attacks_slow(square: usize, blocks: u64) -> u64 {
    let mut res = 0u64;
    let rank: isize = (square / 8) as isize;
    let file: isize = (square % 8) as isize;
    let dirs: [(isize, isize); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    for dir in dirs.iter() {
        let (file_i, rank_i) = dir;
        let mut rn = rank + rank_i;
        let mut fnn = file + file_i;
        while rn >= 0 && rn <= 7 && fnn >= 0 && fnn <= 7 {
            res |= 1u64 << (rn * 8 + fnn);
            if (blocks & (1u64 << (rn * 8 + fnn))) != 0 {
                break;
            }
            rn += rank_i;
            fnn += file_i;
        }
    }
    res
}
//Bishop-specific magic
pub fn init_magics_bishops() -> Vec<Magic> {
    let mut res: Vec<Magic> = Vec::with_capacity(64);
    for square in 0..64 {
        let shift;
        unsafe {
            shift = BISHOP_BITS[square];
        }

        let occupancy_mask = occupancy_mask_bishops(square);
        if occupancy_mask.count_ones() as usize != shift {
            panic!("Not good!");
        }

        let mut blockers_by_index: Vec<u64> = Vec::with_capacity(1 << shift);
        let mut attack_table: Vec<u64> = Vec::with_capacity(1 << shift);
        //Initialize lookup table
        for i in 0..(1 << shift) {
            //i is index of lookup table
            blockers_by_index.push(blockers_to_bitboard(i, shift, occupancy_mask));
            attack_table.push(bishop_attacks_slow(square, blockers_by_index[i]));
        }

        let magic_num = MAGIC_NUMS_BISHOPS[square];
        let mut lookup_table = Vec::with_capacity(1 << shift);
        for _i in 0..(1 << shift) {
            lookup_table.push(0u64);
        }
        //Calculate look-up table
        for i in 0..(1 << shift) {
            let j = transform(blockers_by_index[i], magic_num, shift);
            if lookup_table[j] == 0u64 {
                lookup_table[j] = attack_table[i];
            } else {
                panic!("Isn't valid num!")
            }
        }
        res.push(Magic {
            occupancy_mask,
            shift,
            magic_num,
            lookup_table,
        })
    }
    println!("Finished Initializing Bishop Attacks!");
    res
}

pub fn occupancy_mask_bishops(square: usize) -> u64 {
    let mut res = 0u64;
    let rk = (square / 8) as isize;
    let fl = (square % 8) as isize;
    let dirs: [(isize, isize); 4] = [(1, 1), (-1, -1), (1, -1), (-1, 1)];
    for dir in dirs.iter() {
        let (file_i, rank_i) = dir;
        let mut rn = rk + rank_i;
        let mut fnn = fl + file_i;
        while rn >= 1 && rn <= 6 && fnn >= 1 && fnn <= 6 {
            res |= 1u64 << (rn * 8 + fnn);
            rn += rank_i;
            fnn += file_i;
        }
    }
    res
}

pub fn bishop_attacks_slow(square: usize, blocks: u64) -> u64 {
    let mut res = 0u64;
    let rank: isize = (square / 8) as isize;
    let file: isize = (square % 8) as isize;
    let dirs: [(isize, isize); 4] = [(1, 1), (-1, -1), (1, -1), (-1, 1)];
    for dir in dirs.iter() {
        let (file_i, rank_i) = dir;
        let mut rn = rank + rank_i;
        let mut fnn = file + file_i;
        while rn >= 0 && rn <= 7 && fnn >= 0 && fnn <= 7 {
            res |= 1u64 << (rn * 8 + fnn);
            if (blocks & (1u64 << (rn * 8 + fnn))) != 0 {
                break;
            }
            rn += rank_i;
            fnn += file_i;
        }
    }
    res
}
//General Magic stuff
pub fn transform(blockers: u64, magic: u64, n_bits: usize) -> usize {
    ((blockers.wrapping_mul(magic)) >> (64 - n_bits)) as usize
}

pub fn generate_magic(blockers_by_index: &Vec<u64>, attack_table: &Vec<u64>, n_bits: usize, occ_mask: u64) -> u64 {
    for _iterations in 0..100000000 {
        let random_magic = random_u64_fewbits();
        if ((occ_mask.wrapping_mul(random_magic)) & 0xFF00000000000000u64) < 6 {
            continue;
        }
        if is_valid_magic(random_magic, n_bits, blockers_by_index, attack_table) {
            return random_magic;
        }
    }
    panic!("No Magic found!");
}

pub fn is_valid_magic(magic: u64, n_bits: usize, blockers_by_index: &Vec<u64>, attack_table: &Vec<u64>) -> bool {
    let mut used = Vec::with_capacity(1 << n_bits);
    for _i in 0..(1 << n_bits) {
        used.push(0u64);
    }
    for i in 0..(1 << n_bits) {
        let j = transform(blockers_by_index[i], magic, n_bits);
        if used[j] == 0u64 {
            used[j] = attack_table[i];
        } else if used[j] != attack_table[i] {
            return false;
        }
    }
    return true;
}

pub fn random_u64() -> u64 {
    rand::thread_rng().gen::<u64>()
}

pub fn random_u64_fewbits() -> u64 {
    random_u64() & random_u64() & random_u64()
}

pub fn blockers_to_bitboard(block_index: usize, n_bits: usize, mut mask: u64) -> u64 {
    let mut res = 0u64;
    for i in 0..n_bits {
        let j = mask.trailing_zeros();
        mask &= !(1 << j);
        if (block_index & (1 << i)) != 0 {
            res |= 1u64 << j;
        }
    }
    res
}

//Initializing General BitBoards

pub fn initialize_files() -> [u64; 8] {
    let mut res = [0u64; 8];
    for file in 0..8 {
        if file == 0 {
            res[0] = 1u64 << 0 | 1u64 << 8 | 1u64 << 16 | 1u64 << 24 | 1u64 << 32 | 1u64 << 40 | 1u64 << 48 | 1u64 << 56;
        } else {
            res[file] = res[file - 1] << 1;
        }
    }
    println!("Finished Initializing Files!");
    res
}

pub fn initialize_not_files() -> [u64; 8] {
    let mut res = [0u64; 8];
    for file in 0..8 {
        res[file] = !FILES[file];
    }
    println!("Finished Initializing NOT Files!");
    res
}

pub fn initialize_ranks() -> [u64; 8] {
    let mut res = [0u64; 8];
    for rank in 0..8 {
        if rank == 0 {
            res[0] = 1u64 << 0 | 1u64 << 1 | 1u64 << 2 | 1u64 << 3 | 1u64 << 4 | 1u64 << 5 | 1u64 << 6 | 1u64 << 7;
        } else {
            res[rank] = res[rank - 1] << 8;
        }
    }
    println!("Finished Initializing Ranks!");
    res
}

pub fn initialize_squares() -> [u64; 64] {
    let mut res = [0u64; 64];
    for squares in 0..64 {
        res[squares] = 1u64 << squares;
    }
    println!("Finished Initializing Squares!");
    res
}

pub fn initialize_not_squares() -> [u64; 64] {
    let mut res = [0u64; 64];
    for squares in 0..64 {
        res[squares] = !(1u64 << squares);
    }
    println!("Finished Initializing NOT_Squares!");
    res
}

pub fn north_one(board: u64) -> u64 {
    board << 8
}

pub fn north_east_one(board: u64) -> u64 {
    (board & NOT_FILES[7]) << 9
}

pub fn north_west_one(board: u64) -> u64 {
    (board & NOT_FILES[0]) << 7
}

pub fn south_one(board: u64) -> u64 {
    board >> 8
}

pub fn south_east_one(board: u64) -> u64 {
    (board & NOT_FILES[7]) >> 7
}

pub fn south_west_one(board: u64) -> u64 {
    (board & NOT_FILES[0]) >> 9
}

pub fn west_one(board: u64) -> u64 {
    (board & NOT_FILES[0]) >> 1
}

pub fn east_one(board: u64) -> u64 {
    (board & NOT_FILES[7]) << 1
}

pub fn king_attack(mut king_board: u64) -> u64 {
    let mut attacks = east_one(king_board) | west_one(king_board);
    king_board |= attacks;
    attacks |= south_one(king_board) | north_one(king_board);
    attacks
}

pub fn init_king_attacks() -> [u64; 64] {
    let mut res = [0u64; 64];
    for square in 0..64 {
        res[square] = king_attack(1u64 << square);
    }
    println!("Finished Initializing King Attacks!");
    res
}

pub fn knight_attack(knight: u64) -> u64 {
    let mut attacks;
    let mut east = east_one(knight);
    let mut west = west_one(knight);
    attacks = (east | west) << 16;
    attacks |= (east | west) >> 16;
    east = east_one(east);
    west = west_one(west);
    attacks |= (east | west) << 8;
    attacks |= (east | west) >> 8;
    attacks
}

pub fn init_knight_attacks() -> [u64; 64] {
    let mut res = [0u64; 64];
    for square in 0..64 {
        res[square] = knight_attack(1u64 << square);
    }
    println!("Finished Initializing Knight Attacks!");
    res
}

pub fn init_files_less_than() -> [u64; 8] {
    let mut res = [0u64; 8];
    for files in 0..8 {
        for files_less_than in 0..files {
            res[files] |= FILES[files_less_than];
        }
    }
    println!("Finished Initializing FilesLessThan!");
    res
}

pub fn init_ranks_less_than() -> [u64; 8] {
    let mut res = [0u64; 8];
    for ranks in 0..8 {
        for ranks_less_than in 0..ranks {
            res[ranks] |= RANKS[ranks_less_than];
        }
    }
    println!("Finished Initializing RanksLessThan!");
    res
}

pub fn init_files_greater_than() -> [u64; 8] {
    let mut res = [0u64; 8];
    for files in 0..8 {
        res[files] = !FILES_LESS_THAN[files] & !FILES[files];
    }
    println!("Finished Initializing FilesGreaterThan!");
    res
}

pub fn init_ranks_greater_than() -> [u64; 8] {
    let mut res = [0u64; 8];
    for ranks in 0..8 {
        res[ranks] = !RANKS_LESS_THAN[ranks] & !RANKS[ranks];
    }
    println!("Finished Initializing FilesGreaterThan!");
    res
}

//Misc
pub fn to_string_board(board: u64) -> String {
    let mut res_str: String = String::new();
    res_str.push_str("+---+---+---+---+---+---+---+---+\n");
    for rank in 0..8 {
        res_str.push_str("| ");
        for file in 0..8 {
            let idx = 8 * (7 - rank) + file;
            if ((board >> idx) & 1) != 0 {
                res_str.push_str("X");
            } else {
                res_str.push_str(" ");
            }
            res_str.push_str(" | ");
        }
        res_str.push_str("\n+---+---+---+---+---+---+---+---+\n");
    }
    res_str
}

Now in this file all of the moves are calculated.


King moves

This is done by first calculating which of the fields are attacked by pseudo-legal enemy moves. Then the king moves are all of the possible neighbor fields which aren't attacked. If the kings field coincides with one of the attacked fields, we know that the king is in check. If in check, we figure out how many attackers there are and where they are. If it's a double check, only king moves are possible so those are returned. If it's a single check, a capture and a push mask is calculated. Every capture of any piece has to be on this mask, and every non-capture(push) has to land on the push mask.


Pinned pieces

Pinned pieces are determined by simulating a queen on the king's fields which xrays exactly one piece. If her ray lands on an enemy slider, we know that the xray-piece is pinned. The pinned piece may be able to capture the slider or push in the ray of the slider, if it's on the push and capture mask.


Castles

Castles are only possible when not in check. If not in check, we check the castle flags and check the other conditions needed for a castle.


EnPassants

There is a dedicated flag being set on a double push of a pawn. This way we can check any en-passant move.


Rest of the moves

The rest of the moves get generated by lookup and are pseudo-legal. If they land on the push/capture mask, they are legal and get added.

movegen.rs

use super::bitboards;
use super::game_state::{self, GameMove, GameMoveType, PieceType};

//Move GEn
//King- Piece-Wise by lookup
//Knight-Piece-Wise by lookup
//Bishop/Queen/Rook - Piece-Wise by lookup in Magic
//Pawn-SetWise by shift
pub fn king_attack(square: usize) -> u64 {
    bitboards::KING_ATTACKS[square]
}

pub fn bishop_attack(square: usize, all_pieces: u64) -> u64 {
    bitboards::Magic::get_attacks(&bitboards::MAGICS_BISHOPS[square], all_pieces)
}

pub fn rook_attack(square: usize, all_pieces: u64) -> u64 {
    bitboards::Magic::get_attacks(&bitboards::MAGICS_ROOKS[square], all_pieces)
}

pub fn knight_attack(square: usize) -> u64 {
    bitboards::KNIGHT_ATTACKS[square]
}

pub fn w_single_push_pawn_targets(pawns: u64, empty: u64) -> u64 {
    bitboards::north_one(pawns) & empty
}

pub fn w_double_push_pawn_targets(pawns: u64, empty: u64) -> u64 {
    bitboards::north_one(bitboards::north_one(pawns & bitboards::RANKS[1]) & empty) & empty
}

pub fn b_single_push_pawn_targets(pawns: u64, empty: u64) -> u64 {
    bitboards::south_one(pawns) & empty
}

pub fn b_double_push_pawn_targets(pawns: u64, empty: u64) -> u64 {
    bitboards::south_one(bitboards::south_one(pawns & bitboards::RANKS[6]) & empty) & empty
}

//NorthEast = +9
pub fn w_pawn_east_targets(pawns: u64) -> u64 {
    bitboards::north_east_one(pawns)
}

//NorthWest = +7
pub fn w_pawn_west_targets(pawns: u64) -> u64 {
    bitboards::north_west_one(pawns)
}

//SouthEast = -7
pub fn b_pawn_east_targets(pawns: u64) -> u64 {
    bitboards::south_west_one(pawns)
}

//NorthWest = -9
pub fn b_pawn_west_targets(pawns: u64) -> u64 {
    bitboards::south_east_one(pawns)
}

pub fn add_moves(move_list: &mut Vec<GameMove>, from: usize, mut to_board: u64, piece_type: &PieceType, move_type: GameMoveType) {
    while to_board != 0u64 {
        let idx = to_board.trailing_zeros() as usize;
        let  move_t_cl = move_type.clone();
        let pt_cl= piece_type.clone();
        move_list.push(GameMove {
            from,
            to: idx,
            move_type: move_t_cl,
            piece_type: pt_cl
        });
        to_board ^= 1u64 << idx;
        //to_board&= to_board-1;
    }
}

pub fn add_quiet_pawn_single_pushes(mut single_push_board: u64, color_to_move: &usize, move_list: &mut Vec<GameMove>) {
    while single_push_board != 0u64 {
        let idx = single_push_board.trailing_zeros() as usize;
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - 8 } else { idx + 8 },
            to: idx,
            move_type: GameMoveType::Quiet,
            piece_type: PieceType::Pawn,
        });
        single_push_board ^= 1 << idx;
    }
}

pub fn add_quiet_pawn_double_pushes(mut double_push_board: u64, color_to_move: &usize, move_list: &mut Vec<GameMove>) {
    while double_push_board != 0u64 {
        let idx = double_push_board.trailing_zeros() as usize;
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - 16 } else { idx + 16 },
            to: idx,
            move_type: GameMoveType::Quiet,
            piece_type: PieceType::Pawn,
        });
        double_push_board ^= 1 << idx;
    }
}

pub fn add_promotion_push(mut promotion_board: u64, color_to_move: &usize, move_list: &mut Vec<GameMove>, source_shift: usize) {
    while promotion_board != 0u64 {
        let idx = promotion_board.trailing_zeros() as usize;
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - source_shift } else { idx + source_shift },
            to: idx,
            move_type: GameMoveType::Promotion(PieceType::Queen),
            piece_type: PieceType::Pawn,
        });
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - source_shift } else { idx + source_shift },
            to: idx,
            move_type: GameMoveType::Promotion(PieceType::Rook),
            piece_type: PieceType::Pawn,
        });
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - source_shift } else { idx + source_shift },
            to: idx,
            move_type: GameMoveType::Promotion(PieceType::Bishop),
            piece_type: PieceType::Pawn,
        });
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - source_shift } else { idx + source_shift },
            to: idx,
            move_type: GameMoveType::Promotion(PieceType::Knight),
            piece_type: PieceType::Pawn,
        });
        promotion_board ^= 1 << idx;
    }
}

pub fn add_pawn_capture(mut capture_board: u64, color_to_move: &usize, move_list: &mut Vec<GameMove>, source_shift: usize) {
    while capture_board != 0u64 {
        let idx = capture_board.trailing_zeros() as usize;
        move_list.push(GameMove {
            from: if *color_to_move == 0 { idx - source_shift } else { idx + source_shift },
            to: idx,
            move_type: GameMoveType::Capture,
            piece_type: PieceType::Pawn,
        });
        capture_board ^= 1 << idx;
    }
}

pub fn add_en_passants(mut enpassant_board: u64, color_to_move: &usize, move_list: &mut Vec<GameMove>, source_shift: usize, all_pieces_without_my_king: u64, enemy_rooks: u64, my_king_idx: usize) {
    while enpassant_board != 0u64 {
        let index = enpassant_board.trailing_zeros() as usize;
        enpassant_board ^= 1u64 << index;
        //Check if rare case didn't happen
        //Remove t-7,t-8 or t+7,t+8
        let all_pieces_without_en_passants = all_pieces_without_my_king & !bitboards::SQUARES[if *color_to_move == 0 { index - source_shift } else { index + source_shift }]
            & !bitboards::SQUARES[if *color_to_move == 0 { index - 8 } else { index + 8 }];
        if rook_attack(my_king_idx, all_pieces_without_en_passants) & (!bitboards::FILES[my_king_idx % 8]) & enemy_rooks != 0 {
            continue;
        }
        move_list.push(GameMove {
            from: if *color_to_move == 0 { index - source_shift } else { index + source_shift },
            to: index,
            move_type: GameMoveType::EnPassant,
            piece_type: PieceType::Pawn,
        });
    }
}

//Make moves
pub fn make_move(g: &game_state::GameState, mv: &game_state::GameMove) -> game_state::GameState {
    match mv.move_type {
        GameMoveType::Quiet => make_quiet_move(&g, &mv),
        GameMoveType::Capture => make_capture_move(&g, &mv),
        GameMoveType::EnPassant => make_enpassant_move(&g, &mv),
        GameMoveType::Castle => make_castle_move(&g, &mv),
        GameMoveType::Promotion(PieceType::Queen) | GameMoveType::Promotion(PieceType::Rook) | GameMoveType::Promotion(PieceType::Bishop) | GameMoveType::Promotion(PieceType::Knight)
        => make_promotion_move(&g, &mv),
        _ => panic!("Invalid move type")
    }
}

pub fn move_piece(pieces: &mut [[u64; 2]; 6], mv: &game_state::GameMove, move_color: usize) {
    let index = match mv.piece_type {
        PieceType::Pawn => 0,
        PieceType::Knight => 1,
        PieceType::Bishop => 2,
        PieceType::Rook => 3,
        PieceType::Queen => 4,
        PieceType::King => 5,
    };
    pieces[index][move_color] ^= bitboards::SQUARES[mv.from];
    pieces[index][move_color] |= bitboards::SQUARES[mv.to];
    //pieces[index][move_color] ^= 1u64<<mv.from;
    //pieces[index][move_color] |= 1u64<<mv.to;
}

pub fn delete_piece(pieces: &mut [[u64; 2]; 6], delete_square: usize, delete_color: usize) {
    pieces[0][delete_color] &= bitboards::NOT_SQUARES[delete_square];
    pieces[1][delete_color] &= bitboards::NOT_SQUARES[delete_square];
    pieces[2][delete_color] &= bitboards::NOT_SQUARES[delete_square];
    pieces[3][delete_color] &= bitboards::NOT_SQUARES[delete_square];
    pieces[4][delete_color] &= bitboards::NOT_SQUARES[delete_square];
}

pub fn check_castle_flags(ck: bool, cq: bool, mv: &game_state::GameMove, color_to_move: usize, pieces: [[u64; 2]; 6]) -> (bool, bool) {
    match mv.piece_type {
        PieceType::King => (false, false),
        PieceType::Rook => {
            let mut new_ck = ck;
            if ck {
                if color_to_move == 0 {
                    if pieces[3][0] & bitboards::SQUARES[7] == 0 {
                        new_ck = false;
                    }
                } else {
                    if pieces[3][1] & bitboards::SQUARES[63] == 0 {
                        new_ck = false;
                    }
                }
            }
            let mut new_cq = cq;
            if cq {
                if color_to_move == 0 {
                    if pieces[3][0] & bitboards::SQUARES[0] == 0 {
                        new_cq = false;
                    }
                } else {
                    if pieces[3][1] & bitboards::SQUARES[56] == 0 {
                        new_cq = false;
                    }
                }
            }
            (new_ck, new_cq)
        }
        _ => (ck, cq)
    }
}

pub fn make_quiet_move(g: &game_state::GameState, mv: &game_state::GameMove) -> game_state::GameState {
    let color_to_move = 1 - g.color_to_move;
    let mut pieces = g.pieces.clone();
    //Make the move
    move_piece(&mut pieces, &mv, g.color_to_move);

    //Check new castle rights
    //The enemies castle right's can't change on a quiet move
    let (castle_white_kingside, castle_white_queenside) = if g.color_to_move == 0 {
        check_castle_flags(g.castle_white_kingside, g.castle_white_queenside, &mv, g.color_to_move, pieces)
    } else { (g.castle_white_kingside, g.castle_white_queenside) };
    let (castle_black_kingside, castle_black_queenside) = if g.color_to_move == 0 {
        (g.castle_black_kingside, g.castle_black_queenside)
    } else { check_castle_flags(g.castle_black_kingside, g.castle_black_queenside, &mv, g.color_to_move, pieces) };

    //This will be taken care of later
    let mut en_passant = 0u64;

    let mut half_moves = g.half_moves + 1;

    //Reset half moves if its a pawn move and also check if its a double pawn move, if so, set en passant flag
    match mv.piece_type {
        PieceType::Pawn => {
            half_moves = 0;
            if g.color_to_move == 0 && mv.to - mv.from == 16 {
                en_passant = bitboards::SQUARES[mv.to - 8];
            } else if g.color_to_move == 1 && mv.from - mv.to == 16 {
                en_passant = bitboards::SQUARES[mv.to + 8];
            }
        }
        _ => {}
    };

    //If black was to move, increase full moves by one
    let full_moves = g.full_moves + g.color_to_move;
    //Create new game state object
    game_state::GameState {
        color_to_move,
        pieces,
        castle_white_kingside,
        castle_white_queenside,
        castle_black_kingside,
        castle_black_queenside,
        en_passant,
        half_moves,
        full_moves,
    }
}

pub fn make_capture_move(g: &game_state::GameState, mv: &game_state::GameMove) -> game_state::GameState {
    let color_to_move = 1 - g.color_to_move;
    let mut pieces = g.pieces.clone();
    //Make the move
    move_piece(&mut pieces, &mv, g.color_to_move);
    //Delete to from enemy pieces
    delete_piece(&mut pieces, mv.to, color_to_move);

    let (mut castle_white_kingside, mut castle_white_queenside) = if g.color_to_move == 0 {
        check_castle_flags(g.castle_white_kingside, g.castle_white_queenside, &mv, g.color_to_move, pieces)
    } else { (g.castle_white_kingside, g.castle_white_queenside) };
    let (mut castle_black_kingside, mut castle_black_queenside) = if g.color_to_move == 0 {
        (g.castle_black_kingside, g.castle_black_queenside)
    } else { check_castle_flags(g.castle_black_kingside, g.castle_black_queenside, &mv, g.color_to_move, pieces) };

    if g.color_to_move == 0 {
        //Check that blacks rook didn't get captured
        if pieces[3][1] & bitboards::SQUARES[56] == 0 {
            castle_black_queenside = false;
        }
        if pieces[3][1] & bitboards::SQUARES[63] == 0 {
            castle_black_kingside = false;
        }
    } else {
        if pieces[3][0] & bitboards::SQUARES[0] == 0 {
            castle_white_queenside = false;
        }
        if pieces[3][0] & bitboards::SQUARES[7] == 0 {
            castle_white_kingside = false;
        }
    }
    let en_passant = 0u64;

    let half_moves = 0usize;
    let full_moves = g.full_moves + g.color_to_move;

    game_state::GameState {
        color_to_move,
        pieces,
        castle_white_kingside,
        castle_white_queenside,
        castle_black_kingside,
        castle_black_queenside,
        en_passant,
        half_moves,
        full_moves,
    }
}

pub fn make_enpassant_move(g: &game_state::GameState, mv: &game_state::GameMove) -> game_state::GameState {
    let color_to_move = 1 - g.color_to_move;
    let mut pieces = g.pieces.clone();
    //Make the move
    move_piece(&mut pieces, &mv, g.color_to_move);
    //Delete enemy pawn
    delete_piece(&mut pieces, if g.color_to_move == 0 { mv.to - 8 } else { mv.to + 8 }, color_to_move);

    let castle_white_kingside = g.castle_white_kingside;
    let castle_white_queenside = g.castle_white_queenside;
    let castle_black_kingside = g.castle_black_kingside;
    let castle_black_queenside = g.castle_black_queenside;

    let en_passant = 0u64;

    let half_moves = 0usize;
    let full_moves = g.full_moves + g.color_to_move;

    game_state::GameState {
        color_to_move,
        pieces,
        castle_white_kingside,
        castle_white_queenside,
        castle_black_kingside,
        castle_black_queenside,
        en_passant,
        half_moves,
        full_moves,
    }
}

pub fn make_castle_move(g: &game_state::GameState, mv: &game_state::GameMove) -> game_state::GameState {
    let color_to_move = 1 - g.color_to_move;
    let mut pieces = g.pieces.clone();
    //Move the king
    move_piece(&mut pieces, &mv, g.color_to_move);

    //Move the rook
    //Determine if its kingside or queenside castle
    //Kingside
    if mv.to == 58 {
        pieces[3][1] ^= bitboards::SQUARES[56];
        pieces[3][1] |= bitboards::SQUARES[59];
    } else if mv.to == 2 {
        pieces[3][0] ^= bitboards::SQUARES[0];
        pieces[3][0] |= bitboards::SQUARES[3];
    } else if mv.to == 62 {//Queenside
        pieces[3][1] ^= bitboards::SQUARES[63];
        pieces[3][1] |= bitboards::SQUARES[61];
    } else if mv.to == 6 {
        pieces[3][0] ^= bitboards::SQUARES[7];
        pieces[3][0] |= bitboards::SQUARES[5];
    }

    let (castle_white_kingside, castle_white_queenside) = if g.color_to_move == 0 { (false, false) } else {
        (g.castle_white_kingside, g.castle_white_queenside)
    };
    let (castle_black_kingside, castle_black_queenside) = if g.color_to_move == 1 { (false, false) } else {
        (g.castle_black_kingside, g.castle_black_queenside)
    };

    let en_passant = 0u64;

    let half_moves = g.half_moves + 1;
    let full_moves = g.full_moves + g.color_to_move;

    game_state::GameState {
        color_to_move,
        pieces,
        castle_white_kingside,
        castle_white_queenside,
        castle_black_kingside,
        castle_black_queenside,
        en_passant,
        half_moves,
        full_moves,
    }
}

pub fn make_promotion_move(g: &game_state::GameState, mv: &game_state::GameMove) -> game_state::GameState {
    let color_to_move = 1 - g.color_to_move;
    let mut pieces = g.pieces.clone();
    //Make the move
    move_piece(&mut pieces, &mv, g.color_to_move);
    //Delete enemy piece if any on there
    delete_piece(&mut pieces, mv.to, color_to_move);
    //Delete my pawn
    pieces[0][g.color_to_move] ^= bitboards::SQUARES[mv.to];
    //Add piece respectivly
    pieces[match mv.move_type {
        GameMoveType::Promotion(PieceType::Queen) => { 4 }
        GameMoveType::Promotion(PieceType::Knight) => { 1 }
        GameMoveType::Promotion(PieceType::Bishop) => { 2 }
        GameMoveType::Promotion(PieceType::Rook) => { 3 }
        _ => panic!("Invalid Type")
    }][g.color_to_move] |= bitboards::SQUARES[mv.to];

    let mut castle_white_kingside = g.castle_white_kingside;
    let mut castle_white_queenside = g.castle_white_queenside;
    let mut castle_black_kingside = g.castle_black_kingside;
    let mut castle_black_queenside = g.castle_black_queenside;

    if g.color_to_move == 0 {
        //Check that blacks rook didn't get captured
        if pieces[3][1] & bitboards::SQUARES[56] == 0 {
            castle_black_queenside = false;
        }
        if pieces[3][1] & bitboards::SQUARES[63] == 0 {
            castle_black_kingside = false;
        }
    } else {
        if pieces[3][0] & bitboards::SQUARES[0] == 0 {
            castle_white_queenside = false;
        }
        if pieces[3][0] & bitboards::SQUARES[7] == 0 {
            castle_white_kingside = false;
        }
    }

    let en_passant = 0u64;

    let half_moves = 0usize;
    let full_moves = g.full_moves + g.color_to_move;

    game_state::GameState {
        color_to_move,
        pieces,
        castle_white_kingside,
        castle_white_queenside,
        castle_black_kingside,
        castle_black_queenside,
        en_passant,
        half_moves,
        full_moves,
    }
}

pub fn generate_moves(g: &game_state::GameState) -> (Vec<GameMove>, bool) {
    //Following this guide:
    // https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/

    let mut move_list: Vec<GameMove> = Vec::with_capacity(60);
    let color_to_move = g.color_to_move;
    let enemy_color = 1 - color_to_move;

    //Get my pieces
    let my_king = g.pieces[5][color_to_move];
    let my_king_idx = my_king.trailing_zeros() as usize;

    let mut my_pawns = g.pieces[0][color_to_move];

    let mut my_knights = g.pieces[1][color_to_move];

    let mut my_bishops = g.pieces[2][color_to_move] | g.pieces[4][color_to_move];

    let mut my_rooks = g.pieces[3][color_to_move] | g.pieces[4][color_to_move];
    //Need this to xor out queens later, when we look at pinned pieces
    let my_queens = g.pieces[4][color_to_move];

    //Get enemy pieces
    let enemy_king = g.pieces[5][enemy_color];
    let enemy_king_idx = enemy_king.trailing_zeros() as usize;

    let enemy_pawns = g.pieces[0][enemy_color];

    let enemy_knights = g.pieces[1][enemy_color];

    let enemy_bishops = g.pieces[2][enemy_color] | g.pieces[4][enemy_color];

    let enemy_rooks = g.pieces[3][enemy_color] | g.pieces[4][enemy_color];

    let my_pieces = my_king | my_pawns | my_knights | my_bishops | my_rooks;
    let not_my_pieces = !my_pieces;
    let enemy_sliders = enemy_bishops | enemy_rooks;
    let enemy_pieces = enemy_pawns | enemy_knights | enemy_sliders | enemy_king;
    let not_enemy_pieces = !enemy_pieces;
    let all_pieces_without_my_king = enemy_pieces | (my_pieces & !my_king);
    let all_pieces = all_pieces_without_my_king | my_king;
    let empty = !all_pieces;

    let unsafe_white_squares = if color_to_move == 0 {
        get_b_attacked_squares(enemy_king_idx, enemy_pawns, enemy_knights, enemy_bishops, enemy_rooks
                               , all_pieces_without_my_king)
    } else {
        get_w_attacked_squares(enemy_king_idx, enemy_pawns, enemy_knights, enemy_bishops, enemy_rooks
                               , all_pieces_without_my_king)
    };
    let possible_king_moves = king_attack(my_king_idx) & !unsafe_white_squares & not_my_pieces;
    add_moves(&mut move_list, my_king_idx, possible_king_moves & not_enemy_pieces, &PieceType::King, GameMoveType::Quiet);
    add_moves(&mut move_list, my_king_idx, possible_king_moves & enemy_pieces, &PieceType::King, GameMoveType::Capture);
    let (king_attackers_board, checking_piece_is_slider, checking_piece_slider_is_bishop) = if unsafe_white_squares & my_king == 0 {
        (0u64, false, false)
    } else {
        if color_to_move == 0 {
            attackers_from_black(my_king, my_king_idx, enemy_pawns, enemy_knights
                                 , enemy_bishops, enemy_rooks, all_pieces)
        } else {
            attackers_from_white(my_king, my_king_idx, enemy_pawns, enemy_knights
                                 , enemy_bishops, enemy_rooks, all_pieces)
        }
    };

    let num_checkers = king_attackers_board.count_ones();
    //Double check
    if num_checkers > 1 { //Then only king moves are possible anyway
        return (move_list, true);
    }
    //Calculate capture and push mask
    let mut capture_mask = 0xFFFFFFFFFFFFFFFFu64;
    let mut push_mask = 0xFFFFFFFFFFFFFFFFu64;
    //Single-Check
    {
        if num_checkers == 1 {
            capture_mask = king_attackers_board;
            if checking_piece_is_slider {
                let checking_piece_square = king_attackers_board.trailing_zeros() as usize;
                if checking_piece_slider_is_bishop {
                    push_mask = get_bishop_ray(bishop_attack(checking_piece_square, 0u64), my_king_idx, checking_piece_square);
                } else {
                    push_mask = get_rook_ray(rook_attack(checking_piece_square, 0u64), my_king_idx, checking_piece_square);
                }
            } else {
                push_mask = 0u64;
            }
        }
    }

    //Pinned pieces
    {//Pinned by rook
        let rook_attacks_from_my_king_postion = rook_attack(my_king_idx, all_pieces);
        //See one layer through my pieces
        //If a rook is found seeing through one piece, the piece is pinned
        let xray_rooks = xray_rook_attacks(rook_attacks_from_my_king_postion, all_pieces, my_pieces, my_king_idx);
        //Go through all directions
        //Find the rooks with xray
        let mut rooks_on_xray = xray_rooks & enemy_rooks;
        while rooks_on_xray != 0 {
            let rook_position = rooks_on_xray.trailing_zeros() as usize;
            rooks_on_xray &= rooks_on_xray - 1;
            let ray = get_rook_ray(rook_attacks_from_my_king_postion | xray_rooks, rook_position, my_king_idx);
            let pinned_piece = ray & my_pieces;
            let pinned_piece_position = pinned_piece.trailing_zeros() as usize;
            if pinned_piece & my_rooks != 0 {
                let mut piece_type = PieceType::Rook;
                if pinned_piece & my_queens != 0 {
                    my_bishops ^= pinned_piece;
                    piece_type = PieceType::Queen;
                }
                my_rooks ^= pinned_piece;
                add_moves(&mut move_list, pinned_piece_position, ray & !pinned_piece & push_mask, &piece_type, GameMoveType::Quiet);
                //Don't forget that we can capture the rook aswell
                add_moves(&mut move_list, pinned_piece_position, bitboards::SQUARES[rook_position] & capture_mask, &piece_type, GameMoveType::Capture);
                continue;
            }
            if pinned_piece & my_pawns != 0 {
                my_pawns ^= pinned_piece;
                let pawn_push_once = if color_to_move == 0 { w_single_push_pawn_targets(pinned_piece, empty) } else { b_single_push_pawn_targets(pinned_piece, empty) } & ray;
                let pawn_push_twice = if color_to_move == 0 { w_double_push_pawn_targets(pinned_piece, empty) } else { b_double_push_pawn_targets(pinned_piece, empty) } & ray;
                add_moves(&mut move_list, pinned_piece_position, (pawn_push_once | pawn_push_twice) & push_mask, &PieceType::Pawn, GameMoveType::Quiet);
                continue;
            }
            if pinned_piece & my_knights != 0 {
                my_knights ^= pinned_piece;
                continue;
            }
            if pinned_piece & my_bishops != 0 {
                my_bishops ^= pinned_piece;
            }
        }
        //Pinned by bishop
        let bishop_attacks_from_my_king_position = bishop_attack(my_king_idx, all_pieces);
        let xray_bishops = xray_bishop_attacks(bishop_attacks_from_my_king_position, all_pieces, my_pieces, my_king_idx);
        let mut bishops_on_xray = xray_bishops & enemy_bishops;
        while bishops_on_xray != 0 {
            let bishop_position = bishops_on_xray.trailing_zeros() as usize;
            bishops_on_xray &= bishops_on_xray - 1;
            let ray = get_bishop_ray(bishop_attacks_from_my_king_position | xray_bishops, bishop_position, my_king_idx);
            let pinned_piece = ray & my_pieces;
            let pinned_piece_position = pinned_piece.trailing_zeros() as usize;
            if pinned_piece & my_bishops != 0 {
                let mut piece_type = PieceType::Bishop;
                if pinned_piece & my_queens != 0 {
                    my_rooks ^= pinned_piece;
                    piece_type = PieceType::Queen;
                }
                my_bishops ^= pinned_piece;

                add_moves(&mut move_list, pinned_piece_position, ray & !pinned_piece & push_mask, &piece_type, GameMoveType::Quiet);
                add_moves(&mut move_list, pinned_piece_position, bitboards::SQUARES[bishop_position] & capture_mask, &piece_type, GameMoveType::Capture);
                continue;
            }
            if pinned_piece & my_pawns != 0 {
                my_pawns ^= pinned_piece;
                let pawn_targets = if color_to_move == 0 { w_pawn_east_targets(pinned_piece) } else { b_pawn_east_targets(pinned_piece) } | if color_to_move == 0 { w_pawn_west_targets(pinned_piece) } else { b_pawn_west_targets(pinned_piece) };
                let pawn_captures = pawn_targets & bitboards::SQUARES[bishop_position] & capture_mask;
                //let pawn_enpassants = pawn_targets & g.en_passant;
                add_moves(&mut move_list, pinned_piece_position, pawn_captures, &PieceType::Pawn, GameMoveType::Capture);
                //add_moves(&mut move_list, pinned_piece_position, pawn_enpassants, &PieceType::Pawn, GameMoveType::EnPassant);
                continue;
            }
            if pinned_piece & my_knights != 0 {
                my_knights ^= pinned_piece;
                continue;
            }
            if pinned_piece & my_rooks != 0 {
                my_rooks ^= pinned_piece;
            }
        }
    }
    //Calculate normal moves
    //Pawns
    {
        //Single push
        {
            let my_pawns_single_push = if color_to_move == 0 { w_single_push_pawn_targets(my_pawns, empty) } else { b_single_push_pawn_targets(my_pawns, empty) } & push_mask;
            let my_pawns_no_promotion = my_pawns_single_push & !bitboards::RANKS[if color_to_move == 0 { 7 } else { 0 }];
            let my_pawns_promotion = my_pawns_single_push & bitboards::RANKS[if color_to_move == 0 { 7 } else { 0 }];
            add_quiet_pawn_single_pushes(my_pawns_no_promotion, &color_to_move, &mut move_list);
            add_promotion_push(my_pawns_promotion, &color_to_move, &mut move_list, 8usize);
        }
        //Double push
        {
            let my_pawns_double_push = if color_to_move == 0 { w_double_push_pawn_targets(my_pawns, empty) } else { b_double_push_pawn_targets(my_pawns, empty) } & push_mask;
            add_quiet_pawn_double_pushes(my_pawns_double_push, &color_to_move, &mut move_list);
        }
        //Capture west
        {
            let my_pawns_west_targets = if color_to_move == 0 { w_pawn_west_targets(my_pawns) } else { b_pawn_west_targets(my_pawns) };
            let my_pawns_west_normal_captures = my_pawns_west_targets & capture_mask & enemy_pieces;
            //Checking for promotion on capture
            let my_pawns_no_promotion = my_pawns_west_normal_captures & !bitboards::RANKS[if color_to_move == 0 { 7 } else { 0 }];
            let my_pawns_promotion = my_pawns_west_normal_captures & bitboards::RANKS[if color_to_move == 0 { 7 } else { 0 }];
            //Capture
            add_pawn_capture(my_pawns_no_promotion, &color_to_move, &mut move_list, 7usize);
            //Promotion capture
            add_promotion_push(my_pawns_promotion, &color_to_move, &mut move_list, 7usize);


            //En passant
            //We can capture en passant, if its in capture mask aswell
            let my_pawns_west_enpassants = my_pawns_west_targets & g.en_passant & if color_to_move == 0 { capture_mask << 8 } else { capture_mask >> 8 };
            add_en_passants(my_pawns_west_enpassants, &color_to_move, &mut move_list, 7usize, all_pieces_without_my_king, enemy_rooks, my_king_idx);
        }
        //Capture east
        {
            let my_pawns_east_targets = if color_to_move == 0 { w_pawn_east_targets(my_pawns) } else { b_pawn_east_targets(my_pawns) };
            let my_pawns_east_normal_captures = my_pawns_east_targets & capture_mask & enemy_pieces;
            //Checking for promotion on capture
            let my_pawns_no_promotion = my_pawns_east_normal_captures & !bitboards::RANKS[if color_to_move == 0 { 7 } else { 0 }];
            let my_pawns_promotion = my_pawns_east_normal_captures & bitboards::RANKS[if color_to_move == 0 { 7 } else { 0 }];

            add_pawn_capture(my_pawns_no_promotion, &color_to_move, &mut move_list, 9usize);
            add_promotion_push(my_pawns_promotion, &color_to_move, &mut move_list, 9usize);
            //En passants
            let  my_pawns_east_enpassants = my_pawns_east_targets & g.en_passant & if color_to_move == 0 { capture_mask << 8 } else { capture_mask >> 8 };
            add_en_passants(my_pawns_east_enpassants, &color_to_move, &mut move_list, 9usize, all_pieces_without_my_king, enemy_rooks, my_king_idx);
        }
    }
    //Knights
    {
        while my_knights != 0u64 {
            let index = if color_to_move == 0 { 63usize - my_knights.leading_zeros() as usize } else { my_knights.trailing_zeros() as usize };
            let my_knight_attacks = knight_attack(index) & not_my_pieces;
            let my_knight_captures = my_knight_attacks & enemy_pieces & capture_mask;
            add_moves(&mut move_list, index, my_knight_captures, &PieceType::Knight, GameMoveType::Capture);
            let my_knight_quiets = my_knight_attacks & !enemy_pieces & push_mask;
            add_moves(&mut move_list, index, my_knight_quiets, &PieceType::Knight, GameMoveType::Quiet);
            my_knights ^= 1u64 << index;
        }
    }
    //Bishops
    {
        while my_bishops != 0u64 {
            let index = if color_to_move == 0 { 63usize - my_bishops.leading_zeros() as usize } else { my_bishops.trailing_zeros() as usize };
            let my_bishop_attack = bishop_attack(index, all_pieces) & not_my_pieces;
            let my_bishop_capture = my_bishop_attack & enemy_pieces & capture_mask;
            let piece_type = if bitboards::SQUARES[index] & my_queens != 0 { PieceType::Queen } else { PieceType::Bishop };
            add_moves(&mut move_list, index, my_bishop_capture, &piece_type, GameMoveType::Capture);
            let my_bishop_quiet = my_bishop_attack & !enemy_pieces & push_mask;
            add_moves(&mut move_list, index, my_bishop_quiet, &piece_type, GameMoveType::Quiet);
            my_bishops ^= 1u64 << index;
        }
    }
    //Rooks
    {
        while my_rooks != 0u64 {
            let index = if color_to_move == 0 { 63usize - my_rooks.leading_zeros() as usize } else { my_rooks.trailing_zeros() as usize };
            let my_rook_attack = rook_attack(index, all_pieces) & not_my_pieces;
            let my_rook_capture = my_rook_attack & enemy_pieces & capture_mask;
            let piece_type = if bitboards::SQUARES[index] & my_queens != 0 { PieceType::Queen } else { PieceType::Rook };
            add_moves(&mut move_list, index, my_rook_capture, &piece_type, GameMoveType::Capture);
            let my_rook_quiets = my_rook_attack & !enemy_pieces & push_mask;
            add_moves(&mut move_list, index, my_rook_quiets, &piece_type, GameMoveType::Quiet);
            my_rooks ^= 1u64 << index;
        }
    }
    //Castles
    if num_checkers == 0 {
        if g.color_to_move == 0 {
            //Make sure there is no piece in between and safe squares
            if g.castle_white_kingside {
                if (all_pieces | unsafe_white_squares) & (bitboards::SQUARES[5] | bitboards::SQUARES[6]) == 0 {
                    move_list.push(GameMove {
                        from: my_king_idx,
                        to: 6usize,
                        move_type: GameMoveType::Castle,
                        piece_type: PieceType::King,
                    });
                }
            }
            if g.castle_white_queenside {
                if ((all_pieces | unsafe_white_squares) & (bitboards::SQUARES[2] | bitboards::SQUARES[3]) | all_pieces & bitboards::SQUARES[1]) == 0 {
                    move_list.push(GameMove {
                        from: my_king_idx,
                        to: 2usize,
                        move_type: GameMoveType::Castle,
                        piece_type: PieceType::King,
                    });
                }
            }
        } else {
            if g.castle_black_kingside {
                if (all_pieces | unsafe_white_squares) & (bitboards::SQUARES[61] | bitboards::SQUARES[62]) == 0 {
                    move_list.push(GameMove {
                        from: my_king_idx,
                        to: 62usize,
                        move_type: GameMoveType::Castle,
                        piece_type: PieceType::King,
                    });
                }
            }
            if g.castle_black_queenside {
                if ((all_pieces | unsafe_white_squares) & (bitboards::SQUARES[58] | bitboards::SQUARES[59]) | all_pieces & bitboards::SQUARES[57]) == 0 {
                    move_list.push(GameMove {
                        from: my_king_idx,
                        to: 58usize,
                        move_type: GameMoveType::Castle,
                        piece_type: PieceType::King,
                    });
                }
            }
        }
    }
    (move_list, num_checkers > 0)
}

pub fn xray_rook_attacks(attacks: u64, occupied_square: u64, one_time_blockers: u64, rook_square: usize) -> u64 {
    return attacks ^ rook_attack(rook_square, occupied_square ^ (one_time_blockers & attacks));
}

pub fn xray_bishop_attacks(attacks: u64, occupied_square: u64, one_time_blockers: u64, bishop_square: usize) -> u64 {
    return attacks ^ bishop_attack(bishop_square, occupied_square ^ (one_time_blockers & attacks));
}

//Gets the ray of one rook into a specific direction
pub fn get_rook_ray(rook_attacks_in_all_directions: u64, target_square: usize, rook_square: usize) -> u64 {
    let diff = target_square as isize - rook_square as isize;
    let target_rank = target_square / 8;
    let target_file = target_square % 8;
    let rook_rank = rook_square / 8;
    let rook_file = rook_square % 8;
    if diff > 0 {
        //Same vertical
        if target_rank == rook_rank {
            return bitboards::FILES_LESS_THAN[target_file] & bitboards::FILES_GREATER_THAN[rook_file] & rook_attacks_in_all_directions;
        } else {
            return bitboards::RANKS_LESS_THAN[target_rank] & bitboards::RANKS_GREATER_THAN[rook_rank] & rook_attacks_in_all_directions;
        }
    } else {
        if target_rank == rook_rank {
            return bitboards::FILES_GREATER_THAN[target_file] & bitboards::FILES_LESS_THAN[rook_file] & rook_attacks_in_all_directions;
        } else {
            return bitboards::RANKS_GREATER_THAN[target_rank] & bitboards::RANKS_LESS_THAN[rook_rank] & rook_attacks_in_all_directions;
        }
    }
}

//Gets the rof of one bishop into a specific direction
pub fn get_bishop_ray(bishop_attack_in_all_directions: u64, target_square: usize, bishop_square: usize) -> u64 {
    let diff = target_square as isize - bishop_square as isize;
    let target_rank = target_square / 8;
    let target_file = target_square % 8;
    let bishop_rank = bishop_square / 8;
    let bishop_file = bishop_square % 8;
    if diff > 0 {
        if diff % 7 == 0 {
            return bitboards::FILES_GREATER_THAN[target_file] & bitboards::FILES_LESS_THAN[bishop_file]
                & bitboards::RANKS_LESS_THAN[target_rank] & bitboards::RANKS_GREATER_THAN[bishop_rank]
                & bishop_attack_in_all_directions;
        } else {
            return bitboards::FILES_LESS_THAN[target_file] & bitboards::FILES_GREATER_THAN[bishop_file]
                & bitboards::RANKS_LESS_THAN[target_rank] & bitboards::RANKS_GREATER_THAN[bishop_rank]
                & bishop_attack_in_all_directions;
        }
    } else {
        if diff % -7 == 0 {
            return bitboards::FILES_LESS_THAN[target_file] & bitboards::FILES_GREATER_THAN[bishop_file]
                & bitboards::RANKS_GREATER_THAN[target_rank] & bitboards::RANKS_LESS_THAN[bishop_rank]
                & bishop_attack_in_all_directions;
        } else {
            return bitboards::FILES_GREATER_THAN[target_file] & bitboards::FILES_LESS_THAN[bishop_file]
                & bitboards::RANKS_GREATER_THAN[target_rank] & bitboards::RANKS_LESS_THAN[bishop_rank]
                & bishop_attack_in_all_directions;
        }
    }
}

pub fn attackers_from_white(square_board: u64, square: usize, white_pawns: u64, white_knights: u64, white_bishops: u64, white_rooks: u64, blockers: u64) -> (u64, bool, bool) {
    let mut attackers = 0u64;
    let mut slider_flag = false;
    let mut bishop_slider = false;
    attackers |= knight_attack(square) & white_knights;
    attackers |= (b_pawn_west_targets(square_board) | b_pawn_east_targets(square_board)) & white_pawns;
    let bishop_attacks = bishop_attack(square, blockers) & white_bishops;
    attackers |= bishop_attacks;
    if bishop_attacks != 0 {
        slider_flag = true;
        bishop_slider = true;
    }
    let rook_attacks = rook_attack(square, blockers) & white_rooks;
    attackers |= rook_attacks;
    if rook_attacks != 0 {
        slider_flag = true;
    }
    (attackers, slider_flag, bishop_slider)
}

pub fn attackers_from_black(square_board: u64, square: usize, black_pawns: u64, black_knights: u64, black_bishops: u64, black_rooks: u64, blockers: u64) -> (u64, bool, bool) {
    let mut attackers = 0u64;
    let mut slider_flag = false;
    let mut bishop_slider = false;
    attackers |= knight_attack(square) & black_knights;
    attackers |= (w_pawn_west_targets(square_board) | w_pawn_east_targets(square_board)) & black_pawns;
    let bishop_attacks = bishop_attack(square, blockers) & black_bishops;
    attackers |= bishop_attacks;
    if bishop_attacks != 0 {
        slider_flag = true;
        bishop_slider = true;
    }
    let rook_attacks = rook_attack(square, blockers) & black_rooks;
    attackers |= rook_attacks;
    if rook_attacks != 0 {
        slider_flag = true;
    }
    (attackers, slider_flag, bishop_slider)
}

pub fn get_w_attacked_squares(white_king_idx: usize, white_pawns: u64, mut white_knights: u64, mut white_bishops: u64, mut white_rooks: u64, blocked_squares: u64) -> u64 {
    let mut res = 0u64;
    res |= king_attack(white_king_idx);
    res |= w_pawn_west_targets(white_pawns) | w_pawn_east_targets(white_pawns);
    while white_knights != 0u64 {
        let sq = 63usize - white_knights.leading_zeros() as usize;
        res |= knight_attack(sq);
        white_knights ^= 1u64 << sq;
    }
    while white_bishops != 0u64 {
        let sq = 63usize - white_bishops.leading_zeros() as usize;
        res |= bishop_attack(sq, blocked_squares);
        white_bishops ^= 1u64 << sq;
    }
    while white_rooks != 0u64 {
        let sq = 63usize - white_rooks.leading_zeros() as usize;
        res |= rook_attack(sq, blocked_squares);
        white_rooks ^= 1u64 << sq;
    }
    res
}

pub fn get_b_attacked_squares(black_king_idx: usize, black_pawns: u64, mut black_knights: u64, mut black_bishops: u64, mut black_rooks: u64, blocked_squares: u64) -> u64 {
    let mut res = 0u64;
    res |= king_attack(black_king_idx);
    res |= b_pawn_west_targets(black_pawns) | b_pawn_east_targets(black_pawns);
    while black_knights != 0u64 {
        let sq = black_knights.trailing_zeros() as usize;
        res |= knight_attack(sq);
        black_knights ^= 1u64 << sq;
    }
    while black_bishops != 0u64 {
        let sq = black_bishops.trailing_zeros() as usize;
        res |= bishop_attack(sq, blocked_squares);
        black_bishops ^= 1u64 << sq;
    }
    while black_rooks != 0u64 {
        let sq = black_rooks.trailing_zeros() as usize;
        res |= rook_attack(sq, blocked_squares);
        black_rooks ^= 1u64 << sq;
    }
    res
}

A quick look into valgrind/callgrind Callgrind result also reveals the fact, that add_moves() takes up about 25% of the runtime, while all it does is iterating through the target-squares and pushing the moves found into the move_list vector.This seems a bit odd to me. Weirdly enough, adding #[inline(always)] to all of the add_moves functions increases the generation speed from 75 to 85 million nodes per second.

Now my question is, am I missing a core concept of move generation here, or is my code just badly written? If it's badly written, how can I improve?

I should also mention that I am still pretty new to rust, so I am glad about any non-idiomacy being pointed out.

In the github repository there are also about 50 test cases which indeed confirm that my implementation is working.

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.