From b3d48c9924a2502ba7e93bafb0a8afcd096bec76 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sun, 11 Aug 2019 12:28:38 +0200 Subject: Replaced hashmaps with deterministic hashmaps I'm not worried about ddos attacks here, and this also has better perf for small keys. --- Cargo.lock | 7 +++++++ Cargo.toml | 1 + src/bin/explore-config.rs | 9 +++++++-- src/strategy/minimax.rs | 29 ++++++++++++++++++++--------- tests/strategy.rs | 27 +++++++++++++++++++++++++++ 5 files changed, 62 insertions(+), 11 deletions(-) create mode 100644 tests/strategy.rs diff --git a/Cargo.lock b/Cargo.lock index 8a785a3..15bad26 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -8,6 +8,11 @@ dependencies = [ "nodrop 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "fnv" +version = "1.0.6" +source = "registry+https://github.com/rust-lang/crates.io-index" + [[package]] name = "itoa" version = "0.4.3" @@ -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; 2], + player_score_sums: [FnvHashMap; 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); +} -- cgit v1.2.3