6176f1a41bdfe1b131981f1d7b6709c6cbc635d7
[entelect-challenge-tower-defence.git] / src / strategy / monte_carlo.rs
1 use engine::command::*;
2 use engine::status::GameStatus;
3 use engine::bitwise_engine::{Player, BitwiseGameState};
4 use engine::constants::*;
5 use engine::geometry::*;
6
7 use std::fmt;
8
9 use rand::{Rng, XorShiftRng, SeedableRng};
10
11 use arrayvec::ArrayVec;
12
13 const MAX_MOVES: u16 = 400;
14 const INIT_SEED: [u8;16] = [0x7b, 0x6a, 0xe1, 0xf4, 0x41, 0x3c, 0xe9, 0x0f, 0x67, 0x81, 0x67, 0x99, 0x77, 0x0a, 0x6b, 0xda];
15
16 use time::{Duration, PreciseTime};
17
18 #[cfg(not(feature = "single-threaded"))]
19 use rayon::prelude::*;
20
21 //TODO Rethink / adjust these?
22 #[cfg(feature = "energy-cutoff")] pub const ENERGY_PRODUCTION_CUTOFF: u16 = 50;
23 #[cfg(feature = "energy-cutoff")] pub const ENERGY_STORAGE_CUTOFF: u16 = 100;
24
25 pub fn choose_move(state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Command {
26     let mut command_scores = CommandScore::init_command_scores(state);
27
28     let command = {
29         let best_command_score = simulate_options_to_timeout(&mut command_scores, state, start_time, max_time);
30         match best_command_score {
31             Some(best) if !best.starts_with_nothing => best.command,
32             _ => Command::Nothing
33         }
34     };
35
36     #[cfg(feature = "benchmarking")]
37     {
38         let total_iterations: u32 = command_scores.iter().map(|c| c.attempts).sum();
39         println!("Iterations: {}", total_iterations);
40     }
41     #[cfg(feature = "debug-decisions")]
42     {
43         debug_print_choices("ENERGY", &command_scores, |score| match score.command {
44             Command::Build(p, BuildingType::Energy) => Some((p, score.win_ratio())),
45             _ => None
46         });
47         debug_print_choices("ATTACK", &command_scores, |score| match score.command {
48             Command::Build(p, BuildingType::Attack) => Some((p, score.win_ratio())),
49             _ => None
50         });
51         debug_print_choices("DEFENCE", &command_scores, |score| match score.command {
52             Command::Build(p, BuildingType::Defence) => Some((p, score.win_ratio())),
53             _ => None
54         });
55         debug_print_choices("TESLA", &command_scores, |score| match score.command {
56             Command::Build(p, BuildingType::Tesla) => Some((p, score.win_ratio())),
57             _ => None
58         });
59         
60         println!("NOTHING");
61         println!("{}", command_scores.iter().find(|c| c.command == Command::Nothing).map(|s| s.win_ratio()).unwrap_or(0));
62         println!("");
63
64         println!("IRON CURTAIN");
65         println!("{}", command_scores.iter().find(|c| c.command == Command::IronCurtain).map(|s| s.win_ratio()).unwrap_or(0));
66         println!("");
67     }
68
69     command
70 }
71
72 #[cfg(feature = "debug-decisions")]
73 fn debug_print_choices<F: FnMut(&CommandScore) -> Option<(Point, i32)>>(label: &str, command_scores: &[CommandScore], extractor: F) {
74     println!("#+NAME: {}", label);
75     println!("#+PLOT: type:3d with:pm3d");
76     let relevant_moves: Vec<(Point, i32)>  = command_scores.iter()
77         .filter_map(extractor)
78         .collect();
79     for y in 0..MAP_HEIGHT {
80         for x in 0..SINGLE_MAP_WIDTH {
81             let point = Point::new(x, y);
82             let score = relevant_moves.iter().find(|(p, _)| *p == point);
83             print!(" | {}", score.map(|(_,s)| s).cloned().unwrap_or(0));
84         }
85         println!(" |");
86     }
87     println!("");
88 }
89
90 #[cfg(not(feature = "discard-poor-performers"))]
91 fn simulate_options_to_timeout(command_scores: &'a mut Vec<CommandScore>, settings: &GameSettings, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
92     loop {
93         simulate_all_options_once(command_scores, settings, state);
94         if start_time.to(PreciseTime::now()) > max_time {
95             break;
96         }
97     }
98     command_scores.iter().max_by_key(|&c| c.win_ratio())
99 }
100
101 #[cfg(feature = "discard-poor-performers")]
102 fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
103     use std::cmp;
104     let min_options = cmp::min(command_scores.len(), 5);
105     
106     let maxes = [max_time / 4, max_time / 2, max_time * 3 / 4, max_time];
107     for (i, &max) in maxes.iter().enumerate() {
108         let new_length = cmp::max(min_options, command_scores.len() / (2usize.pow(i as u32)));
109         let active_scores = &mut command_scores[0..new_length];
110         loop {
111             simulate_all_options_once(active_scores, state);
112             if start_time.to(PreciseTime::now()) > max {
113                 break;
114             }
115         }
116         active_scores.sort_unstable_by_key(|c| -c.win_ratio());
117     }
118     command_scores.first()
119 }
120
121 #[cfg(feature = "single-threaded")]
122 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
123     command_scores.iter_mut()
124         .for_each(|score| {
125             let mut rng = XorShiftRng::from_seed(score.next_seed);
126             simulate_to_endstate(score, state, &mut rng);
127         });
128 }
129
130 #[cfg(not(feature = "single-threaded"))]
131 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
132     command_scores.par_iter_mut()
133         .for_each(|score| {
134             let mut rng = XorShiftRng::from_seed(score.next_seed);
135             simulate_to_endstate(score, state, &mut rng);
136         });
137 }
138
139 fn simulate_to_endstate<R: Rng>(command_score: &mut CommandScore, state: &BitwiseGameState, rng: &mut R) {
140     let mut state_mut = state.clone();
141     
142     let mut status = GameStatus::Continue; //state_mut.simulate(command_score.command, opponent_first);
143     let mut first_move_made = false;
144     
145     for _ in 0..MAX_MOVES {
146         if status != GameStatus::Continue {
147             break;
148         }
149
150         let player_command = if first_move_made {
151             random_move(&state_mut.player, rng)
152         } else {
153             let do_nothing = command_score.command.cant_build_yet(state_mut.player.energy);
154             first_move_made = !do_nothing;
155             if do_nothing { Command::Nothing } else { command_score.command }
156         };
157         let opponent_command = random_move(&state_mut.opponent, rng);
158         status = state_mut.simulate(player_command, opponent_command);
159     }
160
161     let mut next_seed: [u8;16] = [0; 16];
162     rng.fill_bytes(&mut next_seed);
163     match status {
164         GameStatus::PlayerWon => command_score.add_victory(next_seed),
165         GameStatus::OpponentWon => command_score.add_defeat(next_seed),
166         GameStatus::Continue => command_score.add_stalemate(next_seed),
167         GameStatus::Draw => command_score.add_draw(next_seed)
168     }
169 }
170
171 // TODO: This needs a decent heuristic play. Don't do nothing and
172 // target certain rows with missiles?
173 fn random_move<R: Rng>(player: &Player, rng: &mut R) -> Command {
174     let free_positions_count = player.unoccupied_cell_count();
175
176     let open_building_spot = free_positions_count > 0;
177
178     let all_buildings = sensible_buildings(player, open_building_spot);
179
180     let iron_curtain_count = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE { 1 } else { 0 };
181     let nothing_count = 1;
182
183     let building_choice_index = rng.gen_range(0, all_buildings.len() + nothing_count + iron_curtain_count);
184
185     if building_choice_index < all_buildings.len() {
186         let position_choice = rng.gen_range(0, free_positions_count);
187         Command::Build(
188             player.location_of_unoccupied_cell(position_choice),
189             all_buildings[building_choice_index]
190         )
191     }
192     else if building_choice_index == all_buildings.len() {
193         Command::Nothing        
194     } else {
195         Command::IronCurtain
196     }
197 }
198
199 #[derive(Debug)]
200 struct CommandScore {
201     command: Command,
202     starts_with_nothing: bool,
203     victories: u32,
204     defeats: u32,
205     draws: u32,
206     stalemates: u32,
207     attempts: u32,
208     next_seed: [u8; 16]
209 }
210
211 impl CommandScore {
212     fn new(command: Command, starts_with_nothing: bool) -> CommandScore {
213         CommandScore {
214             command, starts_with_nothing,
215             victories: 0,
216             defeats: 0,
217             draws: 0,
218             stalemates: 0,
219             attempts: 0,
220             next_seed: INIT_SEED
221         }
222     }
223
224     fn add_victory(&mut self, next_seed: [u8; 16]) {
225         self.victories += 1;
226         self.attempts += 1;
227         self.next_seed = next_seed;
228     }
229
230     fn add_defeat(&mut self, next_seed: [u8; 16]) {
231         self.defeats += 1;
232         self.attempts += 1;
233         self.next_seed = next_seed;
234     }
235
236     fn add_draw(&mut self, next_seed: [u8; 16]) {
237         self.draws += 1;
238         self.attempts += 1;
239         self.next_seed = next_seed;
240     }
241
242     fn add_stalemate(&mut self, next_seed: [u8; 16]) {
243         self.stalemates += 1;
244         self.attempts += 1;
245         self.next_seed = next_seed;
246     }
247
248     fn win_ratio(&self) -> i32 {
249         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
250     }
251
252     fn init_command_scores(state: &BitwiseGameState) -> Vec<CommandScore> {
253         let unoccupied_cells_count = state.player.unoccupied_cell_count();
254         let unoccupied_cells = (0..unoccupied_cells_count)
255             .map(|i| state.player.location_of_unoccupied_cell(i));
256         let energy_generated = state.player.energy_generated();
257
258         let mut all_buildings: ArrayVec<[BuildingType; 4]> = ArrayVec::new();
259         if DEFENCE_PRICE <= state.player.energy {
260             all_buildings.push(BuildingType::Defence);
261         }
262         if MISSILE_PRICE <= state.player.energy {
263             all_buildings.push(BuildingType::Attack);
264         }
265         if ENERGY_PRICE <= state.player.energy {
266             all_buildings.push(BuildingType::Energy);
267         }
268         if !state.player.has_max_teslas() && (TESLA_PRICE.saturating_sub(state.player.energy) / energy_generated < 4) {
269             all_buildings.push(BuildingType::Tesla);
270         }
271         
272         let building_command_count = unoccupied_cells.len()*all_buildings.len();
273         
274         let mut commands = Vec::with_capacity(building_command_count + 1);
275         if state.player.can_build_iron_curtain() && IRON_CURTAIN_PRICE.saturating_sub(state.player.energy) / energy_generated < 4 {
276             commands.push(CommandScore::new(Command::IronCurtain, state.player.energy < IRON_CURTAIN_PRICE));
277         }
278
279         for position in unoccupied_cells {
280             for &building in &all_buildings {
281                 commands.push(CommandScore::new(Command::Build(position, building), building.cant_build_yet(state.player.energy)));
282             }
283         }
284
285         commands
286     }
287 }
288
289 impl fmt::Display for CommandScore {
290     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
291         write!(f, "{},{}", self.command, self.win_ratio())
292     }
293 }
294
295 #[cfg(not(feature = "energy-cutoff"))]
296 fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType;4]> {
297     let mut result = ArrayVec::new();
298     if !open_building_spot {
299         return result;
300     }
301
302     if DEFENCE_PRICE <= player.energy {
303         result.push(BuildingType::Defence);
304     }
305     if MISSILE_PRICE <= player.energy {
306         result.push(BuildingType::Attack);
307     }
308     if ENERGY_PRICE <= player.energy {
309         result.push(BuildingType::Energy);
310     }
311     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
312         result.push(BuildingType::Tesla);
313     }
314
315     result
316 }
317
318 #[cfg(feature = "energy-cutoff")]
319 fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType;4]> {
320     let mut result = ArrayVec::new();
321     if !open_building_spot {
322         return result;
323     }
324
325     let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF ||
326         player.energy <= ENERGY_STORAGE_CUTOFF;
327
328     if DEFENCE_PRICE <= player.energy {
329         result.push(BuildingType::Defence);
330     }
331     if MISSILE_PRICE <= player.energy {
332         result.push(BuildingType::Attack);
333     }
334     if ENERGY_PRICE <= player.energy && needs_energy {
335         result.push(BuildingType::Energy);
336     }
337     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
338         result.push(BuildingType::Tesla);
339     }
340     
341     result
342 }
343