diff options
Diffstat (limited to '2018-tower-defence/src/strategy/monte_carlo.rs')
| -rw-r--r-- | 2018-tower-defence/src/strategy/monte_carlo.rs | 505 |
1 files changed, 505 insertions, 0 deletions
diff --git a/2018-tower-defence/src/strategy/monte_carlo.rs b/2018-tower-defence/src/strategy/monte_carlo.rs new file mode 100644 index 0000000..adbb911 --- /dev/null +++ b/2018-tower-defence/src/strategy/monte_carlo.rs @@ -0,0 +1,505 @@ +use engine::command::*; +use engine::status::GameStatus; +use engine::bitwise_engine::{Player, BitwiseGameState}; +use engine::constants::*; + +use std::fmt; + +use rand::{Rng, XorShiftRng, SeedableRng}; + +use arrayvec::ArrayVec; + +use time::{Duration, PreciseTime}; + +#[cfg(not(feature = "single-threaded"))] +use rayon::prelude::*; + +#[cfg(feature = "energy-cutoff")] pub const ENERGY_PRODUCTION_CUTOFF: u16 = 50; +#[cfg(feature = "energy-cutoff")] pub const ENERGY_STORAGE_CUTOFF: u16 = 120; + +pub fn choose_move(state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Command { + let mut command_scores = CommandScore::init_command_scores(state); + + let command = { + let best_command_score = simulate_options_to_timeout(&mut command_scores, state, start_time, max_time); + match best_command_score { + Some(best) if !best.starts_with_nothing => best.command, + _ => Command::Nothing + } + }; + + #[cfg(feature = "benchmarking")] + { + let total_iterations: u32 = command_scores.iter().map(|c| c.attempts).sum(); + println!("Iterations: {}", total_iterations); + } + #[cfg(feature = "debug-decisions")] + { + debug_print_choices("ENERGY", &command_scores, |score| match score.command { + Command::Build(p, BuildingType::Energy) => Some((p, score.win_ratio())), + _ => None + }); + debug_print_choices("ATTACK", &command_scores, |score| match score.command { + Command::Build(p, BuildingType::Attack) => Some((p, score.win_ratio())), + _ => None + }); + debug_print_choices("DEFENCE", &command_scores, |score| match score.command { + Command::Build(p, BuildingType::Defence) => Some((p, score.win_ratio())), + _ => None + }); + debug_print_choices("TESLA", &command_scores, |score| match score.command { + Command::Build(p, BuildingType::Tesla) => Some((p, score.win_ratio())), + _ => None + }); + + println!("NOTHING"); + println!("{}", command_scores.iter().find(|c| c.command == Command::Nothing).map(|s| s.win_ratio()).unwrap_or(0)); + println!(); + + println!("IRON CURTAIN"); + println!("{}", command_scores.iter().find(|c| c.command == Command::IronCurtain).map(|s| s.win_ratio()).unwrap_or(0)); + println!(); + } + + command +} + +#[cfg(feature = "debug-decisions")] +fn debug_print_choices<F: FnMut(&CommandScore) -> Option<(Point, i32)>>(label: &str, command_scores: &[CommandScore], extractor: F) { + println!("#+NAME: {}", label); + println!("#+PLOT: type:3d with:pm3d"); + let relevant_moves: Vec<(Point, i32)> = command_scores.iter() + .filter_map(extractor) + .collect(); + for y in 0..MAP_HEIGHT { + for x in 0..SINGLE_MAP_WIDTH { + let point = Point::new(x, y); + let score = relevant_moves.iter().find(|(p, _)| *p == point); + print!(" | {}", score.map(|(_,s)| s).cloned().unwrap_or(0)); + } + println!(" |"); + } + println!(); +} + +#[cfg(not(feature = "discard-poor-performers"))] +fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> { + loop { + simulate_all_options_once(command_scores, state); + if start_time.to(PreciseTime::now()) > max_time { + break; + } + } + command_scores.iter().max_by_key(|&c| c.win_ratio()) +} + +#[cfg(feature = "discard-poor-performers")] +fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> { + use std::cmp; + let min_options = cmp::min(command_scores.len(), 5); + + let maxes = [max_time / 3, max_time * 2 / 3, max_time]; + for (i, &max) in maxes.iter().enumerate() { + let new_length = cmp::max(min_options, command_scores.len() / (2usize.pow(i as u32))); + let active_scores = &mut command_scores[0..new_length]; + loop { + simulate_all_options_once(active_scores, state); + if start_time.to(PreciseTime::now()) > max { + break; + } + } + active_scores.sort_unstable_by_key(|c| -c.win_ratio()); + } + command_scores.first() +} + +#[cfg(feature = "single-threaded")] +fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) { + command_scores.iter_mut() + .for_each(|score| { + let mut rng = XorShiftRng::from_seed(score.next_seed); + simulate_to_endstate(score, state, &mut rng); + }); +} + +#[cfg(not(feature = "single-threaded"))] +fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) { + command_scores.par_iter_mut() + .for_each(|score| { + let mut rng = XorShiftRng::from_seed(score.next_seed); + simulate_to_endstate(score, state, &mut rng); + }); +} + +fn simulate_to_endstate<R: Rng>(command_score: &mut CommandScore, state: &BitwiseGameState, rng: &mut R) { + let mut state_mut = state.clone(); + + let mut status = GameStatus::Continue; //state_mut.simulate(command_score.command, opponent_first); + let mut first_move_made = false; + + for _ in 0..MAX_MOVES { + if status != GameStatus::Continue { + break; + } + + let player_command = if first_move_made { + random_move(&state_mut.player, &state_mut.opponent, rng) + } else { + let do_nothing = command_score.command.cant_build_yet(state_mut.player.energy); + first_move_made = !do_nothing; + if do_nothing { Command::Nothing } else { command_score.command } + }; + let opponent_command = random_move(&state_mut.opponent, &state_mut.player, rng); + status = state_mut.simulate(player_command, opponent_command); + } + + let mut next_seed: [u8;16] = [0; 16]; + rng.fill_bytes(&mut next_seed); + match status { + GameStatus::PlayerWon => command_score.add_victory(state_mut.player.count_towers() as i32 - state_mut.opponent.count_towers() as i32, next_seed), + GameStatus::OpponentWon => command_score.add_defeat(state_mut.opponent.count_towers() as i32 - state_mut.player.count_towers() as i32, next_seed), + GameStatus::Continue => command_score.add_stalemate(next_seed), + GameStatus::Draw => command_score.add_draw(next_seed) + } +} + +#[cfg(feature = "heuristic-random")] +pub fn random_move<R: Rng>(player: &Player, opponent: &Player, rng: &mut R) -> Command { + lazy_static! { + static ref MOVES: [Command; NUMBER_OF_POSSIBLE_MOVES] = { + let mut m = [Command::Nothing; NUMBER_OF_POSSIBLE_MOVES]; + m[1] = Command::IronCurtain; + let mut i = 2; + for b in &[BuildingType::Energy, BuildingType::Defence, BuildingType::Attack, BuildingType::Tesla] { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + m[i] = Command::Build(point, *b); + i += 1; + } + } + m + }; + } + + let mut cdf_other = [0; 2]; + let mut cdf_energy = [0; NUMBER_OF_MAP_POSITIONS]; + let mut cdf_defence = [0; NUMBER_OF_MAP_POSITIONS]; + let mut cdf_attack = [0; NUMBER_OF_MAP_POSITIONS]; + let mut cdf_tesla = [0; NUMBER_OF_MAP_POSITIONS]; + + let mut attack_metric_per_row = [0; MAP_HEIGHT as usize]; + let mut defence_metric_per_row = [0; MAP_HEIGHT as usize]; + for y in 0..MAP_HEIGHT { + let opponent_energy = opponent.count_energy_towers_in_row(y); + let opponent_attack = opponent.count_attack_towers_in_row(y); + let opponent_towers = opponent.count_towers_in_row(y); + + let player_energy = player.count_energy_towers_in_row(y); + let player_attack = player.count_attack_towers_in_row(y); + let player_towers = player.count_towers_in_row(y); + + defence_metric_per_row[y as usize] = if opponent_attack == 0 { 0 } else { opponent_attack + player_towers }; + attack_metric_per_row[y as usize] = 8 + opponent_energy + opponent_towers + player_energy - player_attack; + } + + + let mut other_end: u16 = 0; + // Nothing + { + let weight = if player.can_build_iron_curtain() && player.energy < IRON_CURTAIN_PRICE { + 5 + } else { + 0 + }; + other_end += weight; + cdf_other[0] = other_end; + } + + // Iron Curtain + { + let weight = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE { + 50 + } else { + 0 + }; + other_end += weight; + cdf_other[1] = other_end; + } + + // Energy + let mut energy_end: u16 = other_end; + let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF || + player.energy <= ENERGY_STORAGE_CUTOFF; + if needs_energy && player.energy >= ENERGY_PRICE { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if player.occupied & point.to_bitfield() != 0 { + 0 + } else { + 2 + }; + + energy_end += weight; + cdf_energy[p as usize] = energy_end; + } + } + + // Defence + let mut defence_end: u16 = energy_end; + if player.energy >= DEFENCE_PRICE { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let y = usize::from(point.y()); + + let weight = if player.occupied & point.to_bitfield() != 0 || point.x() < 4 { + 0 + } else { + defence_metric_per_row[y] + }; + + defence_end += weight; + cdf_defence[p as usize] = defence_end; + } + } + + // Attack + let mut attack_end: u16 = defence_end; + if player.energy >= MISSILE_PRICE { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if player.occupied & point.to_bitfield() != 0 { + 0 + } else { + let y = usize::from(point.y()); + attack_metric_per_row[y] + }; + + attack_end += weight; + cdf_attack[p as usize] = attack_end; + } + } + + // Tesla + let mut tesla_end: u16 = attack_end; + let cant_tesla = player.has_max_teslas() || player.energy < TESLA_PRICE; + if !cant_tesla { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if (player.occupied & point.to_bitfield() != 0) || point.y() < 7 { + 0 + } else { + 10 + }; + + tesla_end += weight; + cdf_tesla[p as usize] = tesla_end; + } + } + + let cumulative_distribution = tesla_end; + + if cumulative_distribution == 0 { + return Command::Nothing; + } + + let choice = rng.gen_range(0, cumulative_distribution); + + let index = match choice { + c if c < other_end => cdf_other.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + c if c < energy_end => 2 + cdf_energy.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + c if c < defence_end => 2 + NUMBER_OF_MAP_POSITIONS + cdf_defence.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + c if c < attack_end => 2 + 2 * NUMBER_OF_MAP_POSITIONS + cdf_attack.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + _ => 2 + 3 * NUMBER_OF_MAP_POSITIONS + cdf_tesla.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + }; + + MOVES[index] +} + +#[cfg(not(feature = "heuristic-random"))] +pub fn random_move<R: Rng>(player: &Player, _opponent: &Player, rng: &mut R) -> Command { + let free_positions_count = player.unoccupied_cell_count(); + + let open_building_spot = free_positions_count > 0; + + let all_buildings = sensible_buildings(player, open_building_spot); + + let iron_curtain_count = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE { 1 } else { 0 }; + let nothing_count = 1; + + let building_choice_index = rng.gen_range(0, all_buildings.len() + nothing_count + iron_curtain_count); + + if building_choice_index < all_buildings.len() { + let position_choice = rng.gen_range(0, free_positions_count); + Command::Build( + player.location_of_unoccupied_cell(position_choice), + all_buildings[building_choice_index] + ) + } + else if building_choice_index == all_buildings.len() { + Command::Nothing + } else { + Command::IronCurtain + } +} + +#[derive(Debug)] +struct CommandScore { + command: Command, + starts_with_nothing: bool, + victory_score: i32, + victories: u32, + defeat_score: i32, + defeats: u32, + draws: u32, + stalemates: u32, + attempts: u32, + next_seed: [u8; 16] +} + +impl CommandScore { + fn new(command: Command, starts_with_nothing: bool) -> CommandScore { + CommandScore { + command, starts_with_nothing, + victory_score: 0, + victories: 0, + defeat_score: 0, + defeats: 0, + draws: 0, + stalemates: 0, + attempts: 0, + next_seed: INIT_SEED + } + } + + fn add_victory(&mut self, weight: i32, next_seed: [u8; 16]) { + use std::cmp; + self.victory_score += cmp::max(weight, 1); + self.victories += 1; + self.attempts += 1; + self.next_seed = next_seed; + } + + fn add_defeat(&mut self, weight: i32, next_seed: [u8; 16]) { + use std::cmp; + self.defeat_score += cmp::max(weight, 1); + self.defeats += 1; + self.attempts += 1; + self.next_seed = next_seed; + } + + fn add_draw(&mut self, next_seed: [u8; 16]) { + self.draws += 1; + self.attempts += 1; + self.next_seed = next_seed; + } + + fn add_stalemate(&mut self, next_seed: [u8; 16]) { + self.stalemates += 1; + self.attempts += 1; + self.next_seed = next_seed; + } + + #[cfg(feature = "weighted-win-ratio")] + fn win_ratio(&self) -> i32 { + (self.victory_score - self.defeat_score) * 10000 / (self.attempts as i32) + } + + #[cfg(not(feature = "weighted-win-ratio"))] + fn win_ratio(&self) -> i32 { + (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32) + } + + fn init_command_scores(state: &BitwiseGameState) -> Vec<CommandScore> { + let unoccupied_cells_count = state.player.unoccupied_cell_count(); + let unoccupied_cells = (0..unoccupied_cells_count) + .map(|i| state.player.location_of_unoccupied_cell(i)); + let energy_generated = state.player.energy_generated(); + + let mut all_buildings: ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> = ArrayVec::new(); + if DEFENCE_PRICE <= state.player.energy { + all_buildings.push(BuildingType::Defence); + } + if MISSILE_PRICE <= state.player.energy { + all_buildings.push(BuildingType::Attack); + } + if ENERGY_PRICE <= state.player.energy { + all_buildings.push(BuildingType::Energy); + } + if !state.player.has_max_teslas() && (TESLA_PRICE.saturating_sub(state.player.energy) / energy_generated < 4) { + all_buildings.push(BuildingType::Tesla); + } + + let building_command_count = unoccupied_cells.len()*all_buildings.len(); + + let mut commands = Vec::with_capacity(building_command_count + 1); + let time_to_curtain_energy = (IRON_CURTAIN_PRICE.saturating_sub(state.player.energy) / energy_generated) as u8; + + if time_to_curtain_energy < 4 && state.player.can_build_iron_curtain_in(state.round, time_to_curtain_energy) { + commands.push(CommandScore::new(Command::IronCurtain, state.player.energy < IRON_CURTAIN_PRICE)); + } + + for position in unoccupied_cells { + for &building in &all_buildings { + commands.push(CommandScore::new(Command::Build(position, building), building.cant_build_yet(state.player.energy))); + } + } + + commands + } +} + +impl fmt::Display for CommandScore { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "{},{}", self.command, self.win_ratio()) + } +} + +#[cfg(all(not(feature = "heuristic-random"), not(feature = "energy-cutoff")))] +fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> { + let mut result = ArrayVec::new(); + if !open_building_spot { + return result; + } + + if DEFENCE_PRICE <= player.energy { + result.push(BuildingType::Defence); + } + if MISSILE_PRICE <= player.energy { + result.push(BuildingType::Attack); + } + if ENERGY_PRICE <= player.energy { + result.push(BuildingType::Energy); + } + if TESLA_PRICE <= player.energy && !player.has_max_teslas() { + result.push(BuildingType::Tesla); + } + + result +} + +#[cfg(all(not(feature = "heuristic-random"), feature = "energy-cutoff"))] +fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> { + let mut result = ArrayVec::new(); + if !open_building_spot { + return result; + } + + let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF || + player.energy <= ENERGY_STORAGE_CUTOFF; + + if DEFENCE_PRICE <= player.energy { + result.push(BuildingType::Defence); + } + if MISSILE_PRICE <= player.energy { + result.push(BuildingType::Attack); + } + if ENERGY_PRICE <= player.energy && needs_energy { + result.push(BuildingType::Energy); + } + if TESLA_PRICE <= player.energy && !player.has_max_teslas() { + result.push(BuildingType::Tesla); + } + + result +} + |