bishop/src/search.rs

use std::clone;

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



///
/// struct to contain data for a search
/// 
pub struct SearchControl<'a> {
    /// node counter
    pub nodes: usize,

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

    pub last_move: Option<Move>,
    pub countermoves: [[Move; 64]; 64],

    /// current halfmove clock for discarding old hash entries
    pub halfmove_age: u16,

    /// 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
    initial_depth: i32,

    nullmoves_enabled: bool,
}

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,
            killer_moves: vec![[Move::nullmove(); 2]; depth as usize],
            last_move: None,
            countermoves: [[Move::nullmove(); 64]; 64],
            halfmove_age: 0,
            check,
            stopping: false,
            move_history,
            initial_depth: depth,
            nullmoves_enabled: true
        }
    }

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

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

    pub fn countermove_to(&self, last_move: Move) -> Move {
        let from = last_move.to_simple().from;
        let to = last_move.to_simple().to;
        self.countermoves[from as usize][to as usize]
    }

}



/**
 * 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 cache_entry = hash.lookup(game);

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

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

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

        //info!("moveval {} -> {}\n", mov.to_string(), val);
        
        game.undo_move(undo);

        if sc.stopping {
            cancelled = true;
            break;
        }

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

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

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

        let mut rng = rand::thread_rng();
        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 as _, sc.halfmove_age as _, chosen_mov.0.to_simple(), chosen_mov.1 as _));
            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, mut depth: i32) -> PosValue {

    let last_move = sc.last_move;

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

    let cache_entry = hash.lookup(game);

    if let Some(e) = &cache_entry {
        if e.depth() as i32 >= depth {
            //println!("TABLE HIT!");
            match e.entry_type {
                EntryType::Value => { return e.value(); },
                EntryType::LowerBound => {
                    if e.value() >= beta { return beta; }
                },
                EntryType::UpperBound => {
                    if e.value() < alpha { return alpha; }
                },
            }
        }
    }

    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],
        cache_entry,
        game.turn);*/

    let mut moves = MoveGenerator::generate_legal_moves(
        game,
        cache_entry,
        &sc.killer_moves[ply_depth],
        last_move.map(|lm| sc.countermove_to(lm)),
        game.turn
    );

    //info!("nega moves: {:?}", moves.iter().map(|mv| mv.to_string()).collect::<Vec<String>>());

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

    // Nullmove
    if sc.nullmoves_enabled && !check && depth >= 4 && game.get_all_side(game.turn).count_ones() > 5 {

        let reduce = if depth > 5 { if depth > 7 { 5 } else { 4 }} else { 3 };

        let nmov = Move::nullmove();
        let undo = game.apply(nmov);

        sc.nullmoves_enabled = false;
        let val = -negamax(game, sc, hash, -beta, -alpha, depth - reduce);
        sc.nullmoves_enabled = true;
        game.undo_move(undo);

        if is_mate_in_p1(val).is_none() {
            if val >= beta {
                depth -= reduce - 1;
                //return beta;
            }
        }
    }

    let mut best_move: Option<Move> = None;

    while let Some(mov) = moves.next() {
        //println!("mov: {}", mov.to_string());
        let undo = game.apply(mov);
        sc.last_move = Some(mov);

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

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

        if val >= beta {
            hash.cache(game, CacheEntry::new_lower(depth as _, sc.halfmove_age as _, mov.to_simple(), val));
            if !mov.is_capture() {
                sc.insert_killer(ply_depth, mov);
                if depth >= 2 {
                    sc.countermoves[mov.to_simple().from as usize][mov.to_simple().to as usize] = mov;
                }
            }
            return val;
        }
        if val > alpha {
            alpha = val;
            best_move = Some(mov);
            if depth >= 3 {
                sc.countermoves[mov.to_simple().from as usize][mov.to_simple().to as usize] = mov;
            }
            if alpha >= mate_in_p1(1) {
                break;
            }
        }

        if let Some(lm) = last_move {
            moves.update_counter(sc.countermove_to(lm));
        }
    }


    if let Some(mov) = best_move {
        // alpha is exact
        hash.cache(game, CacheEntry::new_value(depth as _, sc.halfmove_age as _, mov.to_simple(), alpha));
        let cur_depth = (sc.initial_depth - depth) as usize;
    }
    else {
        hash.cache(game, CacheEntry::new_upper(depth as _, sc.halfmove_age as _, SimpleMove { from: 0, to: 0 }, 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 checkmated(); }

    //let mut moves = generate_legal_sorted_moves(game, hash, &[], None, true, game.turn);
    let mut moves = generate_legal_moves(game, game.turn, true);

    //sort_moves_no_hash(game, &mut moves);
    sort_moves_least_valuable_attacker(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, false);

    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 nodes_before = sc.nodes;
        let undo = game.apply(mov);
        let do_return = perft(game, sc, depth - 1);
        game.undo_move(undo);

        if depth >= sc.initial_depth {
            println!("{}: {}", mov.to_string(), sc.nodes - nodes_before);
        }

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