bishop/src/movegen.rs

use bitboard::Bitboard;
use bitboard::Square;
use bitboard::*;
use game::Game;
use hash::{Cache, EntryType};
use std::iter::Iterator;

use crate::evaluate::evaluate;
use crate::hash::CacheEntry;

pub type Side = bool;

pub const WHITE: Side = false;
pub const BLACK: Side = true;

pub type PieceType = u8;

pub const NO_PIECE: PieceType = 255;
pub const PAWN: PieceType = 0;
pub const KNIGHT: PieceType = 1;
pub const BISHOP: PieceType = 2;
pub const ROOK: PieceType = 3;
pub const QUEEN: PieceType = 4;
pub const KING: PieceType = 5;

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct SimpleMove {
    pub from: Square,
    pub to: Square,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Move {
    Default { mov: SimpleMove, piece_type: PieceType, captured: Option<PieceType> },
    Castling { side: Side, left: bool },
    EnPassant { mov: SimpleMove, beaten: Square },
    Promotion { mov: SimpleMove, promote_to: PieceType, captured: Option<PieceType> },
    Nullmove
}


#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct MoveUndo {
    pub castling_rights_before: [bool; 4],
    pub halfmoves_since_last_event_before: i8,
    pub en_passant_before: Option<u8>,
    pub mov: Move
}

impl Default for Move {
    fn default() -> Move {
        Move::Nullmove
    }
}


impl Move {
    pub fn parse_square(sq: &str) -> Option<Square> {
        let col = sq.chars().nth(0)?;
        let row = sq.chars().nth(1)?;

        Some((row as u8 - '1' as u8) * 8 + 7 - (col as u8 - 'a' as u8))
    }


    pub fn square_to_string(sq: Square) -> String {
        let col =  7 - (sq % 8);
        let row = sq / 8;
        let colchar = (('a' as u8) + col) as char;
        let rowchar = (('1' as u8) + row) as char;

        let chars = [colchar, rowchar];
        //println!("{} {}", col, row);

        chars.iter().collect()
    }

    pub fn is_null(&self) -> bool {
        *self == Move::Nullmove
    }

    pub fn to_string(&self) -> String {
        match self {
            Move::Default{ mov, piece_type: _pt, captured: _c } => {
                Self::square_to_string(mov.from) + &Self::square_to_string(mov.to)
            },
            Move::Castling{ side, left } => {
                match (side, left) {
                    (&WHITE, false) => {
                        Self::square_to_string(3) + &Self::square_to_string(1)
                    },
                    (&WHITE, true) => {
                        Self::square_to_string(3) + &Self::square_to_string(5)
                    },
                    (&BLACK, false) => {
                        Self::square_to_string(56 + 3) + &Self::square_to_string(56 + 1)
                    },
                    (&BLACK, true) => {
                        Self::square_to_string(56 + 3) + &Self::square_to_string(56 + 5)
                    }
                }
            },
            Move::EnPassant{ mov, beaten: _ } => {
                Self::square_to_string(mov.from) + &Self::square_to_string(mov.to)
            },
            Move::Promotion{ mov, promote_to, captured: _c } => {
                Self::square_to_string(mov.from) + &Self::square_to_string(mov.to) + 
                if *promote_to == QUEEN { "q" }
                else if *promote_to == ROOK { "r" }
                else if *promote_to == KNIGHT { "n" }
                else if *promote_to == BISHOP { "b" }
                else { "" }
            },
            Move::Nullmove => {
                String::from("0000")
            }
        }
    }

    pub fn is_capture(&self) -> bool {
        match self {
            Move::Default{ mov: _, piece_type: _, captured: c } => c.is_some(),
            Move::Promotion{ mov: _, promote_to: _, captured: c } => c.is_some(),
            Move::EnPassant{ mov: _, beaten: _ } => true,
            Move::Castling{ side: _, left: _ } => false,
            Move::Nullmove => false
        }
    }
}

/**
 * @brief Iterator to serialize bitboard bit for bit
 *
 * Extracts every bit out of the bitboard and returns each one as a separate bitboard.
 */
pub struct BitboardIterator (pub Bitboard);

impl Iterator for BitboardIterator {
    type Item = Bitboard;

