Initial stab at monte carlo implementation
authorJustin Worthe <justin@worthe-it.co.za>
Sat, 12 May 2018 15:39:06 +0000 (17:39 +0200)
committerJustin Worthe <justin@worthe-it.co.za>
Sat, 12 May 2018 15:39:06 +0000 (17:39 +0200)
Doesn't seem to be working quite right... just sits there accumulating
energy.

src/engine/command.rs
src/engine/mod.rs
src/json.rs
src/main.rs
src/strategy/mod.rs
src/strategy/monte_carlo.rs [new file with mode: 0644]

index b5cf528..c2edb81 100644 (file)
@@ -23,3 +23,10 @@ pub enum BuildingType {
     Attack = 1,
     Energy = 2,
 }
+
+impl BuildingType {
+    pub fn all() -> [BuildingType; 3] {
+        use self::BuildingType::*;
+        [Defence, Attack, Energy]
+    }
+}
index 11dd5ed..a1a85ce 100644 (file)
@@ -2,7 +2,7 @@ pub mod command;
 pub mod geometry;
 pub mod settings;
 
-use self::command::Command;
+use self::command::{Command, BuildingType};
 use self::geometry::Point;
 use self::settings::{GameSettings, BuildingSettings};
 
@@ -56,35 +56,39 @@ pub struct Missile {
 
 impl GameState {
     pub fn simulate(&self, settings: &GameSettings, player_command: Command, opponent_command: Command) -> GameState {
+        let mut state = self.clone();
+        state.simulate_mut(settings, player_command, opponent_command);
+        state
+    }
+
+    pub fn simulate_mut(&mut self, settings: &GameSettings, player_command: Command, opponent_command: Command) {
         if self.status.is_complete() {
-            return self.clone();
+            return;
         }
-        
-        let mut state = self.clone();
-        let player_valid = GameState::perform_command(&mut state.player_buildings, &mut state.player, settings, player_command, &settings.size);
-        let opponent_valid = GameState::perform_command(&mut state.opponent_buildings, &mut state.opponent, settings, opponent_command, &settings.size);
+
+        let player_valid = GameState::perform_command(&mut self.player_buildings, &mut self.player, settings, player_command, &settings.size);
+        let opponent_valid = GameState::perform_command(&mut self.opponent_buildings, &mut self.opponent, settings, opponent_command, &settings.size);
 
         if !player_valid || !opponent_valid {
-            state.status = GameStatus::InvalidMove;
-            return state;
+            self.status = GameStatus::InvalidMove;
+            return;
         }
 
-        GameState::update_construction(&mut state.player_buildings);
-        GameState::update_construction(&mut state.opponent_buildings);
+        GameState::update_construction(&mut self.player_buildings);
+        GameState::update_construction(&mut self.opponent_buildings);
 
-        GameState::add_missiles(&mut state.player_buildings, &mut state.player_missiles);
-        GameState::add_missiles(&mut state.opponent_buildings, &mut state.opponent_missiles);
+        GameState::add_missiles(&mut self.player_buildings, &mut self.player_missiles);
+        GameState::add_missiles(&mut self.opponent_buildings, &mut self.opponent_missiles);
 
-        GameState::move_missiles(&mut state.player_missiles, |p| p.move_right(&settings.size),
-                                 &mut state.opponent_buildings, &mut state.opponent);
-        GameState::move_missiles(&mut state.opponent_missiles, |p| p.move_left(),
-                                 &mut state.player_buildings, &mut state.player);
+        GameState::move_missiles(&mut self.player_missiles, |p| p.move_right(&settings.size),
+                                 &mut self.opponent_buildings, &mut self.opponent);
+        GameState::move_missiles(&mut self.opponent_missiles, |p| p.move_left(),
+                                 &mut self.player_buildings, &mut self.player);
 
-        GameState::add_energy(&mut state.player, settings, &state.player_buildings);
-        GameState::add_energy(&mut state.opponent, settings, &state.opponent_buildings);
+        GameState::add_energy(&mut self.player, settings, &self.player_buildings);
+        GameState::add_energy(&mut self.opponent, settings, &self.opponent_buildings);
 
-        GameState::update_status(&mut state);
-        state
+        GameState::update_status(self);
     }
 
     fn perform_command(buildings: &mut Vec<Building>, player: &mut Player, settings: &GameSettings, command: Command, size: &Point) -> bool {
@@ -186,6 +190,28 @@ impl GameState {
             .filter(|&p| !self.player_buildings.iter().any(|b| b.pos == p))
             .collect()
     }
+
+    pub fn unoccupied_opponent_cells(&self, settings: &GameSettings) -> Vec<Point> {
+        (0..settings.size.y)
+            .flat_map(|y| (settings.size.x/2..settings.size.x).map(|x| Point::new(x, y)).collect::<Vec<_>>())
+            .filter(|&p| !self.opponent_buildings.iter().any(|b| b.pos == p))
+            .collect()
+    }
+
+    pub fn player_affordable_buildings(&self, settings: &GameSettings) -> Vec<BuildingType> {
+        GameState::affordable_buildings(self.player.energy, settings)
+    }
+
+    pub fn opponent_affordable_buildings(&self, settings: &GameSettings) -> Vec<BuildingType> {
+        GameState::affordable_buildings(self.opponent.energy, settings)
+    }
+
+    fn affordable_buildings(energy: u16, settings: &GameSettings) -> Vec<BuildingType> {
+        BuildingType::all().iter()
+            .filter(|&b| settings.building_settings(*b).price <= energy)
+            .cloned()
+            .collect()
+    }
 }
 
 impl GameStatus {
index 541b479..10c3ab8 100644 (file)
@@ -30,7 +30,7 @@ struct GameDetails {
     map_width: u8,
     map_height: u8,
     round_income_energy: u16,
-    building_stats: BuildingStats
+    buildings_stats: BuildingStats
 }
 
 #[derive(Deserialize)]
@@ -110,9 +110,9 @@ impl State {
         engine::settings::GameSettings {
             size: engine::geometry::Point::new(self.game_details.map_width, self.game_details.map_height),
             energy_income: self.game_details.round_income_energy,
-            energy: self.game_details.building_stats.energy.to_engine(),
-            defence: self.game_details.building_stats.defense.to_engine(),
-            attack: self.game_details.building_stats.attack.to_engine(),
+            energy: self.game_details.buildings_stats.energy.to_engine(),
+            defence: self.game_details.buildings_stats.defense.to_engine(),
+            attack: self.game_details.buildings_stats.attack.to_engine(),
         }
     }
     
index 7b3a62c..e5dc3aa 100644 (file)
@@ -13,7 +13,7 @@ use std::io::prelude::*;
 use std::process;
 
 fn choose_move(settings: &engine::settings::GameSettings, state: &engine::GameState) -> Command {
-    strategy::sample::choose_move(settings, state)
+    strategy::monte_carlo::choose_move(settings, state)
 }
 
 
@@ -25,10 +25,11 @@ fn write_command(filename: &str, command: Command) -> Result<(), Box<Error> > {
 
 
 fn main() {
+    println!("Reading in state.json file");
     let (settings, state) = match json::read_state_from_file(STATE_PATH) {
         Ok(ok) => ok,
         Err(error) => {
-            eprintln!("Error while parsing JSON file: {}", error);
+            println!("Error while parsing JSON file: {}", error);
             process::exit(1);
         }
     };
@@ -37,7 +38,7 @@ fn main() {
     match write_command(COMMAND_PATH, command) {
         Ok(()) => {}
         Err(error) => {
-            eprintln!("Error while writing command file: {}", error);
+            println!("Error while writing command file: {}", error);
             process::exit(1);
         }
     }
index ce8e751..9630c48 100644 (file)
@@ -1 +1,2 @@
 pub mod sample;
+pub mod monte_carlo;
diff --git a/src/strategy/monte_carlo.rs b/src/strategy/monte_carlo.rs
new file mode 100644 (file)
index 0000000..8fbf0a3
--- /dev/null
@@ -0,0 +1,124 @@
+use engine::settings::GameSettings;
+use engine::command::*;
+use engine::{GameState, GameStatus};
+
+use rand::{thread_rng, Rng};
+
+const MAX_MOVES: u16 = 400;
+
+// TODO Round start time here
+pub fn choose_move(settings: &GameSettings, state: &GameState) -> Command {
+    println!("Using MONTE_CARLO strategy");
+    
+    let mut rng = thread_rng();
+    let mut command_scores = CommandScore::init_command_scores(settings, state);
+
+    // TODO Repeat this until time is out
+    for _ in 0..1000 {
+        for mut score in &mut command_scores {
+            if simulate_to_endstate(settings, state, score.command, &mut rng) {
+                score.add_victory();
+            } else {
+                score.add_defeat();
+            }
+        }
+    }
+
+    let command = command_scores.iter().max_by_key(|&c| c.win_ratio());
+    
+    match command {
+        Some(ref command) => command.command,
+        _ => Command::Nothing
+    }
+}
+
+fn simulate_to_endstate<R: Rng>(settings: &GameSettings, state: &GameState, command: Command, rng: &mut R) -> bool {
+    let opponent_first = random_opponent_move(settings, state, rng);
+    let mut state_mut = state.simulate(settings, command, opponent_first);
+    
+    for _ in 0..MAX_MOVES {
+        if state_mut.status != GameStatus::Continue {
+            break;
+        }
+
+        let player_command = random_player_move(settings, state, rng);
+        let opponent_command = random_opponent_move(settings, state, rng);
+        state_mut.simulate_mut(settings, player_command, opponent_command);
+        
+    }
+    
+    state_mut.status == GameStatus::PlayerWon
+}
+
+fn random_player_move<R: Rng>(settings: &GameSettings, state: &GameState, rng: &mut R) -> Command {
+    let all_commands = enumerate_player_commands(settings, state);
+    rng.choose(&all_commands).cloned().unwrap_or(Command::Nothing)
+}
+fn random_opponent_move<R: Rng>(settings: &GameSettings, state: &GameState, rng: &mut R) -> Command {
+    let all_commands = enumerate_opponent_commands(settings, state);
+    rng.choose(&all_commands).cloned().unwrap_or(Command::Nothing)
+}
+
+
+struct CommandScore {
+    command: Command,
+    victories: u32,
+    attempts: u32
+}
+
+impl CommandScore {
+    fn new(command: Command) -> CommandScore {
+        CommandScore {
+            command: command,
+            victories: 0,
+            attempts: 0
+        }
+    }
+
+    fn add_victory(&mut self) {
+        self.victories += 1;
+        self.attempts += 1;
+    }
+
+    fn add_defeat(&mut self) {
+        self.attempts += 1;
+    }
+
+    fn win_ratio(&self) -> u32 {
+        self.victories * 1000 / self.attempts
+    }
+    
+    fn init_command_scores(settings: &GameSettings, state: &GameState) -> Vec<CommandScore> {
+        enumerate_player_commands(settings, state).iter()
+            .map(|&c| CommandScore::new(c))
+            .collect()
+    }
+}
+
+fn enumerate_player_commands(settings: &GameSettings, state: &GameState) -> Vec<Command> {
+    let all_positions = state.unoccupied_player_cells(settings);
+    let all_buildings = state.player_affordable_buildings(settings);
+    
+    let build_commands = all_positions.iter()
+        .flat_map(|&pos| all_buildings.iter()
+                  .map(|&building| Command::Build(pos, building)).collect::<Vec<_>>()
+        );
+    let other_commands = vec!(Command::Nothing);
+
+    build_commands.chain(other_commands)
+        .collect()
+}
+
+fn enumerate_opponent_commands(settings: &GameSettings, state: &GameState) -> Vec<Command> {
+    let all_positions = state.unoccupied_opponent_cells(settings);
+    let all_buildings = state.opponent_affordable_buildings(settings);
+    
+    let build_commands = all_positions.iter()
+        .flat_map(|&pos| all_buildings.iter()
+                  .map(|&building| Command::Build(pos, building)).collect::<Vec<_>>()
+        );
+    let other_commands = vec!(Command::Nothing);
+
+    build_commands.chain(other_commands)
+        .collect()
+}