Updated HashMap to FnvHashMap (slightly faster with small key), Added null window searchHEADmaster

3 files changed, 28 insertions, 5 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 127371b..1a635b1 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,3 +3,12 @@
 [[package]]
 name = "connect4"
 version = "0.1.0"
+dependencies = [
+ "fnv",
+]
+
+[[package]]
+name = "fnv"
+version = "1.0.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
diff --git a/Cargo.toml b/Cargo.toml
index a569228..01fe881 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,3 +7,4 @@ edition = "2018"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
+fnv = "1.0.7"
diff --git a/src/solver.rs b/src/solver.rs
index c83807b..41f6dde 100644
--- a/src/solver.rs
+++ b/src/solver.rs
@@ -1,29 +1,42 @@
-use std::collections::HashMap;
+use fnv::FnvHashMap;  // better hashing function performance on small key (e.g u64)
 
 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>;
+type Cache = FnvHashMap<u64, i32>;
 
 pub struct Solver {
     pub visited: usize,
     pub cache: Cache,
 }
 
-const CACHE_SIZE: usize = 1 << 20 + 1;
+const CACHE_SIZE: usize = 1 << 10 + 1;
 
 impl Solver {
     pub fn new() -> Solver {
         Solver {
             visited: 0,
-            cache: Cache::with_capacity(CACHE_SIZE),
+            cache: Cache::with_capacity_and_hasher(CACHE_SIZE, Default::default()),
         }
     }
 
     pub fn solve(&mut self, p: Position) -> i32 {
-        self.solve_rec(p, -1000, 1000)
+        let mut min = -((WIDTH * HEIGHT - p.play_count) as i32) / 2;
+        let mut max = ((WIDTH * HEIGHT + 1 - p.play_count)) as i32 / 2;
+
+        while min < max {
+            let mut mid = min + (max - min) / 2;
+
+            if      mid <= 0 && min / 2 < mid { mid = min / 2; } // ?? (improve x2 but why?)
+            else if mid >= 0 && max / 2 > mid { mid = max / 2; } // ??
+
+            let score = self.solve_rec(p.clone(), mid, mid + 1);
+            if score > mid { min = score; }
+            else           { max = score; }
+        }
+        return min;
     }
 
     // the weak solver only tells if the position is a win/lose/draw