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