Score based MCTS

4 files changed, 178 insertions, 211 deletions

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::<ArrayVec<[Point2d<i8>; 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::<ArrayVec<[Point2d<i8>; 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<i8>, 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<Position> {
-        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<Position> {
-        self.x
-            .checked_add(distance)
-            .filter(|&x| x < max)
-            .map(|x| Position { x, y: self.y })
-    }
-    pub fn north(&self, distance: i8) -> Option<Position> {
-        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<Position> {
-        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<Command> {
-    let worm = state.players[player_index].active_worm();
+// fn heuristic_moves(state: &GameBoard, player_index: usize) -> Vec<Command> {
+//     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::<i8>() / state.players[player_index].worms.len() as i8,
+//         y: state.players[player_index].worms
+//             .iter()
+//             .map(|w| w.position.y)
+//             .sum::<i8>() / 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<i8>) -> Vec<Command> {
+//     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::<i8>() / state.players[player_index].worms.len() as i8,
-        y: state.players[player_index].worms
-            .iter()
-            .map(|w| w.position.y)
-            .sum::<i8>() / 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<i8>) -> Vec<Command> {
-    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)
 }