bishop/src/search.rs

use std::sync::{RwLock, Arc, Mutex, mpsc};
use std::time::{Instant, Duration};

use movegen::*;
use board::Board;
use evaluate::*;
use log::info;
use rand::prelude::*;
use ttable::*;

use crate::engine::SearchMessage;


pub struct SearchCommon {
    pub hash: Cache,
}

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

    pub board: Board,
    pub hash: Arc<RwLock<Cache>>,

    /// depth the current iteration was started at 
    initial_depth: i32,

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

    pub last_move: Option<Move>,
    pub countermoves: Arc<Mutex<CountermoveTable>>,

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

    /// channel which is probed from time to time to check whether the
    /// search should be aborted
    stop_channel: mpsc::Receiver<SearchMessage>,

    /// whether the search is currently being terminated (after receiving Stop on stop_channel)
    stopping: bool,

    search_started: Instant,
    pub movetime: Option<Duration>,
    pub remaining_time: Option<Duration>,

    reductions_allowed: bool,
}



#[derive(Debug)]
pub enum SearchResult {
    Finished(Move, PosValue),
    NoMove(PosValue),
    Cancelled(Option<(Move, PosValue)>),
    FailHigh(PosValue),
    FailLow(PosValue),
    PerftFinished,
    Invalid
}

impl SearchControl {
    pub fn new(board: &Board, stop_channel: mpsc::Receiver<SearchMessage>, hash: Arc<RwLock<Cache>>) -> Self {
        SearchControl {
            nodes: 0,
            board: board.clone(),
            hash,
            killer_moves: Vec::new(),
            last_move: None,
            countermoves: Arc::new(Mutex::new(CountermoveTable::new())),
            halfmove_age: 0,
            stop_channel,
            stopping: false,
            search_started: Instant::now(),
            movetime: None,
            remaining_time: None,
            initial_depth: 0,
            reductions_allowed: true
        }
    }

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

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

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

    fn reconstruct_pv(&self) -> Vec<Move> {
        let mut pv: Vec<Move> = Vec::new();
        let mut g = self.board.clone();

        // max 100 to avoid infinite loops
        for _ in 0..100 {
            let mce = self.hash.read().unwrap().lookup(&g).map(CacheEntry::clone);
            if let Some(ce) = mce {
                if ce.mov == (SimpleMove{ from: 0, to: 0 }) {
                    break;
                }
                let movs = generate_moves(&g, g.turn);
                let bm = movs.iter().find(|m| (**m).to_simple() == ce.mov);
                if let Some(found) = bm {
                    g.apply(*found);
                    pv.push(*found);
                }
                else {
                    break;
                }
            }
            else {
                break;
            }
        }
        return pv;
    }

    /// is called every 1024 nodes to check if the search will be stopped
    fn check_stop(&self) -> bool {
        if let Some(mt) = self.movetime {
            if self.search_started.elapsed() >= mt {
                return true;
            }
        }

        if let Some(rt) = self.remaining_time {
            if self.search_started.elapsed() >= (rt / 17) {
                return true;
            }
        }

        if let Ok(SearchMessage::Stop) = self.stop_channel.try_recv() {
            return true;
        }

        if self.stopping {
            return true;
        }

        return false;
    }

    fn windowed_search(&mut self, depth: i32, expected_value: PosValue, initial_window_size: i32) -> SearchResult {
        let mut alpha_coeff = 1;
        let mut beta_coeff = 1;
        let mut alpha = expected_value - initial_window_size * alpha_coeff;
        let mut beta = expected_value + initial_window_size * beta_coeff;

        let mut result = search(self.board.clone(), self, self.hash.clone(), alpha, beta, depth);

        loop {
            match result {
                SearchResult::FailHigh(_val) => {
                    beta_coeff *= 3;
                    beta = expected_value + initial_window_size * beta_coeff;
                    if beta_coeff >= 9 {
                        beta = MAX_VALUE;
                    }
                    result = search(self.board.clone(), self, self.hash.clone(), alpha, beta, depth);
                },
                SearchResult::FailLow(_val) => {
                    alpha_coeff *= 3;
                    alpha = expected_value - initial_window_size * alpha_coeff;
                    if alpha_coeff >= 9 {
                        alpha = MIN_VALUE;
                    }
                    result = search(self.board.clone(), self, self.hash.clone(), alpha, beta, depth);
                },
                SearchResult::Finished(_mov, val) => {
                    // successful search within bounds
                    break;
                }
                SearchResult::Invalid => {
                    alpha = MIN_VALUE; beta = MAX_VALUE;
                    result = search(self.board.clone(), self, self.hash.clone(), alpha, beta, depth);
                }
                _ => break,
            }
        }


        return result;
    }