    fn next(&mut self) -> Option<Bitboard> {
        if self.0 != 0 {
            let lsb = self.0 & (self.0.wrapping_neg());
            self.0 ^= lsb;
            //Some(lsb.trailing_zeros())
            Some(lsb)
        } else {
            None
        }
    }
}

impl SimpleMove {
    pub fn apply_to(self, bitboard: Bitboard) -> Bitboard {
        (bitboard & !from_square(self.from)) | from_square(self.to)
    }
}


#[derive(PartialEq)]
enum SortingState {
    PvMove,
    Captures,
    Killers,
    Quiets
}

///
/// generates and sorts moves which can then be extracted via an Iterator interface
/// 
pub struct MoveGenerator {

    game: Game,
    moves: Vec<Move>,

    captures: Vec<Move>,
    quiets: Vec<Move>,

    state: SortingState,

    pv_move: Option<Move>,
    killers: Vec<Move>
}

impl MoveGenerator {
    pub fn generate_legal_moves(game: &mut Game, ce: Option<&CacheEntry>, killers: &[Move], side: Side) -> Self {
        MoveGenerator {
            game: game.clone(),
            moves: generate_legal_moves(game, side, false),
            captures: Vec::new(),
            quiets: Vec::new(),
            state: if ce.is_some() { SortingState::PvMove } else { SortingState::Captures },
            pv_move: ce.map(|e| e.mov),
            killers: killers.to_vec()
        }
    }

    pub fn is_empty(&self) -> bool {
        return self.moves.is_empty() && self.captures.is_empty() && self.quiets.is_empty();
    }
}

impl Iterator for MoveGenerator {
    type Item = Move;

    fn next(&mut self) -> Option<Move> {
        while self.state != SortingState::Quiets || !self.is_empty() {
            match self.state {
                SortingState::PvMove => {
                    self.state = SortingState::Captures;
                    if let Some(pv) = self.pv_move {
                        if self.moves.contains(&pv) {
                            self.moves.retain(|m| *m != pv);
                            return Some(pv);
                        }
                    }
                },
                SortingState::Captures => {
                    if self.captures.is_empty() {
                        self.captures = self.moves.iter().filter(|m| m.is_capture()).map(|m| m.clone()).collect();
                        self.quiets = self.moves.iter().filter(|m| !m.is_capture()).map(|m| m.clone()).collect();
                        self.moves.clear();
                        if self.captures.is_empty() {
                            self.state = SortingState::Killers;
                            continue;
                        }
                    }

                    // lower mvvlva score is better
                    let mut best_mvv_lva = crate::evaluate::MAX_VALUE;
                    let mut best_move: Option<Move> = None;

                    for c in &self.captures {
                        let score = mvv_lva_score(c);
                        if score < best_mvv_lva {
                            best_move = Some(*c);
                            best_mvv_lva = score;
                        }
                    }

                    self.captures.retain(|m| Some(*m) != best_move);
                    if self.captures.is_empty() {
                        self.state = SortingState::Killers;
                    }
                    return best_move;
                },
                SortingState::Killers => {
                    for k in &self.killers {
                        if self.quiets.contains(k) {
                            self.quiets.retain(|m| *m != *k);
                            return Some(*k);
                        }
                    }
                    self.state = SortingState::Quiets;
                },
                SortingState::Quiets => {
                    return self.quiets.pop();
                },
            }
        }

        return None;
    }
}

pub fn generate_moves(game: &Game, side: Side) -> Vec<Move> {

    let mut moves: Vec<Move> = Vec::with_capacity(128);
    generate_pawn_pushes(game, side, &mut moves);
    generate_pawn_doublepushes(game, side, &mut moves);
    generate_pawn_captures(game, side, &mut moves);
    generate_promotions(game, side, &mut moves);
    generate_en_passant(game, side, &mut moves);
    generate_knight_moves(game, side, &mut moves, false);
    generate_bishop_moves(game, side, &mut moves, false);
    generate_rook_moves(game, side, &mut moves, false);
    generate_queen_moves(game, side, &mut moves, false);
    generate_king_moves(game, side, &mut moves, false);
    generate_castling_moves(game, side, &mut moves);
    return moves;
}

/**
 * generates moves that could possibly attack a king,
 * this function is used to check if the king is in check
 */
