diff options
| -rw-r--r-- | src/main.rs | 8 | ||||
| -rw-r--r-- | src/position.rs | 17 | ||||
| -rw-r--r-- | src/solve.rs | 61 |
3 files changed, 51 insertions, 35 deletions
diff --git a/src/main.rs b/src/main.rs index e77ce2b..5dde7cb 100644 --- a/src/main.rs +++ b/src/main.rs @@ -6,7 +6,7 @@ pub mod position; pub mod solve; use position::Position; -use solve::solve; +use solve::{solve, solve_weak}; fn main() { @@ -33,9 +33,13 @@ fn main() { let begin = Instant::now(); let score = solve(pos); let elapsed = begin.elapsed(); + println!("{:03}: score: {:3}, time: {:?}\n", total_solve, score, elapsed); + // if score != expected_score { + // eprintln!("{:03}: score: {:3} {:3}", total_solve, score, expected_score); + // } + // assert_eq!(score, expected_score); total_time += elapsed; total_solve += 1; - println!("score: {:3} {:3}, time: {:?}\n", score, expected_score, elapsed); } Err(msg) => eprintln!("wrong score format {:?}: {}", fields[1], msg), diff --git a/src/position.rs b/src/position.rs index 9ed617d..7fd65c2 100644 --- a/src/position.rs +++ b/src/position.rs @@ -1,6 +1,7 @@ pub const HEIGHT: u64 = 6; pub const WIDTH: u64 = 7; pub const FULL_HEIGHT: u64 = HEIGHT + 1; +pub const MIN_SCORE: i32 = -((WIDTH * HEIGHT) as i32) / 2 + 3; #[derive(Debug, Eq, PartialEq)] enum Cell { @@ -157,27 +158,27 @@ impl fmt::Debug for Position { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { use Cell::*; writeln!(f, "play_count: {}", self.play_count)?; - writeln!(f, "{:10}{:10}{:10}", "position", "mask", "player")?; + writeln!(f, "{:16}{:16}{:16}", "position", "mask", "player")?; for y in (0..FULL_HEIGHT).rev() { for x in 0..WIDTH { match self.at(y, x) { - Empty => write!(f, ".")?, - CurrentPlayer => write!(f, "x")?, - OtherPlayer => write!(f, "o")?, + Empty => write!(f, ". ")?, + CurrentPlayer => write!(f, "x ")?, + OtherPlayer => write!(f, "o ")?, } } write!(f, " ")?; for x in 0..WIDTH { match self.at(y, x) { - Empty => write!(f, ".")?, - CurrentPlayer | OtherPlayer => write!(f, "#")?, + Empty => write!(f, ". ")?, + CurrentPlayer | OtherPlayer => write!(f, "# ")?, } } write!(f, " ")?; for x in 0..WIDTH { match self.at(y, x) { - Empty | OtherPlayer => write!(f, ".")?, - CurrentPlayer => write!(f, "#")?, + Empty | OtherPlayer => write!(f, ". ")?, + CurrentPlayer => write!(f, "# ")?, } } write!(f, "\n")?; diff --git a/src/solve.rs b/src/solve.rs index b950ab6..9561ff1 100644 --- a/src/solve.rs +++ b/src/solve.rs @@ -1,18 +1,22 @@ use std::collections::HashMap; -use crate::position::{Position, WIDTH, HEIGHT}; +use crate::position::{Position, WIDTH, HEIGHT, MIN_SCORE}; const COLUMNS_ORDER: [u64; 7] = [3, 2, 4, 1, 5, 0, 6]; pub fn solve(p: Position) -> i32 { let mut cache = HashMap::with_capacity(30000); - solve_rec(p, -100000, 100000, &mut cache) + solve_rec(p, -1000, 1000, &mut cache) +} + +// the weak solver only tells if the position is a win/lose/draw +// it's faster but less precise +pub fn solve_weak(p: Position) -> i32 { + let mut cache = HashMap::with_capacity(30000); + solve_rec(p, -1, 1, &mut cache) } fn solve_rec(p: Position, a: i32, b: i32, cache: &mut HashMap<u64, i32>) -> i32 { - if let Some(score) = cache.get(&p.key()) { - return *score; - } if p.is_draw() { return 0; } @@ -25,32 +29,39 @@ fn solve_rec(p: Position, a: i32, b: i32, cache: &mut HashMap<u64, i32>) -> i32 let mut alpha = a; let mut beta = b; - let max = (((WIDTH * HEIGHT + 1) as i32) - (p.play_count as i32)) / 2; - - if beta > max { - beta = max; - if alpha >= beta { - return beta; + if let Some(max_score) = cache.get(&p.key()) { + // can't return max_score directly + // because the alpha-beta context in the cache may be + // different than the current alpha-beta + if beta > *max_score { + beta = *max_score; + if alpha >= beta { + return beta; + } } } - for x_unordered in 0..(WIDTH as usize) { - let x = COLUMNS_ORDER[x_unordered]; - if !p.is_valid_play(x) { - continue - } - + let mut best = MIN_SCORE; + for x in (0..(WIDTH as usize)) + .map(|x| COLUMNS_ORDER[x]) + .filter(|x| p.is_valid_play(*x)) + { + // using negamax, variante of minimax where: + // max(player1, player2) == -min(-player1, -player2) let score = -solve_rec(p.play(x), -beta, -alpha, cache); - - if score >= beta { - return score; + if score > best { + best = score; } - - if score > alpha { - alpha = score; + // reduce alpha-beta range if found better score + if best > alpha { + alpha = best; + } + // impossible alpha-beta range reached (alpha is supposed to be < to beta) + if alpha >= beta { + return score; } } - cache.insert(p.key(), alpha); - return alpha; + cache.insert(p.key(), best); + return best; } |