-
Notifications
You must be signed in to change notification settings - Fork 2
The minimax bot algorithm
| gamey/src/bot/minimax.rs
The evaluation of non-terminal positions is driven by a distance-based heuristic that measures how many empty cells each player needs to fill to connect all three sides of the triangular board. The search space is reduced at every node by only considering cells adjacent to already-placed pieces, which dramatically lowers the branching factor compared to searching all available cells.
The public struct exposed by this module. It holds a single field depth, which controls how many moves ahead the search looks. It implements the YBot trait and is registered in the bot server under the identifier "minimax_bot".
pub struct MinimaxBot { depth: u32 }
impl MinimaxBot {
pub fn new(depth: u32) -> Self { Self { depth } }
pub fn depth(&self) -> u32 { self.depth }
}The public method called by the game server to request a move. It handles edge cases before entering the search tree and returns the coordinates of the chosen move.
fn choose_move(&self, board: &GameY) -> Option<Coordinates>The core recursive function. It implements the Minimax algorithm with Alpha-Beta pruning. It is always called from choose_move and calls itself recursively until a terminal condition is reached.
| Condition | Return value |
|---|---|
| Game is over (winner exists) |
WIN_SCORE if bot won, LOSS_SCORE if opponent won |
depth == 0 or no available cells |
evaluate(board, bot) — the heuristic score |
next_player returns None
|
evaluate(board, bot) — defensive fallback |
alpha tracks the best score the maximiser has found so far. beta tracks the best score the minimiser has found. When alpha >= beta the current branch cannot affect the final result and the loop breaks early.
This reduces the number of nodes visited from O(b^d) to approximately O(b^(d/2)) in the best case, where b is the branching factor and d is the depth.
fn minimax(
board: &GameY,
depth: u32,
alpha: i32,
beta: i32,
maximizing: bool,
bot: PlayerId,
) -> i32Called at every leaf node that is not a terminal game state. It computes a signed integer score representing how favourable the current position is for the bot. A positive score means the bot is closer to winning; a negative score means the opponent is closer.
Since position_score measures distance to winning, subtracting the bot's score from the opponent's gives a result where higher is better for the bot.
Evaluates all connected groups of a player and returns the minimum total distance to all three sides across all groups. The minimum is used because the best connected chain is what matters — scattered isolated pieces do not contribute to the winning condition.
fn position_score(
groups: &[Vec<Coordinates>],
passable: &HashSet<Coordinates>,
) -> i32If the player has no pieces on the board, returns UNREACHABLE * 3 as a maximum-penalty. This is safe because UNREACHABLE = 1_000 and 1_000 * 3 = 3_000, which is well within i32 range and below WIN_SCORE.
Returns the set of all coordinates the player is allowed to route through during the distance BFS. This includes the player's own pieces (cost 0) and all empty cells (cost 1). Opponent pieces are excluded because they can never be placed on.
fn passable_cells(board: &GameY, player: PlayerId) -> HashSet<Coordinates>Without this filter the BFS would find shorter paths that pass through opponent pieces, producing optimistic distances that do not correspond to any achievable game position.
Splits all placed pieces of a player into connected components (islands) using BFS. Two pieces belong to the same group if they are barycentric neighbours. Each group is evaluated independently by position_score.
fn connected_groups(board: &GameY, player: PlayerId) -> Vec<Vec<Coordinates>>This separation is critical for correctness. Without it, position_score could treat disconnected pieces as if they were already joined, producing artificially low distance scores. A group of 4 connected pieces touching two sides is genuinely close to winning; 4 scattered pieces are not, usually.
Computes the minimum number of empty cells that must be added to a group to connect it to a given side of the board. It uses a 0-1 BFS (deque-based) starting simultaneously from all cells in the group.
A deque is a double entry queue, this way we can push to the back the cost-1 neighbours and to the front the cost-0 neighbours. Doing this we avoid using the complexity of O(log(n)) for a priority queue.
Instead of searching all available cells at every minimax node, only returns cells that are adjacent to at least one already-occupied cell. On an empty board it falls back to all available cells since there are no occupied cells to be adjacent to.
fn candidate_cells(board: &GameY) -> Vec<u32>-
candidate_cellscan miss strategic moves — a cell far from current pieces but strategically important (e.g. blocking a future fork) will never be considered until the occupied region expands near it. - No move ordering within candidates — alpha-beta pruning is most effective when the best moves are searched first. Currently candidates are visited in index order, leaving pruning effectiveness to chance.
-
Branching factor still grows late game — as more pieces are placed the occupied border expands, so
candidate_cellsreturns more cells each turn, making the search progressively slower toward the end of the game. - Clone cost — because Union-Find (used internally for win detection) is not reversible, every node in the tree requires a full board clone. An undo-based approach is impossible without replacing the internal data structure.