pub fn generate_possattacking_moves(game: &Game, side: Side) -> Vec<Move> {

    let mut moves: Vec<Move> = Vec::with_capacity(32);
    generate_pawn_captures(game, side, &mut moves);
    generate_promotions(game, side, &mut moves);
    generate_knight_moves(game, side, &mut moves, true);
    generate_bishop_moves(game, side, &mut moves, true);
    generate_rook_moves(game, side, &mut moves, true);
    generate_queen_moves(game, side, &mut moves, true);
    generate_king_moves(game, side, &mut moves, true);
    return moves;
}

pub fn generate_legal_moves_old(game: &mut Game, side: Side) -> Vec<Move> {
    let moves = generate_moves(game, side);

    let check_legality = |mov: &Move| {
        let undo = game.apply(*mov);
        let legal = !is_check(game, side);
        game.undo_move(undo);
        return legal;
    };

    moves.into_iter().filter(check_legality).collect::<Vec<Move>>()
}

fn pinned_rays(king: Bitboard, friends: Bitboard, diag_enemies: Bitboard, straight_enemies: Bitboard, all_enemies: Bitboard) -> [Bitboard; 8] {
    let check_ray = |ray_func: fn(Bitboard) -> Bitboard, diagonal: bool| -> Bitboard {
        let mut pos = king;
        let mut ray = 0;
        let mut one_friend = false;

        let enemies = if diagonal { diag_enemies } else { straight_enemies };
        let blockers = friends | all_enemies;

        for _ in 0..7 {
            pos = ray_func(pos);
            ray |= pos;
            if pos & friends != 0 && !one_friend {
                one_friend = true;
            } else if pos & enemies != 0 && one_friend {
                return ray;
            } else if pos & blockers != 0 && !one_friend {
                return 0;
            } else if pos & blockers != 0 && one_friend {
                return 0;
            }
        }
        return 0;
    };

    return [check_ray(north_one, false),
            check_ray(south_one, false),
            check_ray(east_one, false),
            check_ray(west_one, false),
            check_ray(northeast_one, true),
            check_ray(northwest_one, true),
            check_ray(southeast_one, true),
            check_ray(southwest_one, true)];
}


pub fn generate_legal_moves(game: &mut Game, side: Side, captures_only: bool) -> Vec<Move> {
    let moves =
        if captures_only {
            generate_attacking_moves(game, side)
        } else {
            generate_moves(game, side)
        };

    let check = is_check(game, side);
    let king = game.kings(side);

    let straight_enemies = game.queens(!side) | game.rooks(!side);
    let diag_enemies = game.queens(!side) | game.bishops(!side);

    let pin_rays = pinned_rays(king, game.get_all_side(side), diag_enemies, straight_enemies, game.get_all_side(!side));
    let possible_pins = king | pin_rays.iter().fold(0, |a, b| a | b);

    let check_legality = |m: &Move| {
        if !check {
            match m {
                Move::Default { mov, piece_type: _, captured: _ } |
                Move::Promotion { mov, promote_to: _, captured: _ } => {
                    let from = from_square(mov.from);
                    if from & possible_pins == 0 && from != king {
                        return true;
                    }
                    else {
                        let to = from_square(mov.to);
                        for pin_ray in pin_rays {
                            if from & pin_ray != 0 {
                                if to & pin_ray != 0 {
                                    return true;
                                }
                                else {
                                    return false;
                                }
                            }
                        }
                    }
                },
                _ => {}
            }
        }
        let undo = game.apply(*m);
        let legal = !is_check(game, side);
        game.undo_move(undo);
        return legal;
    };

    moves.into_iter().filter(check_legality).collect::<Vec<Move>>()
}


pub fn generate_legal_sorted_moves(game: &mut Game, _hash: &mut Cache, killers: &[Move], ce: Option<CacheEntry>, side: Side) -> Vec<Move> {
    let mut moves = generate_legal_moves(game, side, false);

    let mov_val= |mov: &Move| {
        // if its a pv move from previously
        if let Some(c) = &ce {
            if &c.mov == mov { 
                return -2000;
            }
        };

        let killer_bonus = if killers.contains(mov) { 300 } else { 0 };
        let capture_bonus: i32 = if mov.is_capture() { 400 } else { 0 } - mvv_lva_score(mov) / 16;
        let eval = -killer_bonus - capture_bonus;
        return eval;
    };

    moves.sort_by_cached_key(|m| mov_val(m));

    return moves;
}


