chess-lib 0.1.3

use crate::engine::bitboard::{
    get_single_piece_bitboard, is_diagonal, occupied_squares, Bitboard, Direction, A_FILE,
    CASTLING_BLACK_KING_JUMP_SQUARES, CASTLING_BLACK_KING_OCCUPIABLE_SQUARES,
    CASTLING_BLACK_KING_SQUARE, CASTLING_BLACK_QUEEN_JUMP_SQUARES,
    CASTLING_BLACK_QUEEN_OCCUPIABLE_SQUARES, CASTLING_BLACK_QUEEN_SQUARE,
    CASTLING_WHITE_KING_JUMP_SQUARES, CASTLING_WHITE_KING_OCCUPIABLE_SQUARES,
    CASTLING_WHITE_KING_SQUARE, CASTLING_WHITE_QUEEN_JUMP_SQUARES,
    CASTLING_WHITE_QUEEN_OCCUPIABLE_SQUARES, CASTLING_WHITE_QUEEN_SQUARE, DIRECTIONS, EAST, EMPTY,
    H_FILE, NORTH, NORTH_EAST, NORTH_WEST, RANK_1, RANK_2, RANK_7, RANK_8, SOUTH, SOUTH_EAST,
    SOUTH_WEST, WEST,
};
use crate::engine::board::Board;
use crate::engine::common::Piece::{Bishop, King, Knight, Pawn, Queen, Rook};
use crate::engine::common::{Color, Move, Piece, Promotion, Square};
use crate::engine::magics::Tables;
use crate::engine::moves::{
    lookup_bishop, lookup_king, lookup_knight, lookup_queen, lookup_rook, to_moves,
};

#[derive(Copy, Clone)]
pub struct MoveGenerator<'a> {
    board: Board,

    in_check: bool,
    in_double_check: bool,
    pins_exists: bool,

    friendly_color: Color,
    opponent_color: Color,

    enemy_or_empty: Bitboard,

    pin_horizontal_ray: Bitboard,
    pin_vertical_ray: Bitboard,
    pin_diagonal_a1_to_h8_ray: Bitboard,
    pin_diagonal_a8_to_h1_ray: Bitboard,

    check_ray: Bitboard,
    friendly_king: Bitboard,
    opponent_attack_map: Bitboard,
    friendly_color_board: Bitboard,
    opponent_color_board: Bitboard,

    tables: &'a Tables,
}

impl<'a> MoveGenerator<'a> {
    pub fn new(board: Board, tables: &'a Tables) -> Self {
        let in_check = false;
        let in_double_check = false;
        let pins_exists = false;

        let friendly_color = board.turn;
        let opponent_color = board.turn.opposite();
        let enemy_or_empty = board.enemy_or_empty();
        let opponent_attack_map = EMPTY;
        let pin_horizontal_ray = EMPTY;
        let pin_vertical_ray = EMPTY;
        let pin_diagonal_a1_to_h8_ray = EMPTY;
        let pin_diagonal_a8_to_h1_ray = EMPTY;

        let check_ray = EMPTY;
        let friendly_king = board.get_piece_bitboard(King, friendly_color);
        let friendly_color_board = board.get_color_bitboard(friendly_color);
        let opponent_color_board = board.get_color_bitboard(opponent_color);

        Self {
            board,
            tables,
            in_check,
            in_double_check,
            friendly_color,
            opponent_color,
            friendly_king,
            pins_exists,
            pin_diagonal_a1_to_h8_ray,
            pin_diagonal_a8_to_h1_ray,
            pin_horizontal_ray,
            pin_vertical_ray,
            check_ray,
            enemy_or_empty,
            opponent_attack_map,
            friendly_color_board,
            opponent_color_board,
        }
    }

