summaryrefslogtreecommitdiff
path: root/2018-tower-defence/src/strategy
diff options
context:
space:
mode:
Diffstat (limited to '2018-tower-defence/src/strategy')
-rw-r--r--2018-tower-defence/src/strategy/mod.rs3
-rw-r--r--2018-tower-defence/src/strategy/monte_carlo.rs505
-rw-r--r--2018-tower-defence/src/strategy/monte_carlo_tree.rs243
-rw-r--r--2018-tower-defence/src/strategy/static_opening.rs21
4 files changed, 772 insertions, 0 deletions
diff --git a/2018-tower-defence/src/strategy/mod.rs b/2018-tower-defence/src/strategy/mod.rs
new file mode 100644
index 0000000..9ec41bb
--- /dev/null
+++ b/2018-tower-defence/src/strategy/mod.rs
@@ -0,0 +1,3 @@
+pub mod monte_carlo;
+pub mod monte_carlo_tree;
+pub mod static_opening;
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
+}
+
diff --git a/2018-tower-defence/src/strategy/monte_carlo_tree.rs b/2018-tower-defence/src/strategy/monte_carlo_tree.rs
new file mode 100644
index 0000000..24b2088
--- /dev/null
+++ b/2018-tower-defence/src/strategy/monte_carlo_tree.rs
@@ -0,0 +1,243 @@
+use engine::command::*;
+use engine::status::GameStatus;
+use engine::bitwise_engine::{Player, BitwiseGameState};
+use engine::constants::*;
+
+use rand::{Rng, XorShiftRng, SeedableRng};
+use time::{Duration, PreciseTime};
+
+use strategy::monte_carlo;
+
+use arrayvec::ArrayVec;
+
+#[derive(Debug)]
+struct NodeStats {
+ wins: f32,
+ losses: f32,
+ attempts: f32,
+ average: f32,
+ confidence: f32,
+ explored: Vec<(Command, NodeStats)>,
+ unexplored: Vec<Command>,
+}
+
+impl NodeStats {
+ fn create_node(player: &Player) -> NodeStats {
+ let unoccupied_cells_count = player.unoccupied_cell_count();
+ let unoccupied_cells = (0..unoccupied_cells_count)
+ .map(|i| player.location_of_unoccupied_cell(i));
+
+ let mut all_buildings: ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> = ArrayVec::new();
+ if DEFENCE_PRICE <= player.energy {
+ all_buildings.push(BuildingType::Defence);
+ }
+ if MISSILE_PRICE <= player.energy {
+ all_buildings.push(BuildingType::Attack);
+ }
+ if ENERGY_PRICE <= player.energy {
+ all_buildings.push(BuildingType::Energy);
+ }
+ if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
+ all_buildings.push(BuildingType::Tesla);
+ }
+
+ let building_command_count = unoccupied_cells.len()*all_buildings.len();
+
+ let mut commands = Vec::with_capacity(building_command_count + 2);
+
+ commands.push(Command::Nothing);
+ if IRON_CURTAIN_PRICE <= player.energy && player.can_build_iron_curtain() {
+ commands.push(Command::IronCurtain);
+ }
+
+ for position in unoccupied_cells {
+ for &building in &all_buildings {
+ commands.push(Command::Build(position, building));
+ }
+ }
+
+ NodeStats {
+ wins: 0.,
+ losses: 0.,
+ attempts: 0.,
+ average: 0.,
+ confidence: 0.,
+ explored: Vec::with_capacity(commands.len()),
+ unexplored: commands
+ }
+ }
+
+ fn node_with_highest_ucb<'a>(&'a mut self) -> &'a mut (Command, NodeStats) {
+ debug_assert!(self.unexplored.is_empty());
+ debug_assert!(self.explored.len() > 0);
+ let sqrt_n = self.attempts.sqrt();
+
+ let mut max_position = 0;
+ let mut max_value = self.explored[0].1.ucb(sqrt_n);
+ for i in 1..self.explored.len() {
+ let value = self.explored[i].1.ucb(sqrt_n);
+ if value > max_value {
+ max_position = i;
+ max_value = value;
+ }
+ }
+ &mut self.explored[max_position]
+ }
+
+ fn ucb(&self, sqrt_n: f32) -> f32 {
+ self.average + sqrt_n * self.confidence
+ }
+
+ fn add_node<'a>(&'a mut self, player: &Player, command: Command) -> &'a mut (Command, NodeStats) {
+ let node = NodeStats::create_node(player);
+ self.explored.push((command, node));
+ self.unexplored.retain(|c| *c != command);
+ self.explored.last_mut().unwrap()
+ }
+
+ fn add_victory(&mut self) {
+ self.attempts += 1.;
+ self.wins += 1.;
+ self.update_confidence();
+ }
+ fn add_defeat(&mut self) {
+ self.attempts += 1.;
+ self.losses += 1.;
+ self.update_confidence();
+ }
+ fn add_draw(&mut self) {
+ self.attempts += 1.;
+ self.update_confidence();
+ }
+ fn update_confidence(&mut self) {
+ self.average = self.wins / self.attempts;
+ self.confidence = (2.0 / self.attempts).sqrt();
+ }
+
+ #[cfg(feature = "benchmarking")]
+ fn count_explored(&self) -> usize {
+ 1 + self.explored.iter().map(|(_, n)| n.count_explored()).sum::<usize>()
+ }
+}
+
+pub fn choose_move(state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Command {
+ let mut rng = XorShiftRng::from_seed(INIT_SEED);
+
+ let mut root = NodeStats::create_node(&state.player);
+
+ while start_time.to(PreciseTime::now()) < max_time {
+ tree_search(&state, &mut root, &mut rng);
+ }
+
+ #[cfg(feature = "benchmarking")]
+ {
+ println!("Explored nodes: {}", root.count_explored());
+ }
+
+ let (command, _) = root.node_with_highest_ucb();
+ command.clone()
+}
+
+fn tree_search<R: Rng>(state: &BitwiseGameState, stats: &mut NodeStats, rng: &mut R) -> GameStatus {
+ // root is opponent move
+ // node being added is player move
+
+ if state.round >= MAX_MOVES {
+ return GameStatus::Draw
+ }
+
+ if stats.unexplored.is_empty() {
+ let result = {
+ let (next_command, next_tree) = stats.node_with_highest_ucb();
+ tree_search_opponent(state, next_tree, next_command.clone(), rng)
+ };
+ match result {
+ GameStatus::PlayerWon => {stats.add_defeat()},
+ GameStatus::OpponentWon => {stats.add_victory()},
+ _ => {stats.add_draw()}
+ };
+ result
+ } else {
+ let next_command = rng.choose(&stats.unexplored).expect("Partially explored had no options").clone();
+ let result = {
+ let (_, next_stats) = stats.add_node(&state.opponent, next_command);
+
+ let opponent_random = monte_carlo::random_move(&state.opponent, &state.player, rng);
+ let mut next_state = state.clone();
+ next_state.simulate(next_command, opponent_random);
+
+ let result = simulate_to_endstate(next_state, rng);
+ match result {
+ GameStatus::PlayerWon => {next_stats.add_victory()},
+ GameStatus::OpponentWon => {next_stats.add_defeat()},
+ _ => {next_stats.add_draw()}
+ };
+
+ result
+ };
+
+ match result {
+ GameStatus::PlayerWon => {stats.add_defeat()},
+ GameStatus::OpponentWon => {stats.add_victory()},
+ _ => {stats.add_draw()}
+ };
+ result
+ }
+}
+
+fn tree_search_opponent<R: Rng>(state: &BitwiseGameState, stats: &mut NodeStats, player_command: Command, rng: &mut R) -> GameStatus {
+ // root is player move
+ // node being added is opponent move
+
+ if stats.unexplored.is_empty() {
+ let result = {
+ let (next_command, next_tree) = stats.node_with_highest_ucb();
+ let mut next_state = state.clone();
+ next_state.simulate(player_command, next_command.clone());
+ tree_search(&next_state, next_tree, rng)
+ };
+ match result {
+ GameStatus::PlayerWon => {stats.add_victory()},
+ GameStatus::OpponentWon => {stats.add_defeat()},
+ _ => {stats.add_draw()}
+ };
+ result
+ } else {
+ let next_command = rng.choose(&stats.unexplored).expect("Partially explored had no options").clone();
+ let mut next_state = state.clone();
+ next_state.simulate(player_command, next_command);
+
+ let result = {
+ let (_, next_stats) = stats.add_node(&next_state.player, next_command);
+
+ let result = simulate_to_endstate(next_state, rng);
+ match result {
+ GameStatus::PlayerWon => {next_stats.add_defeat()},
+ GameStatus::OpponentWon => {next_stats.add_victory()},
+ _ => {next_stats.add_draw()}
+ };
+
+ result
+ };
+
+ match result {
+ GameStatus::PlayerWon => {stats.add_victory()},
+ GameStatus::OpponentWon => {stats.add_defeat()},
+ _ => {stats.add_draw()}
+ };
+ result
+ }
+}
+
+
+fn simulate_to_endstate<R: Rng>(mut state: BitwiseGameState, rng: &mut R) -> GameStatus {
+ let mut status = GameStatus::Continue;
+
+ while status == GameStatus::Continue && state.round < MAX_MOVES {
+ let player_command = monte_carlo::random_move(&state.player, &state.opponent, rng);
+ let opponent_command = monte_carlo::random_move(&state.opponent, &state.player, rng);
+ status = state.simulate(player_command, opponent_command);
+ }
+ status
+}
+
diff --git a/2018-tower-defence/src/strategy/static_opening.rs b/2018-tower-defence/src/strategy/static_opening.rs
new file mode 100644
index 0000000..f7e101c
--- /dev/null
+++ b/2018-tower-defence/src/strategy/static_opening.rs
@@ -0,0 +1,21 @@
+use engine::geometry::*;
+use engine::command::*;
+use engine::bitwise_engine::*;
+
+pub const STATIC_OPENING_LENGTH: u16 = 12;
+
+pub fn choose_move(state: &BitwiseGameState) -> Command {
+ match state.round {
+ 0 => Command::Build(Point::new(0,0), BuildingType::Energy),
+ 3 => Command::Build(Point::new(0,1), BuildingType::Energy),
+ 5 => Command::Build(Point::new(0,2), BuildingType::Energy),
+ 7 => Command::Build(Point::new(0,3), BuildingType::Energy),
+ 9 => Command::Build(Point::new(0,4), BuildingType::Energy),
+ 10 => Command::Build(Point::new(0,5), BuildingType::Energy),
+ 11 => Command::Build(Point::new(0,6), BuildingType::Energy),
+ 12 => Command::Build(Point::new(0,7), BuildingType::Energy),
+ 13 => Command::Build(Point::new(1,0), BuildingType::Energy),
+ 14 => Command::Build(Point::new(1,7), BuildingType::Energy),
+ _ => Command::Nothing
+ }
+}