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