    pub fn iterative_deepening(&mut self, max_depth: Option<i32>) -> bool {
        let mut best_move: Option<Move> = None;
        let mut best_val: Option<PosValue> = None;

        self.search_started = Instant::now();
        self.halfmove_age = self.board.ply_number() as _;

        for depth in 1.. {

            self.set_depth(depth);

            let result =
                if let Some(bv) = best_val {
                    const WINDOW_RADIUS: PosValue = 20;
                    self.windowed_search(depth, bv, WINDOW_RADIUS)
                } else {
                    search(self.board.clone(), self, self.hash.clone(), MIN_VALUE, MAX_VALUE, depth)
                };


            match result {
                SearchResult::Finished(mov, val) => {
                    best_move = Some(mov);
                    best_val = Some(val);

                    let elapsed = self.search_started.elapsed();
                    let nodes = self.nodes;
                    let nps = (nodes as f64 / elapsed.as_nanos() as f64 * 1000000000.0) as i64;
                    let hashfull = self.hash.read().unwrap().fullness_permill();
                    let pv_array = self.reconstruct_pv();
                    let pv = &pv_array.iter().filter(|&m| !m.is_null()).map(|m| m.to_string()).fold(String::new(), |a, b| a + " " + &b)[0..];


                    if let Some(plies) = crate::evaluate::is_mate_in_plies(val) {
                        //println!("plies = {}", plies);
                        let turns = (plies + if plies > 0 { 1 } else { -1 }) / 2;
                        let infostring = format!("info depth {} score mate {} time {} nodes {} nps {} hashfull {} pv{}", depth, turns, elapsed.as_millis(), nodes, nps, hashfull, pv);
                        println!("{}", infostring);
                        info!("{}", infostring);
                        if max_depth.is_none() && plies.abs() * 2 <= depth {
                            break;
                        }
                    }
                    else {
                        let infostring = format!("info depth {} score cp {} time {} nodes {} nps {} hashfull {} pv{}", depth, val, elapsed.as_millis(), nodes, nps, hashfull, pv);
                        println!("{}", infostring);
                        info!("{}", infostring);
                    }
                },
                SearchResult::NoMove(val) => {
                    let infostring = format!("info depth {} score cp {}", depth, val);
                    println!("{}", infostring);
                    info!("{}", infostring);
                    break;
                }
                _ => {
                    break;
                }
            }

            if let Some(d) = max_depth {
                if depth >= d {
                    break;
                }
            }
        }

        if let (Some(bm), Some(_bv)) = (best_move, best_val) {
            info!("bestmove {}", bm.to_string());
            println!("bestmove {}", bm.to_string());
        }
        else {
            info!("bestmove 0000");
            println!("bestmove 0000");
        }
        return true;
    }

}



