bishop/src/search.rs

use bitboard::*;
use movegen::*;
use game::Game;
use evaluate::*;
use log::info;
use rand::prelude::*;
use hash::*;


pub struct SearchControl<'a> {
    /// node counter
    pub nodes: usize,

    /// function to check if the search should be exited
    pub check: &'a mut dyn FnMut() -> bool,
    pub move_history: &'a RepetitionTable,

    /// depth the search was started at
    pub initial_depth: i32,
}

pub enum SearchResult {
    Finished(Move, PosValue),
    Cancelled(Option<(Move, PosValue)>),
    Invalid
}


/**
 * searches for moves and returns the best move found plus its value
 */
pub fn search(game: &mut Game, sc: &mut SearchControl, hash: &mut Cache, mut alpha: PosValue, beta: PosValue, depth: i32) -> SearchResult {
    if depth == 0 {
        return SearchResult::Invalid;
    }

    let mut moves = generate_legal_moves(game, game.turn);
    let mut rng = rand::thread_rng();
    sort_moves(game, hash, &mut moves);
    
    info!("moves: {:?}", moves.iter().map(|mv| mv.to_string()).collect::<Vec<String>>());

    //let mut alpha: PosValue = MIN_VALUE;
    //let mut beta: PosValue = MAX_VALUE;

    // use a slight offset for the alpha value in the root node in order to
    // determine possibly multiple good moves
    const ALPHA_OFFSET: PosValue = 50 as _;

    let mut valued_moves: Vec<(Move, PosValue)> = Vec::with_capacity(moves.len());
    let mut cancelled = false;

    for mov in moves {
        let undo = game.apply(mov);
        //assert_eq!(new_game, *game, );

        //info!("searching {}", mov.to_string());
        let (mut val, ret) = negamax(game, sc, hash, -beta, -alpha, depth - 1);
        val = -val;

        if let Some(turns) = is_mate_in_p1(val) {
            if turns < 0 {
                val = mate_in_p1(turns - 1);
            }
            if turns > 0 {
                val = mate_in_p1(turns + 1);
            }
            if turns == 0 {
                if val < 0 {
                    val = mate_in_p1(-1);
                }
                else {
                    val = mate_in_p1(1);
                }
            }
        }

        if ret {
            //return (Move::default(), 0);
            cancelled = true;
            game.undo_move(undo);
            break;
        }

        if val >= mate() {
            // mate in 1 --- can't get better than that
            info!("yay mate!");
            game.undo_move(undo);
            return SearchResult::Finished(mov, val);
        }

        //info!("searched {} -> {}", mov.to_string(), val);

        if val > alpha {
            alpha = val - ALPHA_OFFSET;
            //info!("updated alpha to {}", alpha);
        }

        valued_moves.push((mov, -val));
        
        game.undo_move(undo);
    }



    //info!("movvalues: {:?}", valued_moves.iter().map(|mv| mv.0.to_string() + " - " + &mv.1.to_string()).collect::<Vec<String>>());

    valued_moves.sort_by_key(|mv| mv.1);

    //info!("best movvalues: {:?}", valued_moves.iter().map(|mv| mv.0.to_string() + " - " + &mv.1.to_string()).collect::<Vec<String>>());

    if valued_moves.len() > 0 {
        let min_val = valued_moves[0].1;
        let best_moves = valued_moves.iter().filter(|mv| mv.1 == min_val).collect::<Vec<&(Move, PosValue)>>();

        //info!("bestmove value {}", -min_val);
        let chosen_mov = best_moves[(rng.next_u64() % best_moves.len() as u64) as usize];
        if cancelled {
            return SearchResult::Cancelled(Some((chosen_mov.0, -chosen_mov.1)));
        }
        else {
            hash.cache(game, CacheEntry::new_value(depth, chosen_mov.1));
            return SearchResult::Finished(chosen_mov.0, -chosen_mov.1);
        }
    }
    else {
        return SearchResult::Invalid;
    }
}

