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