/// 
/// searches for moves and returns the best move found plus its value
/// 
pub fn search(mut board: Board, sc: &mut SearchControl, hashs: Arc<RwLock<Cache>>, mut alpha: PosValue, beta: PosValue, depth: i32) -> SearchResult {
    let mut hash = hashs.write().unwrap();
    if depth == 0 {
        return SearchResult::Invalid;
    }

    let cache_entry = hash.lookup(&board).map(CacheEntry::clone);

    let ply_depth = (sc.initial_depth - depth) as usize;
    let turn = board.turn;
    let moves = generate_legal_sorted_moves(&mut board, &mut hash, &sc.killer_moves[ply_depth], cache_entry, false, 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>>());

    let mut cancelled = false;

    if moves.is_empty() {
        if is_check(&board, board.turn) {
            return SearchResult::NoMove(checkmated());
        }
        else {
            return SearchResult::NoMove(0);
        }
    }

    let mut best_move: Option<Move> = None;

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

        let val = increase_mate_in(
            -negamax(&mut board, sc, &mut hash, decrease_mate_in(-beta), decrease_mate_in(-alpha), depth - 1)
        );

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

        board.undo_move(undo);

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

        if val >= beta {
            hash.cache(&board, CacheEntry::new_lower(depth as _, sc.halfmove_age as _, mov.to_simple(), val));
            return SearchResult::FailHigh(val);
        }

        if val > alpha {
            alpha = val;
            best_move = Some(mov);
        }
    }

    if cancelled {
        return SearchResult::Cancelled(None);
    }

    if let Some(mov) = best_move {
        // alpha is exact
        let ce = CacheEntry::new_value(depth as _, sc.halfmove_age as _, mov.to_simple(), alpha);
        hash.cache(&board, ce);
        return SearchResult::Finished(mov, alpha);
    }
    else {
        hash.cache(&board, CacheEntry::new_upper(depth as _, sc.halfmove_age as _, SimpleMove { from: 0, to: 0 }, alpha));
        return SearchResult::FailLow(alpha);
    }
}


pub fn negamax(game: &mut Board, 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_plies(1) {
        return alpha;
    }

    let cache_entry = hash.lookup(game).map(CacheEntry::clone);

    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; }
                },
                EntryType::NoBound => {}
            }
        }
    }

    let check = is_check(game, game.turn);

    if depth == 0 {
        // check extend
        if check {
            depth = 1;
        }
        else {
            return quiescence_search(game, sc, hash, alpha, beta, 9);
        }
    }

    sc.nodes += 1;
    if sc.nodes % 1024 == 0 {
        if sc.check_stop() {
            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.as_ref(),
        &sc.killer_moves[ply_depth],
        if depth >= 3 { last_move } else { None },
        sc.countermoves.clone(),
        game.turn
    );

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


    if moves.is_empty() {
        if check {
            // mate
            return checkmated();
        }
        else {
            // stalemate
            return 0;
        }
    }

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

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

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

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

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

    // futility pruning
    if false && depth == 1 && !check && game_lateness(game) < 60 {
        const FUTILITY_THRESHOLD: PosValue = 240;
        let curr_eval = quiescence_search(game, sc, hash, alpha, beta, 9);
        if curr_eval + FUTILITY_THRESHOLD <= alpha {
            return alpha;
        }
    }

    let mut best_move: Option<Move> = None;

    while let Some(mov) = moves.next() {

        let mut reduce = 0;
        let reductions_allowed_before = sc.reductions_allowed;
        if depth > 4 && moves.is_late() && !mov.is_promotion() && reductions_allowed_before {
            reduce = 1;
            if depth >= 8 {
                reduce = 2;
            }
            sc.reductions_allowed = false;
        }

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

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

        if reduce != 0 && (val >= beta || val > alpha) {
            reduce = 0;
            let undo = game.apply(mov);
            sc.last_move = Some(mov);

            val = increase_mate_in(
                -negamax(game, sc, hash, -decrease_mate_in(beta), -decrease_mate_in(alpha), depth - 1 - reduce)
            );
            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 {
                    if let Some(lm) = last_move {
                        sc.countermoves.as_ref().lock().unwrap().update_score(game.turn, lm, mov, (depth * depth) as i16);
                    }
                }
            }
            return val;
        }
        if val > alpha {
            alpha = val;
            best_move = Some(mov);
            if sc.initial_depth >= 10 && cache_entry.is_some() && cache_entry.as_ref().unwrap().entry_type == EntryType::Value {
                //println!("mov: {}", mov.to_string());
            }
            if depth >= 2 {
                if let Some(_lm) = last_move {
                    //sc.countermoves.as_ref().lock().unwrap().update_score(lm, mov, (depth * depth) as i16);
                }
            }
            if alpha >= mate_in_plies(1) {
                break;
            }
        }
    }


    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));
    }
    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(board: &mut Board, 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_stop() {
            sc.stopping = true;
            return 0;
        }
    }

    let last_move = sc.last_move;

    if board.get_piece(KING, board.turn) == 0 { return checkmated(); }

    let check = is_check(board, board.turn);

    let val = evaluate(board);

    if !check {
        if val >= beta {
            return beta;
        }
        if val > alpha {
            alpha = val;
        }
    }

    if depth <= 0 {
        return alpha;
    }

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

    //sort_moves_no_hash(game, &mut moves);
    //sort_moves_least_valuable_attacker(board, &mut moves, last_move);

    let mut val_movs: Vec<_> = moves.iter()
        .map(|m| (*m, calculate_see(board.clone(), *m, board.turn)))
        .filter(|(_m, v)| *v > 0)
        .collect();
    val_movs.sort_unstable_by_key(|(_m, v)| -*v);
    moves = val_movs.iter().map(|(m, _v)| *m).collect();
    //moves.sort_by_cached_key(|m| -calculate_see(board.clone(), *m, board.turn));


    let apply_delta_pruning = game_lateness(board) < 50;

    for mov in moves {

        if apply_delta_pruning {
            const PIECE_VALUES: [i32; 6] = [
                100, // Pawn
                300, // Knight
                320, // Bishop
                400, // Rook
                800, // Queen
                100000 // King
            ];
            const SAFETY_MARGIN: i32 = 200;
            let target_sq = mov.to_simple().to;
            if let Some((piece_type, _side)) = board.get_square(target_sq) {
                if val + PIECE_VALUES[piece_type as usize] + SAFETY_MARGIN < alpha {
                    continue;
                }
            }
        }

        let undo = board.apply(mov);
        sc.last_move = Some(mov);

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

        if sc.stopping {
            return alpha
        }

        if val >= beta {
            return beta;
        }
        if val > alpha {
            alpha = val;
        }
    }
    return alpha;
}