pub fn generate_attacking_moves(game: &Game, side: Side) -> Vec<Move> {
    let mut moves: Vec<Move> = Vec::with_capacity(32);
    generate_pawn_captures(game, side, &mut moves);
    generate_knight_moves(game, side, &mut moves, true);
    generate_bishop_moves(game, side, &mut moves, true);
    generate_rook_moves(game, side, &mut moves, true);
    generate_queen_moves(game, side, &mut moves, true);
    generate_king_moves(game, side, &mut moves, true);
    return moves;
}


pub fn sort_moves(game: &mut Game, hash: &mut Cache, killers: &[Move], move_list: &mut Vec<Move>) {
    move_list.sort_by_cached_key(|mov| {
        let undo = game.apply(*mov);
        if let Some(e) = hash.lookup(game) {
            game.undo_move(undo);
            if let EntryType::Value = e.entry_type {
                return e.value;
            }
            else if let EntryType::LowerBound = e.entry_type {
                return e.value - 1000;
            }
            else if let EntryType::UpperBound = e.entry_type {
                return e.value + 1000;
            }
            else {
                return crate::evaluate::evaluate(game) - if killers.contains(mov) { 200 } else { 0 };
            }
        }
        else {
            let eval = crate::evaluate::evaluate(game) - if killers.contains(mov) { 200 } else { 0 };
            game.undo_move(undo);
            return eval;
        }
    });
}


///
/// assigns a score to capture moves lower the more valuable the captured piece. Secondly
/// also higher the more the attacking piece is worth.
/// 
fn mvv_lva_score(mov: &Move) -> i32 {
    const PIECE_VALUES: [i32; 6] = [
        100, // Pawn
        220, // Knight
        320, // Bishop
        400, // Rook
        800, // Queen
        100000 // King
    ];

    match mov {
        Move::Default { mov: _, piece_type, captured } => {
            let attack = PIECE_VALUES[*piece_type as usize];
            let victim = captured.map(|ct| PIECE_VALUES[ct as usize]).unwrap_or(0);
            attack - victim * 5
        },
        Move::Promotion { mov: _, promote_to: _, captured } => {
            let victim = captured.map(|ct| PIECE_VALUES[ct as usize]).unwrap_or(0);
            PIECE_VALUES[PAWN as usize] - victim * 5
        },
        _ => 0
    }
}

pub fn sort_moves_least_valuable_attacker(_game: &mut Game, move_list: &mut Vec<Move>) {
    move_list.sort_by_cached_key(mvv_lva_score)
}

pub fn sort_moves_no_hash(game: &mut Game, move_list: &mut Vec<Move>) {
    move_list.sort_by_cached_key(|mov| {
        let undo = game.apply(*mov);
        let our_material = crate::evaluate::material_value(game, game.turn);
        let their_material = crate::evaluate::material_value(game, !game.turn);
        let eval = our_material - their_material;
        game.undo_move(undo);
        return eval;
    });
}


fn generate_pawn_pushes(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    let pawns = game.pawns(side);
    let others = game.get_all_side(!side);
    let pieces = game.get_all_side(side);
    let moved_pawns =
        match side {
            WHITE => north_one(pawns),
            BLACK => south_one(pawns)
        } & !(ROW_1 | ROW_8) & !(others | pieces);

    let iter = BitboardIterator(moved_pawns & !others);
    for p in iter {
        let origin = match side {
            WHITE => south_one(p),
            BLACK => north_one(p)
        };
        move_list.push(Move::Default { mov: SimpleMove { from: square(origin), to: square(p) }, piece_type: PAWN, captured: None });
    }
}

fn generate_pawn_doublepushes(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    let pawns = game.pawns(side) & match side { WHITE => ROW_2, BLACK => ROW_7 };
    let others = game.get_all_side(!side);
    let pieces = game.get_all_side(side);

    let all_pieces = others | pieces;

    let moved_pawns =
        match side {
            WHITE => north_one(north_one(pawns) & !all_pieces),
            BLACK => south_one(south_one(pawns) & !all_pieces)
        } & !all_pieces;

    let iter = BitboardIterator(moved_pawns & !others);
    for p in iter {
        let origin = match side {
            WHITE => south_one(south_one(p)),
            BLACK => north_one(north_one(p))
        };
        move_list.push(Move::Default { mov: SimpleMove { from: square(origin), to: square(p) }, piece_type: PAWN, captured: None });
    }
}

