bishop/src/movegen.rs

use bitboard::Bitboard;
use bitboard::Square;
use bitboard::*;
use board::Board;
use ttable::{Cache, EntryType};
use std::cmp::max;
use std::iter::Iterator;
use std::sync::Arc;
use std::sync::Mutex;

use crate::magic::magic_bishop;
use crate::search::CountermoveTable;
use crate::ttable::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,
}

///
/// stores a PieceType and an additional Option<PieceType> in one single byte
/// (under the assumption that there are only 6 pieces). This allows the Mov
/// structure to be 4 bytes only
/// 
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct PieceCaptureType(u8);

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Move {
    Default { mov: SimpleMove, pc: PieceCaptureType },
    Castling { mov: SimpleMove, side: Side, left: bool },
    EnPassant { mov: SimpleMove, beaten: Square },
    Promotion { mov: SimpleMove, pc: PieceCaptureType },
}

// not true on arm
// also not necessary
// const_assert_eq!(std::mem::size_of::<Move>(), 4);


#[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 PieceCaptureType {

    pub fn new(piece_type: PieceType, capture_type: Option<PieceType>) -> Self {
        if piece_type > KING {
            panic!("ILLEGAL PIECE");
        }
        let upper = piece_type << 4;
        let lower = capture_type.unwrap_or(0xF);
        PieceCaptureType(upper | lower)
    }

    pub fn piece_type(&self) -> PieceType {
        (self.0 >> 4) as PieceType
    }

    pub fn capture_type(&self) -> Option<PieceType> {
        let ct = (self.0 & 0xF) as PieceType;
        
        if ct == 0xF {
            None
        }
        else {
            Some(ct)
        }
    }

    pub fn has_capture(&self) -> bool {
        let ct = (self.0 >> 4) as PieceType;
        ct != 0xF
    }
}



impl Move {

    pub fn nullmove() -> Self {
        Move::Default { mov: SimpleMove{ from: 0, to: 0 }, pc: PieceCaptureType(0) }
    }

    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.to_simple() == SimpleMove{ from: 0, to: 0 }
    }

    pub fn to_string(&self) -> String {
        if self.is_null() {
            return "0000".to_owned();
        }
        match self {
            Move::Default{ mov, pc: _} => {
                Self::square_to_string(mov.from) + &Self::square_to_string(mov.to)
            },
            Move::Castling{ mov: _mov, 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, pc } => {
                let promote_to = pc.piece_type();
                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 { "" }
            }
        }
    }

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

    fn captures(&self) -> Option<PieceType> {
        match self {
            Move::Default{ mov: _, pc } => pc.capture_type(),
            Move::Promotion{ mov: _, pc } => pc.capture_type(),
            Move::EnPassant{ mov: _, beaten: _ } => None,
            Move::Castling{ mov: _, side: _, left: _ } => None,
        }
    }

    pub fn is_promotion(&self) -> bool {
        match self {
            Move::Promotion { mov: _, pc: _ } => true,
            _ => false
        }
    }

    pub fn to_simple(&self) -> SimpleMove {
        match self {
            Move::Default{ mov, pc: _ } |
            Move::Promotion{ mov, pc: _ } |
            Move::Castling{ mov, side: _, left: _ } |
            Move::EnPassant{ mov, beaten: _ } => {
                *mov
            },
        }
    }

    pub fn from(&self) -> Square {
        self.to_simple().from
    }

    pub fn to(&self) -> Square {
        self.to_simple().to
    }

    pub fn piece_type(&self) -> PieceType {
        match self {
            Move::Default{ mov: _, pc } |
            Move::Promotion{ mov: _, pc } => {
                pc.piece_type()
            },
            Move::Castling{ mov: _, side: _, left: _ } => {
                KING
            },
            Move::EnPassant{ mov: _, beaten: _ } => {
                PAWN
            },
        }
    }


}