fn negamax(game: &mut Game, sc: &mut SearchControl, hash: &mut Cache, mut alpha: PosValue, beta: PosValue, depth: i32) -> (PosValue, bool) {

    if let Some(e) = hash.lookup(game) {
        if e.depth >= depth {
            //println!("TABLE HIT!");
            match e.entry_type {
                EntryType::Value => { return (e.value, false); },
                //EntryType::LowerBound => { if e.value > alpha { return (e.value, false) } },
                EntryType::LowerBound => { if e.value > alpha { alpha = e.value; } },
                //EntryType::UpperBound => { if e.value >= beta { return (beta, false); } },
                EntryType::UpperBound => { if e.value >= beta { return (beta, false); } },
            }
        }
    }

    if depth == 0 {
        return quiescence_search(game, sc, hash, alpha, beta, 9);
    }

    sc.nodes += 1;
    if sc.nodes % 1024 == 0 {
        if (sc.check)() {
            return (0 as _, true);
        }
    }

    if game.get_piece(KING, game.turn) == 0 { return (-mate(), false); }


    let mut moves = generate_legal_moves(game, game.turn);

    let check = is_check(game, game.turn);
    if moves.len() == 0 {
        if check {
            // mate
            return (-mate(), false);
        }
        else {
            // stalemate
            return (0 as _, false);
        }
    }

    // Nullmove
    if !check && depth >= 4 && game_lateness(game) < 80 {
        let nmov = Move::Nullmove;
        let undo = game.apply(nmov);

        let (mut val, ret) = negamax(game, sc, hash, -beta, -alpha, depth / 2 - 1);
        val = -val;
        val = increase_mate_in(val);
        
        if ret {
            game.undo_move(undo);
            return (alpha, ret)
        }

        if val >= beta {
            game.undo_move(undo);
            //hash.cache(game, CacheEntry::new_beta(depth, beta));
            //println!("but ret {}: {}", depth, beta);
            return (beta, false);
        }
        game.undo_move(undo);
    }


    sort_moves(game, hash, &mut moves);

    let mut alpha_is_exact = false;

    for mov in moves {
        let undo = game.apply(mov);

        let (mut val, ret) = negamax(game, sc, hash, -beta, -alpha, depth - 1);
        val = -val;

        val = increase_mate_in(val);

        if ret {
            game.undo_move(undo);
            return (alpha, ret)
        }

        if val >= beta {
            game.undo_move(undo);
            hash.cache(game, CacheEntry::new_lower(depth, val));
            //println!("but ret {}: {}", depth, beta);
            return (beta, false);
        }
        if val > alpha {
            alpha = val;//(val as f64 * 0.95) as _;
            alpha_is_exact = true;
        }
        game.undo_move(undo);
    }


    if alpha_is_exact {
        hash.cache(game, CacheEntry::new_value(depth, alpha));
    }
    else {
        hash.cache(game, CacheEntry::new_upper(depth, alpha));
    }
    //info!("best alpha {}", best);
    return (alpha, false);
}

fn quiescence_search(game: &mut Game, sc: &mut SearchControl, hash: &mut Cache, mut alpha: PosValue, beta: PosValue, depth: i32) -> (PosValue, bool) {
    let val = evaluate(game);

    sc.nodes += 1;
    if sc.nodes % 1024 == 0 {
        if (sc.check)() {
            return (0 as _, true);
        }
    }

    if val >= beta {
        return (beta, false);
    }
    if val > alpha {
        alpha = val;
    }

    if depth <= 0 {
        return (alpha, false);
    }

    if game.get_piece(KING, game.turn) == 0 { return (-mate(), false); }

    let moves = generate_attacking_moves(game, game.turn);

    for mov in moves {
        let undo = game.apply(mov);

        let (mut val, ret) = quiescence_search(game, sc, hash, -beta, -alpha, depth - 1);
        val = -val;
        if val >= beta {
            game.undo_move(undo);
            return (beta, false);
        }
        if val > alpha {
            alpha = val;
        }
        game.undo_move(undo);
    }
    return (alpha, false);
}


