Moved solver in a struct

3 files changed, 99 insertions, 76 deletions

diff --git a/src/main.rs b/src/main.rs
index 5dde7cb..4a07373 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -3,15 +3,17 @@ use std::io::prelude::*;
 use std::time::{Instant,Duration};
 
 pub mod position;
-pub mod solve;
+pub mod solver;
 
 use position::Position;
-use solve::{solve, solve_weak};
+use solver::Solver;
 
 
 fn main() {
     let mut total_time = Duration::new(0, 0);
     let mut total_solve = 0;
+    let mut total_visited = 0;
+    let mut solver = Solver::new();
 
     for result in  io::stdin().lock().lines() {
         let line = result.unwrap();
@@ -31,19 +33,21 @@ fn main() {
             Ok(pos) => {
                 print!("{:?}", pos);
                 let begin = Instant::now();
-                let score = solve(pos);
+                let score = solver.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);
+                println!("{:03}: score: {:3}, time: {:?}, visited {}\n", total_solve, score, elapsed, solver.visited);
+                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;
+                total_visited += solver.visited;
+                solver.reset();
             }
             Err(msg) =>
                 eprintln!("wrong score format {:?}: {}", fields[1], msg),
         }
     }
-    println!("mean time {:?}", total_time / total_solve);
+    println!("mean time: {:?} | mean visited {}", total_time / total_solve, total_visited / total_solve as usize);
 }
diff --git a/src/solve.rs b/src/solve.rs
deleted file mode 100644
index 9561ff1..0000000
--- a/src/solve.rs
+++ /dev/null
@@ -1,67 +0,0 @@
-use std::collections::HashMap;
-
-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, -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 p.is_draw() {
-        return 0;
-    }
-    for x in 0..WIDTH {
-        if p.is_valid_play(x) && p.is_winning_play(x) {
-            return (((WIDTH * HEIGHT + 1) as i32) - (p.play_count as i32)) / 2;
-        }
-    }
-
-    let mut alpha = a;
-    let mut beta = b;
-
-    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;
-            }
-        }
-    }
-
-    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 > best {
-            best = 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(), best);
-    return best;
-}
-
diff --git a/src/solver.rs b/src/solver.rs
new file mode 100644
index 0000000..c83807b
--- /dev/null
+++ b/src/solver.rs
@@ -0,0 +1,86 @@
+use std::collections::HashMap;
+
+use crate::position::{Position, WIDTH, HEIGHT, MIN_SCORE};
+
+
+const COLUMNS_ORDER: [u64; 7] = [3, 2, 4, 1, 5, 0, 6];
+
+type Cache = HashMap<u64, i32>;
+
+pub struct Solver {
+    pub visited: usize,
+    pub cache: Cache,
+}
+
+const CACHE_SIZE: usize = 1 << 20 + 1;
+
+impl Solver {
+    pub fn new() -> Solver {
+        Solver {
+            visited: 0,
+            cache: Cache::with_capacity(CACHE_SIZE),
+        }
+    }
+
+    pub fn solve(&mut self, p: Position) -> i32 {
+        self.solve_rec(p, -1000, 1000)
+    }
+
+    // the weak solver only tells if the position is a win/lose/draw
+    // it's faster but less precise
+    pub fn solve_weak(&mut self, p: Position) -> i32 {
+        self.solve_rec(p, -1, 1)
+    }
+
+    fn solve_rec(&mut self, p: Position, mut alpha: i32, mut beta: i32) -> i32 {
+        self.visited += 1;
+        if p.is_draw() {
+            return 0;
+        }
+        for x in 0..WIDTH {
+            if p.is_valid_play(x) && p.is_winning_play(x) {
+                return (((WIDTH * HEIGHT + 1) as i32) - (p.play_count as i32)) / 2;
+            }
+        }
+
+        if let Some(max_score) = self.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;
+                }
+            }
+        }
+
+        let mut best = alpha;
+        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 = -self.solve_rec(p.play(x), -beta, -alpha);
+            if score > best {
+                best = 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;
+                }
+            }
+        }
+        self.cache.insert(p.key(), best);
+        return best;
+    }
+
+    pub fn reset(&mut self) {
+        self.visited = 0;
+        self.cache.clear();
+    }
+}