fn generate_pawn_captures(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    let pawns = game.pawns(side);
    let others = game.get_all_side(!side);
    let promotion_mask = ROW_1 | ROW_8;

    let pawn_iterator = BitboardIterator(pawns);

    for pawn in pawn_iterator {
        let left_cap = match side {
            WHITE => northeast_one(pawn),
            BLACK => southeast_one(pawn)
        };
        let right_cap = match side {
            WHITE => northwest_one(pawn),
            BLACK => southwest_one(pawn)
        };

        for cap in [left_cap, right_cap].iter() {
            if cap & others != 0 {
                let captured = game.find_piece(*cap);
                let simple_move = SimpleMove { from: square(pawn), to: square(*cap)};
                if cap & promotion_mask != 0 {
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: QUEEN, captured: captured });
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: ROOK, captured: captured });
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: BISHOP, captured: captured });
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: KNIGHT, captured: captured });
                } else {
                    move_list.push(Move::Default { mov: simple_move, piece_type: PAWN, captured: captured });
                }
            }
        }
    }
}

fn generate_promotions(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    let pawns = game.pawns(side);
    let others = game.get_all_side(!side);
    let pieces = game.get_all_side(side);

    let moved_pawns =
        match side {
            WHITE => north_one(pawns),
            BLACK => south_one(pawns)
        } & (ROW_1 | ROW_8) & !(others | pieces);

    let iter = BitboardIterator(moved_pawns);
    for p in iter {
        let origin = match side {
            WHITE => south_one(p),
            BLACK => north_one(p)
        };
        let movement = SimpleMove { from: square(origin), to: square(p) };
        //move_list.push(Move::Default { mov: SimpleMove { from: square(origin), to: square(p) }, piece_type: PAWN });
        move_list.push(Move::Promotion { mov: movement, promote_to: QUEEN, captured: None });
        move_list.push(Move::Promotion { mov: movement, promote_to: ROOK, captured: None });
        move_list.push(Move::Promotion { mov: movement, promote_to: BISHOP, captured: None });
        move_list.push(Move::Promotion { mov: movement, promote_to: KNIGHT, captured: None });
    }
}


fn generate_en_passant(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    if let Some(ep) = game.en_passant {
        let pawncolumn = FILE_A >> ep;

        let pawnrow: Bitboard = match side {
            WHITE => ROW_5,
            BLACK => ROW_4
        };

        let beaten_pawn = pawncolumn & pawnrow;
        if beaten_pawn & game.get_piece(PAWN, !side) == 0 {
            return;
        }

        let pawn_left = (beaten_pawn << 1) & pawnrow;
        let pawn_right = (beaten_pawn >> 1) & pawnrow;

        let attacking_pawns = game.get_piece(PAWN, side);
        let target_square = pawncolumn & match side {
            WHITE => ROW_6,
            BLACK => ROW_3
        };

        if pawn_left & attacking_pawns != 0 {
            let mov = Move::EnPassant{ mov: SimpleMove{ from: square(pawn_left), to: square(target_square) }, beaten: square(beaten_pawn) };
            move_list.push(mov);
        }
        if pawn_right & attacking_pawns != 0 {
            let mov = Move::EnPassant{ mov: SimpleMove{ from: square(pawn_right), to: square(target_square) }, beaten: square(beaten_pawn) };
            move_list.push(mov);
        }
    }
}

fn generate_knight_moves(game: &Game, side: Side, move_list: &mut Vec<Move>, captures_only: bool) {
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);

    let knights = game.knights(side);
    let knight_iter = BitboardIterator(knights);

    for k in knight_iter {
        let cap_targets = BitboardIterator(get_knight_targets(square(k)) & (!friends & others));
        let nocap_targets = BitboardIterator(get_knight_targets(square(k)) & (!friends & !others));

        for target in cap_targets {
            let simple_move = SimpleMove { from: square(k), to: square(target) };
            let captured = game.find_piece(target);
            move_list.push(Move::Default{ mov: simple_move, piece_type: KNIGHT, captured });
        }
        if !captures_only {
            for target in nocap_targets {
                let simple_move = SimpleMove { from: square(k), to: square(target) };
                move_list.push(Move::Default{ mov: simple_move, piece_type: KNIGHT, captured: None });
            }
        }
    }
}

