Fixed min and benchmark logging in discarding search
[entelect-challenge-tower-defence.git] / src / strategy / monte_carlo.rs
1 use engine::settings::GameSettings;
2 use engine::command::*;
3 use engine::geometry::*;
4 use engine::{GameState, GameStatus, Player};
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 = 30;
16 #[cfg(feature = "energy-cutoff")] pub const ENERGY_STORAGE_CUTOFF: u16 = 45;
17
18 pub fn choose_move<GS: GameState>(settings: &GameSettings, state: &GS, start_time: &PreciseTime, max_time: Duration) -> Command {
19     let mut command_scores = CommandScore::init_command_scores(settings, state);
20     let command = simulate_options_to_timeout(&mut command_scores, settings, 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<'a, GS: GameState>(command_scores: &'a mut Vec<CommandScore>, settings: &GameSettings, state: &GS, 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, GS: GameState>(command_scores: &'a mut Vec<CommandScore>, settings: &GameSettings, state: &GS, 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, settings, 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<GS: GameState>(command_scores: &mut[CommandScore], settings: &GameSettings, state: &GS) {
75     command_scores.iter_mut()
76         .for_each(|score| {
77             let mut rng = XorShiftRng::from_seed(score.next_seed);
78             simulate_to_endstate(score, settings, state, &mut rng);
79         });
80 }
81
82 #[cfg(not(feature = "single-threaded"))]
83 fn simulate_all_options_once<GS: GameState>(command_scores: &mut[CommandScore], settings: &GameSettings, state: &GS) {
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, settings, state, &mut rng);
88         });
89 }
90
91 fn simulate_to_endstate<R: Rng, GS: GameState>(command_score: &mut CommandScore, settings: &GameSettings, state: &GS, rng: &mut R) {
92     let mut state_mut = state.clone();
93     
94     let opponent_first = random_opponent_move(settings, &state_mut, rng);
95     let mut status = state_mut.simulate(settings, 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_player_move(settings, &state_mut, rng);
103         let opponent_command = random_opponent_move(settings, &state_mut, rng);
104         status = state_mut.simulate(settings, 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 fn random_player_move<R: Rng, GS: GameState>(settings: &GameSettings, state: &GS, rng: &mut R) -> Command {
117     let all_buildings = sensible_buildings(settings, &state.player(), state.player_has_max_teslas());
118     random_move(&all_buildings, rng, state.unoccupied_player_cell_count(), |i| state.location_of_unoccupied_player_cell(i))
119 }
120
121 fn random_opponent_move<R: Rng, GS: GameState>(settings: &GameSettings, state: &GS, rng: &mut R) -> Command {
122     let all_buildings = sensible_buildings(settings, &state.opponent(), state.opponent_has_max_teslas());
123     random_move(&all_buildings, rng, state.unoccupied_opponent_cell_count(), |i| state.location_of_unoccupied_opponent_cell(i))
124 }
125
126 fn random_move<R: Rng, F:Fn(usize)->Point>(all_buildings: &[BuildingType], rng: &mut R, free_positions_count: usize, get_point: F) -> Command {
127     let building_command_count = free_positions_count*all_buildings.len();
128     let nothing_count = 1;
129
130     let number_of_commands = building_command_count + nothing_count;
131     
132     let choice_index = rng.gen_range(0, number_of_commands);
133
134     if choice_index == number_of_commands - 1 {
135         Command::Nothing
136     } else {
137         Command::Build(
138             get_point(choice_index/all_buildings.len()),
139             all_buildings[choice_index%all_buildings.len()]
140         )
141     }
142 }
143
144 #[derive(Debug)]
145 struct CommandScore {
146     command: Command,
147     victories: u32,
148     defeats: u32,
149     draws: u32,
150     stalemates: u32,
151     attempts: u32,
152     next_seed: [u32; 4]
153 }
154
155 impl CommandScore {
156     fn new(command: Command) -> CommandScore {
157         CommandScore {
158             command,
159             victories: 0,
160             defeats: 0,
161             draws: 0,
162             stalemates: 0,
163             attempts: 0,
164             next_seed: [0x7b6a_e1f4, 0x413c_e90f, 0x6781_6799, 0x770a_6bda]
165         }
166     }
167
168     fn add_victory(&mut self, next_seed: [u32; 4]) {
169         self.victories += 1;
170         self.attempts += 1;
171         self.next_seed = next_seed;
172     }
173
174     fn add_defeat(&mut self, next_seed: [u32; 4]) {
175         self.defeats += 1;
176         self.attempts += 1;
177         self.next_seed = next_seed;
178     }
179
180     fn add_draw(&mut self, next_seed: [u32; 4]) {
181         self.draws += 1;
182         self.attempts += 1;
183         self.next_seed = next_seed;
184     }
185
186     fn add_stalemate(&mut self, next_seed: [u32; 4]) {
187         self.stalemates += 1;
188         self.attempts += 1;
189         self.next_seed = next_seed;
190     }
191
192     fn win_ratio(&self) -> i32 {
193         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
194     }
195     
196     fn init_command_scores<GS: GameState>(settings: &GameSettings, state: &GS) -> Vec<CommandScore> {
197         let all_buildings = sensible_buildings(settings, &state.player(), state.player_has_max_teslas());
198
199         let unoccupied_cells = (0..state.unoccupied_player_cell_count()).map(|i| state.location_of_unoccupied_player_cell(i));
200
201         let building_command_count = unoccupied_cells.len()*all_buildings.len();
202         let nothing_count = 1;
203         
204         let mut commands = Vec::with_capacity(building_command_count + nothing_count);
205         commands.push(CommandScore::new(Command::Nothing));
206
207         for position in unoccupied_cells {
208             for &building in &all_buildings {
209                 commands.push(CommandScore::new(Command::Build(position, building)));
210             }
211         }
212
213         commands
214     }
215 }
216
217 #[cfg(not(feature = "energy-cutoff"))]
218 fn sensible_buildings(settings: &GameSettings, player: &Player, has_max_teslas: bool) -> Vec<BuildingType> {
219     let mut result = Vec::with_capacity(4);
220     for b in BuildingType::all().iter() {
221         let building_setting = settings.building_settings(*b);
222         let affordable = building_setting.price <= player.energy;
223         let is_tesla = *b == BuildingType::Tesla;
224         if affordable && (!is_tesla || !has_max_teslas) {
225             result.push(*b);
226         }
227     }
228     result
229 }
230
231
232 #[cfg(feature = "energy-cutoff")]
233 fn sensible_buildings(settings: &GameSettings, player: &Player, has_max_teslas: bool) -> Vec<BuildingType> {
234     let mut result = Vec::with_capacity(4);
235     let needs_energy = player.energy_generated <= ENERGY_PRODUCTION_CUTOFF ||
236         player.energy <= ENERGY_STORAGE_CUTOFF;
237     
238     for b in BuildingType::all().iter() {
239         let building_setting = settings.building_settings(*b);
240         let affordable = building_setting.price <= player.energy;
241         let energy_producing = building_setting.energy_generated_per_turn > 0;
242         let is_tesla = *b == BuildingType::Tesla;
243         if affordable && (!energy_producing || needs_energy) && (!is_tesla || !has_max_teslas) {
244             result.push(*b);
245         }
246     }
247     result
248 }
249