bishop/src/movegen.rs

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

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")
            }
        }
    }
}

/**
 * @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)
    }
}


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(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>>()
}


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, 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);
            }
        }
        else {
            let eval = crate::evaluate::evaluate(game);
            game.undo_move(undo);
            return eval;
        }
    });
}

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 eval = crate::evaluate::evaluate(game);
        game.undo_move(undo);
        return eval;
    });
}

pub fn sort_quiescence(game: &mut Game, move_list: &mut Vec<Move>) {
    let value_piece = |pt| {
        match pt {
            PAWN => 1,
            KNIGHT => 2,
            BISHOP => 3,
            ROOK => 4,
            QUEEN => 5,
            KING => 6,
            _ => 0,
        }
    };

    move_list.sort_by_cached_key(|mov| {
        match *mov {
            Move::Default{ mov: _, piece_type, captured: Some(c) } => {
                value_piece(piece_type) - value_piece(c)
            },
            Move::Promotion{ mov: _, promote_to: _, captured: Some(c) } => {
                value_piece(PAWN) - value_piece(c)
            },
            Move::EnPassant{ mov: _, beaten } => {
                value_piece(PAWN) - value_piece(game.get_square(beaten).0)
            },
            _ => 0
        }
    });
}


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);
}

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 if side's king is in check
 */
pub fn is_check_old(game: &Game, side: Side) -> bool {
    let king = game.get_piece(KING, side);
    let king_square = square(king);
    let possible_attacks = generate_possattacking_moves(game, !side);
    for mov in possible_attacks {
        if let Move::Default{ mov, piece_type: _, captured: _ } = mov {
            if mov.to == king_square {
                if !is_check(game, side) {
                    panic!("incorrect non-check {}", game.beautiful_print());
                }
                return true;
            }
        }
        else if let Move::Promotion{ mov, promote_to: _, captured: _ } = mov {
            if mov.to == king_square {
                if !is_check(game, side) {
                    panic!("incorrect non-check {}", game.beautiful_print());
                }
                return true;
            }
        }
    }
    if is_check(game, side) {
        panic!("incorrect check {}", game.beautiful_print());
    }
    false
}
/*
#[cfg(test)]
mod tests {
    use search::Game;
    use movegen::*;

    #[test]
    fn pawn_pushes() {
        let mut game: Game = Game::default();
        let pawn_moves = generate_pawn_moves(&game, WHITE);
        assert_eq!(pawn_moves, ());
    }
}
*/