pub fn apply_move(game: &Game, mov: Move) -> Game {
    let mut new_game = game.clone();

    let side = game.turn;
    let friends = game.get_all_side(side);
    let others = game.get_all_side(!side);
    match mov {
        Move::Default{ mov, piece_type: pt, captured: _ } => {

            if pt == KING {
                // invalidate castling rights
                new_game.castling_rights[if game.turn == BLACK { 2 } else { 0 }] = false;
                new_game.castling_rights[if game.turn == BLACK { 3 } else { 1 }] = false;
            }

            // invalidate castling rights
            if mov.from == square_from_indices(7, 0) || mov.to == square_from_indices(7, 0) {
                new_game.castling_rights[0] = false;
            }
            if mov.from == square_from_indices(0, 0) || mov.to == square_from_indices(0, 0) {
                new_game.castling_rights[1] = false;
            }
            if mov.from == square_from_indices(7, 7) || mov.to == square_from_indices(7, 7) {
                new_game.castling_rights[2] = false;
            }
            if mov.from == square_from_indices(0, 7) || mov.to == square_from_indices(0, 7) {
                new_game.castling_rights[3] = false;
            }

            // if it is a capture
            if from_square(mov.to) & others != 0 {
                let (other_piece, other_side) = game.get_square(mov.to);
                if let Some((ref zt, ref _zv)) = game.zobrist {
                    let hup = zt.piece_hash(other_piece, other_side, mov.to);
                    new_game.update_zobrist(hup);
                }
                new_game.apply_mask(!from_square(mov.to));
            }

            let moved_piece = mov.apply_to(new_game.get_piece(pt, side));
            new_game.set_piece(pt, side, moved_piece);

            if let Some((ref zt, ref _zv)) = game.zobrist {
                let hup = zt.piece_hash(pt, side, mov.from) ^ zt.piece_hash(pt, side, mov.to);
                new_game.update_zobrist(hup);
            }
        },
        Move::Castling { side, left } => {
            // invalidate future castling rights
            new_game.castling_rights[if game.turn == BLACK { 2 } else { 0 }] = false;
            new_game.castling_rights[if game.turn == BLACK { 3 } else { 1 }] = false;

            let king = game.get_piece(KING, side);
            let rook = if left {
                game.get_piece(ROOK, side) & (king << 4)
            }
            else {
                game.get_piece(ROOK, side) & (king >> 3)
            };

            let new_king = if left { king << 2 } else { king >> 2 };
            let new_rook = if left { rook >> 3 } else { rook << 2 };

            new_game.set_piece(KING, side, new_king);
            *new_game.get_piece_mut(ROOK, side) |= new_rook;
            *new_game.get_piece_mut(ROOK, side) &= !rook;
        },
        Move::EnPassant { mov, beaten } => {
            let pawns = game.pawns(side);
            if let Some(ep) = game.en_passant {
                *new_game.get_piece_mut(PAWN, side) &= !from_square(mov.from);
                *new_game.get_piece_mut(PAWN, side) |= from_square(mov.to);
                *new_game.get_piece_mut(PAWN, !side) &= !from_square(beaten);
            }
        },
        Move::Promotion { mov, promote_to, captured } => {
            //if from_square(mov.to) & others != 0 {
            if let Some(pt) = captured {
                *new_game.get_piece_mut(pt, !side) &= !from_square(mov.to);
            }
            new_game.apply_mask(!from_square(mov.from));

            match promote_to {
                QUEEN => { *new_game.queens_mut(side) |= from_square(mov.to); }
                ROOK => { *new_game.rooks_mut(side) |= from_square(mov.to); }
                BISHOP => { *new_game.bishops_mut(side) |= from_square(mov.to); }
                KNIGHT => { *new_game.knights_mut(side) |= from_square(mov.to); }
                _ => {
                    info!("internal error");
                }
            }
        },
        Move::Nullmove => {}
    }

    new_game.turn = !new_game.turn;


    if let Some((ref zt, ref zv)) = new_game.zobrist {
        //info!("applied {}, zobrist now {}", mov.to_string(), *zv);
    }
    return new_game;
}


pub fn perft(game: &mut Game, sc: &mut SearchControl, depth: i32) -> bool {
    let moves = generate_legal_moves(game, game.turn);

    if depth <= 1 {
        sc.nodes += moves.len();
        if sc.nodes % 1024 < moves.len() {
            if (sc.check)() {
                return true;
            }
        }
        return false;
    }

    
    for mov in moves {
        let undo = game.apply(mov);
        let do_return = perft(game, sc, depth - 1);
        if do_return {
            game.undo_move(undo);
            return true;
        }
        game.undo_move(undo);
    }

    return false;
}


#[cfg(test)]
mod tests {

    use super::*;
    #[test]
    fn test_move_generation() {
        let positions = [
            "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8",
            "r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10"
        ];
        let perft_results: [Vec<usize>; 2] = [
            vec![44, 1486, 62379, 2103487],
            vec![46, 2079, 89890, 3894594]
        ];

        for (i, &position) in positions.iter().enumerate() {
            let mut game = Game::from_fen_str(position).unwrap();
            for (j, &p_res) in perft_results[i].iter().enumerate() {
                let depth = j + 1;
                let mut sc = SearchControl{ nodes: 0, check: &mut (|| false), move_history: &mut RepetitionTable::new(), initial_depth: depth as _ };
                perft(&mut game, &mut sc, depth as _);
                assert_eq!(sc.nodes, p_res);
            }
        }
    }
}