Removed unused import
[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 rand::{Rng, XorShiftRng, SeedableRng};
7
8 const MAX_MOVES: u16 = 400;
9
10 use time::{Duration, PreciseTime};
11
12 #[cfg(not(feature = "single-threaded"))]
13 use rayon::prelude::*;
14
15 #[cfg(feature = "energy-cutoff")] pub const ENERGY_PRODUCTION_CUTOFF: u16 = 100;
16 #[cfg(feature = "energy-cutoff")] pub const ENERGY_STORAGE_CUTOFF: u16 = 100;
17
18 pub fn choose_move(state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Command {
19     let mut command_scores = CommandScore::init_command_scores(state);
20     let command = simulate_options_to_timeout(&mut command_scores, state, start_time, max_time);
21     
22     match command {
23         Some(command) => command.command,
24         _ => Command::Nothing
25     }
26 }
27
28 #[cfg(not(feature = "discard-poor-performers"))]
29 fn simulate_options_to_timeout(command_scores: &'a mut Vec<CommandScore>, settings: &GameSettings, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
30     loop {
31         simulate_all_options_once(command_scores, settings, state);
32         if start_time.to(PreciseTime::now()) > max_time {
33             break;
34         }
35     }
36
37     #[cfg(feature = "benchmarking")]
38     {
39         let total_iterations: u32 = command_scores.iter().map(|c| c.attempts).sum();
40         println!("Iterations: {}", total_iterations);
41     }
42
43     command_scores.iter().max_by_key(|&c| c.win_ratio())
44 }
45
46 #[cfg(feature = "discard-poor-performers")]
47 fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
48     use std::cmp;
49     let min_options = cmp::min(command_scores.len(), 5);
50     
51     let maxes = [max_time / 4, max_time / 2, max_time * 3 / 4, max_time];
52     for (i, &max) in maxes.iter().enumerate() {
53         let new_length = cmp::max(min_options, command_scores.len() / (2usize.pow(i as u32)));
54         let active_scores = &mut command_scores[0..new_length];
55         loop {
56             simulate_all_options_once(active_scores, state);
57             if start_time.to(PreciseTime::now()) > max {
58                 break;
59             }
60         }
61         active_scores.sort_unstable_by_key(|c| -c.win_ratio());
62     }
63
64     #[cfg(feature = "benchmarking")]
65     {
66         let total_iterations: u32 = command_scores.iter().map(|c| c.attempts).sum();
67         println!("Iterations: {}", total_iterations);
68     }
69
70     command_scores.first()
71 }
72
73 #[cfg(feature = "single-threaded")]
74 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
75     command_scores.iter_mut()
76         .for_each(|score| {
77             let mut rng = XorShiftRng::from_seed(score.next_seed);
78             simulate_to_endstate(score, state, &mut rng);
79         });
80 }
81
82 #[cfg(not(feature = "single-threaded"))]
83 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
84     command_scores.par_iter_mut()
85         .for_each(|score| {
86             let mut rng = XorShiftRng::from_seed(score.next_seed);
87             simulate_to_endstate(score, state, &mut rng);
88         });
89 }
90
91 fn simulate_to_endstate<R: Rng>(command_score: &mut CommandScore, state: &BitwiseGameState, rng: &mut R) {
92     let mut state_mut = state.clone();
93     
94     let opponent_first = random_move(&state_mut.opponent, rng);
95     let mut status = state_mut.simulate(command_score.command, opponent_first);
96     
97     for _ in 0..MAX_MOVES {
98         if status != GameStatus::Continue {
99             break;
100         }
101
102         let player_command = random_move(&state_mut.player, rng);
103         let opponent_command = random_move(&state_mut.opponent, rng);
104         status = state_mut.simulate(player_command, opponent_command);
105     }
106
107     let next_seed = [rng.next_u32(), rng.next_u32(), rng.next_u32(), rng.next_u32()];
108     match status {
109         GameStatus::PlayerWon => command_score.add_victory(next_seed),
110         GameStatus::OpponentWon => command_score.add_defeat(next_seed),
111         GameStatus::Continue => command_score.add_stalemate(next_seed),
112         GameStatus::Draw => command_score.add_draw(next_seed)
113     }
114 }
115
116 // TODO: Given enough energy, most opponents won't do nothing
117 fn random_move<R: Rng>(player: &Player, rng: &mut R) -> Command {
118     let all_buildings = sensible_buildings(player);
119     let nothing_count = 1;
120     let iron_curtain_count = if player.can_build_iron_curtain() { 1 } else { 0 };
121     let free_positions_count = player.unoccupied_cell_count();
122         
123     let building_choice_index = rng.gen_range(0, all_buildings.len() + nothing_count + iron_curtain_count);
124     
125     if building_choice_index == all_buildings.len() {
126         Command::Nothing
127     } else if iron_curtain_count > 0 && building_choice_index == all_buildings.len() + 1 {
128         Command::IronCurtain
129     } else if free_positions_count > 0 {
130         let position_choice = rng.gen_range(0, free_positions_count);
131         Command::Build(
132             player.location_of_unoccupied_cell(position_choice),
133             all_buildings[building_choice_index]
134         )
135     } else {
136         Command::Nothing
137     }
138 }
139
140 #[derive(Debug)]
141 struct CommandScore {
142     command: Command,
143     victories: u32,
144     defeats: u32,
145     draws: u32,
146     stalemates: u32,
147     attempts: u32,
148     next_seed: [u32; 4]
149 }
150
151 impl CommandScore {
152     fn new(command: Command) -> CommandScore {
153         CommandScore {
154             command,
155             victories: 0,
156             defeats: 0,
157             draws: 0,
158             stalemates: 0,
159             attempts: 0,
160             next_seed: [0x7b6a_e1f4, 0x413c_e90f, 0x6781_6799, 0x770a_6bda]
161         }
162     }
163
164     fn add_victory(&mut self, next_seed: [u32; 4]) {
165         self.victories += 1;
166         self.attempts += 1;
167         self.next_seed = next_seed;
168     }
169
170     fn add_defeat(&mut self, next_seed: [u32; 4]) {
171         self.defeats += 1;
172         self.attempts += 1;
173         self.next_seed = next_seed;
174     }
175
176     fn add_draw(&mut self, next_seed: [u32; 4]) {
177         self.draws += 1;
178         self.attempts += 1;
179         self.next_seed = next_seed;
180     }
181
182     fn add_stalemate(&mut self, next_seed: [u32; 4]) {
183         self.stalemates += 1;
184         self.attempts += 1;
185         self.next_seed = next_seed;
186     }
187
188     fn win_ratio(&self) -> i32 {
189         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
190     }
191
192     //TODO: Devalue nothing so that it doesn't stand and do nothing when it can do things
193     fn init_command_scores(state: &BitwiseGameState) -> Vec<CommandScore> {
194         let all_buildings = sensible_buildings(&state.player);
195
196         let unoccupied_cells = (0..state.player.unoccupied_cell_count()).map(|i| state.player.location_of_unoccupied_cell(i));
197
198         let building_command_count = unoccupied_cells.len()*all_buildings.len();
199         
200         let mut commands = Vec::with_capacity(building_command_count + 2);
201         commands.push(CommandScore::new(Command::Nothing));
202         if state.player.can_build_iron_curtain() {
203             commands.push(CommandScore::new(Command::IronCurtain));
204         }
205
206         for position in unoccupied_cells {
207             for &building in &all_buildings {
208                 commands.push(CommandScore::new(Command::Build(position, building)));
209             }
210         }
211
212         commands
213     }
214 }
215
216 #[cfg(not(feature = "energy-cutoff"))]
217 fn sensible_buildings(player: &Player) -> Vec<BuildingType> {
218     let mut result = Vec::with_capacity(4);
219
220     if DEFENCE_PRICE <= player.energy {
221         result.push(BuildingType::Defence);
222     }
223     if MISSILE_PRICE <= player.energy {
224         result.push(BuildingType::Attack);
225     }
226     if ENERGY_PRICE <= player.energy {
227         result.push(BuildingType::Energy);
228     }
229     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
230         result.push(BuildingType::Tesla);
231     }
232
233     result
234 }
235
236
237 //TODO: Heuristic that avoids building the initial energy towers all in the same row? Max energy in a row?
238 //TODO: Update cutoff to maybe build iron curtains
239 #[cfg(feature = "energy-cutoff")]
240 fn sensible_buildings(player: &Player) -> Vec<BuildingType> {
241     let mut result = Vec::with_capacity(4);
242     let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF ||
243         player.energy <= ENERGY_STORAGE_CUTOFF;
244
245     if DEFENCE_PRICE <= player.energy {
246         result.push(BuildingType::Defence);
247     }
248     if MISSILE_PRICE <= player.energy {
249         result.push(BuildingType::Attack);
250     }
251     if ENERGY_PRICE <= player.energy && needs_energy {
252         result.push(BuildingType::Energy);
253     }
254     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
255         result.push(BuildingType::Tesla);
256     }
257     
258     result
259 }
260