From 97880f6a368085e9a409f1fb0030791a4a65005c Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sat, 12 May 2018 17:39:06 +0200 Subject: Initial stab at monte carlo implementation Doesn't seem to be working quite right... just sits there accumulating energy. --- src/engine/command.rs | 7 +++ src/engine/mod.rs | 66 ++++++++++++++++------- src/json.rs | 8 +-- src/main.rs | 7 +-- src/strategy/mod.rs | 1 + src/strategy/monte_carlo.rs | 124 ++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 186 insertions(+), 27 deletions(-) create mode 100644 src/strategy/monte_carlo.rs (limited to 'src') diff --git a/src/engine/command.rs b/src/engine/command.rs index b5cf528..c2edb81 100644 --- a/src/engine/command.rs +++ b/src/engine/command.rs @@ -23,3 +23,10 @@ pub enum BuildingType { Attack = 1, Energy = 2, } + +impl BuildingType { + pub fn all() -> [BuildingType; 3] { + use self::BuildingType::*; + [Defence, Attack, Energy] + } +} diff --git a/src/engine/mod.rs b/src/engine/mod.rs index 11dd5ed..a1a85ce 100644 --- a/src/engine/mod.rs +++ b/src/engine/mod.rs @@ -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, 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 { + (0..settings.size.y) + .flat_map(|y| (settings.size.x/2..settings.size.x).map(|x| Point::new(x, y)).collect::>()) + .filter(|&p| !self.opponent_buildings.iter().any(|b| b.pos == p)) + .collect() + } + + pub fn player_affordable_buildings(&self, settings: &GameSettings) -> Vec { + GameState::affordable_buildings(self.player.energy, settings) + } + + pub fn opponent_affordable_buildings(&self, settings: &GameSettings) -> Vec { + GameState::affordable_buildings(self.opponent.energy, settings) + } + + fn affordable_buildings(energy: u16, settings: &GameSettings) -> Vec { + BuildingType::all().iter() + .filter(|&b| settings.building_settings(*b).price <= energy) + .cloned() + .collect() + } } impl GameStatus { diff --git a/src/json.rs b/src/json.rs index 541b479..10c3ab8 100644 --- a/src/json.rs +++ b/src/json.rs @@ -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(), } } diff --git a/src/main.rs b/src/main.rs index 7b3a62c..e5dc3aa 100644 --- a/src/main.rs +++ b/src/main.rs @@ -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 > { 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); } } diff --git a/src/strategy/mod.rs b/src/strategy/mod.rs index ce8e751..9630c48 100644 --- a/src/strategy/mod.rs +++ b/src/strategy/mod.rs @@ -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 index 0000000..8fbf0a3 --- /dev/null +++ b/src/strategy/monte_carlo.rs @@ -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(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(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(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 { + enumerate_player_commands(settings, state).iter() + .map(|&c| CommandScore::new(c)) + .collect() + } +} + +fn enumerate_player_commands(settings: &GameSettings, state: &GameState) -> Vec { + 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::>() + ); + let other_commands = vec!(Command::Nothing); + + build_commands.chain(other_commands) + .collect() +} + +fn enumerate_opponent_commands(settings: &GameSettings, state: &GameState) -> Vec { + 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::>() + ); + let other_commands = vec!(Command::Nothing); + + build_commands.chain(other_commands) + .collect() +} -- cgit v1.2.3