3dc94ebe7aacede41a49928e81ecf5ff7728b38d
[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     
21     loop {
22         #[cfg(feature = "single-threaded")]
23         {
24             command_scores.iter_mut()
25                 .for_each(|score| {
26                     let mut rng = XorShiftRng::from_seed(score.next_seed);
27                     simulate_to_endstate(score, settings, state, &mut rng);
28                 });
29         }
30         #[cfg(not(feature = "single-threaded"))]
31         {
32             command_scores.par_iter_mut()
33                 .for_each(|score| {
34                     let mut rng = XorShiftRng::from_seed(score.next_seed);
35                     simulate_to_endstate(score, settings, state, &mut rng);
36                 });
37         }
38         if start_time.to(PreciseTime::now()) > max_time {
39             break;
40         }
41     }
42
43     let command = command_scores.iter().max_by_key(|&c| c.win_ratio());
44
45     #[cfg(feature = "benchmarking")]
46     {
47         let total_iterations: u32 = command_scores.iter().map(|c| c.attempts).sum();
48         println!("Iterations: {}", total_iterations);
49     }
50     
51     match command {
52         Some(command) => command.command,
53         _ => Command::Nothing
54     }
55 }
56
57 fn simulate_to_endstate<R: Rng, GS: GameState>(command_score: &mut CommandScore, settings: &GameSettings, state: &GS, rng: &mut R) {
58     let mut state_mut = state.clone();
59     
60     let opponent_first = random_opponent_move(settings, &state_mut, rng);
61     let mut status = state_mut.simulate(settings, command_score.command, opponent_first);
62     
63     for _ in 0..MAX_MOVES {
64         if status != GameStatus::Continue {
65             break;
66         }
67
68         let player_command = random_player_move(settings, &state_mut, rng);
69         let opponent_command = random_opponent_move(settings, &state_mut, rng);
70         status = state_mut.simulate(settings, player_command, opponent_command);
71     }
72
73     let next_seed = [rng.next_u32(), rng.next_u32(), rng.next_u32(), rng.next_u32()];
74     match status {
75         GameStatus::PlayerWon => command_score.add_victory(next_seed),
76         GameStatus::OpponentWon => command_score.add_defeat(next_seed),
77         GameStatus::Continue => command_score.add_stalemate(next_seed),
78         GameStatus::Draw => command_score.add_draw(next_seed)
79     }
80 }
81
82 fn random_player_move<R: Rng, GS: GameState>(settings: &GameSettings, state: &GS, rng: &mut R) -> Command {
83     let all_buildings = sensible_buildings(settings, &state.player(), state.player_has_max_teslas());
84     random_move(&all_buildings, rng, state.unoccupied_player_cell_count(), |i| state.location_of_unoccupied_player_cell(i))
85 }
86
87 fn random_opponent_move<R: Rng, GS: GameState>(settings: &GameSettings, state: &GS, rng: &mut R) -> Command {
88     let all_buildings = sensible_buildings(settings, &state.opponent(), state.opponent_has_max_teslas());
89     random_move(&all_buildings, rng, state.unoccupied_opponent_cell_count(), |i| state.location_of_unoccupied_opponent_cell(i))
90 }
91
92 fn random_move<R: Rng, F:Fn(usize)->Point>(all_buildings: &[BuildingType], rng: &mut R, free_positions_count: usize, get_point: F) -> Command {
93     let building_command_count = free_positions_count*all_buildings.len();
94     let nothing_count = 1;
95
96     let number_of_commands = building_command_count + nothing_count;
97     
98     let choice_index = rng.gen_range(0, number_of_commands);
99
100     if choice_index == number_of_commands - 1 {
101         Command::Nothing
102     } else {
103         Command::Build(
104             get_point(choice_index/all_buildings.len()),
105             all_buildings[choice_index%all_buildings.len()]
106         )
107     }
108 }
109
110 #[derive(Debug)]
111 struct CommandScore {
112     command: Command,
113     victories: u32,
114     defeats: u32,
115     draws: u32,
116     stalemates: u32,
117     attempts: u32,
118     next_seed: [u32; 4]
119 }
120
121 impl CommandScore {
122     fn new(command: Command) -> CommandScore {
123         CommandScore {
124             command,
125             victories: 0,
126             defeats: 0,
127             draws: 0,
128             stalemates: 0,
129             attempts: 0,
130             next_seed: [0x7b6a_e1f4, 0x413c_e90f, 0x6781_6799, 0x770a_6bda]
131         }
132     }
133
134     fn add_victory(&mut self, next_seed: [u32; 4]) {
135         self.victories += 1;
136         self.attempts += 1;
137         self.next_seed = next_seed;
138     }
139
140     fn add_defeat(&mut self, next_seed: [u32; 4]) {
141         self.defeats += 1;
142         self.attempts += 1;
143         self.next_seed = next_seed;
144     }
145
146     fn add_draw(&mut self, next_seed: [u32; 4]) {
147         self.draws += 1;
148         self.attempts += 1;
149         self.next_seed = next_seed;
150     }
151
152     fn add_stalemate(&mut self, next_seed: [u32; 4]) {
153         self.stalemates += 1;
154         self.attempts += 1;
155         self.next_seed = next_seed;
156     }
157
158     fn win_ratio(&self) -> i32 {
159         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
160     }
161     
162     fn init_command_scores<GS: GameState>(settings: &GameSettings, state: &GS) -> Vec<CommandScore> {
163         let all_buildings = sensible_buildings(settings, &state.player(), state.player_has_max_teslas());
164
165         let unoccupied_cells = (0..state.unoccupied_player_cell_count()).map(|i| state.location_of_unoccupied_player_cell(i));
166
167         let building_command_count = unoccupied_cells.len()*all_buildings.len();
168         let nothing_count = 1;
169         
170         let mut commands = Vec::with_capacity(building_command_count + nothing_count);
171         commands.push(CommandScore::new(Command::Nothing));
172
173         for position in unoccupied_cells {
174             for &building in &all_buildings {
175                 commands.push(CommandScore::new(Command::Build(position, building)));
176             }
177         }
178
179         commands
180     }
181 }
182
183 #[cfg(not(feature = "energy-cutoff"))]
184 fn sensible_buildings(settings: &GameSettings, player: &Player, has_max_teslas: bool) -> Vec<BuildingType> {
185     let mut result = Vec::with_capacity(4);
186     for b in BuildingType::all().iter() {
187         let building_setting = settings.building_settings(*b);
188         let affordable = building_setting.price <= player.energy;
189         let is_tesla = *b == BuildingType::Tesla;
190         if affordable && (!is_tesla || !has_max_teslas) {
191             result.push(*b);
192         }
193     }
194     result
195 }
196
197
198 #[cfg(feature = "energy-cutoff")]
199 fn sensible_buildings(settings: &GameSettings, player: &Player, has_max_teslas: bool) -> Vec<BuildingType> {
200     let mut result = Vec::with_capacity(4);
201     let needs_energy = player.energy_generated <= ENERGY_PRODUCTION_CUTOFF ||
202         player.energy <= ENERGY_STORAGE_CUTOFF;
203     
204     for b in BuildingType::all().iter() {
205         let building_setting = settings.building_settings(*b);
206         let affordable = building_setting.price <= player.energy;
207         let energy_producing = building_setting.energy_generated_per_turn > 0;
208         let is_tesla = *b == BuildingType::Tesla;
209         if affordable && (!energy_producing || needs_energy) && (!is_tesla || !has_max_teslas) {
210             result.push(*b);
211         }
212     }
213     result
214 }
215