1 files changed, 86 insertions, 0 deletions
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();
+    }
+}