pub fn get_knight_targets(square: Square) -> Bitboard {
    /// @brief array containing the possible targets for a knight on each square.
    /// entry at index i is a bitboard with all bits set where a knight on square i can jump
    const TARGETS: [Bitboard; 64] = [132096, 329728, 659712, 1319424, 2638848, 5277696, 10489856,
    4202496, 33816580, 84410376, 168886289, 337772578, 675545156, 1351090312, 2685403152,
    1075839008, 8657044482, 21609056261, 43234889994, 86469779988, 172939559976, 345879119952,
    687463207072, 275414786112, 2216203387392, 5531918402816, 11068131838464, 22136263676928,
    44272527353856, 88545054707712, 175990581010432, 70506185244672, 567348067172352,
    1416171111120896, 2833441750646784, 5666883501293568, 11333767002587136, 22667534005174272,
    45053588738670592, 18049583422636032, 145241105196122112, 362539804446949376,
    725361088165576704, 1450722176331153408, 2901444352662306816, 5802888705324613632,
    11533718717099671552, 4620693356194824192, 288234782788157440, 576469569871282176,
    1224997833292120064, 2449995666584240128, 4899991333168480256, 9799982666336960512,
    1152939783987658752, 2305878468463689728, 1128098930098176, 2257297371824128, 4796069720358912,
    9592139440717824, 19184278881435648, 38368557762871296, 4679521487814656, 9077567998918656];

    TARGETS[square as usize]
}

fn generate_bishop_moves(game: &Game, side: Side, move_list: &mut Vec<Move>, captures_only: bool) {
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);
    
    generate_sliding_moves(game, friends, others, game.bishops(side), BISHOP, false, true, move_list, captures_only);
}

fn generate_rook_moves(game: &Game, side: Side, move_list: &mut Vec<Move>, captures_only: bool) {
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);
    
    generate_sliding_moves(game, friends, others, game.rooks(side), ROOK, true, false, move_list, captures_only);
}

fn generate_queen_moves(game: &Game, side: Side, move_list: &mut Vec<Move>, captures_only: bool) {
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);
    
    generate_sliding_moves(game, friends, others, game.queens(side), QUEEN, true, true, move_list, captures_only);
}


pub fn count_sliding_move_bitboard(friends: Bitboard, others: Bitboard, pieces: Bitboard, straight: bool, diagonal: bool, captures_only: bool) -> u32 {
    let pieces_iter = BitboardIterator(pieces);

    let mask = if captures_only { others } else { !(0 as Bitboard) };
    let mut sum = 0;
    for piece in pieces_iter {
        let destinations = generate_sliding_destinations(friends, others, piece, straight, diagonal);
        
        sum += (destinations & mask).count_ones();
    }
    return sum;
}

fn generate_sliding_moves(game: &Game, friends: Bitboard, others: Bitboard, pieces: Bitboard, piece_type: PieceType,
                          straight: bool, diagonal: bool, move_list: &mut Vec<Move>, captures_only: bool) {
    let pieces_iter = BitboardIterator(pieces);

    let mask = if captures_only { others } else { !(0 as Bitboard) };

    for piece in pieces_iter {
        let destinations = generate_sliding_destinations(friends, others, piece, straight, diagonal);
        let dest_iter = BitboardIterator(destinations & mask);
        for dest in dest_iter {
            let smove = SimpleMove{ from: square(piece), to: square(dest) };
            if dest & others != 0 {
                move_list.push(Move::Default { mov: smove, piece_type: piece_type, captured: game.find_piece(dest) });
            }
            else {
                move_list.push(Move::Default { mov: smove, piece_type: piece_type, captured: None });
            }
        }
    }
}

