From a737142562c57a53a54bed76ef4d37794c79f44d Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sun, 2 Sep 2018 16:52:41 +0200 Subject: A bit more performance tweaking on CDF. Broke into smaller more cache friendly arrays. --- src/strategy/monte_carlo.rs | 140 ++++++++++++++++++++++++-------------------- 1 file changed, 78 insertions(+), 62 deletions(-) (limited to 'src/strategy') diff --git a/src/strategy/monte_carlo.rs b/src/strategy/monte_carlo.rs index 0587e31..0acaaae 100644 --- a/src/strategy/monte_carlo.rs +++ b/src/strategy/monte_carlo.rs @@ -185,95 +185,104 @@ fn random_move(player: &Player, opponent: &Player, rng: &mut R) -> Comma }; } - let mut cdf = [0; NUMBER_OF_POSSIBLE_MOVES]; - let mut cumulative_distribution: u32 = 0; + let mut cdf_other = [0; 2]; + let mut cdf_energy = [0; NUMBER_OF_MAP_POSITIONS]; + let mut cdf_defence = [0; NUMBER_OF_MAP_POSITIONS]; + let mut cdf_attack = [0; NUMBER_OF_MAP_POSITIONS]; + let mut cdf_tesla = [0; NUMBER_OF_MAP_POSITIONS]; + + let mut other_end: u32 = 0; // Nothing { - let weight = 0; - cumulative_distribution += weight; - cdf[0] = cumulative_distribution; + let weight = 1; + other_end += weight; + cdf_other[0] = other_end; } // Iron Curtain { let weight = if player.can_build_iron_curtain() && player.energy >= IRON_CURTAIN_PRICE { - 20 + 30 } else { 0 }; - cumulative_distribution += weight; - cdf[1] = cumulative_distribution; + other_end += weight; + cdf_other[1] = other_end; } // Energy - let e_base = 2; + let mut energy_end: u32 = other_end; let needs_energy = player.energy_generated() <= ENERGY_PRODUCTION_CUTOFF || player.energy <= ENERGY_STORAGE_CUTOFF; - for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { - let i = e_base + p as usize; - let point = Point::new_index(p); - let weight = if !needs_energy || player.energy < ENERGY_PRICE || player.occupied & point.to_either_bitfield() != 0 { - 0 - } else if point.x() < 2 { - 2 - } else { - 1 - }; - - cumulative_distribution += weight; - cdf[i] = cumulative_distribution; + if needs_energy && player.energy >= ENERGY_PRICE { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if player.occupied & point.to_either_bitfield() != 0 { + 0 + } else if point.x() < 2 { + 2 + } else { + 1 + }; + + energy_end += weight; + cdf_energy[p as usize] = energy_end; + } } // Defence - let d_base = e_base + NUMBER_OF_MAP_POSITIONS; - for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { - let i = d_base + p as usize; - let point = Point::new_index(p); - let weight = if player.energy < DEFENCE_PRICE || player.occupied & point.to_either_bitfield() != 0 { - 0 - } else { - //TODO: Favour the front and rows with something to defend - opponent.count_attack_towers_in_row(point.y()) - }; - - cumulative_distribution += weight; - cdf[i] = cumulative_distribution; + let mut defence_end: u32 = energy_end; + if player.energy >= DEFENCE_PRICE { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if player.occupied & point.to_either_bitfield() != 0 { + 0 + } else { + //TODO: Favour the front and rows with something to defend + opponent.count_attack_towers_in_row(point.y()) + }; + + defence_end += weight; + cdf_defence[p as usize] = defence_end; + } } // Attack - let a_base = d_base + NUMBER_OF_MAP_POSITIONS; - for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { - let i = a_base + p as usize; - let point = Point::new_index(p); - let weight = if player.energy < MISSILE_PRICE || player.occupied & point.to_either_bitfield() != 0 { - 0 - } else { - // TODO: take into account opponent attacks and defence in row? - 8 + opponent.count_energy_towers_in_row(point.y()) - player.count_attack_towers_in_row(point.y()) - }; - - cumulative_distribution += weight; - cdf[i] = cumulative_distribution; + let mut attack_end: u32 = defence_end; + if player.energy >= MISSILE_PRICE { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if player.occupied & point.to_either_bitfield() != 0 { + 0 + } else { + // TODO: take into account opponent attacks and defence in row? + 8 + opponent.count_energy_towers_in_row(point.y()) - player.count_attack_towers_in_row(point.y()) + }; + + attack_end += weight; + cdf_attack[p as usize] = attack_end; + } } // Tesla - let t_base = a_base + NUMBER_OF_MAP_POSITIONS; + let mut tesla_end: u32 = attack_end; let cant_tesla = player.has_max_teslas() || player.energy < TESLA_PRICE; - for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { - let i = t_base + p as usize; - let point = Point::new_index(p); - let weight = if cant_tesla || (player.occupied & point.to_either_bitfield() != 0) || point.y() < 7 { - 0 - } else { - 2 - }; - - cumulative_distribution += weight; - cdf[i] = cumulative_distribution; + if !cant_tesla { + for p in 0..NUMBER_OF_MAP_POSITIONS as u8 { + let point = Point::new_index(p); + let weight = if (player.occupied & point.to_either_bitfield() != 0) || point.y() < 7 { + 0 + } else { + 2 + }; + + tesla_end += weight; + cdf_tesla[p as usize] = tesla_end; + } } - debug_assert_eq!(MOVES.len(), t_base + NUMBER_OF_MAP_POSITIONS); + let cumulative_distribution = tesla_end; if cumulative_distribution == 0 { return Command::Nothing; @@ -282,7 +291,14 @@ fn random_move(player: &Player, opponent: &Player, rng: &mut R) -> Comma let choice = rng.gen_range(0, cumulative_distribution); // TODO can this be a more efficient lookup? - let index = cdf.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"); + + let index = match choice { + c if c < other_end => cdf_other.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + c if c < energy_end => 2 + cdf_energy.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + c if c < defence_end => 2 + NUMBER_OF_MAP_POSITIONS + cdf_defence.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + 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"), + _ => 2 + 3 * NUMBER_OF_MAP_POSITIONS + cdf_tesla.iter().position(|&c| c > choice).expect("Random number has exceeded cumulative distribution"), + }; MOVES[index] } -- cgit v1.2.3