From 7ec48d0d454499177b63bc5bd512a3a2d6baa839 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 21:26:49 +0200 Subject: Refile for merging repos --- 2018-tower-defence/src/bin/perf-test.rs | 26 ++ 2018-tower-defence/src/engine/bitwise_engine.rs | 483 ++++++++++++++++++++ 2018-tower-defence/src/engine/command.rs | 66 +++ 2018-tower-defence/src/engine/constants.rs | 52 +++ 2018-tower-defence/src/engine/geometry.rs | 71 +++ 2018-tower-defence/src/engine/mod.rs | 5 + 2018-tower-defence/src/engine/status.rs | 8 + 2018-tower-defence/src/input/json.rs | 191 ++++++++ 2018-tower-defence/src/input/mod.rs | 1 + 2018-tower-defence/src/lib.rs | 20 + 2018-tower-defence/src/main.rs | 55 +++ 2018-tower-defence/src/strategy/mod.rs | 3 + 2018-tower-defence/src/strategy/monte_carlo.rs | 505 +++++++++++++++++++++ .../src/strategy/monte_carlo_tree.rs | 243 ++++++++++ 2018-tower-defence/src/strategy/static_opening.rs | 21 + 15 files changed, 1750 insertions(+) create mode 100644 2018-tower-defence/src/bin/perf-test.rs create mode 100644 2018-tower-defence/src/engine/bitwise_engine.rs create mode 100644 2018-tower-defence/src/engine/command.rs create mode 100644 2018-tower-defence/src/engine/constants.rs create mode 100644 2018-tower-defence/src/engine/geometry.rs create mode 100644 2018-tower-defence/src/engine/mod.rs create mode 100644 2018-tower-defence/src/engine/status.rs create mode 100644 2018-tower-defence/src/input/json.rs create mode 100644 2018-tower-defence/src/input/mod.rs create mode 100644 2018-tower-defence/src/lib.rs create mode 100644 2018-tower-defence/src/main.rs create mode 100644 2018-tower-defence/src/strategy/mod.rs create mode 100644 2018-tower-defence/src/strategy/monte_carlo.rs create mode 100644 2018-tower-defence/src/strategy/monte_carlo_tree.rs create mode 100644 2018-tower-defence/src/strategy/static_opening.rs (limited to '2018-tower-defence/src') diff --git a/2018-tower-defence/src/bin/perf-test.rs b/2018-tower-defence/src/bin/perf-test.rs new file mode 100644 index 0000000..ee0c2be --- /dev/null +++ b/2018-tower-defence/src/bin/perf-test.rs @@ -0,0 +1,26 @@ +extern crate zombot; +extern crate time; +use time::{PreciseTime, Duration}; + +use zombot::*; +use zombot::engine::constants::*; + +const STATE_PATH: &str = "tests/state0.json"; + +use std::process; + +fn main() { + println!("Running bitwise engine"); + let start_time = PreciseTime::now(); + let state = match input::json::read_bitwise_state_from_file(STATE_PATH) { + Ok(ok) => ok, + Err(error) => { + println!("Error while parsing JSON file: {}", error); + process::exit(1); + } + }; + let max_time = Duration::milliseconds(MAX_TIME_MILLIS); + + #[cfg(feature = "full-monte-carlo-tree")] strategy::monte_carlo_tree::choose_move(&state, start_time, max_time); + #[cfg(not(feature = "full-monte-carlo-tree"))] strategy::monte_carlo::choose_move(&state, start_time, max_time); +} diff --git a/2018-tower-defence/src/engine/bitwise_engine.rs b/2018-tower-defence/src/engine/bitwise_engine.rs new file mode 100644 index 0000000..694a309 --- /dev/null +++ b/2018-tower-defence/src/engine/bitwise_engine.rs @@ -0,0 +1,483 @@ +use engine::command::{Command, BuildingType}; +use engine::geometry::Point; +use engine::constants::*; +use engine::status::GameStatus; + +use arrayvec::ArrayVec; + +const LEFT_COL_MASK: u64 = 0x0101_0101_0101_0101; +const RIGHT_COL_MASK: u64 = 0x8080_8080_8080_8080; + +const ROW_MASKS: [u64; MAP_HEIGHT as usize] = [ + 0x0000_0000_0000_00ff, + 0x0000_0000_0000_ff00, + 0x0000_0000_00ff_0000, + 0x0000_0000_ff00_0000, + 0x0000_00ff_0000_0000, + 0x0000_ff00_0000_0000, + 0x00ff_0000_0000_0000, + 0xff00_0000_0000_0000, +]; + +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct BitwiseGameState { + pub status: GameStatus, + pub player: Player, + pub opponent: Player, + pub round: u16 +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct Player { + pub energy: u16, + pub health: u8, + pub unconstructed: ArrayVec<[UnconstructedBuilding; MAX_CONCURRENT_CONSTRUCTION]>, + pub buildings: [u64; DEFENCE_HEALTH], + pub occupied: u64, + + pub energy_towers: u64, + + pub missile_towers: [u64; MISSILE_COOLDOWN_STATES], + pub firing_tower: usize, + + pub missiles: [(u64, u64); MISSILE_MAX_SINGLE_CELL], + pub tesla_cooldowns: ArrayVec<[TeslaCooldown; TESLA_MAX]>, + + pub iron_curtain_available: bool, + pub iron_curtain_remaining: u8, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct UnconstructedBuilding { + pub pos: Point, + pub construction_time_left: u8, + pub building_type: BuildingType +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct TeslaCooldown { + pub pos: Point, + pub cooldown: u8, + pub age: u16 +} + + +impl BitwiseGameState { + pub fn simulate(&mut self, player_command: Command, opponent_command: Command) -> GameStatus { + self.player.perform_command(player_command); + self.opponent.perform_command(opponent_command); + + self.player.update_construction(); + self.opponent.update_construction(); + + self.player.add_missiles(); + self.opponent.add_missiles(); + + BitwiseGameState::fire_teslas(&mut self.player, &mut self.opponent); + + BitwiseGameState::move_and_collide_missiles(&mut self.player, &mut self.opponent.missiles); + BitwiseGameState::move_and_collide_missiles(&mut self.opponent, &mut self.player.missiles); + + BitwiseGameState::add_energy(&mut self.player); + BitwiseGameState::add_energy(&mut self.opponent); + + BitwiseGameState::update_iron_curtain(&mut self.player, self.round); + BitwiseGameState::update_iron_curtain(&mut self.opponent, self.round); + + self.round += 1; + + self.update_status(); + self.status + } +} + +fn find_bit_index_from_rank(occupied: u64, i: u64) -> u8 { + // Adapted from https://graphics.stanford.edu/~seander/bithacks.html#SelectPosFromMSBRank + let v = !occupied; + + let mut r = u64::from(v.count_ones()) - i; + + let a: u64 = v - ((v >> 1) & (!0u64/3)); + let b: u64 = (a & (!0u64/5)) + ((a >> 2) & (!0u64/5)); + let c: u64 = (b + (b >> 4)) & (!0u64/0x11); + let d: u64 = (c + (c >> 8)) & (!0u64/0x101); + let mut t: u64 = (d >> 32) + (d >> 48); + + let mut s: u64 = 64; + s -= (t.wrapping_sub(r) & 256) >> 3; r -= t & (t.wrapping_sub(r) >> 8); + t = (d >> (s - 16)) & 0xff; + s -= (t.wrapping_sub(r) & 256) >> 4; r -= t & (t.wrapping_sub(r) >> 8); + t = (c >> (s - 8)) & 0xf; + s -= (t.wrapping_sub(r) & 256) >> 5; r -= t & (t.wrapping_sub(r) >> 8); + t = (b >> (s - 4)) & 0x7; + s -= (t.wrapping_sub(r) & 256) >> 6; r -= t & (t.wrapping_sub(r) >> 8); + t = (a >> (s - 2)) & 0x3; + s -= (t.wrapping_sub(r) & 256) >> 7; r -= t & (t.wrapping_sub(r) >> 8); + t = (v >> (s - 1)) & 0x1; + s -= (t.wrapping_sub(r) & 256) >> 8; + s = 65 - s; + + 64 - s as u8 +} + +impl BitwiseGameState { + pub fn new( + player: Player, opponent: Player, + round: u16 + ) -> BitwiseGameState { + BitwiseGameState { + status: GameStatus::Continue, + player, opponent, + round + } + } + + /** + * This is to make things more comparable when writing tests, not + * for actual use in the engine. + */ + #[cfg(debug_assertions)] + pub fn sort(&mut self) { + for i in 0..MISSILE_MAX_SINGLE_CELL { + for j in i+1..MISSILE_MAX_SINGLE_CELL { + let move_down1 = !self.player.missiles[i].0 & self.player.missiles[j].0; + self.player.missiles[i].0 |= move_down1; + self.player.missiles[j].0 &= !move_down1; + + let move_down2 = !self.player.missiles[i].1 & self.player.missiles[j].1; + self.player.missiles[i].1 |= move_down2; + self.player.missiles[j].1 &= !move_down2; + + let move_down3 = !self.opponent.missiles[i].0 & self.opponent.missiles[j].0; + self.opponent.missiles[i].0 |= move_down3; + self.opponent.missiles[j].0 &= !move_down3; + + let move_down4 = !self.opponent.missiles[i].1 & self.opponent.missiles[j].1; + self.opponent.missiles[i].1 |= move_down4; + self.opponent.missiles[j].1 &= !move_down4; + } + } + + self.player.unconstructed.sort_by_key(|b| b.pos); + self.opponent.unconstructed.sort_by_key(|b| b.pos); + + self.player.tesla_cooldowns.sort_by_key(|b| b.pos); + self.opponent.tesla_cooldowns.sort_by_key(|b| b.pos); + + + while self.player.firing_tower > 0 { + self.player.firing_tower -= 1; + let zero = self.player.missile_towers[0]; + for i in 1..self.player.missile_towers.len() { + self.player.missile_towers[i-1] = self.player.missile_towers[i]; + } + let end = self.player.missile_towers.len()-1; + self.player.missile_towers[end] = zero; + } + while self.opponent.firing_tower > 0 { + self.opponent.firing_tower -= 1; + let zero = self.opponent.missile_towers[0]; + for i in 1..self.opponent.missile_towers.len() { + self.opponent.missile_towers[i-1] = self.opponent.missile_towers[i]; + } + let end = self.opponent.missile_towers.len()-1; + self.opponent.missile_towers[end] = zero; + } + } + + #[cfg(debug_assertions)] + pub fn sorted(&self) -> BitwiseGameState { + let mut res = self.clone(); + res.sort(); + res + } + + fn update_iron_curtain(player: &mut Player, round: u16) { + if round != 0 && round % IRON_CURTAIN_UNLOCK_INTERVAL == 0 { + player.iron_curtain_available = true; + } + player.iron_curtain_remaining = player.iron_curtain_remaining.saturating_sub(1); + } + + fn fire_teslas(player: &mut Player, opponent: &mut Player) { + BitwiseGameState::fire_single_players_teslas_without_cleanup(player, opponent); + BitwiseGameState::fire_single_players_teslas_without_cleanup(opponent, player); + + BitwiseGameState::update_tesla_activity(player); + BitwiseGameState::update_tesla_activity(opponent); + } + + fn fire_single_players_teslas_without_cleanup(player: &mut Player, opponent: &mut Player) { + // It's technically more accurate to have this in, but for + // most practical purposes it's a moot point and it's faster + // without it. + // + // player.tesla_cooldowns.sort_unstable_by(|a, b| b.age.cmp(&a.age)); + for tesla in player.tesla_cooldowns.iter_mut() { + tesla.age += 1; + if tesla.cooldown > 0 { + tesla.cooldown -= 1; + } else if player.energy >= TESLA_FIRING_ENERGY && opponent.iron_curtain_remaining > 0 { + player.energy -= TESLA_FIRING_ENERGY; + tesla.cooldown = TESLA_COOLDOWN; + } else if player.energy >= TESLA_FIRING_ENERGY { + player.energy -= TESLA_FIRING_ENERGY; + tesla.cooldown = TESLA_COOLDOWN; + + if tesla.pos.to_bitfield() & RIGHT_COL_MASK != 0 { + opponent.health = opponent.health.saturating_sub(TESLA_DAMAGE); + } + + let x = tesla.pos.x(); + let y = tesla.pos.y(); + let missed_cells = (u32::from(SINGLE_MAP_WIDTH - x)).saturating_sub(2); + + let top_row = y.saturating_sub(1); + let top_row_mask = ROW_MASKS[top_row as usize]; + let mut destroy_mask = top_row_mask.wrapping_shl(missed_cells) & top_row_mask; + + let mut hits = 0; + for _ in 0..(if y == 0 || y == MAP_HEIGHT-1 { 2 } else { 3 }) { + hits |= destroy_mask & opponent.buildings[0]; + destroy_mask &= !hits; + destroy_mask <<= SINGLE_MAP_WIDTH; + } + BitwiseGameState::destroy_buildings(opponent, hits); + } + } + } + + fn move_and_collide_missiles(opponent: &mut Player, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) { + let mut destroyed = 0; + let mut damaging = 0; + for _ in 0..MISSILE_SPEED { + for missile in player_missiles.iter_mut() { + let swapping_sides = if opponent.iron_curtain_remaining > 0 { 0 } else { missile.0 & RIGHT_COL_MASK }; + let about_to_hit_opponent = missile.1 & LEFT_COL_MASK; + + missile.0 = (missile.0 & !RIGHT_COL_MASK) << 1; + missile.1 = ((missile.1 & !LEFT_COL_MASK) >> 1) | swapping_sides; + + damaging = (damaging << 1) | about_to_hit_opponent; + + let mut hits = 0; + for health_tier in (0..DEFENCE_HEALTH).rev() { + hits = opponent.buildings[health_tier] & missile.1; + missile.1 &= !hits; + opponent.buildings[health_tier] &= !hits; + } + destroyed |= hits; + } + } + let damage = damaging.count_ones() as u8 * MISSILE_DAMAGE; + opponent.health = opponent.health.saturating_sub(damage); + + BitwiseGameState::destroy_buildings(opponent, destroyed); + BitwiseGameState::update_tesla_activity(opponent); + } + + fn destroy_buildings(buildings: &mut Player, hit_mask: u64) { + let deconstruct_mask = !hit_mask; + + buildings.energy_towers &= deconstruct_mask; + for tier in &mut buildings.missile_towers { + *tier &= deconstruct_mask; + } + for tier in &mut buildings.buildings { + *tier &= deconstruct_mask; + } + buildings.occupied &= deconstruct_mask; + } + + fn update_tesla_activity(buildings: &mut Player) { + let occupied = buildings.occupied; + buildings.tesla_cooldowns.retain(|t| (t.pos.to_bitfield() & occupied) != 0); + } + + + fn add_energy(player: &mut Player) { + player.energy += player.energy_generated(); + } + + fn update_status(&mut self) { + let player_dead = self.player.health == 0; + let opponent_dead = self.opponent.health == 0; + self.status = match (player_dead, opponent_dead) { + (true, true) => GameStatus::Draw, + (false, true) => GameStatus::PlayerWon, + (true, false) => GameStatus::OpponentWon, + (false, false) => GameStatus::Continue, + }; + } + +} + +impl Player { + pub fn count_teslas(&self) -> usize { + self.tesla_cooldowns.len() + + self.unconstructed.iter().filter(|t| t.building_type == BuildingType::Tesla).count() + } + + pub fn empty() -> Player { + Player { + health: 0, + energy: 0, + unconstructed: ArrayVec::new(), + buildings: [0; DEFENCE_HEALTH], + occupied: 0, + energy_towers: 0, + missile_towers: [0; MISSILE_COOLDOWN_STATES], + firing_tower: 0, + missiles: [(0,0); MISSILE_MAX_SINGLE_CELL], + tesla_cooldowns: ArrayVec::new(), + iron_curtain_available: false, + iron_curtain_remaining: 0, + } + } + + pub fn energy_generated(&self) -> u16 { + ENERGY_GENERATED_BASE + self.energy_towers.count_ones() as u16 * ENERGY_GENERATED_TOWER + } + + pub fn has_max_teslas(&self) -> bool { + self.count_teslas() >= TESLA_MAX + } + + pub fn can_build_iron_curtain(&self) -> bool { + self.iron_curtain_available && self.iron_curtain_remaining == 0 + } + + pub fn can_build_iron_curtain_in(&self, round: u16, moves: u8) -> bool { + let unlocks = round % IRON_CURTAIN_UNLOCK_INTERVAL > round + u16::from(moves) % IRON_CURTAIN_UNLOCK_INTERVAL; + (self.iron_curtain_available || unlocks) && self.iron_curtain_remaining.saturating_sub(moves) == 0 + } + + pub fn unoccupied_cell_count(&self) -> usize { self.occupied.count_zeros() as usize } + pub fn location_of_unoccupied_cell(&self, i: usize) -> Point { + let bit = find_bit_index_from_rank(self.occupied, i as u64); + let point = Point { index: bit }; + debug_assert!(point.to_bitfield() & self.occupied == 0); + point + } + + + fn perform_command(&mut self, command: Command) { + match command { + Command::Nothing => {}, + Command::Build(p, b) => { + let bitfield = p.to_bitfield(); + + let price = match b { + BuildingType::Attack => MISSILE_PRICE, + BuildingType::Defence => DEFENCE_PRICE, + BuildingType::Energy => ENERGY_PRICE, + BuildingType::Tesla => TESLA_PRICE, + }; + let construction_time = match b { + BuildingType::Attack => MISSILE_CONSTRUCTION_TIME, + BuildingType::Defence => DEFENCE_CONSTRUCTION_TIME, + BuildingType::Energy => ENERGY_CONSTRUCTION_TIME, + BuildingType::Tesla => TESLA_CONSTRUCTION_TIME, + }; + + // This is used internally. I should not be making + // invalid moves! + debug_assert!(self.buildings[0] & bitfield == 0); + debug_assert!(p.x() < FULL_MAP_WIDTH && p.y() < MAP_HEIGHT); + debug_assert!(self.energy >= price); + debug_assert!(b != BuildingType::Tesla || + self.count_teslas() < TESLA_MAX); + + self.energy -= price; + self.unconstructed.push(UnconstructedBuilding { + pos: p, + construction_time_left: construction_time, + building_type: b + }); + self.occupied |= bitfield; + }, + Command::IronCurtain => { + debug_assert!(self.iron_curtain_available); + debug_assert!(self.energy >= IRON_CURTAIN_PRICE); + + self.energy -= IRON_CURTAIN_PRICE; + self.iron_curtain_available = false; + self.iron_curtain_remaining = IRON_CURTAIN_DURATION; + } + } + } + + fn update_construction(&mut self) { + let mut buildings_len = self.unconstructed.len(); + for i in (0..buildings_len).rev() { + if self.unconstructed[i].construction_time_left == 0 { + let building_type = self.unconstructed[i].building_type; + let health = if building_type == BuildingType::Defence { DEFENCE_HEALTH } else { 1 }; + + let pos = self.unconstructed[i].pos; + let bitfield = pos.to_bitfield(); + + for health_tier in 0..health { + self.buildings[health_tier] |= bitfield; + } + if building_type == BuildingType::Energy { + self.energy_towers |= bitfield; + } + if building_type == BuildingType::Attack { + self.missile_towers[self.firing_tower] |= bitfield; + } + if building_type == BuildingType::Tesla { + self.tesla_cooldowns.push(TeslaCooldown { + pos, + cooldown: 0, + age: 0 + }); + } + + buildings_len -= 1; + self.unconstructed.swap(i, buildings_len); + } else { + self.unconstructed[i].construction_time_left -= 1 + } + } + self.unconstructed.truncate(buildings_len); + } + + fn add_missiles(&mut self) { + let mut missiles = self.missile_towers[self.firing_tower]; + for mut tier in &mut self.missiles { + let setting = !tier.0 & missiles; + tier.0 |= setting; + missiles &= !setting; + } + self.firing_tower = (self.firing_tower + 1) % MISSILE_COOLDOWN_STATES; + } + + fn any_missile_towers(&self) -> u64 { + self.missile_towers.iter().fold(0, |acc, next| acc | next) + } + + pub fn count_attack_towers_in_row(&self, y: u8) -> u16 { + let mask = ROW_MASKS[y as usize]; + (self.any_missile_towers() & mask).count_ones() as u16 + } + + pub fn count_energy_towers_in_row(&self, y: u8) -> u16 { + let mask = ROW_MASKS[y as usize]; + (self.energy_towers & mask).count_ones() as u16 + } + + pub fn count_healthy_defence_in_row(&self, y: u8) -> u16 { + let mask = ROW_MASKS[y as usize]; + (self.buildings[1] & mask).count_ones() as u16 + } + + pub fn count_towers_in_row(&self, y: u8) -> u16 { + let mask = ROW_MASKS[y as usize]; + (self.occupied & mask).count_ones() as u16 + } + + pub fn count_towers(&self) -> u32 { + self.occupied.count_ones() + } +} diff --git a/2018-tower-defence/src/engine/command.rs b/2018-tower-defence/src/engine/command.rs new file mode 100644 index 0000000..76cfaee --- /dev/null +++ b/2018-tower-defence/src/engine/command.rs @@ -0,0 +1,66 @@ +use std::fmt; +use super::constants::*; +use super::geometry::Point; + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum Command { + Nothing, + Build(Point, BuildingType), + IronCurtain +} + +impl fmt::Display for Command { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + Command::Nothing => write!(f, ""), + Command::Build(p, b) => write!(f, "{},{},{}", p.x(), p.y(), b as u8), + Command::IronCurtain => write!(f, "0,0,5") + } + } +} + +impl Command { + pub fn cant_build_yet(self, energy: u16) -> bool { + use self::Command::*; + + match self { + Nothing => false, + Build(_, b) => b.cant_build_yet(energy), + IronCurtain => energy < IRON_CURTAIN_PRICE + } + } +} + + +#[repr(u8)] +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum BuildingType { + Defence = 0, + Attack = 1, + Energy = 2, + Tesla = 4, +} + +impl BuildingType { + pub fn all() -> [BuildingType; NUMBER_OF_BUILDING_TYPES] { + use self::BuildingType::*; + [Defence, Attack, Energy, Tesla] + } + + pub fn from_u8(id: u8) -> Option { + use std::mem; + if id <= 4 && id != 3 { Some(unsafe { mem::transmute(id) }) } else { None } + } + + pub fn cant_build_yet(self, energy: u16) -> bool { + use self::BuildingType::*; + + let required = match self { + Defence => DEFENCE_PRICE, + Attack => MISSILE_PRICE, + Energy => ENERGY_PRICE, + Tesla => TESLA_PRICE + }; + energy < required + } +} diff --git a/2018-tower-defence/src/engine/constants.rs b/2018-tower-defence/src/engine/constants.rs new file mode 100644 index 0000000..a66c9e1 --- /dev/null +++ b/2018-tower-defence/src/engine/constants.rs @@ -0,0 +1,52 @@ +pub const FULL_MAP_WIDTH: u8 = 16; +pub const SINGLE_MAP_WIDTH: u8 = FULL_MAP_WIDTH/2; +pub const MAP_HEIGHT: u8 = 8; + +pub const MAX_MOVES: u16 = 400; +pub const INIT_SEED: [u8;16] = [0x7b, 0x6a, 0xe1, 0xf4, 0x41, 0x3c, 0xe9, 0x0f, 0x67, 0x81, 0x67, 0x99, 0x77, 0x0a, 0x6b, 0xda]; + +pub const MISSILE_COOLDOWN: usize = 3; +pub const MISSILE_COOLDOWN_STATES: usize = MISSILE_COOLDOWN+1; +pub const MISSILE_SPEED: usize = 2; +pub const MISSILE_MAX_SINGLE_CELL: usize = SINGLE_MAP_WIDTH as usize / MISSILE_SPEED; +pub const MISSILE_DAMAGE: u8 = 5; +pub const MISSILE_PRICE: u16 = 30; +pub const MISSILE_CONSTRUCTION_TIME: u8 = 1; + +pub const DEFENCE_HEALTH: usize = 4; // '20' health is 4 hits +pub const DEFENCE_PRICE: u16 = 30; +pub const DEFENCE_CONSTRUCTION_TIME: u8 = 3; + +pub const TESLA_MAX: usize = 2; +pub const TESLA_COOLDOWN: u8 = 10; +pub const TESLA_FIRING_ENERGY: u16 = 100; +pub const TESLA_DAMAGE: u8 = 20; +pub const TESLA_PRICE: u16 = 100; +pub const TESLA_CONSTRUCTION_TIME: u8 = 10; + +pub const ENERGY_GENERATED_BASE: u16 = 5; +pub const ENERGY_GENERATED_TOWER: u16 = 3; +pub const ENERGY_PRICE: u16 = 20; +pub const ENERGY_CONSTRUCTION_TIME: u8 = 1; + +pub const IRON_CURTAIN_PRICE: u16 = 100; +pub const IRON_CURTAIN_UNLOCK_INTERVAL: u16 = 30; +pub const IRON_CURTAIN_DURATION: u8 = 6; + +pub const DECONSTRUCT_ENERGY: u16 = 5; + +pub const MAX_CONCURRENT_CONSTRUCTION: usize = 6; //2 teslas, and 3 of anything else, 1 extra because it's push here then update construction times + + +pub const NUMBER_OF_BUILDING_TYPES: usize = 4; +pub const NUMBER_OF_MAP_POSITIONS: usize = SINGLE_MAP_WIDTH as usize * MAP_HEIGHT as usize; +pub const NUMBER_OF_POSSIBLE_MOVES: usize = NUMBER_OF_MAP_POSITIONS * NUMBER_OF_BUILDING_TYPES + 2; + +#[cfg(not(any(feature = "reduced-time", feature = "extended-time")))] +pub const MAX_TIME_MILLIS: i64 = 1950; + +#[cfg(feature = "reduced-time")] +pub const MAX_TIME_MILLIS: i64 = 950; + +#[cfg(feature = "extended-time")] +pub const MAX_TIME_MILLIS: i64 = 19950; diff --git a/2018-tower-defence/src/engine/geometry.rs b/2018-tower-defence/src/engine/geometry.rs new file mode 100644 index 0000000..9cd1d90 --- /dev/null +++ b/2018-tower-defence/src/engine/geometry.rs @@ -0,0 +1,71 @@ +use engine::constants::*; + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct Point { + pub index: u8 +} + +impl Point { + pub fn new(x: u8, y: u8) -> Point { + let flipped_x = if x >= SINGLE_MAP_WIDTH { + FULL_MAP_WIDTH - x - 1 + } else { + x + }; + Point { + index: y * SINGLE_MAP_WIDTH + flipped_x + } + } + + pub fn new_index(index: u8) -> Point { + Point { + index + } + } + + pub fn new_double_bitfield(x: u8, y: u8, is_left_player: bool) -> (u64, u64) { + let bitfield = Point::new(x, y).to_bitfield(); + if (x >= SINGLE_MAP_WIDTH) == is_left_player { + (0, bitfield) + } else { + (bitfield, 0) + } + } + + pub fn x(self) -> u8 { + self.index % SINGLE_MAP_WIDTH + } + + pub fn y(self) -> u8 { + self.index / SINGLE_MAP_WIDTH + } +} + +impl Point { + /** + * # Bitfields + * + * 0,0 is the top left point. + * >> (towards 0) moves bits towards the player that owns that side + * << (towards max) moves bits towards the opponent + * This involves mirroring the x dimension for the opponent's side + */ + + pub fn to_bitfield(self) -> u64 { + 1u64 << self.index + } +} + +use std::cmp::Ord; +use std::cmp::Ordering; + +impl PartialOrd for Point { + fn partial_cmp(&self, other: &Point) -> Option { + Some(self.cmp(other)) + } +} +impl Ord for Point { + fn cmp(&self, other: &Point) -> Ordering { + self.index.cmp(&other.index) + } +} diff --git a/2018-tower-defence/src/engine/mod.rs b/2018-tower-defence/src/engine/mod.rs new file mode 100644 index 0000000..f98ef6b --- /dev/null +++ b/2018-tower-defence/src/engine/mod.rs @@ -0,0 +1,5 @@ +pub mod command; +pub mod geometry; +pub mod bitwise_engine; +pub mod constants; +pub mod status; diff --git a/2018-tower-defence/src/engine/status.rs b/2018-tower-defence/src/engine/status.rs new file mode 100644 index 0000000..d6ee4dd --- /dev/null +++ b/2018-tower-defence/src/engine/status.rs @@ -0,0 +1,8 @@ +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum GameStatus { + Continue, + PlayerWon, + OpponentWon, + Draw +} + diff --git a/2018-tower-defence/src/input/json.rs b/2018-tower-defence/src/input/json.rs new file mode 100644 index 0000000..a71d49e --- /dev/null +++ b/2018-tower-defence/src/input/json.rs @@ -0,0 +1,191 @@ +use std::fs::File; +use std::io::prelude::*; +use serde_json; +use std::error::Error; + +use engine; +use engine::command; +use engine::bitwise_engine; +use engine::constants::*; + +pub fn read_bitwise_state_from_file(filename: &str) -> Result> { + let mut file = File::open(filename)?; + let mut content = String::new(); + file.read_to_string(&mut content)?; + let state: State = serde_json::from_str(content.as_ref())?; + + let engine_state = state.to_bitwise_engine(); + Ok(engine_state) +} + +#[derive(Deserialize)] +#[serde(rename_all = "camelCase")] +struct State { + game_details: GameDetails, + players: Vec, + game_map: Vec>, +} + +#[derive(Deserialize)] +#[serde(rename_all = "camelCase")] +struct GameDetails { + round: u16 +} + +#[derive(Deserialize)] +#[serde(rename_all = "camelCase")] +struct Player { + player_type: char, + energy: u16, + health: u8, + iron_curtain_available: bool, + active_iron_curtain_lifetime: i16 +} + +#[derive(Deserialize)] +#[serde(rename_all = "camelCase")] +struct GameCell { + x: u8, + y: u8, + buildings: Vec, + missiles: Vec, +} + +#[derive(Deserialize)] +#[serde(rename_all = "camelCase")] +struct BuildingState { + health: u8, + construction_time_left: i16, + weapon_cooldown_time_left: u8, + building_type: String, + x: u8, + y: u8, + player_type: char +} + +#[derive(Deserialize)] +#[serde(rename_all = "camelCase")] +struct MissileState { + player_type: char +} + + +impl State { + fn to_bitwise_engine(&self) -> bitwise_engine::BitwiseGameState { + let mut player = bitwise_engine::Player::empty(); + let mut opponent = bitwise_engine::Player::empty(); + + self.player().map_onto_engine(&mut player); + self.opponent().map_onto_engine(&mut opponent); + + for row in &self.game_map { + for cell in row { + let point = engine::geometry::Point::new(cell.x, cell.y); + for building in &cell.buildings { + let building_type = building.convert_building_type(); + + let mut bitwise_buildings = if building.player_type == 'A' { + &mut player + } else { + &mut opponent + }; + let bitfield = point.to_bitfield(); + + bitwise_buildings.occupied |= bitfield; + if building.construction_time_left >= 0 { + bitwise_buildings.unconstructed.push(building.to_bitwise_engine_unconstructed()); + } else { + for health_tier in 0..DEFENCE_HEALTH { + if building.health > health_tier as u8 * MISSILE_DAMAGE { + bitwise_buildings.buildings[health_tier] |= bitfield; + } + } + if building_type == command::BuildingType::Energy { + bitwise_buildings.energy_towers |= bitfield; + } + else if building_type == command::BuildingType::Attack { + for cooldown_tier in 0..MISSILE_COOLDOWN + 1 { + if building.weapon_cooldown_time_left == cooldown_tier as u8 { + bitwise_buildings.missile_towers[cooldown_tier] |= bitfield; + } + } + } + else if building_type == command::BuildingType::Tesla { + bitwise_buildings.tesla_cooldowns.push(bitwise_engine::TeslaCooldown { + pos: point, + cooldown: building.weapon_cooldown_time_left, + age: building.construction_time_left.abs() as u16 + }); + } + } + } + for missile in &cell.missiles { + let (mut left, mut right) = engine::geometry::Point::new_double_bitfield(cell.x, cell.y, missile.player_type == 'A'); + let mut bitwise_buildings = if missile.player_type == 'A' { + &mut player + } else { + &mut opponent + }; + + for mut tier in &mut bitwise_buildings.missiles { + let setting = (!tier.0 & left, !tier.1 & right); + tier.0 |= setting.0; + tier.1 |= setting.1; + left &= !setting.0; + right &= !setting.1; + } + } + } + } + + bitwise_engine::BitwiseGameState::new( + player, opponent, + self.game_details.round + ) + } + + fn player(&self) -> &Player { + self.players.iter() + .find(|p| p.player_type == 'A') + .expect("Player character did not appear in state.json") + } + + fn opponent(&self) -> &Player { + self.players.iter() + .find(|p| p.player_type == 'B') + .expect("Opponent character did not appear in state.json") + } +} + +impl BuildingState { + fn to_bitwise_engine_unconstructed(&self) -> bitwise_engine::UnconstructedBuilding { + bitwise_engine::UnconstructedBuilding { + pos: engine::geometry::Point::new(self.x, self.y), + construction_time_left: self.construction_time_left as u8, // > 0 check already happened + building_type: self.convert_building_type() + } + } + + fn convert_building_type(&self) -> command::BuildingType { + match self.building_type.as_ref() { + "ATTACK" => command::BuildingType::Attack, + "ENERGY" => command::BuildingType::Energy, + "TESLA" => command::BuildingType::Tesla, + _ => command::BuildingType::Defence, + } + } +} + + +impl Player { + fn map_onto_engine(&self, engine_player: &mut bitwise_engine::Player) { + engine_player.health = self.health; + engine_player.energy = self.energy; + engine_player.iron_curtain_available = self.iron_curtain_available; + engine_player.iron_curtain_remaining = if self.active_iron_curtain_lifetime < 0 { + 0 + } else { + self.active_iron_curtain_lifetime as u8 + }; + } +} diff --git a/2018-tower-defence/src/input/mod.rs b/2018-tower-defence/src/input/mod.rs new file mode 100644 index 0000000..22fdbb3 --- /dev/null +++ b/2018-tower-defence/src/input/mod.rs @@ -0,0 +1 @@ +pub mod json; diff --git a/2018-tower-defence/src/lib.rs b/2018-tower-defence/src/lib.rs new file mode 100644 index 0000000..6cd8730 --- /dev/null +++ b/2018-tower-defence/src/lib.rs @@ -0,0 +1,20 @@ +extern crate serde; +extern crate serde_json; + +#[macro_use] +extern crate serde_derive; + +extern crate rand; +extern crate time; + +extern crate rayon; + +extern crate arrayvec; + +#[macro_use] +#[cfg(feature = "heuristic-random")] +extern crate lazy_static; + +pub mod input; +pub mod engine; +pub mod strategy; diff --git a/2018-tower-defence/src/main.rs b/2018-tower-defence/src/main.rs new file mode 100644 index 0000000..4fa0366 --- /dev/null +++ b/2018-tower-defence/src/main.rs @@ -0,0 +1,55 @@ +extern crate zombot; +extern crate time; +use time::{PreciseTime, Duration}; + +use zombot::*; +use zombot::engine::constants::*; +use zombot::engine::command::Command; + +use std::error::Error; + +const STATE_PATH: &str = "state.json"; + +const COMMAND_PATH: &str = "command.txt"; + +use std::fs::File; +use std::io::prelude::*; +use std::process; + +fn write_command(filename: &str, command: Command) -> Result<(), Box > { + let mut file = File::create(filename)?; + write!(file, "{}", command)?; + Ok(()) +} + +fn main() { + let start_time = PreciseTime::now(); + let max_time = Duration::milliseconds(MAX_TIME_MILLIS); + + let state = match input::json::read_bitwise_state_from_file(STATE_PATH) { + Ok(ok) => ok, + Err(error) => { + println!("Error while parsing JSON file: {}", error); + process::exit(1); + } + }; + + let command = if cfg!(feature = "static-opening") && state.round < strategy::static_opening::STATIC_OPENING_LENGTH { + strategy::static_opening::choose_move(&state) + } else if cfg!(feature = "full-monte-carlo-tree") { + strategy::monte_carlo_tree::choose_move(&state, start_time, max_time) + } else { + strategy::monte_carlo::choose_move(&state, start_time, max_time) + }; + + match write_command(COMMAND_PATH, command) { + Ok(()) => {} + Err(error) => { + println!("Error while writing command file: {}", error); + process::exit(1); + } + } + + println!("Elapsed time: {}", start_time.to(PreciseTime::now())); +} + 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 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, 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, 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(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(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(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 { + 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, +} + +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::() + } +} + +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(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(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(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 + } +} -- cgit v1.2.3