fn generate_sliding_destinations(friends: Bitboard, others: Bitboard,
                               piece: Bitboard, straight: bool,
                               diagonal: bool) -> Bitboard {
    let occupied = friends | others;

    let straights = [north_one, south_one, east_one, west_one];
    let diagonals = [northeast_one, southeast_one, northwest_one, southwest_one];

    let mut result: Bitboard = 0;
    if straight {
        for direction in straights.iter() {
            result |= generate_direction(piece, *direction, occupied);
        }
    }
    if diagonal {
        for direction in diagonals.iter() {
            result |= generate_direction(piece, *direction, occupied);
        }
    }

    return result & !friends;
}

fn generate_direction(piece: Bitboard, direction: fn(Bitboard) -> Bitboard, occupied: Bitboard) -> Bitboard {
    let mut result: Bitboard = 0;
    let mut b = piece;
    loop {
        b = direction(b);
        result |= b;
        if b & (occupied) != 0 || b == 0 {
            break;
        }
    }
    return result;
}


fn generate_king_moves(game: &Game, side: Side, move_list: &mut Vec<Move>, captures_only: bool) {
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);

    let king = game.kings(side);

    //assert_eq!(king.count_ones(), 1); // assume only one king per player 

    if king.count_ones() != 1 { return; }

    let mask =
        if captures_only {
            !friends & others
        }
        else {
            !friends
        };

    let area = (north_one(king)
              | south_one(king)
              | east_one(king)
              | west_one(king)
              | northeast_one(king)
              | northwest_one(king)
              | southwest_one(king)
              | southeast_one(king))
            & mask;

    let area_iter = BitboardIterator(area);
    for destination in area_iter {
        let simple_move = SimpleMove{ from: square(king), to: square(destination) };
        let captured = game.find_piece(destination);
        move_list.push(Move::Default { mov: simple_move, piece_type: KING, captured });
    }
}


fn generate_castling_moves(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    let c1 = Move::Castling{ side: side, left: false };
    let c2 = Move::Castling{ side: side, left: true };

    let legal_castlings: &[bool] = match side {
        WHITE => &game.castling_rights[0..2],
        BLACK => &game.castling_rights[2..4],
    };

    let all_pieces = game.get_all_side(WHITE) | game.get_all_side(BLACK);

    // kingside castling
    if legal_castlings[0] {
        //info!("possible castling? {} {} {}", game.get_piece(KING, side), game.get_piece(ROOK, side), ((game.get_piece(KING, side) >> 3) & game.get_piece(ROOK, side)));
        if ((game.get_piece(KING, side) >> 3) & game.get_piece(ROOK, side)) != 0 &&
            ((game.get_piece(KING, side) >> 1) | (game.get_piece(KING, side) >> 2)) & all_pieces == 0 {
                let mut tg1 = game.clone();

                *tg1.get_piece_mut(KING, side) = game.get_piece(KING, side) >> 1;

                if !is_check(game, side) && !is_check(&tg1, side) {
                    move_list.push(c1);
                }
        }
    }
    // queenside
    if legal_castlings[1] {
        //info!("possible castling? {} {} {}", game.get_piece(KING, side), game.get_piece(ROOK, side), ((game.get_piece(KING, side) >> 3) & game.get_piece(ROOK, side)));
        if ((game.get_piece(KING, side) << 4) & game.get_piece(ROOK, side)) != 0 &&
            ((game.get_piece(KING, side) << 1) | (game.get_piece(KING, side) << 2) | (game.get_piece(KING, side) << 3)) & all_pieces == 0 {

                let mut tg1 = game.clone();
                let mut tg2 = game.clone();

                *tg1.get_piece_mut(KING, side) = game.get_piece(KING, side) << 1;
                *tg2.get_piece_mut(KING, side) = game.get_piece(KING, side) << 2;

                if !is_check(game, side) && !is_check(&tg1, side) && !is_check(&tg2, side) {
                    move_list.push(c2);
                }
        }
    }
}

