bishop/src/search.rs

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


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

    pub pv: Vec<Move>,
    pub killer_moves: Vec<[Move; 2]>,

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

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

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


impl<'a> SearchControl<'a> {
    pub fn new(check: &'a mut dyn FnMut() -> bool, move_history: &'a mut RepetitionTable, depth: i32) -> Self {
        SearchControl {
            nodes: 0,
            pv: Vec::with_capacity(depth as usize),
            killer_moves: vec![[Move::Nullmove; 2]; depth as usize],
            check,
            stopping: false,
            move_history,
            initial_depth: depth
        }
    }

    pub fn set_depth(&mut self, depth: i32) {
        self.initial_depth = depth;
        self.killer_moves = vec![[Move::Nullmove; 2]; depth as usize];
        self.pv = vec![Move::Nullmove; depth as _];
    }

    pub fn insert_killer(&mut self, ply_depth: usize, killer: Move) {
        if self.is_killer(ply_depth, &killer) {
            return;
        }
        let nkm = self.killer_moves[ply_depth].len();
        for i in 1..nkm {
            self.killer_moves[ply_depth][i - 1] = self.killer_moves[ply_depth][i];
        }
        self.killer_moves[ply_depth][nkm - 1] = killer;
    }

    pub fn is_killer(&self, ply_depth: usize, killer: &Move) -> bool {
        self.killer_moves[ply_depth].contains(killer)
    }
}


/**
 * 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();
    let ply_depth = (sc.initial_depth - depth) as usize;
    sort_moves(game, hash, &sc.killer_moves[ply_depth], &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 = 0 as PosValue;

    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 val = -negamax(game, sc, hash, decrease_mate_in(-beta), decrease_mate_in(-alpha), depth - 1);
        game.undo_move(undo);

        if sc.stopping {
            //return (Move::default(), 0);
            cancelled = true;
            break;
        }

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

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

        if increase_mate_in(val) > alpha {
            alpha = increase_mate_in(val) - ALPHA_OFFSET;
            valued_moves.push((mov, -alpha));
        }
    }



    //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));
            sc.pv[0] = chosen_mov.0;
            return SearchResult::Finished(chosen_mov.0, -chosen_mov.1);
        }
    }
    else {
        return SearchResult::Invalid;
    }
}

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

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

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

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

    let ply_depth = (sc.initial_depth - depth) as usize;
    let moves = generate_legal_sorted_moves(game, hash, &sc.killer_moves[ply_depth], game.turn);
    //info!("nega moves: {:?}", moves.iter().map(|mv| mv.to_string()).collect::<Vec<String>>());

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

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

        let val = -negamax(game, sc, hash, -beta, -alpha, depth / 2 - 1);
        game.undo_move(undo);

        if sc.stopping {
            return alpha;
        }

        if is_mate_in_p1(val).is_none() {
            if val >= beta {
                return beta;
            }
        }
    }


    //sort_moves(game, hash, &sc.killer_moves, &mut moves);
    //moves.sort_by_cached_key(|m| if sc.is_killer(*m) { -1 } else { 0 });

    let mut alpha_is_exact = false;
    let mut best_move = Move::Nullmove;

    // we can't beat an alpha this good
    if alpha >= mate() {
        return alpha;
    }

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

        let val = -negamax(game, sc, hash, -decrease_mate_in(beta), -decrease_mate_in(alpha), depth - 1);
        game.undo_move(undo);
        //val = increase_mate_in(val);

        // return if the search has been cancelled
        if sc.stopping {
            return alpha;
        }

        if val >= beta {
            hash.cache(game, CacheEntry::new_upper(depth, val));
            //println!("but ret {}: {}", depth, beta);
            //info!("{} causes beta cutoff at {} ", mov.to_string(), val);
            if !mov.is_capture() {
                sc.insert_killer(ply_depth, mov);
            }
            return beta;
        }
        if increase_mate_in(val) > alpha {
            alpha = increase_mate_in(val);
            alpha_is_exact = true;
            best_move = mov;
        }
    }


    if alpha_is_exact {
        hash.cache(game, CacheEntry::new_value(depth, alpha));
        let cur_depth = (sc.initial_depth - depth) as usize;
        sc.pv[cur_depth] = best_move;
    }
    else {
        hash.cache(game, CacheEntry::new_lower(depth, alpha));
    }
    //info!("best alpha {}", alpha);
    return alpha;
}

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

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

    let val = evaluate(game);
    if val >= beta {
        return beta;
    }
    if val > alpha {
        alpha = val;
    }

    if depth <= 0 {
        return alpha;
    }

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

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

    sort_moves_no_hash(game, &mut moves);

    for mov in moves {
        let undo = game.apply(mov);
        let val = -quiescence_search(game, sc, hash, decrease_mate_in(-beta), decrease_mate_in(-alpha), depth - 1);
        game.undo_move(undo);

        if sc.stopping {
            return alpha
        }

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


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);
        game.undo_move(undo);

        if do_return {
            return true;
        }
    }

    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 check_fn = || false;
                let mut rt = RepetitionTable::new();
                let mut sc = SearchControl::new(&mut check_fn, &mut rt, depth as _);
                perft(&mut game, &mut sc, depth as _);
                assert_eq!(sc.nodes, p_res);
            }
        }
    }
}