-
Notifications
You must be signed in to change notification settings - Fork 2
The minimax bot algorithm
| gamey/src/bot/minimax.rs
This bot uses Minimax with alpha-beta pruning, guided by a distance-based heuristic. It estimates how many empty cells each player needs to connect all three sides, preferring positions where the bot is closer to winning.
To stay efficient:
- Only adjacent cells (
candidate_cells) are considered - Moves are heuristically ordered to improve pruning
- Only the top 15 candidates are explored per node
A full-board scan (find_immediate_win) ensures no 1-move win is ever missed.
It implements the YBot trait and is registered in the bot server under the identifier "minimax_bot".
pub struct MinimaxBot { depth: i32 }
impl MinimaxBot {
pub fn new(depth: i32) -> Self { Self { depth } }
pub fn depth(&self) -> i32 { self.depth }
}Controls search using depth
- 0 : No lookahead (first available move)
-
0 : Fixed-depth search
- <0 : Iterative deepening (time-limited)
The public method called by the game server to request a move. Handles all three depth modes and returns the coordinates of the chosen move.
fn choose_move(&self, board: &GameY) -> Option<Coordinates>Returns None if available_cells is empty.
Runs one complete minimax search at a fixed depth and returns the best (move, score) pair. Called by choose_move for both fixed-depth and iterative deepening modes.
- Calls
find_immediate_winfirst. If a 1-move win exists, returns it immediately withWIN_SCORE. - Otherwise iterates over
ordered_moves, callsminimaxfor each candidate (depth − 1), and propagates the root alpha bound to enable early pruning. - Stops early if
best_score >= WIN_SCORE(forced win found).
fn search_at_depth(board: &GameY, bot: PlayerId, depth: u32) -> (Option<Coordinates>, i32)Scans all available cells (not just candidate_cells) for a move that immediately wins the game for bot. This guarantees the bot never misses a winning move regardless of how that cell scores in move ordering.
fn find_immediate_win(board: &GameY, bot: PlayerId) -> Option<Coordinates>The core recursive function. Implements Minimax with Alpha-Beta pruning. Always called from search_at_depth 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. The effectiveness is amplified by move ordering (see ordered_moves).
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. 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.
Returns opp_score - bot_score, where each score is produced by position_score.
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.
Returns the set of all coordinates the player is allowed to route through during the distance BFS. 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. A group of 4 connected pieces touching two sides is genuinely close to winning; 4 scattered pieces are not.
Helper used inside dist_to_side. Relaxes a single neighbouring cell in the 0-1 BFS: skips it if it is not passable or already visited, computes a tentative distance (0 if the neighbour belongs to the group, 1 otherwise), and updates dist/deque if a shorter path is found. Cost-0 neighbours are pushed to the front of the deque; cost-1 neighbours to the back.
fn relax_neighbour(
neighbour: &Coordinates,
current_dist: i32,
group_set: &HashSet<Coordinates>,
passable: &HashSet<Coordinates>,
visited: &HashSet<Coordinates>,
dist: &mut HashMap<Coordinates, i32>,
deque: &mut VecDeque<Coordinates>,
)Computes the minimum number of empty cells that must be added to a group to connect it to a given side of the board. Uses a 0-1 BFS (deque-based) starting simultaneously from all cells in the group. Each relaxation step is delegated to relax_neighbour. Returns UNREACHABLE if no path through passable cells exists.
A deque is a double-entry queue. Cost-0 neighbours (already owned by the group) are pushed to the front, and cost-1 neighbours (empty passable cells) are pushed to the back. This preserves distance-ordering without the O(log n) overhead of a priority queue.
Returns candidate_cells sorted by order_score in descending order, so the most promising moves are evaluated first by alpha-beta. Precomputes the sides already touched by each player and the size of the opponent's largest connected group (via largest_group_size), then scores each candidate.
fn ordered_moves(board: &GameY, player: PlayerId, bot: PlayerId) -> Vec<Coordinates>Scores a single candidate cell for move ordering. Higher means more promising. The score is the sum of:
| Component | Weight |
|---|---|
human_neighbours × (15 + largest_human_group_size) |
blocking near a large group is highly rewarded |
20 per opponent-held side that this cell also touches |
directly contesting opponent sides |
player_neighbours × 10 |
extending own chains |
10 per own-held side that this cell also touches |
reinforcing own sides |
neighbour_count × 5 |
central cells with more neighbours are preferred |
Returns the subset of available cells that are adjacent to at least one already-occupied cell. On an empty board it falls back to all available cells. Called by ordered_moves, not directly by minimax.
fn candidate_cells(board: &GameY) -> Vec<u32>Returns the number of cells in the largest connected component among a list of owned cells. Used by ordered_moves to weight blocking scores: blocking near a large opponent group is more urgent than blocking near isolated pieces.
-
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.find_immediate_winmitigates this only for 1-move wins. -
MAX_CANDIDATEShard cap silently discards moves — when more than 15 adjacent cells exist, everything beyond rank 15 in the ordered list is never evaluated, even if the 16th move is objectively better than something within the cap. -
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 (thoughMAX_CANDIDATESpartially limits this). - 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.