    pub fn generate_moves(&mut self) -> Vec<(Piece, Move)> {
        self.calculate_checks_pins_and_attack_map();

        let king_moves = self.generate_king_moves();

        if self.in_double_check {
            return king_moves.iter().map(|m| (King, *m)).collect();
        }

        let queen_moves = self.generate_queen_moves();

        let bishop_moves = self.generate_bishop_moves();

        let knight_moves = self.generate_knight_moves();

        let rook_moves = self.generate_rook_moves();

        let pawn_moves = self.generate_pawn_moves();

        let mut moves = Vec::with_capacity(
            queen_moves.len()
                + bishop_moves.len()
                + knight_moves.len()
                + rook_moves.len()
                + pawn_moves.len()
                + king_moves.len(),
        );

        moves.extend(king_moves.iter().map(|m| (King, *m)));
        moves.extend(queen_moves.iter().map(|m| (Queen, *m)));
        moves.extend(bishop_moves.iter().map(|m| (Bishop, *m)));
        moves.extend(knight_moves.iter().map(|m| (Knight, *m)));
        moves.extend(rook_moves.iter().map(|m| (Rook, *m)));
        moves.extend(pawn_moves.iter().map(|m| (Pawn, *m)));

        moves
    }

    fn generate_king_moves(&mut self) -> Vec<Move> {
        let pseudo_moves = lookup_king(self.friendly_king);

        let mut moves =
            pseudo_moves & self.enemy_or_empty & !self.check_ray & !self.opponent_attack_map;

        let attack_moves = pseudo_moves & self.opponent_color_board & !self.opponent_attack_map;

        moves |= attack_moves;

        let king_squares = occupied_squares(self.friendly_king);
        assert_eq!(king_squares.len(), 1);
        let square = king_squares[0];

        if !self.in_check {
            // Move of castle will be handle when applying the actual move on the board
            if self.can_castle_king_side() {
                match self.board.turn {
                    Color::White => {
                        if CASTLING_WHITE_KING_JUMP_SQUARES & self.opponent_attack_map == EMPTY
                            && CASTLING_WHITE_KING_OCCUPIABLE_SQUARES & self.board.occupied == EMPTY
                        {
                            moves |= CASTLING_WHITE_KING_SQUARE;
                        }
                    }
                    Color::Black => {
                        if CASTLING_BLACK_KING_JUMP_SQUARES & self.opponent_attack_map == EMPTY
                            && CASTLING_BLACK_KING_OCCUPIABLE_SQUARES & self.board.occupied == EMPTY
                        {
                            moves |= CASTLING_BLACK_KING_SQUARE;
                        }
                    }
                }
            }

            if self.can_castle_queen_side() {
                match self.board.turn {
                    Color::White => {
                        if CASTLING_WHITE_QUEEN_JUMP_SQUARES & self.opponent_attack_map == EMPTY
                            && CASTLING_WHITE_QUEEN_OCCUPIABLE_SQUARES & self.board.occupied
                                == EMPTY
                        {
                            moves |= CASTLING_WHITE_QUEEN_SQUARE;
                        }
                    }
                    Color::Black => {
                        if CASTLING_BLACK_QUEEN_JUMP_SQUARES & self.opponent_attack_map == EMPTY
                            && CASTLING_BLACK_QUEEN_OCCUPIABLE_SQUARES & self.board.occupied
                                == EMPTY
                        {
                            moves |= CASTLING_BLACK_QUEEN_SQUARE;
                        }
                    }
                }
            }
        }

        to_moves(moves, square)
    }

    fn can_castle_king_side(&self) -> bool {
        match self.board.turn {
            Color::White => self.board.king_side_castle_white,
            Color::Black => self.board.king_side_castle_black,
        }
    }

    fn can_castle_queen_side(&self) -> bool {
        match self.board.turn {
            Color::White => self.board.queen_side_castle_white,
            Color::Black => self.board.queen_side_castle_black,
        }
    }

    fn generate_queen_moves(&self) -> Vec<Move> {
        let mut moves = vec![];
        let piece_bitboard = self.board.get_piece_bitboard(Queen, self.friendly_color);

        for src in occupied_squares(piece_bitboard) {
            if self.is_pinned(src.bitboard()) && self.in_check {
                continue;
            }

            let pseudo_moves = lookup_queen(
                self.tables,
                src,
                self.friendly_color_board,
                self.board.occupied,
            );

            let mut legal_moves = pseudo_moves & self.enemy_or_empty;

            if self.in_check {
                legal_moves &= self.check_ray;
            }

            if self.is_pinned(src.bitboard()) {
                let queen = src.bitboard();

                if queen & self.pin_vertical_ray != EMPTY {
                    legal_moves &= self.pin_vertical_ray;
                } else if queen & self.pin_horizontal_ray != EMPTY {
                    legal_moves &= self.pin_horizontal_ray;
                } else if queen & self.pin_diagonal_a1_to_h8_ray != EMPTY {
                    legal_moves &= self.pin_diagonal_a1_to_h8_ray;
                } else {
                    legal_moves &= self.pin_diagonal_a8_to_h1_ray;
                }
            }

            to_moves(legal_moves, src).iter().for_each(|m| {
                moves.push(*m);
            });
        }

        moves
    }

