Most of the heuristic random move lookup structure
authorJustin Worthe <justin@worthe-it.co.za>
Fri, 31 Aug 2018 20:23:02 +0000 (22:23 +0200)
committerJustin Worthe <justin@worthe-it.co.za>
Fri, 31 Aug 2018 20:23:02 +0000 (22:23 +0200)
Cargo.toml
src/engine/command.rs
src/engine/constants.rs
src/engine/geometry.rs
src/lib.rs
src/strategy/monte_carlo.rs

index ab624cb..6f19b1c 100644 (file)
@@ -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"]
 
index 764e3cb..b34553f 100644 (file)
@@ -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]
     }
index 9ece36d..7d260e8 100644 (file)
@@ -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;
index 090652f..b9b556a 100644 (file)
@@ -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 {
index de8b120..6cd8730 100644 (file)
@@ -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;
index 2489c8a..952e2b1 100644 (file)
@@ -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;