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