diff options
author | Justin Worthe <justin.worthe@gmail.com> | 2017-05-20 22:20:47 +0200 |
---|---|---|
committer | Justin Worthe <justin.worthe@gmail.com> | 2017-05-20 22:20:47 +0200 |
commit | 6b8c71c635539a8609f82aa6eb52ea56c2c41c0c (patch) | |
tree | 23da0d8ae0d15ebc1e9b48797965f58958e9c34d | |
parent | 973f7be695f7c3308d384e1ee30066547e4a07c7 (diff) |
Finished up efficient elimination of found ships
-rw-r--r-- | src/knowledge.rs | 90 | ||||
-rw-r--r-- | src/lib.rs | 2 | ||||
-rw-r--r-- | src/math.rs | 11 | ||||
-rw-r--r-- | src/shooting.rs | 40 |
4 files changed, 118 insertions, 25 deletions
diff --git a/src/knowledge.rs b/src/knowledge.rs index 01c098d..f009c10 100644 --- a/src/knowledge.rs +++ b/src/knowledge.rs @@ -8,21 +8,24 @@ use std::collections::HashMap; #[derive(Serialize, Deserialize, Clone, Debug)] pub struct Knowledge { pub last_action: Action, - pub opponent_map: OpponentMapKnowledge + pub opponent_map: OpponentMapKnowledge, + pub map_size: u16 } impl Knowledge { pub fn new(map_size: u16, action: Action) -> Knowledge { Knowledge { last_action: action, - opponent_map: OpponentMapKnowledge::new(map_size) + opponent_map: OpponentMapKnowledge::new(map_size), + map_size: map_size } } pub fn with_action(&self, action: Action) -> Knowledge { Knowledge { last_action: action, - opponent_map: self.opponent_map.clone() + opponent_map: self.opponent_map.clone(), + map_size: self.map_size } } @@ -38,7 +41,39 @@ impl Knowledge { new_knowledge } - + 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 + .ships + .values() + .flat_map(|knowledge| knowledge.possible_placements.clone()); + + 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 + } } #[derive(Serialize, Deserialize, Clone, Debug)] @@ -68,7 +103,6 @@ impl OpponentMapKnowledge { } fn update_from_shot(&mut self, p: Point, state: &State) { - let cells_copy = self.cells.clone(); let ref shot_cell = state.opponent_map.cells[p.x as usize][p.y as usize]; let sunk_ship = self.ships.iter() .filter(|&(_, x)| !x.destroyed) @@ -90,15 +124,16 @@ impl OpponentMapKnowledge { else { self.cells[p.x as usize][p.y as usize].hit = true; self.cells[p.x as usize][p.y as usize].known_ship = sunk_ship; + } - if sunk_ship.is_some() { - for knowledge in self.ships.values_mut() { - knowledge.possible_placements.retain(|x| { - (sunk_ship != Some(x.ship) && !x.touches_point(p)) || + let cells_copy = self.cells.clone(); + if sunk_ship.is_some() { + for knowledge in self.ships.values_mut() { + knowledge.possible_placements.retain(|x| { + (sunk_ship != Some(x.ship) && !x.touches_point(p)) || (sunk_ship == Some(x.ship) && x.touches_point(p) && x.all_are_hits(&cells_copy)) - }); - } + }); } } @@ -123,6 +158,21 @@ impl OpponentMapKnowledge { knowledge.possible_placements.retain(|x| x.all_could_be_hits(&cells)); } } + + 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() + } } #[derive(Serialize, Deserialize, Clone, Debug)] @@ -161,7 +211,7 @@ impl PossibleShipPlacement { }, PossibleShipPlacement { ship: ship, - direction: Direction::South, + direction: Direction::North, position: Point::new(per, par) } ) @@ -169,11 +219,11 @@ impl PossibleShipPlacement { }).collect() } - fn touches_point(&self, p: Point) -> bool { + pub fn touches_point(&self, p: Point) -> bool { p.check_for_ship_collision(self.position, self.direction, self.ship.length()) } - fn points_on_ship(&self) -> Vec<Point> { + 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() @@ -194,6 +244,14 @@ impl PossibleShipPlacement { 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)] @@ -214,11 +272,11 @@ impl KnowledgeCell { } } - fn shot_attempted(&self) -> bool { + pub fn shot_attempted(&self) -> bool { self.missed || self.hit } - fn unknown_hit(&self) -> bool { + pub fn unknown_hit(&self) -> bool { self.hit && self.known_ship.is_none() } @@ -60,7 +60,7 @@ fn placement(map_size: u16) -> (Action, Knowledge) { fn shoot(state: &State) -> Result<(Action, Knowledge), String> { let old_knowledge = read_knowledge()?; let knowledge = old_knowledge.resolve_last_action(&state); - let action = shoot_randomly(&state); + let action = shoot_smartly(&knowledge); Ok((action.clone(), knowledge.with_action(action))) } diff --git a/src/math.rs b/src/math.rs index 2ef1013..ce9d885 100644 --- a/src/math.rs +++ b/src/math.rs @@ -116,10 +116,19 @@ impl Point { }; let corrected_parr_ship = match reverse { - true => parr_ship - length + 1, + true => 1 + parr_ship - length, false => parr_ship }; same_cross && parr_self >= corrected_parr_ship && parr_self < corrected_parr_ship + length } + + pub fn is_adjacent(&self, other: Point) -> bool { + let dx = if self.x > other.x {self.x - other.x} else {other.x - self.x}; + let dy = if self.y > other.y {self.y - other.y} else {other.y - self.y}; + + (dx == 0 && dy == 1) || + (dx == 1 && dy == 0) + + } } diff --git a/src/shooting.rs b/src/shooting.rs index c2ca56e..616ebf3 100644 --- a/src/shooting.rs +++ b/src/shooting.rs @@ -1,16 +1,42 @@ +use rand; +use rand::distributions::{IndependentSample, Range}; + use actions::*; use math::*; -use state::*; +use knowledge::*; + +pub fn shoot_smartly(knowledge: &Knowledge) -> Action { + let shot = if knowledge.has_unknown_hits() { + destroy_shoot(&knowledge) + } + else { + seek_shoot(&knowledge) + }; + + Action::Shoot(shot) +} -pub fn shoot_randomly(state: &State) -> Action { +fn seek_shoot(knowledge: &Knowledge) -> Point { let mut shot: Point; while { - shot = Point::random(state.map_size); - let ref target = state.opponent_map.cells[shot.x as usize][shot.y as usize]; - target.damaged || target.missed + shot = Point::random(knowledge.map_size); + let ref target = knowledge.opponent_map.cells[shot.x as usize][shot.y as usize]; + target.shot_attempted() } {} + shot +} - - Action::Shoot(shot) +fn destroy_shoot(knowledge: &Knowledge) -> Point { + let possibilities = knowledge.get_best_adjacent_shots(); + if possibilities.is_empty() { + seek_shoot(&knowledge) + } + else { + let mut rng = rand::thread_rng(); + let between = Range::new(0, possibilities.len()); + let i = between.ind_sample(&mut rng); + + possibilities[i as usize] + } } |