Added option for discarding poor performing moves early
authorJustin Worthe <justin@worthe-it.co.za>
Mon, 23 Jul 2018 20:32:10 +0000 (22:32 +0200)
committerJustin Worthe <justin@worthe-it.co.za>
Mon, 23 Jul 2018 20:32:10 +0000 (22:32 +0200)
Cargo.toml
src/bin/depth-first-search.rs
src/strategy/monte_carlo.rs

index d95ae94..23e18b5 100644 (file)
@@ -20,6 +20,7 @@ single-threaded = []
 energy-cutoff = []
 reduced-time = []
 extended-time = []
+discard-poor-performers = []
 
 default = ["energy-cutoff"]
 
index c2b82de..c04061d 100644 (file)
@@ -5,7 +5,6 @@ use time::PreciseTime;
 use zombot::*;
 use zombot::engine::*;
 use zombot::engine::settings::*;
-use zombot::engine::constants::*;
 use zombot::engine::command::*;
 
 const STATE_PATH: &str = "tests/state0.json";
@@ -87,6 +86,9 @@ fn walk_states<GS: GameState>(settings: &GameSettings, state: &GS, depth: u32) {
     if status == GameStatus::Continue {
         walk_states(settings, &after_move, depth+1);
     }
+    if depth < 10 {
+        print!(".");
+    }
 }
 
 fn valid_buildings(settings: &GameSettings, player: &Player, has_max_teslas: bool) -> Vec<BuildingType> {
index 3dc94eb..d735074 100644 (file)
@@ -17,28 +17,8 @@ use rayon::prelude::*;
 
 pub fn choose_move<GS: GameState>(settings: &GameSettings, state: &GS, start_time: &PreciseTime, max_time: Duration) -> Command {
     let mut command_scores = CommandScore::init_command_scores(settings, state);
-    
-    loop {
-        #[cfg(feature = "single-threaded")]
-        {
-            command_scores.iter_mut()
-                .for_each(|score| {
-                    let mut rng = XorShiftRng::from_seed(score.next_seed);
-                    simulate_to_endstate(score, settings, state, &mut rng);
-                });
-        }
-        #[cfg(not(feature = "single-threaded"))]
-        {
-            command_scores.par_iter_mut()
-                .for_each(|score| {
-                    let mut rng = XorShiftRng::from_seed(score.next_seed);
-                    simulate_to_endstate(score, settings, state, &mut rng);
-                });
-        }
-        if start_time.to(PreciseTime::now()) > max_time {
-            break;
-        }
-    }
+
+    simulate_options_to_timeout(&mut command_scores, settings, state, start_time, max_time);
 
     let command = command_scores.iter().max_by_key(|&c| c.win_ratio());
 
@@ -54,6 +34,50 @@ pub fn choose_move<GS: GameState>(settings: &GameSettings, state: &GS, start_tim
     }
 }
 
+#[cfg(not(feature = "discard-poor-performers"))]
+fn simulate_options_to_timeout<GS: GameState>(command_scores: &mut Vec<CommandScore>, settings: &GameSettings, state: &GS, start_time: &PreciseTime, max_time: Duration) {
+    loop {
+        simulate_all_options_once(command_scores, settings, state);
+        if start_time.to(PreciseTime::now()) > max_time {
+            break;
+        }
+    }
+}
+
+#[cfg(feature = "discard-poor-performers")]
+fn simulate_options_to_timeout<GS: GameState>(command_scores: &mut Vec<CommandScore>, settings: &GameSettings, state: &GS, start_time: &PreciseTime, max_time: Duration) {
+    let maxes = [max_time / 4, max_time / 2, max_time * 3 / 4, max_time];
+    for &max in maxes.iter() {
+        loop {
+            simulate_all_options_once(command_scores, settings, state);
+            if start_time.to(PreciseTime::now()) > max {
+                break;
+            }
+        }
+        command_scores.sort_unstable_by_key(|c| -c.win_ratio());
+        let new_length = command_scores.len()/2;
+        command_scores.truncate(new_length);
+    }
+}
+
+#[cfg(feature = "single-threaded")]
+fn simulate_all_options_once<GS: GameState>(command_scores: &mut[CommandScore], settings: &GameSettings, state: &GS) {
+    command_scores.iter_mut()
+        .for_each(|score| {
+            let mut rng = XorShiftRng::from_seed(score.next_seed);
+            simulate_to_endstate(score, settings, state, &mut rng);
+        });
+}
+
+#[cfg(not(feature = "single-threaded"))]
+fn simulate_all_options_once<GS: GameState>(command_scores: &mut[CommandScore], settings: &GameSettings, state: &GS) {
+    command_scores.par_iter_mut()
+        .for_each(|score| {
+            let mut rng = XorShiftRng::from_seed(score.next_seed);
+            simulate_to_endstate(score, settings, state, &mut rng);
+        });
+}
+
 fn simulate_to_endstate<R: Rng, GS: GameState>(command_score: &mut CommandScore, settings: &GameSettings, state: &GS, rng: &mut R) {
     let mut state_mut = state.clone();