    fn generate_bishop_moves(&self) -> Vec<Move> {
        let mut moves = vec![];
        let piece_bitboard = self.board.get_piece_bitboard(Bishop, self.friendly_color);

        for src in occupied_squares(piece_bitboard) {
            let bishop = src.bitboard();

            if (bishop & self.pin_horizontal_ray != EMPTY)
                || (bishop & self.pin_vertical_ray != EMPTY)
            {
                continue;
            }

            let pseudo_moves = lookup_bishop(
                &self.tables.bishop,
                src,
                self.friendly_color_board,
                self.board.occupied,
            );

            let mut legal_moves = pseudo_moves & self.enemy_or_empty;

            if self.in_check {
                legal_moves &= self.check_ray;
            }

            if self.is_pinned(src.bitboard()) {
                if bishop & self.pin_diagonal_a1_to_h8_ray != EMPTY {
                    legal_moves &= self.pin_diagonal_a1_to_h8_ray;
                } else {
                    legal_moves &= self.pin_diagonal_a8_to_h1_ray;
                }
            }

            to_moves(legal_moves, src).iter().for_each(|m| {
                moves.push(*m);
            });
        }

        moves
    }

    fn generate_knight_moves(&self) -> Vec<Move> {
        let mut moves = vec![];
        let piece_bitboard = self.board.get_piece_bitboard(Knight, self.friendly_color);

        for src in occupied_squares(piece_bitboard) {
            if self.is_pinned(src.bitboard()) {
                continue;
            }

            let pseudo_moves = lookup_knight(get_single_piece_bitboard(piece_bitboard, src));

            let mut legal_moves = pseudo_moves & self.enemy_or_empty;

            if self.in_check {
                legal_moves &= self.check_ray;
            }

            to_moves(legal_moves, src).iter().for_each(|m| {
                moves.push(*m);
            });
        }

        moves
    }

    fn generate_rook_moves(&self) -> Vec<Move> {
        let mut moves = vec![];
        let piece_bitboard = self.board.get_piece_bitboard(Rook, self.friendly_color);

        for src in occupied_squares(piece_bitboard) {
            let rook = src.bitboard();
            if (self.pin_diagonal_a8_to_h1_ray & rook != EMPTY)
                || (self.pin_diagonal_a1_to_h8_ray & rook != EMPTY)
            {
                continue;
            }

            let pseudo_moves = lookup_rook(
                &self.tables.rook,
                src,
                self.friendly_color_board,
                self.board.occupied,
            );

            let mut legal_moves = pseudo_moves & self.enemy_or_empty;

            if self.in_check {
                legal_moves &= self.check_ray;
            }

            if self.is_pinned(src.bitboard()) {
                if rook & self.pin_vertical_ray != EMPTY {
                    legal_moves &= self.pin_vertical_ray;
                } else {
                    legal_moves &= self.pin_horizontal_ray;
                }
            }

            to_moves(legal_moves, src).iter().for_each(|m| {
                moves.push(*m);
            });
        }

        moves
    }

