From a866bde485c7d8bc82820f2def70af7b6c70a066 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 21:25:36 +0200 Subject: Refile for merging repos --- 2017-battleships/src/knowledge.rs | 504 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 504 insertions(+) create mode 100644 2017-battleships/src/knowledge.rs (limited to '2017-battleships/src/knowledge.rs') 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, + pub shootable_weapons: Vec, + pub charging_weapons: HashMap +} + +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, state: &State) -> (Vec, Vec, Vec) { + 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, Vec, Vec) { + let mut misses: Vec = Vec::new(); + let mut hits: Vec = 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::>(), &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 { + 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) { + 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, 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, usize))> = + best_shots.get(&Weapon::SingleShot).map(|x| (Weapon::SingleShot, x.clone())); + + let best: (Weapon, (Vec, 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 { + 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, + pub cells: Vec> +} + +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::>(); + + OpponentMapKnowledge { + ships: ships, + cells: cells + } + } + + fn update_sunk_ships(&mut self, state: &State) -> Vec { + 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, missed_cells: Vec, sunk_ships: Vec) { + 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, must_touch_any: &Vec) { + 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 { + 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) -> Vec { + 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 { + self.cells.iter().flat_map(|x| { + x.iter().map(|y| y.position) + }).collect() + } + + fn cells_on_lattice(&self, lattice_size: u16) -> Vec { + 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 { + 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 +} + +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 { + (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) -> bool { + ps.iter().any(|&p| self.touches_point(p)) + } + + pub fn points_on_ship(&self) -> Vec { + (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>) -> 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>) -> 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) -> 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, + 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() + } + +} + + -- cgit v1.2.3