impl SearchControl {
    pub fn new_perft(board: &Board, stop_channel: mpsc::Receiver<SearchMessage>, depth: i32) -> Self {
        SearchControl {
            nodes: 0,
            board: board.clone(),
            hash: Arc::new(RwLock::new(Cache::new(0))),
            initial_depth: depth,
            killer_moves: Vec::new(),
            last_move: None,
            countermoves: Arc::new(Mutex::new(CountermoveTable::new())),
            halfmove_age: board.ply_number() as _,
            stop_channel,
            stopping: false,
            search_started: Instant::now(),
            movetime: None,
            remaining_time: None,
            reductions_allowed: false
        }
    }

    pub fn perft(&mut self, depth: i32) -> bool {
        let board = &mut self.board;
        let moves = generate_legal_moves(board, board.turn, false);

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


        for mov in moves {
            let nodes_before = self.nodes;
            let undo = self.board.apply(mov);
            let do_return = self.perft(depth - 1);
            self.board.undo_move(undo);

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

            if do_return {
                return true;
            }
        }

        return false;
    }

}


pub struct CountermoveTable {
    table: Box<[[[[i16; 12]; 64]; 12]]>,
}


impl CountermoveTable {

    pub fn new() -> Self {
        //CountermoveTable { table: Box::new([[[[0; 12]; 64]; 12]; 64]) }
        CountermoveTable { table: vec![[[[0; 12]; 64]; 12]; 64].into_boxed_slice() }
    }

    pub fn get_score(&self, side: Side, last_move: Move, this_move: Move) -> i16 {
        let side_offs = if side == BLACK { 6 } else { 0 };
        self.table
            [last_move.to() as usize]
            [last_move.piece_type() as usize + side_offs]
            [this_move.to() as usize]
            [this_move.piece_type() as usize + side_offs]
    }

    pub fn update_score(&mut self, side: Side, last_move: Move, this_move: Move, increase: i16) {
        let side_offs = if side == BLACK { 6 } else { 0 };
        let entry = &mut self.table
            [last_move.to() as usize]
            [last_move.piece_type() as usize + side_offs]
            [this_move.to() as usize]
            [this_move.piece_type() as usize + side_offs];
        *entry = entry.saturating_add(increase);
    }
}


#[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 board = Board::from_fen_str(position).unwrap();
            for (j, &p_res) in perft_results[i].iter().enumerate() {
                let depth = j + 1;
                let (_, stop_check) = mpsc::channel::<SearchMessage>();
                let mut pc = SearchControl::new_perft(&board, stop_check, depth as _);
                pc.perft(depth as _);
                assert_eq!(pc.nodes, p_res);
            }
        }
    }
}