    fn generate_pawn_moves(&self) -> Vec<Move> {
        let mut moves = vec![];
        let piece_bitboard = self.board.get_piece_bitboard(Pawn, self.friendly_color);

        for src in occupied_squares(piece_bitboard) {
            let pseudo_moves = self.lookup_pawn_moves(src);

            let mut legal_moves = pseudo_moves;

            if self.in_check {
                legal_moves &= self.check_ray;
            }

            let en_passant_pseudo_moves = pseudo_moves & self.board.en_passant;
            if en_passant_pseudo_moves != EMPTY {
                for dst in occupied_squares(en_passant_pseudo_moves) {
                    let en_passant_captured = match self.friendly_color {
                        Color::White => self.board.en_passant >> 8,
                        Color::Black => self.board.en_passant << 8,
                    } & self.opponent_color_board;

                    if en_passant_captured & self.check_ray != EMPTY {
                        moves.push(Move::new(src, dst, None));
                    }
                }
            }

            if self.is_pinned(src.bitboard()) {
                let pawn = src.bitboard();

                if pawn & self.pin_vertical_ray != EMPTY {
                    legal_moves &= self.pin_vertical_ray;
                } else if pawn & self.pin_horizontal_ray != EMPTY {
                    legal_moves &= self.pin_horizontal_ray;
                } else if pawn & self.pin_diagonal_a1_to_h8_ray != EMPTY {
                    legal_moves &= self.pin_diagonal_a1_to_h8_ray;
                } else {
                    legal_moves &= self.pin_diagonal_a8_to_h1_ray;
                }
            }

            let promotion_moves = legal_moves & (RANK_1 | RANK_8);
            for dst in occupied_squares(promotion_moves) {
                moves.push(Move::new(src, dst, Some(Promotion::Queen)));
                moves.push(Move::new(src, dst, Some(Promotion::Bishop)));
                moves.push(Move::new(src, dst, Some(Promotion::Knight)));
                moves.push(Move::new(src, dst, Some(Promotion::Rook)));
            }

            // Only moves without promotion
            to_moves(legal_moves & !promotion_moves, src)
                .iter()
                .for_each(|m| {
                    moves.push(*m);
                });
        }

        moves
    }

    fn lookup_pawn_moves(&self, src: Square) -> Bitboard {
        let pawn = src.bitboard();

        let mut pseudo_moves: Bitboard;

        let turn = self.board.turn;
        let occupied = self.board.occupied;
        let opponent = self.opponent_color_board;
        let en_passant = self.board.en_passant;

        if turn == Color::White {
            pseudo_moves = pawn << 8 & !occupied;

            // pawns can't move two squares if there is a piece in front of them
            pseudo_moves |= (pawn & RANK_2) << (2 * 8) & !(occupied << 8) & !occupied;

            // attacks
            pseudo_moves |=
                (((!H_FILE & pawn) << 9) & opponent) | (((pawn & !A_FILE) << 7) & opponent);

            // en passant
            let pseudo_en_passant_moves = ((pawn & !A_FILE) << 7) | ((pawn & !H_FILE) << 9);
            let pseudo_en_passant_moves = pseudo_en_passant_moves & en_passant;

            if pseudo_en_passant_moves != EMPTY {
                for mov in to_moves(pseudo_en_passant_moves, src) {
                    let mut tmp_board = self.board.apply_move_for_piece(Pawn, mov);
                    // We need to undo the turn switch, because we want to test the same color
                    tmp_board.switch_turn();
                    if self.is_en_passant_legal(&tmp_board) {
                        pseudo_moves |= mov.to.bitboard();
                    }
                }
            }
        } else {
            pseudo_moves = pawn >> 8 & !occupied;

            // pawns can't move two squares if there is a piece in front of them
            pseudo_moves |= (pawn & RANK_7) >> (2 * 8) & !(occupied >> 8) & !occupied;

            // attacks
            pseudo_moves |=
                (((pawn & !H_FILE) >> 7) & opponent) | (((pawn & !A_FILE) >> 9) & opponent);

            // en passant
            let pseudo_en_passant_moves = ((pawn & !A_FILE) >> 9) | ((pawn & !H_FILE) >> 7);
            let pseudo_en_passant_moves = pseudo_en_passant_moves & en_passant;

            if pseudo_en_passant_moves != EMPTY {
                for mov in to_moves(pseudo_en_passant_moves, src) {
                    let mut tmp_board = self.board.apply_move_for_piece(Pawn, mov);
                    // We need to undo the turn switch, because we want to test the same color
                    tmp_board.switch_turn();
                    if self.is_en_passant_legal(&tmp_board) {
                        pseudo_moves |= mov.to.bitboard();
                    }
                }
            }
        }

        pseudo_moves & self.enemy_or_empty
    }

