From d37be51f196eebdb8df57c87e8ab5bb684e1dcd9 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sun, 26 May 2019 00:28:28 +0200 Subject: Score based MCTS --- src/game.rs | 177 +++++++++++++++++++++++++++-------------------------- src/game/player.rs | 8 +-- src/json.rs | 58 +----------------- src/strategy.rs | 146 +++++++++++++++++++++++-------------------- 4 files changed, 178 insertions(+), 211 deletions(-) (limited to 'src') diff --git a/src/game.rs b/src/game.rs index 2112076..982c276 100644 --- a/src/game.rs +++ b/src/game.rs @@ -153,8 +153,9 @@ impl GameBoard { // here. I'm treating that as an edge case that I // don't need to handle for now. for player in &mut self.players { - let worm = player.active_worm_mut(); - worm.health = worm.health.saturating_sub(damage); + if let Some(worm) = player.active_worm_mut() { + worm.health = worm.health.saturating_sub(damage); + } player.moves_score += 5; } }, @@ -165,24 +166,24 @@ impl GameBoard { self.players[player_index].moves_score += 5; - let worm = self.players[player_index].active_worm_mut(); - - debug_assert!( - (worm.position.x - p.x).abs() <= 1 && - (worm.position.y - p.y).abs() <= 1, - "Tried to move too far away, ({}, {})", p.x, p.y - ); - - worm.position = p; - - self.powerups.retain(|power| { - if power.position == worm.position { - worm.health += power.value; - false - } else { - true - } - }); + if let Some(worm) = self.players[player_index].active_worm_mut() { + debug_assert!( + (worm.position.x - p.x).abs() <= 1 && + (worm.position.y - p.y).abs() <= 1, + "Tried to move too far away, ({}, {})", p.x, p.y + ); + + worm.position = p; + + self.powerups.retain(|power| { + if power.position == worm.position { + worm.health += power.value; + false + } else { + true + } + }); + } } } } @@ -198,8 +199,8 @@ impl GameBoard { "Tried to dig through air, ({}, {})", p.x, p.y ); debug_assert!{ - (self.players[player_index].active_worm().position.x - p.x).abs() <= 1 && - (self.players[player_index].active_worm().position.y - p.y).abs() <= 1, + (self.players[player_index].active_worm().unwrap().position.x - p.x).abs() <= 1 && + (self.players[player_index].active_worm().unwrap().position.y - p.y).abs() <= 1, "Tried to dig too far away, ({}, {})", p.x, p.y }; @@ -213,57 +214,58 @@ impl GameBoard { fn simulate_shoots(&mut self, moves: [Command; 2]) { 'players_loop: for player_index in 0..moves.len() { if let Command::Shoot(dir) = moves[player_index] { - let (center, weapon_range, weapon_damage) = { - let worm = self.players[player_index].active_worm(); - (worm.position, worm.weapon_range, worm.weapon_damage) - }; - let diff = dir.as_vec(); - - let range = if dir.is_diagonal() { - ((weapon_range as f32 + 1.) / 2f32.sqrt()).floor() as i8 - } else { - weapon_range as i8 - }; - - for distance in 1..=range { - let target = center + diff * distance; - match self.map.at(target) { - Some(false) => { - let target_own_worm: Option<&mut Worm> = self.players[player_index] - .worms.iter_mut() - .find(|w| w.position == target); - - if let Some(target_worm) = target_own_worm { - target_worm.health -= weapon_damage; - if target_worm.health <= 0 { - // TODO: This will probably be changed soon https://github.com/EntelectChallenge/2019-Worms/issues/42 - self.players[player_index].moves_score += 40; - } else { - self.players[player_index].moves_score -= 20; + if let Some(worm) = self.players[player_index].active_worm() { + let (center, weapon_range, weapon_damage) = { + (worm.position, worm.weapon_range, worm.weapon_damage) + }; + let diff = dir.as_vec(); + + let range = if dir.is_diagonal() { + ((weapon_range as f32 + 1.) / 2f32.sqrt()).floor() as i8 + } else { + weapon_range as i8 + }; + + for distance in 1..=range { + let target = center + diff * distance; + match self.map.at(target) { + Some(false) => { + let target_own_worm: Option<&mut Worm> = self.players[player_index] + .worms.iter_mut() + .find(|w| w.position == target); + + if let Some(target_worm) = target_own_worm { + target_worm.health -= weapon_damage; + if target_worm.health <= 0 { + // TODO: This will probably be changed soon https://github.com/EntelectChallenge/2019-Worms/issues/42 + self.players[player_index].moves_score += 40; + } else { + self.players[player_index].moves_score -= 20; + } + continue 'players_loop; } - continue 'players_loop; - } - - let target_opponent_worm: Option<&mut Worm> = self.players[GameBoard::opponent(player_index)] - .worms.iter_mut() - .find(|w| w.position == target); - if let Some(target_worm) = target_opponent_worm { - target_worm.health -= weapon_damage; - if target_worm.health <= 0 { - self.players[player_index].moves_score += 40; - } else { - self.players[player_index].moves_score += 20; + + let target_opponent_worm: Option<&mut Worm> = self.players[GameBoard::opponent(player_index)] + .worms.iter_mut() + .find(|w| w.position == target); + if let Some(target_worm) = target_opponent_worm { + target_worm.health -= weapon_damage; + if target_worm.health <= 0 { + self.players[player_index].moves_score += 40; + } else { + self.players[player_index].moves_score += 20; + } + + continue 'players_loop; } - - continue 'players_loop; - } - }, - _ => break + }, + _ => break + } } - } - // You get here if the shot missed. Hits are an early return. - self.players[player_index].moves_score += 2; + // You get here if the shot missed. Hits are an early return. + self.players[player_index].moves_score += 2; + } } } } @@ -274,23 +276,26 @@ impl GameBoard { pub fn valid_move_commands(&self, player_index: usize) -> ArrayVec<[Command;8]> { - let worm = self.players[player_index].active_worm(); - let taken_positions = self.players.iter() - .flat_map(|p| p.worms.iter()) - .map(|w| w.position) - .collect::; 6]>>(); - - Direction::all() - .iter() - .map(Direction::as_vec) - .map(|d| worm.position + d) - .filter(|p| !taken_positions.contains(p)) - .filter_map(|p| match self.map.at(p) { - Some(false) => Some(Command::Move(p)), - Some(true) => Some(Command::Dig(p)), - _ => None, - }) - .collect() + if let Some(worm) = self.players[player_index].active_worm() { + let taken_positions = self.players.iter() + .flat_map(|p| p.worms.iter()) + .map(|w| w.position) + .collect::; 6]>>(); + + Direction::all() + .iter() + .map(Direction::as_vec) + .map(|d| worm.position + d) + .filter(|p| !taken_positions.contains(p)) + .filter_map(|p| match self.map.at(p) { + Some(false) => Some(Command::Move(p)), + Some(true) => Some(Command::Dig(p)), + _ => None, + }) + .collect() + } else { + ArrayVec::new() + } } pub fn valid_shoot_commands(&self, player_index: usize, center: Point2d, weapon_range: u8) -> ArrayVec<[Command;8]> { diff --git a/src/game/player.rs b/src/game/player.rs index 917abef..1704a27 100644 --- a/src/game/player.rs +++ b/src/game/player.rs @@ -30,12 +30,12 @@ impl Player { .find(|w| w.id == id) } - pub fn active_worm(&self) -> &Worm { - &self.worms[self.active_worm] + pub fn active_worm(&self) -> Option<&Worm> { + self.worms.get(self.active_worm) } - pub fn active_worm_mut(&mut self) -> &mut Worm { - &mut self.worms[self.active_worm] + pub fn active_worm_mut(&mut self) -> Option<&mut Worm> { + self.worms.get_mut(self.active_worm) } pub fn health(&self) -> i32 { diff --git a/src/json.rs b/src/json.rs index 3cd603c..09095b0 100644 --- a/src/json.rs +++ b/src/json.rs @@ -39,7 +39,7 @@ pub struct Player { impl Player { pub fn health_score(&self) -> i32 { - self.health / self.worms.len() as i32 + self.health / 3 } } @@ -155,37 +155,11 @@ impl State { self.my_player .worms .iter() + .filter(|w| w.health > 0) .position(|w| w.id == self.current_worm_id) } } -impl Position { - pub fn west(&self, distance: i8) -> Option { - self.x - .checked_sub(distance) - .filter(|&x| x >= 0) - .map(|x| Position { x, y: self.y }) - } - pub fn east(&self, distance: i8, max: i8) -> Option { - self.x - .checked_add(distance) - .filter(|&x| x < max) - .map(|x| Position { x, y: self.y }) - } - pub fn north(&self, distance: i8) -> Option { - self.y - .checked_sub(distance) - .filter(|&y| y >= 0) - .map(|y| Position { x: self.x, y }) - } - pub fn south(&self, distance: i8, max: i8) -> Option { - self.y - .checked_add(distance) - .filter(|&y| y < max) - .map(|y| Position { x: self.x, y }) - } -} - #[cfg(test)] mod test { use super::*; @@ -418,32 +392,4 @@ mod test { parsed, expected ); } - - #[test] - fn west_moving_stays_in_bounds() { - let pos = Position { x: 1, y: 1 }; - assert_eq!(pos.west(1), Some(Position { x: 0, y: 1 })); - assert_eq!(pos.west(2), None); - } - - #[test] - fn east_moving_stays_in_bounds() { - let pos = Position { x: 1, y: 1 }; - assert_eq!(pos.east(1, 3), Some(Position { x: 2, y: 1 })); - assert_eq!(pos.east(2, 3), None); - } - - #[test] - fn north_moving_stays_in_bounds() { - let pos = Position { x: 1, y: 1 }; - assert_eq!(pos.north(1), Some(Position { x: 1, y: 0 })); - assert_eq!(pos.north(2), None); - } - - #[test] - fn south_moving_stays_in_bounds() { - let pos = Position { x: 1, y: 1 }; - assert_eq!(pos.south(1, 3), Some(Position { x: 1, y: 2 })); - assert_eq!(pos.south(2, 3), None); - } } diff --git a/src/strategy.rs b/src/strategy.rs index 39bbe66..8e004cf 100644 --- a/src/strategy.rs +++ b/src/strategy.rs @@ -159,8 +159,8 @@ fn mcts(node: &mut Node) -> Score { } fn mcts_move_combo(state: &GameBoard) -> Vec<[Command; 2]> { - let player_moves = heuristic_moves(state, 0); - let opponent_moves = heuristic_moves(state, 1); + let player_moves = valid_moves(state, 0); + let opponent_moves = valid_moves(state, 1); debug_assert!(player_moves.len() > 0, "No player moves"); debug_assert!(player_moves.len() > 0, "No opponent moves"); @@ -183,12 +183,12 @@ fn best_player_move(node: &Node) -> Command { } fn score(state: &GameBoard) -> Score { - let mutiplier = match state.outcome { - SimulationOutcome::PlayerWon(_) => 1000., - _ => 1., - }; Score { - val: mutiplier * (state.players[0].health() - state.players[1].health()) as f32, + val: match state.outcome { + SimulationOutcome::PlayerWon(0) => 10000., + SimulationOutcome::PlayerWon(1) => -10000., + _ => (state.players[0].score() - state.players[1].score()) as f32, + } } } @@ -242,71 +242,87 @@ fn update(node: &mut Node, commands: [Command; 2], score: Score) { node.score_sum += score; } -fn heuristic_moves(state: &GameBoard, player_index: usize) -> Vec { - let worm = state.players[player_index].active_worm(); +// fn heuristic_moves(state: &GameBoard, player_index: usize) -> Vec { +// let worm = state.players[player_index].active_worm(); + +// let shoots = state +// .valid_shoot_commands(player_index, worm.position, worm.weapon_range); + +// let closest_powerup = state.powerups +// .iter() +// .min_by_key(|p| (p.position - worm.position).walking_distance()); + +// let average_player_position = Point2d { +// x: state.players[player_index].worms +// .iter() +// .map(|w| w.position.x) +// .sum::() / state.players[player_index].worms.len() as i8, +// y: state.players[player_index].worms +// .iter() +// .map(|w| w.position.y) +// .sum::() / state.players[player_index].worms.len() as i8 +// }; + +// let closest_opponent = state.players[GameBoard::opponent(player_index)].worms +// .iter() +// .min_by_key(|w| (w.position - average_player_position).walking_distance()); + +// let mut commands = if !shoots.is_empty() { +// // we're in combat now. Feel free to move anywhere. +// let moves = state.valid_move_commands(player_index); +// moves.iter().chain(shoots.iter()).cloned().collect() +// } else if let Some(powerup) = closest_powerup { +// // there are powerups! Let's go grab the closest one. +// moves_towards(state, player_index, powerup.position) +// } else if let Some(opponent) = closest_opponent { +// // we're not currently in combat. Let's go find the closest worm. +// moves_towards(state, player_index, opponent.position) +// } else { +// // this shouldn't happen +// debug_assert!(false, "No valid heuristic moves"); +// vec!() +// }; +// commands.push(Command::DoNothing); +// commands +// } + +// fn moves_towards(state: &GameBoard, player_index: usize, to: Point2d) -> Vec { +// let distance = (to - state.players[player_index].active_worm().position).walking_distance(); +// state.valid_move_commands(player_index) +// .iter() +// .filter(|c| match c { +// Command::Move(p) | Command::Dig(p) => (to - *p).walking_distance() < distance, +// _ => false +// }) +// .cloned() +// .collect() +// } - let shoots = state - .valid_shoot_commands(player_index, worm.position, worm.weapon_range); +fn rollout_moves(state: &GameBoard, player_index: usize) -> ArrayVec<[Command; 8]> { + if let Some(worm) = state.players[player_index].active_worm() { - let closest_powerup = state.powerups - .iter() - .min_by_key(|p| (p.position - worm.position).walking_distance()); + let shoots = state.valid_shoot_commands(player_index, worm.position, worm.weapon_range); - let average_player_position = Point2d { - x: state.players[player_index].worms - .iter() - .map(|w| w.position.x) - .sum::() / state.players[player_index].worms.len() as i8, - y: state.players[player_index].worms - .iter() - .map(|w| w.position.y) - .sum::() / state.players[player_index].worms.len() as i8 - }; + if !shoots.is_empty() { + return shoots; + } - let closest_opponent = state.players[GameBoard::opponent(player_index)].worms - .iter() - .min_by_key(|w| (w.position - average_player_position).walking_distance()); - - let mut commands = if !shoots.is_empty() { - // we're in combat now. Feel free to move anywhere. - let moves = state.valid_move_commands(player_index); - moves.iter().chain(shoots.iter()).cloned().collect() - } else if let Some(powerup) = closest_powerup { - // there are powerups! Let's go grab the closest one. - moves_towards(state, player_index, powerup.position) - } else if let Some(opponent) = closest_opponent { - // we're not currently in combat. Let's go find the closest worm. - moves_towards(state, player_index, opponent.position) + // TODO: More directed destruction movements? + state.valid_move_commands(player_index) } else { - // this shouldn't happen - debug_assert!(false, "No valid heuristic moves"); - vec!() - }; - commands.push(Command::DoNothing); - commands + [Command::DoNothing].iter().cloned().collect() + } } -fn moves_towards(state: &GameBoard, player_index: usize, to: Point2d) -> Vec { - let distance = (to - state.players[player_index].active_worm().position).walking_distance(); - state.valid_move_commands(player_index) - .iter() - .filter(|c| match c { - Command::Move(p) | Command::Dig(p) => (to - *p).walking_distance() < distance, - _ => false - }) - .cloned() - .collect() -} +fn valid_moves(state: &GameBoard, player_index: usize) -> ArrayVec<[Command; 17]> { + if let Some(worm) = state.players[player_index].active_worm() { -fn rollout_moves(state: &GameBoard, player_index: usize) -> ArrayVec<[Command; 8]> { - let worm = state.players[player_index].active_worm(); - - let shoots = state.valid_shoot_commands(player_index, worm.position, worm.weapon_range); - - if !shoots.is_empty() { - return shoots; + state.valid_shoot_commands(player_index, worm.position, worm.weapon_range) + .iter() + .chain(state.valid_move_commands(player_index).iter()) + .cloned() + .collect() + } else { + [Command::DoNothing].iter().cloned().collect() } - - // TODO: More directed destruction movements? - state.valid_move_commands(player_index) } -- cgit v1.2.3