Replaced hashmaps with deterministic hashmaps

I'm not worried about ddos attacks here, and this also has better perf
for small keys.

5 files changed, 62 insertions, 11 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 8a785a3..15bad26 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -9,6 +9,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "fnv"
+version = "1.0.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "itoa"
 version = "0.4.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -87,6 +92,7 @@ name = "steam-powered-wyrm"
 version = "1.0.0"
 dependencies = [
  "arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)",
+ "fnv 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 1.0.90 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 1.0.39 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -139,6 +145,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [metadata]
 "checksum arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)" = "92c7fb76bc8826a8b33b4ee5bb07a247a81e76764ab4d55e8f73e3a4d8808c71"
+"checksum fnv 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "2fad85553e09a6f881f739c29f0b00b0f01357c743266d478b68951ce23285f3"
 "checksum itoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1306f3464951f30e30d12373d31c79fbd52d236e5e896fd92f96ec7babbbe60b"
 "checksum libc 0.2.51 (registry+https://github.com/rust-lang/crates.io-index)" = "bedcc7a809076656486ffe045abeeac163da1b558e963a31e29fbfbeba916917"
 "checksum nodrop 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)" = "2f9667ddcc6cc8a43afc9b7917599d7216aa09c463919ea32c59ed6cac8bc945"
diff --git a/Cargo.toml b/Cargo.toml
index 5192198..4e5f811 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -9,6 +9,7 @@ serde_json = "1.0.39"
 time = "0.1.42"
 num-traits = "0.2.6"
 arrayvec = "0.4.10"
+fnv = "1.0.6"
 
 [profile.release]
 debug = true
diff --git a/src/bin/explore-config.rs b/src/bin/explore-config.rs
index 2d880d9..33ff82b 100644
--- a/src/bin/explore-config.rs
+++ b/src/bin/explore-config.rs
@@ -29,6 +29,7 @@ fn main() {
                 choose_move_with_normalized_perf(&state, &config2, 1, depth),
             ];
             state.simulate(commands);
+            println!("Commands: {:?}", commands);
         }
 
         println!("{:?}", state.outcome);
@@ -36,7 +37,11 @@ fn main() {
             "Runtime: {}ms",
             start_time.to(PreciseTime::now()).num_milliseconds()
         );
-        println!("{}", state.players[0].health());
-        println!("{}", state.players[1].health());
+        println!(
+            "Health: {} - {}",
+            state.players[0].health(),
+            state.players[1].health()
+        );
+        println!("Round: {}", state.round);
     }
 }
diff --git a/src/strategy/minimax.rs b/src/strategy/minimax.rs
index b34d2f8..55abcec 100644
--- a/src/strategy/minimax.rs
+++ b/src/strategy/minimax.rs
@@ -2,8 +2,8 @@ use crate::command::{Action, Command};
 use crate::constants::*;
 use crate::game::{GameBoard, SimulationOutcome};
 
+use fnv::FnvHashMap;
 use std::cmp;
-use std::collections::HashMap;
 use std::ops::*;
 use time::{Duration, PreciseTime};
 
@@ -45,9 +45,9 @@ pub fn choose_move(
 ) -> Command {
     let mut root_node = Node {
         score_sum: ScoreSum::new(),
-        player_score_sums: [HashMap::new(), HashMap::new()],
+        player_score_sums: [FnvHashMap::default(), FnvHashMap::default()],
         unexplored: move_combos(state),
-        children: HashMap::new(),
+        children: FnvHashMap::default(),
     };
 
     while start_time.to(PreciseTime::now()) < max_time {
@@ -75,23 +75,33 @@ pub fn choose_move_with_normalized_perf(
 ) -> Command {
     let mut root_node = Node {
         score_sum: ScoreSum::new(),
-        player_score_sums: [HashMap::new(), HashMap::new()],
+        player_score_sums: [FnvHashMap::default(), FnvHashMap::default()],
         unexplored: move_combos(state),
-        children: HashMap::new(),
+        children: FnvHashMap::default(),
     };
 
     for _ in 0..iterations {
         let _ = expand_tree(&mut root_node, state.clone(), config);
     }
 
+    eprintln!("Number of simulations: {}", root_node.score_sum.visit_count);
+    for (command, score_sum) in &root_node.player_score_sums[player_index] {
+        eprintln!(
+            "{} = {} ({} visits)",
+            command,
+            score_sum.avg().val,
+            score_sum.visit_count
+        );
+    }
+
     best_player_move(&root_node, player_index)
 }
 
 pub struct Node {
     score_sum: ScoreSum,
-    player_score_sums: [HashMap<Command, ScoreSum>; 2],
+    player_score_sums: [FnvHashMap<Command, ScoreSum>; 2],
     unexplored: Vec<[Command; 2]>,
-    children: HashMap<[Command; 2], Node>,
+    children: FnvHashMap<[Command; 2], Node>,
 }
 
 #[derive(Clone, Copy, Debug, PartialEq, PartialOrd)]
@@ -177,9 +187,9 @@ fn expand_tree(node: &mut Node, mut state: GameBoard, config: &ScoreConfig) -> S
 
         let new_node = Node {
             score_sum: ScoreSum::with_initial(score),
-            player_score_sums: [HashMap::new(), HashMap::new()],
+            player_score_sums: [FnvHashMap::default(), FnvHashMap::default()],
             unexplored,
-            children: HashMap::new(),
+            children: FnvHashMap::default(),
         };
         node.children.insert(commands, new_node);
         update(node, commands, score);
@@ -243,6 +253,7 @@ fn score(state: &GameBoard, config: &ScoreConfig) -> Score {
     let snowballs = state.players[0].snowballs() as f32 - state.players[1].snowballs() as f32;
     let bombs = state.players[0].bombs() as f32 - state.players[1].bombs() as f32;
 
+    // TODO: None of these attributes give any signal early on.
     // TODO: Try adding new features here. Something about board position?
     Score {
         val: max_health * config.max_health_weight
diff --git a/tests/strategy.rs b/tests/strategy.rs
new file mode 100644
index 0000000..7088099
--- /dev/null
+++ b/tests/strategy.rs
@@ -0,0 +1,27 @@
+use std::path::Path;
+
+use steam_powered_wyrm::game;
+use steam_powered_wyrm::json;
+use steam_powered_wyrm::strategy::{choose_move_with_normalized_perf, ScoreConfig};
+
+#[test]
+fn strategy_is_implemented_symetrically() {
+    let state = game::GameBoard::new(
+        json::read_state_from_json_file(&Path::new(&format!("./tests/example-state.json")))
+            .unwrap(),
+    );
+    let depth = 100;
+
+    let config = ScoreConfig::default();
+    let flipped_state = {
+        let mut flipped_state = state.clone();
+        flipped_state.players[0] = state.players[1].clone();
+        flipped_state.players[1] = state.players[0].clone();
+        flipped_state
+    };
+
+    let position_one_move = choose_move_with_normalized_perf(&state, &config, 0, depth);
+    let position_two_move = choose_move_with_normalized_perf(&flipped_state, &config, 1, depth);
+
+    assert_eq!(position_one_move, position_two_move);
+}