Added targeted waiting to evaluated moves
[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 fn random_move<R: Rng>(player: &Player, rng: &mut R) -> Command {
172     let free_positions_count = player.unoccupied_cell_count();
173
174     let open_building_spot = free_positions_count > 0;
175
176     let all_buildings = sensible_buildings(player, open_building_spot);
177
178     let iron_curtain_count = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE { 1 } else { 0 };
179     let nothing_count = 1;
180
181     let building_choice_index = rng.gen_range(0, all_buildings.len() + nothing_count + iron_curtain_count);
182
183     if building_choice_index < all_buildings.len() {
184         let position_choice = rng.gen_range(0, free_positions_count);
185         Command::Build(
186             player.location_of_unoccupied_cell(position_choice),
187             all_buildings[building_choice_index]
188         )
189     }
190     else if building_choice_index == all_buildings.len() {
191         Command::Nothing        
192     } else {
193         Command::IronCurtain
194     }
195 }
196
197 #[derive(Debug)]
198 struct CommandScore {
199     command: Command,
200     starts_with_nothing: bool,
201     victories: u32,
202     defeats: u32,
203     draws: u32,
204     stalemates: u32,
205     attempts: u32,
206     next_seed: [u8; 16]
207 }
208
209 impl CommandScore {
210     fn new(command: Command, starts_with_nothing: bool) -> CommandScore {
211         CommandScore {
212             command, starts_with_nothing,
213             victories: 0,
214             defeats: 0,
215             draws: 0,
216             stalemates: 0,
217             attempts: 0,
218             next_seed: INIT_SEED
219         }
220     }
221
222     fn add_victory(&mut self, next_seed: [u8; 16]) {
223         self.victories += 1;
224         self.attempts += 1;
225         self.next_seed = next_seed;
226     }
227
228     fn add_defeat(&mut self, next_seed: [u8; 16]) {
229         self.defeats += 1;
230         self.attempts += 1;
231         self.next_seed = next_seed;
232     }
233
234     fn add_draw(&mut self, next_seed: [u8; 16]) {
235         self.draws += 1;
236         self.attempts += 1;
237         self.next_seed = next_seed;
238     }
239
240     fn add_stalemate(&mut self, next_seed: [u8; 16]) {
241         self.stalemates += 1;
242         self.attempts += 1;
243         self.next_seed = next_seed;
244     }
245
246     fn win_ratio(&self) -> i32 {
247         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
248     }
249
250     fn init_command_scores(state: &BitwiseGameState) -> Vec<CommandScore> {
251         let unoccupied_cells_count = state.player.unoccupied_cell_count();
252         let unoccupied_cells = (0..unoccupied_cells_count)
253             .map(|i| state.player.location_of_unoccupied_cell(i));
254
255         let all_buildings = [BuildingType::Defence, BuildingType::Attack, BuildingType::Energy, BuildingType::Tesla];
256
257         let building_command_count = unoccupied_cells.len()*all_buildings.len();
258         
259         let mut commands = Vec::with_capacity(building_command_count + 1);
260         if state.player.can_build_iron_curtain() {
261             commands.push(CommandScore::new(Command::IronCurtain, state.player.energy < IRON_CURTAIN_PRICE));
262         }
263
264         for position in unoccupied_cells {
265             for &building in &all_buildings {
266                 commands.push(CommandScore::new(Command::Build(position, building), building.cant_build_yet(state.player.energy)));
267             }
268         }
269
270         commands
271     }
272 }
273
274 impl fmt::Display for CommandScore {
275     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
276         write!(f, "{},{}", self.command, self.win_ratio())
277     }
278 }
279
280
281 #[cfg(not(feature = "energy-cutoff"))]
282 fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType;4]> {
283     let mut result = ArrayVec::new();
284     if !open_building_spot {
285         return result;
286     }
287
288     if DEFENCE_PRICE <= player.energy {
289         result.push(BuildingType::Defence);
290     }
291     if MISSILE_PRICE <= player.energy {
292         result.push(BuildingType::Attack);
293     }
294     if ENERGY_PRICE <= player.energy {
295         result.push(BuildingType::Energy);
296     }
297     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
298         result.push(BuildingType::Tesla);
299     }
300
301     result
302 }
303
304 #[cfg(feature = "energy-cutoff")]
305 fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType;4]> {
306     let mut result = ArrayVec::new();
307     if !open_building_spot {
308         return result;
309     }
310
311     let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF ||
312         player.energy <= ENERGY_STORAGE_CUTOFF;
313
314     if DEFENCE_PRICE <= player.energy {
315         result.push(BuildingType::Defence);
316     }
317     if MISSILE_PRICE <= player.energy {
318         result.push(BuildingType::Attack);
319     }
320     if ENERGY_PRICE <= player.energy && needs_energy {
321         result.push(BuildingType::Energy);
322     }
323     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
324         result.push(BuildingType::Tesla);
325     }
326     
327     result
328 }
329