Added initial seed on nothing move
[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         for score in command_scores {
41             println!("{}", score);
42         }
43     }
44
45     command
46 }
47
48 #[cfg(not(feature = "discard-poor-performers"))]
49 fn simulate_options_to_timeout(command_scores: &'a mut Vec<CommandScore>, settings: &GameSettings, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
50     loop {
51         simulate_all_options_once(command_scores, settings, state);
52         if start_time.to(PreciseTime::now()) > max_time {
53             break;
54         }
55     }
56     command_scores.iter().max_by_key(|&c| c.win_ratio())
57 }
58
59 #[cfg(feature = "discard-poor-performers")]
60 fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
61     use std::cmp;
62     let min_options = cmp::min(command_scores.len(), 5);
63     
64     let maxes = [max_time / 4, max_time / 2, max_time * 3 / 4, max_time];
65     for (i, &max) in maxes.iter().enumerate() {
66         let new_length = cmp::max(min_options, command_scores.len() / (2usize.pow(i as u32)));
67         let active_scores = &mut command_scores[0..new_length];
68         loop {
69             simulate_all_options_once(active_scores, state);
70             if start_time.to(PreciseTime::now()) > max {
71                 break;
72             }
73         }
74         active_scores.sort_unstable_by_key(|c| -c.win_ratio());
75     }
76     command_scores.first()
77 }
78
79 #[cfg(feature = "single-threaded")]
80 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
81     command_scores.iter_mut()
82         .for_each(|score| {
83             let mut rng = XorShiftRng::from_seed(score.next_seed);
84             simulate_to_endstate(score, state, &mut rng);
85         });
86 }
87
88 #[cfg(not(feature = "single-threaded"))]
89 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
90     command_scores.par_iter_mut()
91         .for_each(|score| {
92             let mut rng = XorShiftRng::from_seed(score.next_seed);
93             simulate_to_endstate(score, state, &mut rng);
94         });
95 }
96
97 fn simulate_to_endstate<R: Rng>(command_score: &mut CommandScore, state: &BitwiseGameState, rng: &mut R) {
98     let mut state_mut = state.clone();
99     
100     let opponent_first = random_move(&state_mut.opponent, rng);
101     let mut status = state_mut.simulate(command_score.command, opponent_first);
102     
103     for _ in 0..MAX_MOVES {
104         if status != GameStatus::Continue {
105             break;
106         }
107
108         let player_command = random_move(&state_mut.player, rng);
109         let opponent_command = random_move(&state_mut.opponent, rng);
110         status = state_mut.simulate(player_command, opponent_command);
111     }
112
113     let mut next_seed: [u8;16] = [0; 16];
114     rng.fill_bytes(&mut next_seed);
115     match status {
116         GameStatus::PlayerWon => command_score.add_victory(next_seed),
117         GameStatus::OpponentWon => command_score.add_defeat(next_seed),
118         GameStatus::Continue => command_score.add_stalemate(next_seed),
119         GameStatus::Draw => command_score.add_draw(next_seed)
120     }
121 }
122
123 fn random_move<R: Rng>(player: &Player, rng: &mut R) -> Command {
124     let all_buildings = sensible_buildings(player);
125     let free_positions_count = player.unoccupied_cell_count();
126     
127     let nothing_count = if all_buildings.len() > 2 && free_positions_count > 0 { 0 } else { 1 };
128     let iron_curtain_count = if player.can_build_iron_curtain() { 1 } else { 0 };
129         
130     let building_choice_index = rng.gen_range(0, all_buildings.len() + nothing_count + iron_curtain_count);
131
132     if building_choice_index < all_buildings.len() && free_positions_count > 0 {
133         let position_choice = rng.gen_range(0, free_positions_count);
134         Command::Build(
135             player.location_of_unoccupied_cell(position_choice),
136             all_buildings[building_choice_index]
137         )
138     }
139     else if iron_curtain_count > 0 && building_choice_index == all_buildings.len() {
140         Command::IronCurtain
141     } else {
142         Command::Nothing
143     }
144 }
145
146 #[derive(Debug)]
147 struct CommandScore {
148     command: Command,
149     victories: u32,
150     defeats: u32,
151     draws: u32,
152     stalemates: u32,
153     attempts: u32,
154     next_seed: [u8; 16]
155 }
156
157 impl CommandScore {
158     fn new(command: Command) -> CommandScore {
159         CommandScore {
160             command,
161             victories: 0,
162             defeats: 0,
163             draws: 0,
164             stalemates: 0,
165             attempts: 0,
166             next_seed: INIT_SEED
167         }
168     }
169
170     fn with_seeded_stalemate(command: Command) -> CommandScore {
171         CommandScore {
172             command,
173             victories: 0,
174             defeats: 0,
175             draws: 0,
176             stalemates: 0,
177             attempts: 1,
178             next_seed: INIT_SEED
179         }
180     }
181
182     fn add_victory(&mut self, next_seed: [u8; 16]) {
183         self.victories += 1;
184         self.attempts += 1;
185         self.next_seed = next_seed;
186     }
187
188     fn add_defeat(&mut self, next_seed: [u8; 16]) {
189         self.defeats += 1;
190         self.attempts += 1;
191         self.next_seed = next_seed;
192     }
193
194     fn add_draw(&mut self, next_seed: [u8; 16]) {
195         self.draws += 1;
196         self.attempts += 1;
197         self.next_seed = next_seed;
198     }
199
200     fn add_stalemate(&mut self, next_seed: [u8; 16]) {
201         self.stalemates += 1;
202         self.attempts += 1;
203         self.next_seed = next_seed;
204     }
205
206     fn win_ratio(&self) -> i32 {
207         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
208     }
209
210     fn init_command_scores(state: &BitwiseGameState) -> Vec<CommandScore> {
211         let all_buildings = sensible_buildings(&state.player);
212
213         let unoccupied_cells = (0..state.player.unoccupied_cell_count()).map(|i| state.player.location_of_unoccupied_cell(i));
214
215         let building_command_count = unoccupied_cells.len()*all_buildings.len();
216         
217         let mut commands = Vec::with_capacity(building_command_count + 2);
218         commands.push(CommandScore::with_seeded_stalemate(Command::Nothing));
219         if state.player.can_build_iron_curtain() {
220             commands.push(CommandScore::new(Command::IronCurtain));
221         }
222
223         for position in unoccupied_cells {
224             for &building in &all_buildings {
225                 commands.push(CommandScore::new(Command::Build(position, building)));
226             }
227         }
228
229         commands
230     }
231 }
232
233 impl fmt::Display for CommandScore {
234     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
235         write!(f, "{},{}", self.command, self.win_ratio())
236     }
237 }
238
239
240 #[cfg(not(feature = "energy-cutoff"))]
241 fn sensible_buildings(player: &Player) -> Vec<BuildingType> {
242     let mut result = Vec::with_capacity(4);
243
244     if DEFENCE_PRICE <= player.energy {
245         result.push(BuildingType::Defence);
246     }
247     if MISSILE_PRICE <= player.energy {
248         result.push(BuildingType::Attack);
249     }
250     if ENERGY_PRICE <= player.energy {
251         result.push(BuildingType::Energy);
252     }
253     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
254         result.push(BuildingType::Tesla);
255     }
256
257     result
258 }
259
260 //TODO: Heuristic that avoids building the initial energy towers all in the same row? Max energy in a row?
261 #[cfg(feature = "energy-cutoff")]
262 fn sensible_buildings(player: &Player) -> Vec<BuildingType> {
263     let mut result = Vec::with_capacity(4);
264     let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF ||
265         player.energy <= ENERGY_STORAGE_CUTOFF;
266
267     if DEFENCE_PRICE <= player.energy {
268         result.push(BuildingType::Defence);
269     }
270     if MISSILE_PRICE <= player.energy {
271         result.push(BuildingType::Attack);
272     }
273     if ENERGY_PRICE <= player.energy && needs_energy {
274         result.push(BuildingType::Energy);
275     }
276     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
277         result.push(BuildingType::Tesla);
278     }
279     
280     result
281 }
282