diff options
author | Justin Worthe <justin@worthe-it.co.za> | 2018-08-31 22:23:02 +0200 |
---|---|---|
committer | Justin Worthe <justin@worthe-it.co.za> | 2018-08-31 22:23:02 +0200 |
commit | 6f2f6ce1e5d53a2344a26862eb05e4e12bfabe1a (patch) | |
tree | ba21e33fa137c987a8489e30bbadba38d0b157bf | |
parent | 82230e9f67dbebb3a0a608a53bca05aa38a5f501 (diff) |
Most of the heuristic random move lookup structure
-rw-r--r-- | Cargo.toml | 4 | ||||
-rw-r--r-- | src/engine/command.rs | 2 | ||||
-rw-r--r-- | src/engine/constants.rs | 5 | ||||
-rw-r--r-- | src/engine/geometry.rs | 6 | ||||
-rw-r--r-- | src/lib.rs | 4 | ||||
-rw-r--r-- | src/strategy/monte_carlo.rs | 46 |
6 files changed, 52 insertions, 15 deletions
@@ -13,6 +13,8 @@ rayon = "1.0.2" arrayvec = "0.4.7" +lazy_static = { version = "1.1.0", optional = true } + [dev-dependencies] proptest = "0.8.4" @@ -25,7 +27,7 @@ extended-time = [] energy-cutoff = [] discard-poor-performers = [] -heuristic-random = [] +heuristic-random = ["lazy_static"] default = ["energy-cutoff", "discard-poor-performers"] diff --git a/src/engine/command.rs b/src/engine/command.rs index 764e3cb..b34553f 100644 --- a/src/engine/command.rs +++ b/src/engine/command.rs @@ -42,7 +42,7 @@ pub enum BuildingType { } impl BuildingType { - pub fn all() -> [BuildingType; 4] { + pub fn all() -> [BuildingType; NUMBER_OF_BUILDING_TYPES] { use self::BuildingType::*; [Defence, Attack, Energy, Tesla] } diff --git a/src/engine/constants.rs b/src/engine/constants.rs index 9ece36d..7d260e8 100644 --- a/src/engine/constants.rs +++ b/src/engine/constants.rs @@ -35,6 +35,11 @@ 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(feature = "reduced-time"))] #[cfg(not(feature = "extended-time"))] pub const MAX_TIME_MILLIS: i64 = 1950; diff --git a/src/engine/geometry.rs b/src/engine/geometry.rs index 090652f..b9b556a 100644 --- a/src/engine/geometry.rs +++ b/src/engine/geometry.rs @@ -17,6 +17,12 @@ impl Point { } } + 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_either_bitfield(); if (x >= SINGLE_MAP_WIDTH) == is_left_player { @@ -11,6 +11,10 @@ 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/strategy/monte_carlo.rs b/src/strategy/monte_carlo.rs index 2489c8a..952e2b1 100644 --- a/src/strategy/monte_carlo.rs +++ b/src/strategy/monte_carlo.rs @@ -168,18 +168,38 @@ fn simulate_to_endstate<R: Rng>(command_score: &mut CommandScore, state: &Bitwis } } -// TODO -// 1. Have a (static) array of all moves. Even invalid ones. ALL -// 2. Create a new CDF array, same size. -// 3. Loop moves -// 3.1. Compute PDF for move. Invalid moves are 0. -// 3.2. Add to last CDF value and stick in array -// 4. Generate random number uniformly, 0 to CDF max -// 5. Binary search to find random number in CDF array. Min index where CDF[index] > random -// 6. Lookup move in static array #[cfg(feature = "heuristic-random")] fn random_move<R: Rng>(player: &Player, rng: &mut R) -> Command { - Command::Nothing + lazy_static! { + static ref MOVES: Vec<Command> = { + let mut m = Vec::with_capacity(NUMBER_OF_POSSIBLE_MOVES); + m.push(Command::IronCurtain); + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + for b in [BuildingType::Energy, BuildingType::Defence, BuildingType::Attack, BuildingType::Tesla].iter() { + m.push(Command::Build(point, *b)); + } + } + m + }; + } + + let mut cdf = Vec::with_capacity(NUMBER_OF_POSSIBLE_MOVES); + let mut cumulative_distribution: u32 = 0; + for m in MOVES.iter() { + // TODO: Heuristic here. Invalid moves are 0. Higher is more likely. + let weight = 1; + + cumulative_distribution += weight; + cdf.push(cumulative_distribution); + } + + let choice = rng.gen_range(0, cumulative_distribution); + + // TODO: Binary search here. Find choice in cdf. + let index = 0; + + MOVES[index].clone() } #[cfg(not(feature = "heuristic-random"))] @@ -268,7 +288,7 @@ impl CommandScore { .map(|i| state.player.location_of_unoccupied_cell(i)); let energy_generated = state.player.energy_generated(); - let mut all_buildings: ArrayVec<[BuildingType; 4]> = ArrayVec::new(); + let mut all_buildings: ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> = ArrayVec::new(); if DEFENCE_PRICE <= state.player.energy { all_buildings.push(BuildingType::Defence); } @@ -306,7 +326,7 @@ impl fmt::Display for CommandScore { } #[cfg(not(feature = "energy-cutoff"))] -fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType;4]> { +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; @@ -329,7 +349,7 @@ fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[Bu } #[cfg(feature = "energy-cutoff")] -fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType;4]> { +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; |