    fn is_en_passant_legal(&self, board: &Board) -> bool {
        // board is not equal to self.board
        // it is temporary and applied the en peasant move, so we can't use self.board
        // in any case here, only if things have not changed self.board.turn

        let friendly_color_board = board.get_color_bitboard(self.friendly_color);
        let opponent_color_board = board.get_color_bitboard(self.opponent_color);

        for direction in DIRECTIONS {
            let mut square = self.friendly_king;
            let is_diagonal = is_diagonal(direction);

            loop {
                let new_square = self.move_in_direction(direction, square);
                if new_square.is_none() {
                    break;
                }

                square = new_square.unwrap();

                if square & board.occupied == EMPTY {
                    continue;
                }

                // friendly piece in the way, so king is safe in this direction
                if square & friendly_color_board != EMPTY {
                    break;
                }

                // Check if an enemy piece can attack the king in this direction
                // after an en passant move was done
                if square & opponent_color_board != EMPTY {
                    let opponent_piece = board.get_piece(square, self.opponent_color).unwrap();

                    if is_diagonal && (opponent_piece == Bishop || opponent_piece == Queen) {
                        return false;
                    }

                    if !is_diagonal && (opponent_piece == Rook || opponent_piece == Queen) {
                        return false;
                    }

                    // Safe in this direction, as opponent piece can't attack king
                    break;
                }

                // TODO Also need to include pawn, but have not understand yet the possible
                //  scenario in which an opponent pawn makes this move illegal
            }
        }

        true
    }

    fn calculate_checks_pins_and_attack_map(&mut self) {
        // TODO Could eg. exclude `NORTH, EAST, SOUTH, WEST` if the enemy does not have any queen or rook

        for direction in DIRECTIONS {
            let is_diagonal = is_diagonal(direction);
            let mut square = self.friendly_king;
            let mut friendly_piece_along_ray = false;

            let mut raymask_diagonal = EMPTY;
            let mut raymask_straight = EMPTY;

            loop {
                let new_square = self.move_in_direction(direction, square);
                if new_square.is_none() {
                    break;
                }

                square = new_square.unwrap();

                if is_diagonal {
                    raymask_diagonal |= square;
                } else {
                    raymask_straight |= square;
                }

                if square & self.board.occupied == EMPTY {
                    continue;
                }

                if square & self.friendly_color_board != EMPTY {
                    // Friendly piece that might be pinned
                    if !friendly_piece_along_ray {
                        friendly_piece_along_ray = true;
                    } else {
                        // second friendly piece so pin is not possible
                        break;
                    }
                } else {
                    // Square contains opponent piece
                    // can unwrap as there is always an opponent piece at this square
                    let opponent_piece = self.board.get_piece(square, self.opponent_color).unwrap();

                    if opponent_piece == Queen
                        || is_diagonal && opponent_piece == Bishop
                        || !is_diagonal && opponent_piece == Rook
                    {
                        if friendly_piece_along_ray {
                            // friendly piece is blocking so it is a pin
                            if is_diagonal {
                                if direction == NORTH_EAST || direction == SOUTH_WEST {
                                    self.pin_diagonal_a1_to_h8_ray |= raymask_diagonal;
                                } else {
                                    debug_assert!(
                                        direction == NORTH_WEST || direction == SOUTH_EAST
                                    );
                                    self.pin_diagonal_a8_to_h1_ray |= raymask_diagonal;
                                }
                            } else if direction == NORTH || direction == SOUTH {
                                self.pin_vertical_ray |= raymask_straight;
                            } else {
                                debug_assert!(direction == EAST || direction == WEST);
                                self.pin_horizontal_ray |= raymask_straight;
                            }
                            self.pins_exists = true;
                        } else {
                            // no friendly piece blocking attack so it is a check
                            self.check_ray |= raymask_diagonal | raymask_straight;
                            self.in_double_check = self.in_check;
                            self.in_check = true;
                        }
                        break;
                    } else {
                        // opponent piece not able to move in this direction to king
                        break;
                    }
                }
            }

            if self.in_double_check {
                // only king moves are legal during double check, so no need to search for pins
                return;
            }
        }

        let pawn_attack_directions = match self.friendly_color {
            Color::White => [NORTH_WEST, NORTH_EAST],
            Color::Black => [SOUTH_WEST, SOUTH_EAST],
        };

        for direction in pawn_attack_directions {
            let new_square = self.move_in_direction(direction, self.friendly_king);
            if new_square.is_none() {
                continue;
            }

            let square = new_square.unwrap();

            if square & self.board.get_piece_bitboard(Pawn, self.opponent_color) != EMPTY {
                self.check_ray |= square;
                self.in_double_check = self.in_check;
                self.in_check = true;
            }
        }

        let opponent_knights = self.board.get_piece_bitboard(Knight, self.opponent_color);
        let opponent_knights_check_attacks = lookup_knight(self.friendly_king) & opponent_knights;
        if opponent_knights_check_attacks != EMPTY {
            self.check_ray |= opponent_knights_check_attacks;
            self.in_double_check = self.in_check;
            self.in_check = true;
        }

        let pawn_attacks = self.pawns_attack();

        let opponent_king = self.board.get_piece_bitboard(King, self.opponent_color);
        let king_attacks = lookup_king(opponent_king);

        self.opponent_attack_map =
            self.sliding_attack() | lookup_knight(opponent_knights) | pawn_attacks | king_attacks;
    }