/**
 * @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,
    Counter,
    Quiets,
    LosingCaptures,
}

///
/// generates and sorts moves which can then be extracted via an Iterator interface
/// 
pub struct MoveGenerator {
    board: Board,
    moves: Vec<Move>,
    side: Side,

    captures: Vec<(Move, i32)>,
    counters: Vec<(Move, i16)>,
    quiets: Vec<Move>,
    losing_captures: Vec<(Move, i32)>,

    state: SortingState,

    pv_move: Option<SimpleMove>,
    killers: Vec<Move>,
    last_move: Option<Move>,
    counters_table: Arc<Mutex<CountermoveTable>>,

    is_late: bool,
}

impl MoveGenerator {
    pub fn generate_legal_moves(game: &mut Board, ce: Option<&CacheEntry>, killers: &[Move], last_move: Option<Move>, counters_table: Arc<Mutex<CountermoveTable>>, side: Side) -> Self {
        MoveGenerator {
            board: game.clone(),
            moves: generate_legal_moves(game, side, false),
            side,
            captures: Vec::with_capacity(32),
            counters: Vec::with_capacity(32),
            quiets: Vec::with_capacity(32),
            losing_captures: Vec::with_capacity(32),
            state: if ce.is_some() { SortingState::PvMove } else { SortingState::Captures },
            pv_move: ce.map(|e| e.mov),
            killers: killers.to_vec(),
            last_move,
            counters_table,
            is_late: false,
        }
    }

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

    pub fn is_late(&self) -> bool {
        self.is_late
    }
}

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 {
                        let found = self.moves.iter().find(|m| m.to_simple() == pv).map(Move::clone);
                        if let Some(mov) = found {
                            self.moves.retain(|m| *m != mov);
                            return Some(mov);
                        }
                    }
                },
                SortingState::Captures => {
                    if self.captures.is_empty() {
                        for m in &self.moves {
                            if m.is_capture() {
                                let see = calculate_see(self.board.clone(), *m, self.board.turn);
                                if see >= 0 {
                                    self.captures.push((*m, see));
                                }
                                else {
                                    self.losing_captures.push((*m, see));
                                }
                            }
                            else {
                                self.quiets.push(*m);
                            }
                        }
                        self.moves.clear();
                        if self.captures.is_empty() {
                            self.state = SortingState::Killers;
                            continue;
                        }
                    }

                    let mut best_score = crate::evaluate::MIN_VALUE;
                    let mut best_move: Option<Move> = None;

                    for (c, score) in &self.captures {
                        if *score > best_score {
                            best_move = Some(*c);
                            best_score = *score;
                        }
                    }

                    self.captures.retain(|(m, _s)| 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::Counter;
                },
                SortingState::Counter => {
                    self.state = SortingState::Quiets;
                    //continue;
                    if let Some(lm) = self.last_move {
                        if let Ok(countermoves) = self.counters_table.lock() {
                            let side = self.side;
                            for q in &mut self.quiets {
                                let score = countermoves.get_score(side, lm, *q);
                                if score > 0 {
                                    self.counters.push((*q, score));
                                    *q = Move::nullmove();
                                }
                            }
                            self.quiets.retain(|m| !m.is_null());
                            //self.counters.sort_unstable_by_key(|(_m, s)| *s);
                            continue;
                        }
                    }
                },
                SortingState::Quiets => {
                    if !self.counters.is_empty() {
                        let mut best = self.counters[0];
                        for c in &self.counters {
                            if c.1 > best.1 {
                                best = *c;
                            }
                        }
                        self.counters.retain(|c| *c != best);

                        if best.1 <= 0 {
                            self.is_late = true;
                        }

                        return Some(best.0);
                    }

                    let mut promo: Option<Move> = None;
                    for q in &self.quiets {
                        if q.is_promotion() {
                            promo = Some(*q);
                            break;
                        }
                    }
                    self.is_late = true;
                    if let Some(p) = promo {
                        self.quiets.retain(|m| *m != p);
                        return Some(p);
                    }

                    if let Some(last) = self.quiets.pop() {
                        return Some(last);
                    }
                    else {
                        self.state = SortingState::LosingCaptures;
                        continue;
                    }
                },
                SortingState::LosingCaptures => {
                    let mut best_score = crate::evaluate::MIN_VALUE;
                    let mut best_move: Option<Move> = None;

                    for (c, score) in &self.losing_captures {
                        if *score > best_score {
                            best_move = Some(*c);
                            best_score = *score;
                        }
                    }

                    self.losing_captures.retain(|(m, _s)| Some(*m) != best_move);
                    return best_move;
                }
            }
        }

        return None;
    }
}

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

    let mut moves: Vec<Move> = Vec::with_capacity(128);
    generate_promotions(game, side, &mut moves);
    generate_pawn_captures(game, side, &mut moves);
    generate_en_passant(game, side, &mut moves);
    generate_pawn_pushes(game, side, &mut moves);
    generate_pawn_doublepushes(game, side, &mut moves);
    generate_knight_moves(game, side, &mut moves, false);
    generate_queen_moves(game, side, &mut moves, false);
    generate_bishop_moves(game, side, &mut moves, false);
    generate_rook_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: &Board, 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 Board, 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 Board, 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, pc: _ } |
                Move::Promotion { mov, pc: _ } => {
                    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 Board, _hash: &mut Cache, killers: &[Move], ce: Option<CacheEntry>, captures_only: bool, side: Side) -> Vec<Move> {
    let mut moves = generate_legal_moves(game, side, captures_only);

    let mov_val= |mov: &Move| {
        // if its a pv move from previously
        if let Some(c) = &ce {
            if c.mov == mov.to_simple() { 
                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: &Board, 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 Board, 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.
/// 
pub 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: _, pc } => {
            let attack = PIECE_VALUES[pc.piece_type() as usize];
            let victim = pc.capture_type().map(|ct| PIECE_VALUES[ct as usize]).unwrap_or(0);
            attack - victim
        },
        Move::Promotion { mov: _, pc } => {
            let victim = pc.capture_type().map(|ct| PIECE_VALUES[ct as usize]).unwrap_or(0);
            PIECE_VALUES[PAWN as usize] - victim
        },
        _ => 0
    }
}

const SEE_PIECE_VALUES: [i32; 6] = [
    100, // Pawn
    300, // Knight
    320, // Bishop
    500, // Rook
    1000, // Queen
    100000 // King
];

pub fn calculate_see(mut board: Board, mov: Move, side: Side) -> i32 {
    let capture_type = mov.captures();
    board.apply(mov);

    if let Some(ct) = capture_type {
        return SEE_PIECE_VALUES[ct as usize] - see_score::<true>(&mut board, mov.to(), !side);
    }
    else {
        return 0;
    }
}

fn see_score<const NO_CAPTURE_ALLLOWED: bool>(board: &mut Board, sq: Square, side: Side) -> i32 {
    let sq_bb = from_square(sq);
    let friends = board.get_all_side(side);
    let others = board.get_all_side(!side);

    let (piece_type, piece_side) =
        if let Some(piece) = board.get_square(sq) {
            piece
        }
        else { return 0; };


    let pawns = if side == BLACK { northeast_one(sq_bb) | northwest_one(sq_bb) }
                     else { southeast_one(sq_bb) | southwest_one(sq_bb) };
    let actual_pawns = board.get_piece(PAWN, side);
    if (sq_bb & (ROW_1 | ROW_8)) == 0 && (pawns & actual_pawns) != 0 {
        for pawn in BitboardIterator(pawns & actual_pawns) {
            *board.pawns_mut(side) ^= pawn | sq_bb;
            *board.get_piece_mut(piece_type, piece_side) ^= sq_bb;

            let subsee = SEE_PIECE_VALUES[piece_type as usize] - see_score::<true>(board, sq, !side);
            if NO_CAPTURE_ALLLOWED {
                return max(0, subsee);
            }
            else {
                return subsee;
            }
        }
    }

    let knights = get_knight_targets(sq);
    let actual_knights = board.get_piece(KNIGHT, side);
    if (knights & actual_knights) != 0 {
        for knight in BitboardIterator(knights & actual_knights) {
            *board.knights_mut(side) ^= knight | sq_bb;
            *board.get_piece_mut(piece_type, piece_side) ^= sq_bb;

            let subsee = SEE_PIECE_VALUES[piece_type as usize] - see_score::<true>(board, sq, !side);
            if NO_CAPTURE_ALLLOWED {
                return max(0, subsee);
            }
            else {
                return subsee;
            }
        }
    }

    let diags = generate_sliding_destinations(others, friends, sq, false, true);
    let actual_bishops = board.get_piece(BISHOP, side);
    if (diags & actual_bishops) != 0 {
        for bishop in BitboardIterator(diags & actual_bishops) {
            *board.bishops_mut(side) ^= bishop | sq_bb;
            *board.get_piece_mut(piece_type, piece_side) ^= sq_bb;

            let subsee = SEE_PIECE_VALUES[piece_type as usize] - see_score::<true>(board, sq, !side);
            if NO_CAPTURE_ALLLOWED {
                return max(0, subsee);
            }
            else {
                return subsee;
            }
        }
    }

    let straights = generate_sliding_destinations(others, friends, sq, true, false);
    let actual_rooks = board.get_piece(ROOK, side);
    if (straights & actual_rooks) != 0 {
        for rook in BitboardIterator(straights & actual_rooks) {
            *board.rooks_mut(side) ^= rook | sq_bb;
            *board.get_piece_mut(piece_type, piece_side) ^= sq_bb;

            let subsee = SEE_PIECE_VALUES[piece_type as usize] - see_score::<true>(board, sq, !side);
            if NO_CAPTURE_ALLLOWED {
                return max(0, subsee);
            }
            else {
                return subsee;
            }
        }
    }

    let actual_queens = board.get_piece(QUEEN, side);
    if ((straights | diags) & actual_queens) != 0 {
        for queen in BitboardIterator((straights | diags) & actual_queens) {
            *board.queens_mut(side) ^= queen | sq_bb;
            *board.get_piece_mut(piece_type, piece_side) ^= sq_bb;

            let subsee = SEE_PIECE_VALUES[piece_type as usize] - see_score::<true>(board, sq, !side);
            if NO_CAPTURE_ALLLOWED {
                return max(0, subsee);
            }
            else {
                return subsee;
            }
        }
    }

    let file = north_one(sq_bb) | sq_bb | south_one(sq_bb);
    let kings= west_one(file) | file | east_one(file);
    let actual_king= board.get_piece(KING, side);
    if (kings & actual_king) != 0 {
        for king in BitboardIterator(kings & actual_king) {
            *board.kings_mut(side) ^= king | sq_bb;
            *board.get_piece_mut(piece_type, piece_side) ^= sq_bb;

            let subsee = SEE_PIECE_VALUES[piece_type as usize] - see_score::<true>(board, sq, !side);
            if NO_CAPTURE_ALLLOWED {
                return max(0, subsee);
            }
            else {
                return subsee;
            }
        }
    }
    0
}

pub fn sort_moves_least_valuable_attacker(_game: &mut Board, move_list: &mut Vec<Move>, last_move: Option<Move>) {
    if let Some(lm) = last_move {
        move_list.sort_by_cached_key(|m| {
            mvv_lva_score(m) + if m.to() == lm.to() { -1000 } else { 0 }
        })
    } else {
        move_list.sort_by_cached_key(mvv_lva_score)
    }
}

pub fn sort_moves_no_hash(game: &mut Board, 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_legal_pawn_pushes<const SIDE: Side>(game: &Board, move_list: &mut Vec<Move>) {
    let pawns = game.pawns(SIDE);
    let adv_pieces= game.get_all_side(!SIDE);
    let own_pieces = game.get_all_side(SIDE);

    let moved_pawns =
        match SIDE {
            WHITE => north_one(pawns),
            BLACK => south_one(pawns)
        } & !(ROW_1 | ROW_8) & !(adv_pieces | own_pieces);
    
    let adv_bishops = game.get_piece(BISHOP, !SIDE);
    let adv_queens = game.get_piece(QUEEN, !SIDE);
    let adv_rooks= game.get_piece(ROOK, !SIDE);

    let king = game.get_piece(KING, SIDE);

    let diagonal_pinline = magic_bishop(square(king), adv_bishops | adv_queens);
    
    let iter = BitboardIterator(moved_pawns & !adv_pieces);
}


fn generate_pawn_pushes(game: &Board, 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) }, pc: PieceCaptureType::new(PAWN, None) });
    }
}

fn generate_pawn_doublepushes(game: &Board, 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) }, pc: PieceCaptureType::new(PAWN, None) });
    }
}

fn generate_pawn_captures(game: &Board, 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 right_cap = match side {
            WHITE => northeast_one(pawn),
            BLACK => southeast_one(pawn)
        };
        let left_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, pc: PieceCaptureType::new(QUEEN, captured) });
                    move_list.push(Move::Promotion { mov: simple_move, pc: PieceCaptureType::new(KNIGHT, captured) });
                    move_list.push(Move::Promotion { mov: simple_move, pc: PieceCaptureType::new(ROOK, captured) });
                    move_list.push(Move::Promotion { mov: simple_move, pc: PieceCaptureType::new(BISHOP, captured) });
                } else {
                    move_list.push(Move::Default { mov: simple_move, pc: PieceCaptureType::new(PAWN, captured) });
                }
            }
        }
    }
}

fn generate_promotions(game: &Board, 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, pc: PieceCaptureType::new(QUEEN, None) });
        move_list.push(Move::Promotion { mov: movement, pc: PieceCaptureType::new(KNIGHT, None) });
        move_list.push(Move::Promotion { mov: movement, pc: PieceCaptureType::new(ROOK, None) });
        move_list.push(Move::Promotion { mov: movement, pc: PieceCaptureType::new(BISHOP, None) });
    }
}


fn generate_en_passant(game: &Board, 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: &Board, 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, pc: PieceCaptureType::new(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, pc: PieceCaptureType::new(KNIGHT, None) });
            }
        }
    }
}

pub fn get_knight_targets(square: Square) -> Bitboard {
    /// 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: &Board, 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: &Board, 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: &Board, 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, square(piece), straight, diagonal);
        
        sum += (destinations & mask).count_ones();
    }
    return sum;
}

fn generate_sliding_moves(game: &Board, 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, square(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, pc: PieceCaptureType::new(piece_type, game.find_piece(dest)) });
            }
            else {
                move_list.push(Move::Default { mov: smove, pc: PieceCaptureType::new(piece_type, None) });
            }
        }
    }
}

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


    let mut destinations: Bitboard = 0;
    if diagonal {
        destinations |= crate::magic::magic_bishop(piece, friends | others) & !friends;
    }
    if straight {
        destinations |= crate::magic::magic_rook(piece, friends | others) & !friends;
    }
    
    return destinations & !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: &Board, 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 file = north_one(king) | king | south_one(king);
    let area = (west_one(file) | file | east_one(file)) & 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, pc: PieceCaptureType::new(KING, captured) });
    }
}


fn generate_castling_moves(game: &Board, side: Side, move_list: &mut Vec<Move>) {
    let king = game.kings(side);
    let king_sq = square(king);
    let c1 = Move::Castling{ mov: SimpleMove { from: king_sq, to: king_sq - 2 }, side: side, left: false };
    let c2 = Move::Castling{ mov: SimpleMove { from: king_sq, to: king_sq + 2 }, 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 king = game.get_piece(KING, side);
                if !is_check(game, side) && !is_attacked(game, square(king) - 1, !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 king = game.get_piece(KING, side);
                if !is_check(game, side) && !is_attacked(game, square(king) + 1, !side) && !is_attacked(game, square(king) + 2, !side)  {
                    move_list.push(c2);
                }
        }
    }
}

pub fn is_check(game: &Board, 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_square, false, true);
    let straight = generate_sliding_destinations(friends, others, king_square, 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: &Board, 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, false, true);
    let straight = generate_sliding_destinations(others, friends, sq, 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 std::sync::mpsc;

    use movegen::*;

    use crate::{search::SearchControl, engine::SearchMessage};

    ///
    /// 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 board: Board = Board::from_fen_str(fen).unwrap();
        let (_, stop_check) = mpsc::channel::<SearchMessage>();
        let mut pc = SearchControl::new_perft(&board, stop_check, depth);
        pc.perft(depth);
        return pc.nodes;
    }
}