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