gale.ai.minimax module

This file contains a generic minimax search with alpha-beta pruning for turn-based adversarial games, such as a tactical hacking terminal minigame inside a stealth game, or the classic tic-tac-toe. It works over any state exposing (move, next_state) transitions and a leaf evaluation, such as a gale.ai.graph.StateGraph (whose edges already carry an action/move label) or a plain callable, so it is not tied to any single game representation.

Author: Alejandro Mujica (aledrums@gmail.com)

gale.ai.minimax.minimax(state, depth, maximizing, get_children, evaluate, is_terminal, alpha=-inf, beta=inf)[source]

Find the optimal move from state by exploring depth plies ahead (or until a terminal state is reached), alternating between the maximizing and minimizing player and pruning branches with alpha-beta that cannot affect the final decision.

Parameters:

  • state (T) – The state to search from.

  • depth (int) – How many plies ahead to explore. 0 evaluates state directly without expanding it.

  • maximizing (bool) – Whether the player to move at state is the maximizing player.

  • get_children (Callable[[T], Iterable[Tuple[Any, T]]]) – Callable state -> iterable of (move, next_state) pairs describing every move available at state, such as a StateGraph’s edges out of state paired with their action.

  • evaluate (Callable[[T], float]) – Callable state -> heuristic/terminal score from the maximizing player’s perspective. Larger is better for the maximizing player.

  • is_terminal (Callable[[T], bool]) – Callable state -> whether state is a terminal state (win/loss/draw, or no more moves), regardless of depth.

  • alpha (float)

  • beta (float)

Returns:

A pair (best_score, best_move), where best_move is the move leading to best_score, or None if depth is 0, state is terminal, or get_children yields nothing.

Return type:

Tuple[float, Any | None]

gale.ai.minimax.best_move(state, depth, maximizing, get_children, evaluate, is_terminal)[source]
Parameters:

  • state (T) – The state to search from.

  • depth (int) – How many plies ahead to explore. 0 evaluates state directly without expanding it.

  • maximizing (bool) – Whether the player to move at state is the maximizing player.

  • get_children (Callable[[T], Iterable[Tuple[Any, T]]]) – Callable state -> iterable of (move, next_state) pairs describing every move available at state.

  • evaluate (Callable[[T], float]) – Callable state -> heuristic/terminal score from the maximizing player’s perspective.

  • is_terminal (Callable[[T], bool]) – Callable state -> whether state is a terminal state.

Returns:

The move minimax deems best from state, or None if there is none.

Return type:

Any