summaryrefslogtreecommitdiff
path: root/2017-battleships/src/knowledge.rs
diff options
context:
space:
mode:
Diffstat (limited to '2017-battleships/src/knowledge.rs')
-rw-r--r--2017-battleships/src/knowledge.rs504
1 files changed, 504 insertions, 0 deletions
diff --git a/2017-battleships/src/knowledge.rs b/2017-battleships/src/knowledge.rs
new file mode 100644
index 0000000..4a66e8b
--- /dev/null
+++ b/2017-battleships/src/knowledge.rs
@@ -0,0 +1,504 @@
+use actions::*;
+use ships::*;
+use state::*;
+use math::*;
+
+use std::collections::HashMap;
+use std::cmp::Ordering;
+
+#[derive(Serialize, Deserialize, Clone, Debug)]
+pub struct Knowledge {
+ pub last_action: Action,
+ pub opponent_map: OpponentMapKnowledge,
+ pub map_size: u16,
+ pub available_weapons: Vec<Weapon>,
+ pub shootable_weapons: Vec<Weapon>,
+ pub charging_weapons: HashMap<Weapon, u16>
+}
+
+impl Knowledge {
+ pub fn new(map_size: u16, action: Action) -> Knowledge {
+ Knowledge {
+ last_action: action,
+ opponent_map: OpponentMapKnowledge::new(map_size),
+ map_size: map_size,
+ available_weapons: Vec::new(),
+ shootable_weapons: Vec::new(),
+ charging_weapons: HashMap::new()
+ }
+ }
+
+ pub fn with_action(&self, action: Action) -> Knowledge {
+ Knowledge {
+ last_action: action,
+ ..self.clone()
+ }
+ }
+
+ pub fn resolve_last_action(&self, state: &State) -> Knowledge {
+ let mut new_knowledge = self.clone();
+
+ let energy = state.player_map.energy;
+ let mut available_weapons: Vec<_> = state.player_map.ships.iter()
+ .filter(|&(_, ship_data)| !ship_data.destroyed)
+ .flat_map(|(ship, _)| ship.weapons())
+ .collect();
+
+ available_weapons.sort_by_key(|weapon| format!("{}",weapon));
+ available_weapons.dedup();
+ new_knowledge.available_weapons = available_weapons;
+
+ new_knowledge.shootable_weapons = new_knowledge.available_weapons.iter()
+ .filter(|weapon| weapon.energy_cost(state.map_size) <= energy)
+ .cloned()
+ .collect();
+
+ new_knowledge.charging_weapons = new_knowledge.available_weapons.iter()
+ .filter(|weapon| weapon.energy_cost(state.map_size) > energy)
+ .map(|weapon| (weapon.clone(), weapon.single_shot_rounds_to_ready(energy, state.map_size)))
+ .collect();
+
+ let (hits, misses, _) = match self.last_action {
+ Action::PlaceShips(_) => {
+ (vec!(), vec!(), vec!())
+ },
+ Action::Shoot(Weapon::SeekerMissle, p) => {
+ Knowledge::seeker_hits_and_misses(p, &state)
+ }
+
+ Action::Shoot(w, p) => {
+ Knowledge::to_hits_and_misses(w.affected_cells(p, state.map_size), &state)
+ }
+ };
+
+ let sunk_ships = new_knowledge.opponent_map.update_sunk_ships(&state);
+
+ new_knowledge.opponent_map.update_from_shot(hits, misses, sunk_ships);
+
+ new_knowledge
+ }
+
+ fn to_hits_and_misses(points: Vec<Point>, state: &State) -> (Vec<Point>, Vec<Point>, Vec<Point>) {
+ let hits = points.iter().filter(|p| state.opponent_map.cells[p.x as usize][p.y as usize].damaged).cloned().collect();
+ let misses = points.iter().filter(|p| state.opponent_map.cells[p.x as usize][p.y as usize].missed).cloned().collect();
+ let unknown = points.iter().filter(|p| !state.opponent_map.cells[p.x as usize][p.y as usize].missed && !state.opponent_map.cells[p.x as usize][p.y as usize].damaged).cloned().collect();
+
+ (hits, misses, unknown)
+ }
+
+ fn seeker_hits_and_misses(p: Point, state: &State) -> (Vec<Point>, Vec<Point>, Vec<Point>) {
+ let mut misses: Vec<Point> = Vec::new();
+ let mut hits: Vec<Point> = Vec::new();
+
+ let rings = vec!(
+ vec!(
+ //0
+ Some(p)
+ ),
+ vec!(
+ //1
+ p.move_point(Direction::North, 1, state.map_size),
+ p.move_point(Direction::East, 1, state.map_size),
+ p.move_point(Direction::South, 1, state.map_size),
+ p.move_point(Direction::West, 1, state.map_size),
+ ),
+ vec!(
+ //1.44
+ p.move_point(Direction::NorthEast, 1, state.map_size),
+ p.move_point(Direction::SouthEast, 1, state.map_size),
+ p.move_point(Direction::NorthWest, 1, state.map_size),
+ p.move_point(Direction::SouthWest, 1, state.map_size)
+ ),
+ vec!(
+ //2
+ p.move_point(Direction::North, 2, state.map_size),
+ p.move_point(Direction::East, 2, state.map_size),
+ p.move_point(Direction::South, 2, state.map_size),
+ p.move_point(Direction::West, 2, state.map_size),
+ )
+ );
+
+ //start in the center. Add rings, until I find a hit
+ //don't add more after a hit is found
+ for ring in rings {
+ if hits.is_empty() {
+ let (mut new_hits, mut new_misses, mut unknown) = Knowledge::to_hits_and_misses(ring.iter().filter_map(|&p| p).collect::<Vec<_>>(), &state);
+ misses.append(&mut new_misses);
+ if !new_hits.is_empty() {
+ hits.append(&mut new_hits);
+ } else {
+ misses.append(&mut unknown);
+ }
+ }
+ }
+
+ (hits, misses, vec!())
+ }
+
+ pub fn has_unknown_hits(&self) -> bool {
+ self.opponent_map.cells.iter().fold(false, |acc, x| {
+ x.iter().fold(acc, |acc, y| acc || y.unknown_hit())
+ })
+ }
+
+ pub fn get_best_adjacent_shots(&self) -> Vec<Point> {
+ let unknown_hits = self.opponent_map.cells_with_unknown_hits();
+ let adjacent_cells = self.opponent_map.adjacent_unshot_cells(&unknown_hits);
+
+ let possible_placements = self.opponent_map.possible_placements();
+
+ let mut max_score = 1;
+ let mut best_cells = Vec::new();
+
+ for placement in possible_placements {
+ for &cell in &adjacent_cells {
+ let score = placement.count_hit_cells(cell, &unknown_hits);
+ if score > max_score {
+ max_score = score;
+ best_cells = vec!(cell);
+ }
+ else if score == max_score {
+ best_cells.push(cell);
+ }
+ }
+ }
+
+ best_cells
+ }
+
+ pub fn get_best_seek_shots(&self) -> (Weapon, Vec<Point>) {
+ let possible_placements = self.opponent_map.possible_placements();
+ // let lattice = self.lattice_size(); //TODO use the lattice still?
+
+ let guaranteed_hits = self.get_points_that_touch_all_possibilities_on_unsunk_ship();
+ if !guaranteed_hits.is_empty() {
+ return (Weapon::SingleShot, guaranteed_hits);
+ }
+
+ let mut best_shots: HashMap<Weapon, (Vec<Point>, usize)> = HashMap::new();
+
+ for &weapon in self.available_weapons.iter() {
+ let mut current_best_score = 1;
+ let mut best_cells = Vec::new();
+
+ for target in self.opponent_map.flat_cell_position_list() {
+ let cells = if weapon == Weapon::SeekerMissle {
+ let full_range = weapon.affected_cells(target, self.map_size);
+ let has_hits = full_range.iter().any(|p| self.opponent_map.cells[p.x as usize][p.y as usize].hit);
+ if has_hits {
+ vec!()
+ }
+ else {
+ full_range
+ }
+ }
+ else {
+ weapon.affected_cells(target, self.map_size)
+ .iter()
+ .filter(|p| !self.opponent_map.cells[p.x as usize][p.y as usize].hit)
+ .cloned()
+ .collect()
+ };
+
+ let possibilities = possible_placements.iter()
+ .filter(|placement| placement.touches_any_point(&cells))
+ .count();
+
+ if possibilities > current_best_score {
+ current_best_score = possibilities;
+ best_cells = vec!(target);
+ }
+ else if possibilities == current_best_score {
+ best_cells.push(target);
+ }
+ }
+
+ best_shots.insert(weapon, (best_cells, current_best_score));
+ }
+
+ let best_single: Option<(Weapon, (Vec<Point>, usize))> =
+ best_shots.get(&Weapon::SingleShot).map(|x| (Weapon::SingleShot, x.clone()));
+
+ let best: (Weapon, (Vec<Point>, usize)) =
+ best_shots.iter()
+ .max_by(|&(weapon_a, &(_, score_a)), &(weapon_b, &(_, score_b))| {
+ let score = score_a.cmp(&score_b);
+ let cost = weapon_a.energy_cost(self.map_size).cmp(&weapon_b.energy_cost(self.map_size));
+ if score == Ordering::Equal { cost } else { score }
+ })
+ .and_then(|(&weapon, x)| {
+ if self.shootable_weapons.contains(&weapon) {
+ Some((weapon, x.clone()))
+ } else {
+ best_single
+ }
+ })
+ .unwrap_or((Weapon::SingleShot, (vec!(), 0)));
+
+
+ (best.0.clone(), (best.1).0)
+ }
+
+ fn get_points_that_touch_all_possibilities_on_unsunk_ship(&self) -> Vec<Point> {
+ self.opponent_map.flat_cell_position_list().iter().cloned().filter(|&point| {
+ self.opponent_map.ships.values()
+ .any(|ref ship| !ship.destroyed &&
+ ship.possible_placements.iter().all(|placement| {
+ placement.touches_point(point)
+ }))
+ }).collect()
+ }
+
+ fn lattice_size(&self) -> u16 {
+ let any_long_ships = self.opponent_map.ships.iter()
+ .any(|(ship, knowledge)| ship.length() >= 4 && !knowledge.destroyed);
+ if any_long_ships {
+ 4
+ }
+ else {
+ 2
+ }
+ }
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug)]
+pub struct OpponentMapKnowledge {
+ pub ships: HashMap<Ship, OpponentShipKnowledge>,
+ pub cells: Vec<Vec<KnowledgeCell>>
+}
+
+impl OpponentMapKnowledge {
+ fn new(map_size: u16) -> OpponentMapKnowledge {
+ let mut cells = Vec::with_capacity(map_size as usize);
+ for x in 0..map_size {
+ cells.push(Vec::with_capacity(map_size as usize));
+ for y in 0..map_size {
+ cells[x as usize].push(KnowledgeCell::new(x, y));
+ }
+ }
+
+ let ships = Ship::all_types().iter()
+ .map(|s| (s.clone(), OpponentShipKnowledge::new(s.clone(), map_size)))
+ .collect::<HashMap<_, _>>();
+
+ OpponentMapKnowledge {
+ ships: ships,
+ cells: cells
+ }
+ }
+
+ fn update_sunk_ships(&mut self, state: &State) -> Vec<Ship> {
+ let sunk_ships = self.ships.iter()
+ .filter(|&(_, x)| !x.destroyed)
+ .filter(|&(s, _)| state.opponent_map.ships.get(s).map(|x| x.destroyed) == Some(true))
+ .map(|(s, _)| s.clone())
+ .collect();
+
+ for &ship in &sunk_ships {
+ self.ships.get_mut(&ship).map(|ref mut ship_knowledge| ship_knowledge.destroyed = true);
+ }
+
+ sunk_ships
+ }
+
+ fn update_from_shot(&mut self, hit_cells: Vec<Point>, missed_cells: Vec<Point>, sunk_ships: Vec<Ship>) {
+ for &missed in &missed_cells {
+ self.cells[missed.x as usize][missed.y as usize].missed = true;
+ }
+ for &hit in &hit_cells {
+ self.cells[hit.x as usize][hit.y as usize].hit = true;
+ }
+
+ self.clear_sunk_ship_impossible_placements(&sunk_ships, &hit_cells);
+
+ let mut more_changes = true;
+ while more_changes {
+ more_changes = self.derive_ship_positions() || self.clear_impossible_placements();
+ }
+ }
+
+ fn derive_ship_positions(&mut self) -> bool {
+ let mut any_changes = false;
+ for knowledge in self.ships.values() {
+ if knowledge.possible_placements.len() == 1 {
+ let ref true_placement = knowledge.possible_placements[0];
+ for p in true_placement.points_on_ship() {
+ if self.cells[p.x as usize][p.y as usize].known_ship == None {
+ self.cells[p.x as usize][p.y as usize].known_ship = Some(true_placement.ship);
+ any_changes = true;
+ }
+ }
+ }
+ }
+ any_changes
+ }
+
+ fn clear_impossible_placements(&mut self) -> bool {
+ let mut any_changes = false;
+ let ref cells = self.cells;
+ for knowledge in self.ships.values_mut() {
+ let before = knowledge.possible_placements.len();
+ knowledge.possible_placements.retain(|x| x.all_could_be_hits(&cells));
+ let after = knowledge.possible_placements.len();
+ if before != after {
+ any_changes = true;
+ }
+ }
+ any_changes
+ }
+
+ fn clear_sunk_ship_impossible_placements(&mut self, sunk_ships: &Vec<Ship>, must_touch_any: &Vec<Point>) {
+ let cells_copy = self.cells.clone();
+
+ for knowledge in self.ships.values_mut() {
+ knowledge.possible_placements.retain(|x| !sunk_ships.contains(&x.ship) || (x.touches_any_point(&must_touch_any) && x.all_are_hits(&cells_copy)));
+ }
+ }
+
+ fn cells_with_unknown_hits(&self) -> Vec<Point> {
+ self.cells.iter().flat_map(|x| {
+ x.iter().filter(|y| y.unknown_hit()).map(|y| y.position)
+ }).collect()
+ }
+
+ fn adjacent_unshot_cells(&self, cells: &Vec<Point>) -> Vec<Point> {
+ self.cells.iter().flat_map(|x| {
+ x.iter()
+ .filter(|y| !y.shot_attempted())
+ .map(|y| y.position)
+ .filter(|&y| cells.iter().any(|z| z.is_adjacent(y)))
+ }).collect()
+ }
+
+ fn flat_cell_position_list(&self) -> Vec<Point> {
+ self.cells.iter().flat_map(|x| {
+ x.iter().map(|y| y.position)
+ }).collect()
+ }
+
+ fn cells_on_lattice(&self, lattice_size: u16) -> Vec<Point> {
+ self.cells.iter().flat_map(|x| {
+ x.iter()
+ .filter(|y| !y.shot_attempted() && y.position.is_on_lattice(lattice_size))
+ .map(|y| y.position)
+ }).collect()
+ }
+
+ fn possible_placements(&self) -> Vec<PossibleShipPlacement> {
+ self.ships
+ .values()
+ .flat_map(|knowledge| knowledge.possible_placements.clone())
+ .collect()
+ }
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug)]
+pub struct OpponentShipKnowledge {
+ pub ship: Ship,
+ pub destroyed: bool,
+ pub possible_placements: Vec<PossibleShipPlacement>
+}
+
+impl OpponentShipKnowledge {
+ fn new(ship: Ship, map_size: u16) -> OpponentShipKnowledge {
+ OpponentShipKnowledge {
+ ship: ship,
+ destroyed: false,
+ possible_placements: PossibleShipPlacement::enumerate(ship, map_size)
+ }
+ }
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug)]
+pub struct PossibleShipPlacement {
+ pub ship: Ship,
+ pub direction: Direction,
+ pub position: Point
+}
+
+impl PossibleShipPlacement {
+ fn enumerate(ship: Ship, map_size: u16) -> Vec<PossibleShipPlacement> {
+ (0..(map_size-ship.length()+1)).flat_map(move |par| {
+ (0..map_size).flat_map(move |per| {
+ vec!(
+ PossibleShipPlacement {
+ ship: ship,
+ direction: Direction::East,
+ position: Point::new(par, per)
+ },
+ PossibleShipPlacement {
+ ship: ship,
+ direction: Direction::North,
+ position: Point::new(per, par)
+ }
+ )
+ })
+ }).collect()
+ }
+
+ pub fn touches_point(&self, p: Point) -> bool {
+ p.check_for_ship_collision(self.position, self.direction, self.ship.length())
+ }
+ pub fn touches_any_point(&self, ps: &Vec<Point>) -> bool {
+ ps.iter().any(|&p| self.touches_point(p))
+ }
+
+ pub fn points_on_ship(&self) -> Vec<Point> {
+ (0..self.ship.length() as i32).map(|i| {
+ self.position.move_point_no_bounds_check(self.direction, i)
+ }).collect()
+ }
+
+ fn all_are_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool {
+ self.points_on_ship()
+ .iter()
+ .fold(true, |acc, p| acc && cells[p.x as usize][p.y as usize].hit)
+ }
+
+ fn all_could_be_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool {
+ self.points_on_ship()
+ .iter()
+ .all(|p| {
+ let ref cell = cells[p.x as usize][p.y as usize];
+ !cell.missed && cell.known_ship.map(|ship| ship == self.ship).unwrap_or(true)
+ })
+ }
+
+ fn count_hit_cells(&self, required: Point, wanted: &Vec<Point>) -> u16 {
+ if !self.touches_point(required) {
+ return 0;
+ }
+
+ wanted.iter().filter(|&&x| self.touches_point(x)).count() as u16
+ }
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug)]
+pub struct KnowledgeCell {
+ pub missed: bool,
+ pub hit: bool,
+ pub known_ship: Option<Ship>,
+ pub position: Point
+}
+
+impl KnowledgeCell {
+ fn new(x: u16, y: u16) -> KnowledgeCell {
+ KnowledgeCell {
+ missed: false,
+ hit: false,
+ position: Point::new(x, y),
+ known_ship: None
+ }
+ }
+
+ pub fn shot_attempted(&self) -> bool {
+ self.missed || self.hit
+ }
+
+ pub fn unknown_hit(&self) -> bool {
+ self.hit && self.known_ship.is_none()
+ }
+
+}
+
+