diff options
author | eug-vs <eugene@eug-vs.xyz> | 2023-09-04 08:18:00 +0300 |
---|---|---|
committer | eug-vs <eugene@eug-vs.xyz> | 2023-09-04 08:18:00 +0300 |
commit | 870577620aebaa3011ca42c222a338d0eb0a07e0 (patch) | |
tree | 5b9785dab00ce39ed6a9bc47db36dc6086f6bf8f | |
parent | b32745208e8565ce2c9263c77bd5071441d7bd79 (diff) | |
download | chessnost-870577620aebaa3011ca42c222a338d0eb0a07e0.tar.gz |
feat: use MTD(f) instead of aspiration windows
-rw-r--r-- | src/grossmeister/search.rs | 58 |
1 files changed, 29 insertions, 29 deletions
diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs index 378349c..d0fddbb 100644 --- a/src/grossmeister/search.rs +++ b/src/grossmeister/search.rs @@ -246,43 +246,46 @@ impl Grossmeister { pv } + /// Memory-enhanced Test Driver + /// Given a guess score (from previous iteration), use it for series of small-window searches + fn mtdf(&mut self, score_guess: Score, depth: u8) -> Score { + let window_size = 1.00; + let mut score = score_guess; + let mut lowerbound = -INFINITY; + let mut upperbound = INFINITY; + + while lowerbound < upperbound { + let beta = score + if score == lowerbound { + window_size + } else { + 0.0 + }; + + score = self.negamax_search(beta - window_size, beta, depth, 0); + + if score < beta { + upperbound = score + } else { + lowerbound = score + } + } + + score + } + pub fn iterative_deepening(&mut self, max_depth: u8) -> (Score, Vec<Move>) { let mut best_score = 0.0; let mut pv = Vec::new(); - - let mut depth = 1; - let mut alpha = -INFINITY; - let mut beta = INFINITY; - let window_size = 0.25; - let mut gradual_widening_counter = 0; + let mut depth = 0; while depth <= max_depth { - if self.debug { - println!("info string window {:?}", (alpha, beta)); - } - - let score = self.negamax_search(alpha, beta, depth, 0); + let score = self.mtdf(best_score, depth); if self.should_halt.load(std::sync::atomic::Ordering::SeqCst) { println!("info string halting search"); break; } - if score <= alpha { // Alpha-cutoff - gradual_widening_counter += 1; - beta = alpha + window_size * 0.1; - alpha = score - window_size * 2.0f32.powi(gradual_widening_counter); - println!("info depth {} score upperbound {:.0}", depth, beta * 100.0); - continue; - } - if score >= beta { // Beta-cutoff - gradual_widening_counter += 1; - alpha = beta - window_size * 0.1; - beta = score + window_size * 2.0f32.powi(gradual_widening_counter); - println!("info depth {} score lowerbound {:.0}", depth, alpha * 100.0); - continue; - } - best_score = score; pv = self.reconstruct_pv(depth); @@ -305,9 +308,6 @@ impl Grossmeister { println!(); depth += 1; - gradual_widening_counter = 0; - alpha = score - window_size; - beta = score + window_size; // If our score is mate in N, we break at depth N if depth as Score >= SCORE_MATE - score.abs() { |