diff options
-rw-r--r-- | src/strategy.rs | 2 | ||||
-rw-r--r-- | src/strategy/minimax.rs | 62 |
2 files changed, 18 insertions, 46 deletions
diff --git a/src/strategy.rs b/src/strategy.rs index 9c92ba5..fce842b 100644 --- a/src/strategy.rs +++ b/src/strategy.rs @@ -2,4 +2,4 @@ //pub use mcts::{choose_move, Node}; mod minimax; -pub use minimax::{choose_move, Node, ScoreConfig}; +pub use minimax::{choose_move, choose_move_with_normalized_perf, Node, ScoreConfig}; diff --git a/src/strategy/minimax.rs b/src/strategy/minimax.rs index 1d833cb..b34d2f8 100644 --- a/src/strategy/minimax.rs +++ b/src/strategy/minimax.rs @@ -64,12 +64,13 @@ pub fn choose_move( ); } - best_player_move(&root_node) + best_player_move(&root_node, 0) } pub fn choose_move_with_normalized_perf( state: &GameBoard, config: &ScoreConfig, + player_index: usize, iterations: usize, ) -> Command { let mut root_node = Node { @@ -83,7 +84,7 @@ pub fn choose_move_with_normalized_perf( let _ = expand_tree(&mut root_node, state.clone(), config); } - best_player_move(&root_node) + best_player_move(&root_node, player_index) } pub struct Node { @@ -113,6 +114,15 @@ impl Div<u32> for Score { } } +impl Mul<f32> for Score { + type Output = Self; + fn mul(self, other: f32) -> Self { + Score { + val: self.val * other, + } + } +} + impl cmp::Eq for Score {} impl cmp::Ord for Score { fn cmp(&self, other: &Score) -> cmp::Ordering { @@ -174,46 +184,7 @@ fn expand_tree(node: &mut Node, mut state: GameBoard, config: &ScoreConfig) -> S node.children.insert(commands, new_node); update(node, commands, score); - if false && node.unexplored.is_empty() { - // TODO: Prune dominated moves - // Any move that, regardless of opponent move, there's some other move that gives a better score. - // Prune for both players. - // TODO: Prune opponent moves too - // TODO: Propagate score up - // TODO: prune moves from the explored states - let mut to_prune: Vec<Command> = Vec::new(); - for player_move in node.player_score_sums[0].keys() { - let mut better_moves: Vec<Command> = node.player_score_sums[0] - .keys() - .filter(|m| **m != *player_move) - .cloned() - .collect(); - for opponent_move in node.player_score_sums[1].keys() { - let baseline_score = node - .children - .get(&[*player_move, *opponent_move]) - .unwrap() - .score_sum - .avg(); - - better_moves.retain(|possible_better_move| { - let possibly_better_score = node - .children - .get(&[*possible_better_move, *opponent_move]) - .unwrap() - .score_sum - .avg(); - baseline_score >= possibly_better_score - }); - } - if !better_moves.is_empty() { - to_prune.push(player_move.clone()); - } - } - for pruning in to_prune { - node.player_score_sums[0].remove(&pruning); - } - } + // TODO: Prune dominated moves score } else { @@ -247,10 +218,11 @@ fn move_combos(state: &GameBoard) -> Vec<[Command; 2]> { result } -fn best_player_move(node: &Node) -> Command { - node.player_score_sums[0] +fn best_player_move(node: &Node, player_index: usize) -> Command { + let multiplier = if player_index == 0 { 1. } else { -1. }; + node.player_score_sums[player_index] .iter() - .max_by_key(|(_command, score_sum)| score_sum.avg()) + .max_by_key(|(_command, score_sum)| score_sum.avg() * multiplier) .map(|(command, _score_sum)| *command) .unwrap_or_else(|| Command::new(Action::DoNothing)) } |