    fn move_in_direction(&self, direction: Direction, square: Bitboard) -> Option<Bitboard> {
        let new_square = match direction {
            NORTH => square << 8,
            SOUTH => square >> 8,
            EAST => (square & !H_FILE) << 1,
            WEST => (square & !A_FILE) >> 1,
            NORTH_EAST => (square & !H_FILE) << 9,
            NORTH_WEST => (square & !A_FILE) << 7,
            SOUTH_EAST => (square & !H_FILE) >> 7,
            SOUTH_WEST => (square & !A_FILE) >> 9,
            _ => {
                unreachable!("invalid direction");
            }
        };

        // check for overflow
        if new_square == 0 {
            return None;
        }

        Some(new_square)
    }

    fn sliding_attack(&self) -> Bitboard {
        let mut opponent_sliding_attacks = EMPTY;

        // When creating the sliding attack map, we want to skip the friendly king
        // so that the king can't move in the opposite direction of the attack
        // We also exclude potential captures by the king
        let opponent_without_friendly_king_and_potential_captures = self.opponent_color_board
            & !self.friendly_king
            & !(lookup_king(self.friendly_king)
                & self
                    .board
                    .get_color_bitboard(self.friendly_color.opposite()));
        let occupied_without_friendly_king = self.board.occupied & !self.friendly_king;

        for piece in [Bishop, Rook, Queen] {
            let bitboard = self.board.get_piece_bitboard(piece, self.opponent_color);
            for src in occupied_squares(bitboard) {
                match piece {
                    Queen => {
                        opponent_sliding_attacks |= lookup_bishop(
                            &self.tables.bishop,
                            src,
                            opponent_without_friendly_king_and_potential_captures,
                            occupied_without_friendly_king,
                        ) & !src.bitboard();
                        opponent_sliding_attacks |= lookup_rook(
                            &self.tables.rook,
                            src,
                            opponent_without_friendly_king_and_potential_captures,
                            occupied_without_friendly_king,
                        ) & !src.bitboard();
                    }
                    Bishop => {
                        opponent_sliding_attacks |= lookup_bishop(
                            &self.tables.bishop,
                            src,
                            opponent_without_friendly_king_and_potential_captures,
                            occupied_without_friendly_king,
                        ) & !src.bitboard();
                    }
                    Rook => {
                        opponent_sliding_attacks |= lookup_rook(
                            &self.tables.rook,
                            src,
                            opponent_without_friendly_king_and_potential_captures,
                            occupied_without_friendly_king,
                        ) & !src.bitboard();
                    }
                    _ => {}
                }
            }
        }

        opponent_sliding_attacks
    }

    fn pawns_attack(&self) -> Bitboard {
        if self.board.turn == Color::Black {
            ((!H_FILE & self.board.white_pawns) << 9) | ((self.board.white_pawns & !A_FILE) << 7)
        } else {
            ((!H_FILE & self.board.black_pawns) >> 7) | ((self.board.black_pawns & !A_FILE) >> 9)
        }
    }

