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 --- src/bin/perf-test.rs | 26 -- src/engine/bitwise_engine.rs | 483 ------------------------------------- src/engine/command.rs | 66 ----- src/engine/constants.rs | 52 ---- src/engine/geometry.rs | 71 ------ src/engine/mod.rs | 5 - src/engine/status.rs | 8 - src/input/json.rs | 191 --------------- src/input/mod.rs | 1 - src/lib.rs | 20 -- src/main.rs | 55 ----- src/strategy/mod.rs | 3 - src/strategy/monte_carlo.rs | 505 --------------------------------------- src/strategy/monte_carlo_tree.rs | 243 ------------------- src/strategy/static_opening.rs | 21 -- 15 files changed, 1750 deletions(-) delete mode 100644 src/bin/perf-test.rs delete mode 100644 src/engine/bitwise_engine.rs delete mode 100644 src/engine/command.rs delete mode 100644 src/engine/constants.rs delete mode 100644 src/engine/geometry.rs delete mode 100644 src/engine/mod.rs delete mode 100644 src/engine/status.rs delete mode 100644 src/input/json.rs delete mode 100644 src/input/mod.rs delete mode 100644 src/lib.rs delete mode 100644 src/main.rs delete mode 100644 src/strategy/mod.rs delete mode 100644 src/strategy/monte_carlo.rs delete mode 100644 src/strategy/monte_carlo_tree.rs delete mode 100644 src/strategy/static_opening.rs (limited to 'src') diff --git a/src/bin/perf-test.rs b/src/bin/perf-test.rs deleted file mode 100644 index ee0c2be..0000000 --- a/src/bin/perf-test.rs +++ /dev/null @@ -1,26 +0,0 @@ -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/src/engine/bitwise_engine.rs b/src/engine/bitwise_engine.rs deleted file mode 100644 index 694a309..0000000 --- a/src/engine/bitwise_engine.rs +++ /dev/null @@ -1,483 +0,0 @@ -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/src/engine/command.rs b/src/engine/command.rs deleted file mode 100644 index 76cfaee..0000000 --- a/src/engine/command.rs +++ /dev/null @@ -1,66 +0,0 @@ -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/src/engine/constants.rs b/src/engine/constants.rs deleted file mode 100644 index a66c9e1..0000000 --- a/src/engine/constants.rs +++ /dev/null @@ -1,52 +0,0 @@ -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/src/engine/geometry.rs b/src/engine/geometry.rs deleted file mode 100644 index 9cd1d90..0000000 --- a/src/engine/geometry.rs +++ /dev/null @@ -1,71 +0,0 @@ -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/src/engine/mod.rs b/src/engine/mod.rs deleted file mode 100644 index f98ef6b..0000000 --- a/src/engine/mod.rs +++ /dev/null @@ -1,5 +0,0 @@ -pub mod command; -pub mod geometry; -pub mod bitwise_engine; -pub mod constants; -pub mod status; diff --git a/src/engine/status.rs b/src/engine/status.rs deleted file mode 100644 index d6ee4dd..0000000 --- a/src/engine/status.rs +++ /dev/null @@ -1,8 +0,0 @@ -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -pub enum GameStatus { - Continue, - PlayerWon, - OpponentWon, - Draw -} - diff --git a/src/input/json.rs b/src/input/json.rs deleted file mode 100644 index a71d49e..0000000 --- a/src/input/json.rs +++ /dev/null @@ -1,191 +0,0 @@ -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/src/input/mod.rs b/src/input/mod.rs deleted file mode 100644 index 22fdbb3..0000000 --- a/src/input/mod.rs +++ /dev/null @@ -1 +0,0 @@ -pub mod json; diff --git a/src/lib.rs b/src/lib.rs deleted file mode 100644 index 6cd8730..0000000 --- a/src/lib.rs +++ /dev/null @@ -1,20 +0,0 @@ -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/src/main.rs b/src/main.rs deleted file mode 100644 index 4fa0366..0000000 --- a/src/main.rs +++ /dev/null @@ -1,55 +0,0 @@ -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/src/strategy/mod.rs b/src/strategy/mod.rs deleted file mode 100644 index 9ec41bb..0000000 --- a/src/strategy/mod.rs +++ /dev/null @@ -1,3 +0,0 @@ -pub mod monte_carlo; -pub mod monte_carlo_tree; -pub mod static_opening; diff --git a/src/strategy/monte_carlo.rs b/src/strategy/monte_carlo.rs deleted file mode 100644 index adbb911..0000000 --- a/src/strategy/monte_carlo.rs +++ /dev/null @@ -1,505 +0,0 @@ -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/src/strategy/monte_carlo_tree.rs b/src/strategy/monte_carlo_tree.rs deleted file mode 100644 index 24b2088..0000000 --- a/src/strategy/monte_carlo_tree.rs +++ /dev/null @@ -1,243 +0,0 @@ -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/src/strategy/static_opening.rs b/src/strategy/static_opening.rs deleted file mode 100644 index f7e101c..0000000 --- a/src/strategy/static_opening.rs +++ /dev/null @@ -1,21 +0,0 @@ -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