diff options
Diffstat (limited to 'src/strategy/minimax.rs')
-rw-r--r-- | src/strategy/minimax.rs | 45 |
1 files changed, 29 insertions, 16 deletions
diff --git a/src/strategy/minimax.rs b/src/strategy/minimax.rs index deba92e..2ed84b2 100644 --- a/src/strategy/minimax.rs +++ b/src/strategy/minimax.rs @@ -16,7 +16,7 @@ pub fn choose_move( None => Node { score_sum: ScoreSum::new(), player_score_sums: [HashMap::new(), HashMap::new()], - unexplored: mcts_move_combo(state), + unexplored: move_combos(state), children: HashMap::new(), }, Some(mut node) => node @@ -27,17 +27,16 @@ pub fn choose_move( .unwrap_or_else(|| { eprintln!("Previous round did not appear in the cache"); Node { - state: state.clone(), score_sum: ScoreSum::new(), player_score_sums: [HashMap::new(), HashMap::new()], - unexplored: mcts_move_combo(state), + unexplored: move_combos(state), children: HashMap::new(), } }), }; while start_time.to(PreciseTime::now()) < max_time { - let _ = mcts(&mut root_node); + let _ = expand_tree(&mut root_node, &state); } eprintln!("Number of simulations: {}", root_node.score_sum.visit_count); @@ -126,21 +125,20 @@ impl AddAssign<Score> for ScoreSum { } // TODO: Transform this into more of a minimax with AB pruning approach? -fn mcts(node: &mut Node) -> Score { - if node.state.outcome != SimulationOutcome::Continue { - score(&node.state) +fn expand_tree(node: &mut Node, state: &GameBoard) -> Score { + if state.outcome != SimulationOutcome::Continue { + score(state) } else if let Some(commands) = node.unexplored.pop() { - let mut new_state = node.state.clone(); + let mut new_state = state.clone(); new_state.simulate(commands); let score = score(&new_state); let unexplored = if new_state.outcome == SimulationOutcome::Continue { - mcts_move_combo(&new_state) + move_combos(&new_state) } else { Vec::new() }; let new_node = Node { - state: new_state, score_sum: ScoreSum::with_initial(score), player_score_sums: [HashMap::new(), HashMap::new()], unexplored, @@ -152,19 +150,22 @@ fn mcts(node: &mut Node) -> Score { score } else { let commands = choose_existing(node); - let score = mcts( + let mut new_state = state.clone(); + new_state.simulate(commands); + let score = expand_tree( node.children .get_mut(&commands) .expect("The existing node hasn't been tried yet"), + &new_state, ); update(node, commands, score); score } } -fn mcts_move_combo(state: &GameBoard) -> Vec<[Command; 2]> { - let player_moves = valid_moves(state, 0); - let opponent_moves = valid_moves(state, 1); +fn move_combos(state: &GameBoard) -> Vec<[Command; 2]> { + let player_moves = pruned_moves(state, 0); + let opponent_moves = pruned_moves(state, 1); debug_assert!(!player_moves.is_empty(), "No player moves"); debug_assert!(!opponent_moves.is_empty(), "No opponent moves"); @@ -187,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) => 2000., + SimulationOutcome::PlayerWon(1) => -2000., _ => (state.players[0].score() - state.players[1].score()) as f32, }, } @@ -224,6 +226,17 @@ fn update(node: &mut Node, commands: [Command; 2], score: Score) { node.score_sum += score; } +fn pruned_moves(state: &GameBoard, player_index: usize) -> Vec<Command> { + // TODO: Play one move into the future and make sure this doesn't + // hurt me or do something dumb? Should I rather specialize this + // to each type of move? + + // TODO: Ensure that there are at least some moves left here. If + // there's nothing, at least return a vector that contains a + // nothing move. + valid_moves(state, player_index) +} + fn valid_moves(state: &GameBoard, player_index: usize) -> Vec<Command> { state .valid_shoot_commands(player_index) |