bishop/src/movegen.rs

use bitboard::Bitboard;
use bitboard::Square;
use bitboard::*;
use game::Game;
use log::info;

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 },
    Castling { side: Side, left: bool },
    EnPassant { mov: SimpleMove, beaten: Square },
    Promotion { mov: SimpleMove, promote_to: PieceType },
}

impl Default for Move {
    fn default() -> Move {
        Move::Default{ mov: SimpleMove { from: 0, to: 0 }, piece_type: NO_PIECE }
    }
}


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 to_string(&self) -> String {
        match self {
            Move::Default{ mov, piece_type } => {
                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 } => {
                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 { "" }
            },
        }
    }
}

/**
 * @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 board: Bitboard }

impl Iterator for BitboardIterator {
    type Item = Bitboard;

    fn next(&mut self) -> Option<Bitboard> {
        if self.board != 0 {
            let lsb = self.board & (self.board.wrapping_neg());
            self.board ^= 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: &Game, side: Side) -> Vec<Move> {
    let moves = generate_moves(game, side);

    moves.into_iter().filter(|mov| {
        let tryout = super::search::apply_move(game, *mov);
        !is_check(&tryout, side)
    }).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: &Game, move_list: &mut Vec<Move>) {
    let all_pieces = game.get_all_side(WHITE) | game.get_all_side(BLACK);

    move_list.sort_by_key(|mov| {
        match mov {
            Move::Default { mov, piece_type } => if (from_square(mov.to) & all_pieces) != 0 { -10 } else { 0 },
            Move::Castling { side: _, left: _ } => 0,
            Move::Promotion { mov, promote_to } => -15,
            Move::EnPassant { mov: _, beaten: _ } => -10,
        }
    });
}


/*
pub fn generate_pawn_moves(game: &Game, side: Side) -> Bitboard {
    let pushed = generate_pawn_pushes(game, side);
    let iter = BitboardIterator { board: pushed };
    for p in iter {
        println!("{}", p.trailing_zeros());
    }

    return 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 { board: 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 });
    }
}

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 { board: 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 });
    }
}

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 { board: 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 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 });
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: ROOK });
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: BISHOP });
                    move_list.push(Move::Promotion { mov: simple_move, promote_to: KNIGHT });
                } else {
                    move_list.push(Move::Default { mov: simple_move, piece_type: PAWN });
                }
            }
        }
    }
}

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 { board: 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 });
        move_list.push(Move::Promotion { mov: movement, promote_to: ROOK });
        move_list.push(Move::Promotion { mov: movement, promote_to: BISHOP });
        move_list.push(Move::Promotion { mov: movement, promote_to: KNIGHT });
    }
}


fn generate_en_passant(game: &Game, side: Side, move_list: &mut Vec<Move>) {
    if let Some(ep) = game.en_passant {
        let pawncolumn = A_FILE >> 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{ board: knights };

    for k in knight_iter {
        let target_mask = if captures_only {
            !friends & others
        } else {
            !friends
        };
        let targets = BitboardIterator { board: get_knight_targets(square(k)) & target_mask };
        for target in targets {
            let simple_move = SimpleMove { from: square(k), to: square(target) };
            move_list.push(Move::Default{ mov: simple_move, piece_type: KNIGHT });
        }
    }
}

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(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(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(friends, others, game.queens(side), QUEEN, true, true, move_list, captures_only);
}

fn generate_sliding_moves(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 { board: 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 { board: destinations & mask };
        for dest in dest_iter {
            let smove = SimpleMove{ from: square(piece), to: square(dest) };
            move_list.push(Move::Default { mov: smove, piece_type: piece_type});
        }
    }
}

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 { board: area };
    for destination in area_iter {
        let simple_move = SimpleMove{ from: square(king), to: square(destination) };
        move_list.push(Move::Default { mov: simple_move, piece_type: KING });
    }
}


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

/**
 * checks if side's king is in check
 */
pub fn is_check(game: &Game, side: Side) -> bool {
    let king_square = square(game.get_piece(KING, side));
    let possible_attacks = generate_possattacking_moves(game, !side);
    for mov in possible_attacks {
        if let Move::Default{ mov, piece_type: _ } = mov {
            if mov.to == king_square {
                return true;
            }
        }
        else if let Move::Promotion{ mov, promote_to: _ } = mov {
            if mov.to == king_square {
                return true;
            }
        }
    }
    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, ());
    }
}
*/