From 366edf57a811e979fd39c3eb7d5bb06d21de41f7 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Fri, 9 Aug 2019 17:27:21 +0200 Subject: Scoring based on multiple criteria --- src/game/player.rs | 4 ++++ src/strategy.rs | 8 +++---- src/strategy/mcts.rs | 7 +++--- src/strategy/minimax.rs | 57 +++++++++++++++++++++++++++++++++---------------- 4 files changed, 51 insertions(+), 25 deletions(-) diff --git a/src/game/player.rs b/src/game/player.rs index 6c2efb2..0d24e60 100644 --- a/src/game/player.rs +++ b/src/game/player.rs @@ -46,6 +46,10 @@ impl Player { self.worms.iter().map(|w| w.health).sum() } + pub fn max_worm_health(&self) -> i32 { + self.worms.iter().map(|w| w.health).max().unwrap_or(0) + } + pub fn clear_dead_worms(&mut self) { for worm_index in (0..self.worms.len()).rev() { if self.worms[worm_index].health <= 0 { diff --git a/src/strategy.rs b/src/strategy.rs index f16a4a0..b6069a1 100644 --- a/src/strategy.rs +++ b/src/strategy.rs @@ -1,5 +1,5 @@ -mod mcts; -pub use mcts::{choose_move, Node}; +//mod mcts; +//pub use mcts::{choose_move, Node}; -//mod minimax; -//pub use minimax::{choose_move, Node}; +mod minimax; +pub use minimax::{choose_move, Node}; diff --git a/src/strategy/mcts.rs b/src/strategy/mcts.rs index b7478b8..dc6a5a3 100644 --- a/src/strategy/mcts.rs +++ b/src/strategy/mcts.rs @@ -26,7 +26,7 @@ pub fn choose_move( .map(|(_k, n)| n) .find(|n| n.state == *state) .unwrap_or_else(|| { - //eprintln!("Previous round did not appear in the cache"); + eprintln!("Previous round did not appear in the cache"); Node { state: state.clone(), score_sum: ScoreSum::new(), @@ -188,10 +188,11 @@ fn best_player_move(node: &Node) -> Command { } fn score(state: &GameBoard) -> Score { + // TODO: Try adding new features here, like max worm health, weighted in some way Score { val: match state.outcome { - SimulationOutcome::PlayerWon(0) => 500., - SimulationOutcome::PlayerWon(1) => -500., + SimulationOutcome::PlayerWon(0) => 3000., + SimulationOutcome::PlayerWon(1) => -3000., _ => (state.players[0].score() - state.players[1].score()) as f32, }, } diff --git a/src/strategy/minimax.rs b/src/strategy/minimax.rs index be0c485..7cc4918 100644 --- a/src/strategy/minimax.rs +++ b/src/strategy/minimax.rs @@ -23,9 +23,9 @@ pub fn choose_move( .children .drain() .map(|(_k, n)| n) - .find(|_n| false) // TODO: Identify the last opponent move to use this cache + .find(|_n| false) // TODO: Use the last player / opponent move and worm positions to use this cache. .unwrap_or_else(|| { - //eprintln!("Previous round did not appear in the cache"); + eprintln!("Previous round did not appear in the cache"); Node { score_sum: ScoreSum::new(), player_score_sums: [HashMap::new(), HashMap::new()], @@ -39,15 +39,15 @@ pub fn choose_move( let _ = expand_tree(&mut root_node, &state); } - //eprintln!("Number of simulations: {}", root_node.score_sum.visit_count); - // for (command, score_sum) in &root_node.player_score_sums[0] { - // eprintln!( - // "{} = {} ({} visits)", - // command, - // score_sum.avg().val, - // score_sum.visit_count - // ); - // } + eprintln!("Number of simulations: {}", root_node.score_sum.visit_count); + for (command, score_sum) in &root_node.player_score_sums[0] { + eprintln!( + "{} = {} ({} visits)", + command, + score_sum.avg().val, + score_sum.visit_count + ); + } let chosen_command = best_player_move(&root_node); @@ -128,6 +128,7 @@ fn expand_tree(node: &mut Node, state: &GameBoard) -> Score { if state.outcome != SimulationOutcome::Continue { score(state) } else if let Some(commands) = node.unexplored.pop() { + // TODO: Explore preemptively doing the rollout let mut new_state = state.clone(); new_state.simulate(commands); let score = score(&new_state); @@ -190,6 +191,9 @@ fn expand_tree(node: &mut Node, state: &GameBoard) -> Score { score } else { let commands = choose_existing(node); + // TODO: Is there anyway I can avoid this clone? Clone before + // calling update_tree and just pass ownership all the way + // down. let mut new_state = state.clone(); new_state.simulate(commands); let score = expand_tree( @@ -228,13 +232,21 @@ fn best_player_move(node: &Node) -> Command { } fn score(state: &GameBoard) -> Score { + let max_health = + (state.players[0].max_worm_health() - state.players[1].max_worm_health()) as f32; + let points = (state.players[0].score() - state.players[1].score()) as f32; + + const MAX_HEALTH_WEIGHT: f32 = 1.; + const POINTS_WEIGHT: f32 = 0.; + const VICTORY_WEIGHT: f32 = 3000.; + // TODO: Try adding new features here, like max worm health, weighted in some way - // TODO: Distance to dirt heatmap? + // TODO: Distance to dirt heatmap? Probably less relevant these days. Score { val: match state.outcome { - SimulationOutcome::PlayerWon(0) => 2000., - SimulationOutcome::PlayerWon(1) => -2000., - _ => (state.players[0].score() - state.players[1].score()) as f32, + SimulationOutcome::PlayerWon(0) => VICTORY_WEIGHT, + SimulationOutcome::PlayerWon(1) => -VICTORY_WEIGHT, + _ => max_health * MAX_HEALTH_WEIGHT + points * POINTS_WEIGHT, }, } } @@ -279,15 +291,24 @@ fn pruned_moves(state: &GameBoard, player_index: usize) -> Vec { state_cpy }; + let mut do_nothing_state = state.clone(); + do_nothing_state.simulate([ + Command::new(Action::DoNothing), + Command::new(Action::DoNothing), + ]); + let opponent_index = GameBoard::opponent(player_index); - let my_starting_health = state.players[player_index].health(); - let opponent_starting_health = state.players[opponent_index].health(); + let my_starting_health = do_nothing_state.players[player_index].health(); + let opponent_starting_health = do_nothing_state.players[opponent_index].health(); state .valid_moves(player_index) .into_iter() .filter(|command| { - //NB: These rules should pass for doing nothing, otherwise + // TODO: Filtering out of snowball moves to only freeze opponents + // TODO: Filter bombs out to only hurt opponents + + // NB: These rules should pass for doing nothing, otherwise // we need some other mechanism for sticking in a do // nothing option. Unfortunately, sitting in lava is a situation where this prunes all moves currently :( -- cgit v1.2.3