pub fn is_check(game: &Game, side: Side) -> bool {
    let king = game.get_piece(KING, side);
    let king_square = square(king);
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);

    let knights = get_knight_targets(king_square);
    if knights & game.get_piece(KNIGHT, !side) != 0 {
        return true;
    }

    let diagonal = generate_sliding_destinations(friends, others, king, false, true);
    let straight = generate_sliding_destinations(friends, others, king, true, false);

    if diagonal & game.get_piece(BISHOP, !side) != 0 {
        return true;
    }
    if diagonal & game.get_piece(QUEEN, !side) != 0 {
        return true;
    }
    if straight & game.get_piece(ROOK, !side) != 0 {
        return true;
    }
    if straight & game.get_piece(QUEEN, !side) != 0 {
        return true;
    }

    if side == BLACK {
        if ((southeast_one(king) | southwest_one(king)) & game.get_piece(PAWN, !side)) != 0 {
            return true;
        }
    }
    else {
        if ((northeast_one(king) | northwest_one(king)) & game.get_piece(PAWN, !side)) != 0 {
            return true;
        }
    }

    let king_area = north_one(king)
              | south_one(king)
              | east_one(king)
              | west_one(king)
              | northeast_one(king)
              | northwest_one(king)
              | southwest_one(king)
              | southeast_one(king);
    if king_area & game.get_piece(KING, !side) != 0 {
        return true;
    }

    return false;
}

///
/// checks wether the square sq is attacked by the specified side
/// 
pub fn is_attacked(game: &Game, sq: Square, side: Side) -> bool {
    let others = game.get_all_side(!side);
    let friends = game.get_all_side(side);

    let sq_bb = from_square(sq);

    let knights = get_knight_targets(sq);
    if knights & game.get_piece(KNIGHT, side) != 0 {
        return true;
    }

    let diagonal = generate_sliding_destinations(others, friends, sq_bb, false, true);
    let straight = generate_sliding_destinations(others, friends, sq_bb, true, false);

    if diagonal & game.get_piece(BISHOP, side) != 0 {
        return true;
    }
    if diagonal & game.get_piece(QUEEN, side) != 0 {
        return true;
    }
    if straight & game.get_piece(ROOK, side) != 0 {
        return true;
    }
    if straight & game.get_piece(QUEEN, side) != 0 {
        return true;
    }

    if side == WHITE {
        if ((southeast_one(sq_bb) | southwest_one(sq_bb)) & game.get_piece(PAWN, side)) != 0 {
            return true;
        }
    }
    else {
        if ((northeast_one(sq_bb) | northwest_one(sq_bb)) & game.get_piece(PAWN, side)) != 0 {
            return true;
        }
    }

    let sq_lr = east_one(sq_bb) | sq_bb | west_one(sq_bb);
    let sq_area = north_one(sq_lr) | sq_lr | south_one(sq_lr);
    if sq_area & game.get_piece(KING, side) != 0 {
        return true;
    }

    return false;
}



#[cfg(test)]
mod tests {
    use movegen::*;

    use crate::{search::{perft, SearchControl}, hash::RepetitionTable};

    ///
    /// tests the move generation from some positions to depth 4 and checks wether the correct
    /// amount of moves has been generated
    /// 
    #[test]
    fn some_positions_perft() {
        assert_eq!(nodes_from_pos("5bk1/5p2/7p/q2r1p2/2Q5/P4N2/3prPPP/1R3RK1 b - - 1 34", 4), 3773096);
        assert_eq!(nodes_from_pos("r1bqkbnr/1p1p1ppp/p1N1p3/8/4P3/2N5/PPP2PPP/R1BQKB1R b KQkq - 0 6", 4), 2008894);
        assert_eq!(nodes_from_pos("1r5r/p2b2p1/1p1k1bp1/2pBpp2/1P1n1P2/P1NP3P/2PB2P1/R2KR3 w - - 1 23", 4), 1971751);

        // some positions from https://www.chessprogramming.org/Perft_Results
        assert_eq!(nodes_from_pos("rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8", 4), 2103487);
        assert_eq!(nodes_from_pos("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1", 5), 15833292);
        assert_eq!(nodes_from_pos("r2q1rk1/pP1p2pp/Q4n2/bbp1p3/Np6/1B3NBn/pPPP1PPP/R3K2R b KQ - 0 1", 5), 15833292);
    }

    fn nodes_from_pos(fen: &str, depth: i32) -> usize {
        let mut game: Game = Game::from_fen_str(fen).unwrap();
        let mut check = || false;
        let mut rt = &mut RepetitionTable::new();
        let mut sc = SearchControl::new(&mut check, &mut rt, depth);
        perft(&mut game, &mut sc, depth);
        return sc.nodes;
    }
}