First stab at pruning game tree

1 files changed, 39 insertions, 2 deletions

diff --git a/src/strategy/minimax.rs b/src/strategy/minimax.rs
index e620339..11e19a1 100644
--- a/src/strategy/minimax.rs
+++ b/src/strategy/minimax.rs
@@ -144,12 +144,49 @@ fn expand_tree(node: &mut Node, state: &GameBoard) -> Score {
             children: HashMap::new(),
         };
         node.children.insert(commands, new_node);
+        update(node, commands, score);
 
-        if node.unexplored.is_empty() {
+        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);
+            }
         }
 
-        update(node, commands, score);
         score
     } else {
         let commands = choose_existing(node);