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