Renamed variable to be more concise
[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 use arrayvec::ArrayVec;
11
12 use time::{Duration, PreciseTime};
13
14 #[cfg(not(feature = "single-threaded"))]
15 use rayon::prelude::*;
16
17 #[cfg(feature = "energy-cutoff")] pub const ENERGY_PRODUCTION_CUTOFF: u16 = 50;
18 #[cfg(feature = "energy-cutoff")] pub const ENERGY_STORAGE_CUTOFF: u16 = 120;
19
20 pub fn choose_move(state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Command {
21     let mut command_scores = CommandScore::init_command_scores(state);
22
23     let command = {
24         let best_command_score = simulate_options_to_timeout(&mut command_scores, state, start_time, max_time);
25         match best_command_score {
26             Some(best) if !best.starts_with_nothing => best.command,
27             _ => Command::Nothing
28         }
29     };
30
31     #[cfg(feature = "benchmarking")]
32     {
33         let total_iterations: u32 = command_scores.iter().map(|c| c.attempts).sum();
34         println!("Iterations: {}", total_iterations);
35     }
36     #[cfg(feature = "debug-decisions")]
37     {
38         debug_print_choices("ENERGY", &command_scores, |score| match score.command {
39             Command::Build(p, BuildingType::Energy) => Some((p, score.win_ratio())),
40             _ => None
41         });
42         debug_print_choices("ATTACK", &command_scores, |score| match score.command {
43             Command::Build(p, BuildingType::Attack) => Some((p, score.win_ratio())),
44             _ => None
45         });
46         debug_print_choices("DEFENCE", &command_scores, |score| match score.command {
47             Command::Build(p, BuildingType::Defence) => Some((p, score.win_ratio())),
48             _ => None
49         });
50         debug_print_choices("TESLA", &command_scores, |score| match score.command {
51             Command::Build(p, BuildingType::Tesla) => Some((p, score.win_ratio())),
52             _ => None
53         });
54         
55         println!("NOTHING");
56         println!("{}", command_scores.iter().find(|c| c.command == Command::Nothing).map(|s| s.win_ratio()).unwrap_or(0));
57         println!();
58
59         println!("IRON CURTAIN");
60         println!("{}", command_scores.iter().find(|c| c.command == Command::IronCurtain).map(|s| s.win_ratio()).unwrap_or(0));
61         println!();
62     }
63
64     command
65 }
66
67 #[cfg(feature = "debug-decisions")]
68 fn debug_print_choices<F: FnMut(&CommandScore) -> Option<(Point, i32)>>(label: &str, command_scores: &[CommandScore], extractor: F) {
69     println!("#+NAME: {}", label);
70     println!("#+PLOT: type:3d with:pm3d");
71     let relevant_moves: Vec<(Point, i32)>  = command_scores.iter()
72         .filter_map(extractor)
73         .collect();
74     for y in 0..MAP_HEIGHT {
75         for x in 0..SINGLE_MAP_WIDTH {
76             let point = Point::new(x, y);
77             let score = relevant_moves.iter().find(|(p, _)| *p == point);
78             print!(" | {}", score.map(|(_,s)| s).cloned().unwrap_or(0));
79         }
80         println!(" |");
81     }
82     println!();
83 }
84
85 #[cfg(not(feature = "discard-poor-performers"))]
86 fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
87     loop {
88         simulate_all_options_once(command_scores, state);
89         if start_time.to(PreciseTime::now()) > max_time {
90             break;
91         }
92     }
93     command_scores.iter().max_by_key(|&c| c.win_ratio())
94 }
95
96 #[cfg(feature = "discard-poor-performers")]
97 fn simulate_options_to_timeout<'a>(command_scores: &'a mut Vec<CommandScore>, state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Option<&'a CommandScore> {
98     use std::cmp;
99     let min_options = cmp::min(command_scores.len(), 5);
100     
101     let maxes = [max_time / 3, max_time * 2 / 3, max_time];
102     for (i, &max) in maxes.iter().enumerate() {
103         let new_length = cmp::max(min_options, command_scores.len() / (2usize.pow(i as u32)));
104         let active_scores = &mut command_scores[0..new_length];
105         loop {
106             simulate_all_options_once(active_scores, state);
107             if start_time.to(PreciseTime::now()) > max {
108                 break;
109             }
110         }
111         active_scores.sort_unstable_by_key(|c| -c.win_ratio());
112     }
113     command_scores.first()
114 }
115
116 #[cfg(feature = "single-threaded")]
117 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
118     command_scores.iter_mut()
119         .for_each(|score| {
120             let mut rng = XorShiftRng::from_seed(score.next_seed);
121             simulate_to_endstate(score, state, &mut rng);
122         });
123 }
124
125 #[cfg(not(feature = "single-threaded"))]
126 fn simulate_all_options_once(command_scores: &mut[CommandScore], state: &BitwiseGameState) {
127     command_scores.par_iter_mut()
128         .for_each(|score| {
129             let mut rng = XorShiftRng::from_seed(score.next_seed);
130             simulate_to_endstate(score, state, &mut rng);
131         });
132 }
133
134 fn simulate_to_endstate<R: Rng>(command_score: &mut CommandScore, state: &BitwiseGameState, rng: &mut R) {
135     let mut state_mut = state.clone();
136     
137     let mut status = GameStatus::Continue; //state_mut.simulate(command_score.command, opponent_first);
138     let mut first_move_made = false;
139     
140     for _ in 0..MAX_MOVES {
141         if status != GameStatus::Continue {
142             break;
143         }
144
145         let player_command = if first_move_made {
146             random_move(&state_mut.player, &state_mut.opponent, rng)
147         } else {
148             let do_nothing = command_score.command.cant_build_yet(state_mut.player.energy);
149             first_move_made = !do_nothing;
150             if do_nothing { Command::Nothing } else { command_score.command }
151         };
152         let opponent_command = random_move(&state_mut.opponent, &state_mut.player, rng);
153         status = state_mut.simulate(player_command, opponent_command);
154     }
155
156     let mut next_seed: [u8;16] = [0; 16];
157     rng.fill_bytes(&mut next_seed);
158     match status {
159         GameStatus::PlayerWon => command_score.add_victory(state_mut.player.count_towers() as i32 - state_mut.opponent.count_towers() as i32, next_seed),
160         GameStatus::OpponentWon => command_score.add_defeat(state_mut.opponent.count_towers() as i32 - state_mut.player.count_towers() as i32, next_seed),
161         GameStatus::Continue => command_score.add_stalemate(next_seed),
162         GameStatus::Draw => command_score.add_draw(next_seed)
163     }
164 }
165
166 #[cfg(feature = "heuristic-random")]
167 pub fn random_move<R: Rng>(player: &Player, opponent: &Player, rng: &mut R) -> Command {
168     lazy_static! {
169         static ref MOVES: [Command; NUMBER_OF_POSSIBLE_MOVES] = {
170             let mut m = [Command::Nothing; NUMBER_OF_POSSIBLE_MOVES];
171             m[1] = Command::IronCurtain;
172             let mut i = 2;
173             for b in &[BuildingType::Energy, BuildingType::Defence, BuildingType::Attack, BuildingType::Tesla] {
174                 for p in 0..NUMBER_OF_MAP_POSITIONS as u8 {
175                 let point = Point::new_index(p);
176                     m[i] = Command::Build(point, *b);
177                     i += 1;
178                 }
179             }
180             m
181         };
182     }
183
184     let mut cdf_other = [0; 2];
185     let mut cdf_energy = [0; NUMBER_OF_MAP_POSITIONS];
186     let mut cdf_defence = [0; NUMBER_OF_MAP_POSITIONS];
187     let mut cdf_attack = [0; NUMBER_OF_MAP_POSITIONS];
188     let mut cdf_tesla = [0; NUMBER_OF_MAP_POSITIONS];
189
190     let mut attack_metric_per_row = [0; MAP_HEIGHT as usize];
191     let mut defence_metric_per_row = [0; MAP_HEIGHT as usize];
192     for y in 0..MAP_HEIGHT {
193         let opponent_energy = opponent.count_energy_towers_in_row(y);
194         let opponent_attack = opponent.count_attack_towers_in_row(y);
195         let opponent_towers = opponent.count_towers_in_row(y);
196
197         let player_energy = player.count_energy_towers_in_row(y);
198         let player_attack = player.count_attack_towers_in_row(y);
199         let player_towers = player.count_towers_in_row(y);
200
201         defence_metric_per_row[y as usize] = if opponent_attack == 0 { 0 } else { opponent_attack + player_towers };
202         attack_metric_per_row[y as usize] = 8 + opponent_energy + opponent_towers + player_energy - player_attack;
203     }
204     
205
206     let mut other_end: u16 = 0;
207     // Nothing
208     {
209         let weight = if player.can_build_iron_curtain() && player.energy < IRON_CURTAIN_PRICE {
210             5
211         } else {
212             0
213         };
214         other_end += weight;
215         cdf_other[0] = other_end;
216     }
217     
218     // Iron Curtain
219     {
220         let weight = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE {
221             50
222         } else {
223             0
224         };
225         other_end += weight;
226         cdf_other[1] = other_end;
227     }
228
229     // Energy
230     let mut energy_end: u16 = other_end;
231     let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF ||
232         player.energy <= ENERGY_STORAGE_CUTOFF;
233     if needs_energy && player.energy >= ENERGY_PRICE {
234         for p in 0..NUMBER_OF_MAP_POSITIONS as u8 {
235             let point = Point::new_index(p);
236             let weight = if player.occupied & point.to_bitfield() != 0 {
237                 0
238             } else {
239                 2
240             };
241
242             energy_end += weight;
243             cdf_energy[p as usize] = energy_end;
244         }
245     }
246
247     // Defence
248     let mut defence_end: u16 = energy_end;
249     if player.energy >= DEFENCE_PRICE {
250         for p in 0..NUMBER_OF_MAP_POSITIONS as u8 {
251             let point = Point::new_index(p);
252             let y = usize::from(point.y());
253
254             let weight = if player.occupied & point.to_bitfield() != 0 || point.x() < 4 {
255                 0
256             } else {
257                 defence_metric_per_row[y]
258             };
259
260             defence_end += weight;
261             cdf_defence[p as usize] = defence_end;
262         }
263     }
264
265     // Attack
266     let mut attack_end: u16 = defence_end;
267     if player.energy >= MISSILE_PRICE {
268         for p in 0..NUMBER_OF_MAP_POSITIONS as u8 {
269             let point = Point::new_index(p);
270             let weight = if player.occupied & point.to_bitfield() != 0 {
271                 0
272             } else {
273                 let y = usize::from(point.y());
274                 attack_metric_per_row[y]
275             };
276
277             attack_end += weight;
278             cdf_attack[p as usize] = attack_end;
279         }
280     }
281
282     // Tesla
283     let mut tesla_end: u16 = attack_end;
284     let cant_tesla = player.has_max_teslas() || player.energy < TESLA_PRICE;
285     if !cant_tesla {
286         for p in 0..NUMBER_OF_MAP_POSITIONS as u8 {
287             let point = Point::new_index(p);
288             let weight = if (player.occupied & point.to_bitfield() != 0) || point.y() < 7 {
289                 0
290             } else {
291                 10
292             };
293
294             tesla_end += weight;
295             cdf_tesla[p as usize] = tesla_end;
296         }
297     }
298
299     let cumulative_distribution = tesla_end;
300
301     if cumulative_distribution == 0 {
302         return Command::Nothing;
303     }
304
305     let choice = rng.gen_range(0, cumulative_distribution);
306
307     let index = match choice {
308         c if c < other_end => cdf_other.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"),
309         c if c < energy_end => 2 + cdf_energy.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"),
310         c if c < defence_end => 2 + NUMBER_OF_MAP_POSITIONS + cdf_defence.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"),
311         c if c < attack_end => 2 + 2 * NUMBER_OF_MAP_POSITIONS + cdf_attack.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"),
312         _ => 2 + 3 * NUMBER_OF_MAP_POSITIONS + cdf_tesla.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"),
313     };
314
315     MOVES[index]
316 }
317
318 #[cfg(not(feature = "heuristic-random"))]
319 pub fn random_move<R: Rng>(player: &Player, _opponent: &Player, rng: &mut R) -> Command {
320     let free_positions_count = player.unoccupied_cell_count();
321
322     let open_building_spot = free_positions_count > 0;
323
324     let all_buildings = sensible_buildings(player, open_building_spot);
325
326     let iron_curtain_count = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE { 1 } else { 0 };
327     let nothing_count = 1;
328
329     let building_choice_index = rng.gen_range(0, all_buildings.len() + nothing_count + iron_curtain_count);
330
331     if building_choice_index < all_buildings.len() {
332         let position_choice = rng.gen_range(0, free_positions_count);
333         Command::Build(
334             player.location_of_unoccupied_cell(position_choice),
335             all_buildings[building_choice_index]
336         )
337     }
338     else if building_choice_index == all_buildings.len() {
339         Command::Nothing        
340     } else {
341         Command::IronCurtain
342     }
343 }
344
345 #[derive(Debug)]
346 struct CommandScore {
347     command: Command,
348     starts_with_nothing: bool,
349     victory_score: i32,
350     victories: u32,
351     defeat_score: i32,
352     defeats: u32,
353     draws: u32,
354     stalemates: u32,
355     attempts: u32,
356     next_seed: [u8; 16]
357 }
358
359 impl CommandScore {
360     fn new(command: Command, starts_with_nothing: bool) -> CommandScore {
361         CommandScore {
362             command, starts_with_nothing,
363             victory_score: 0,
364             victories: 0,
365             defeat_score: 0,
366             defeats: 0,
367             draws: 0,
368             stalemates: 0,
369             attempts: 0,
370             next_seed: INIT_SEED
371         }
372     }
373
374     fn add_victory(&mut self, weight: i32, next_seed: [u8; 16]) {
375         use std::cmp;
376         self.victory_score += cmp::max(weight, 1);
377         self.victories += 1;
378         self.attempts += 1;
379         self.next_seed = next_seed;
380     }
381
382     fn add_defeat(&mut self, weight: i32, next_seed: [u8; 16]) {
383         use std::cmp;
384         self.defeat_score += cmp::max(weight, 1);
385         self.defeats += 1;
386         self.attempts += 1;
387         self.next_seed = next_seed;
388     }
389
390     fn add_draw(&mut self, next_seed: [u8; 16]) {
391         self.draws += 1;
392         self.attempts += 1;
393         self.next_seed = next_seed;
394     }
395
396     fn add_stalemate(&mut self, next_seed: [u8; 16]) {
397         self.stalemates += 1;
398         self.attempts += 1;
399         self.next_seed = next_seed;
400     }
401
402     #[cfg(feature = "weighted-win-ratio")]
403     fn win_ratio(&self) -> i32 {
404         (self.victory_score - self.defeat_score) * 10000 / (self.attempts as i32)
405     }
406
407     #[cfg(not(feature = "weighted-win-ratio"))]
408     fn win_ratio(&self) -> i32 {
409         (self.victories as i32 - self.defeats as i32) * 10000 / (self.attempts as i32)
410     }
411
412     fn init_command_scores(state: &BitwiseGameState) -> Vec<CommandScore> {
413         let unoccupied_cells_count = state.player.unoccupied_cell_count();
414         let unoccupied_cells = (0..unoccupied_cells_count)
415             .map(|i| state.player.location_of_unoccupied_cell(i));
416         let energy_generated = state.player.energy_generated();
417
418         let mut all_buildings: ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> = ArrayVec::new();
419         if DEFENCE_PRICE <= state.player.energy {
420             all_buildings.push(BuildingType::Defence);
421         }
422         if MISSILE_PRICE <= state.player.energy {
423             all_buildings.push(BuildingType::Attack);
424         }
425         if ENERGY_PRICE <= state.player.energy {
426             all_buildings.push(BuildingType::Energy);
427         }
428         if !state.player.has_max_teslas() && (TESLA_PRICE.saturating_sub(state.player.energy) / energy_generated < 4) {
429             all_buildings.push(BuildingType::Tesla);
430         }
431         
432         let building_command_count = unoccupied_cells.len()*all_buildings.len();
433
434         let mut commands = Vec::with_capacity(building_command_count + 1);
435         let time_to_curtain_energy = (IRON_CURTAIN_PRICE.saturating_sub(state.player.energy) / energy_generated) as u8;
436         
437         if time_to_curtain_energy < 4 && state.player.can_build_iron_curtain_in(state.round, time_to_curtain_energy) {
438             commands.push(CommandScore::new(Command::IronCurtain, state.player.energy < IRON_CURTAIN_PRICE));
439         }
440
441         for position in unoccupied_cells {
442             for &building in &all_buildings {
443                 commands.push(CommandScore::new(Command::Build(position, building), building.cant_build_yet(state.player.energy)));
444             }
445         }
446
447         commands
448     }
449 }
450
451 impl fmt::Display for CommandScore {
452     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
453         write!(f, "{},{}", self.command, self.win_ratio())
454     }
455 }
456
457 #[cfg(all(not(feature = "heuristic-random"), not(feature = "energy-cutoff")))]
458 fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> {
459     let mut result = ArrayVec::new();
460     if !open_building_spot {
461         return result;
462     }
463
464     if DEFENCE_PRICE <= player.energy {
465         result.push(BuildingType::Defence);
466     }
467     if MISSILE_PRICE <= player.energy {
468         result.push(BuildingType::Attack);
469     }
470     if ENERGY_PRICE <= player.energy {
471         result.push(BuildingType::Energy);
472     }
473     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
474         result.push(BuildingType::Tesla);
475     }
476
477     result
478 }
479
480 #[cfg(all(not(feature = "heuristic-random"), feature = "energy-cutoff"))]
481 fn sensible_buildings(player: &Player, open_building_spot: bool) -> ArrayVec<[BuildingType; NUMBER_OF_BUILDING_TYPES]> {
482     let mut result = ArrayVec::new();
483     if !open_building_spot {
484         return result;
485     }
486
487     let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF ||
488         player.energy <= ENERGY_STORAGE_CUTOFF;
489
490     if DEFENCE_PRICE <= player.energy {
491         result.push(BuildingType::Defence);
492     }
493     if MISSILE_PRICE <= player.energy {
494         result.push(BuildingType::Attack);
495     }
496     if ENERGY_PRICE <= player.energy && needs_energy {
497         result.push(BuildingType::Energy);
498     }
499     if TESLA_PRICE <= player.energy && !player.has_max_teslas() {
500         result.push(BuildingType::Tesla);
501     }
502     
503     result
504 }
505