    fn is_pinned(&self, square: Bitboard) -> bool {
        ((self.pin_horizontal_ray
            | self.pin_vertical_ray
            | self.pin_diagonal_a1_to_h8_ray
            | self.pin_diagonal_a8_to_h1_ray)
            & square)
            != EMPTY
    }

    pub fn get_board(&self) -> Board {
        self.board
    }

    pub fn get_tables(&self) -> &Tables {
        self.tables
    }
}

pub fn perft(mut move_gen: MoveGenerator, depth: usize) -> usize {
    if depth == 0 {
        return 1;
    }

    let moves = move_gen.generate_moves();
    let mut num_position: usize = 0;

    for (piece, mov) in moves {
        let new_board = move_gen.get_board().apply_move_for_piece(piece, mov);
        let num = recursive_perft(
            MoveGenerator::new(new_board, move_gen.get_tables()),
            depth - 1,
        );

        println!("{}: {}", mov, num);
        num_position += num;
    }

    num_position
}

fn recursive_perft(mut move_gen: MoveGenerator, depth: usize) -> usize {
    if depth == 0 {
        return 1;
    }

    let moves = move_gen.generate_moves();
    let mut num_position = 0;

    for (piece, mov) in moves {
        let new_board = move_gen.get_board().apply_move_for_piece(piece, mov);
        let num = recursive_perft(
            MoveGenerator::new(new_board, move_gen.get_tables()),
            depth - 1,
        );
        num_position += num;
    }

    num_position
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::engine::magics::load_magics_table;

    #[test]
    fn test_generate_moves_perft_depth_1() {
        let board = Board::new();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 1);

        assert_eq!(num_positions, 20);
    }

    #[test]
    fn test_generate_moves_perft_depth_2() {
        let board = Board::new();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 2);

        assert_eq!(num_positions, 400);
    }

    #[test]
    fn test_generate_moves_perft_depth_3() {
        let board = Board::new();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 3);

        assert_eq!(num_positions, 8902);
    }

    #[test]
    fn test_generate_moves_perft_depth_4() {
        let board = Board::new();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 4);

        assert_eq!(num_positions, 197281);
    }

    #[cfg(all(test, feature = "expensive_tests"))]
    #[test]
    fn test_generate_moves_perft_depth_5() {
        let board = Board::new();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 5);

        assert_eq!(num_positions, 4865609);
    }

    #[test]
    fn test_generate_moves_perft_position_two() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_2
        let board =
            Board::from_fen("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -")
                .unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 4);

        assert_eq!(num_positions, 4085603);
    }

    #[test]
    fn test_generate_moves_perft_position_three() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_3
        let board = Board::from_fen("8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -").unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 5);

        assert_eq!(num_positions, 674624);
    }

    #[test]
    fn test_generate_moves_perft_position_three_expensive() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_3
        let board = Board::from_fen("8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -").unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 6);

        assert_eq!(num_positions, 11030083);
    }

    #[test]
    fn test_generate_moves_perft_position_four() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_4
        let board =
            Board::from_fen("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1")
                .unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 4);

        assert_eq!(num_positions, 422333);
    }

    #[cfg(all(test, feature = "expensive_tests"))]
    #[test]
    fn test_generate_moves_perft_position_four_expensive() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_4
        let board =
            Board::from_fen("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1")
                .unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 5);

        assert_eq!(num_positions, 15833292);
    }

    #[test]
    fn test_generate_moves_perft_position_five() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_5
        let board =
            Board::from_fen("rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8").unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 3);

        assert_eq!(num_positions, 62379);
    }

    #[cfg(all(test, feature = "expensive_tests"))]
    #[test]
    fn test_generate_moves_perft_position_five_expensive() {
        // reference: https://www.chessprogramming.org/Perft_Results#Position_5
        let board =
            Board::from_fen("rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8").unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 4);

        assert_eq!(num_positions, 2103487);
    }

    #[test]
    fn test_generate_moves_perft_position_six() {
        // https://www.chessprogramming.org/Perft_Results#Position_6
        let board = Board::from_fen(
            "r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10 ",
        )
        .unwrap();
        let tables = load_magics_table();
        let move_generator = MoveGenerator::new(board, &tables);

        let num_positions = perft(move_generator, 4);

        assert_eq!(num_positions, 3894594);
    }
}