Computer AI

This module contains the decision algorithms for the computer player. The AI uses an alpha-beta pruning minimax algorithm to loop over all possibilities to a certain depth and determine the best move.

ComputerData

class computer.ComputerData(compound_move: list[tuple[vec2, vec2]], achievable_score: int, compute_time: int, search_depth: int)

Holds the result of the AI’s computation.

achievable_score: int: The best score the AI believes it can achieve in relation to its search depth.

compound_move: list[tuple[vec2, vec2]]: The move (or sequence of capturing moves) the AI has determined to make.

compute_time: int: The time it took to compute the result.

search_depth: int: The depth of the minimax search.

get_compound_moves

computer.get_compound_moves(board: Board, player: Player) → Generator[tuple[list[vec2], Board]]

Generate all possible sequences of moves for a player.

This function starts by generating all possible moves, if there are capturing moves, it will generate all possible moves from those positions and so on until there are no more moves. This function also takes care of turning normal pieces into kings if they reach the opposite side.

Parameters

board (Board) – The board to generate moves for.
player (Player) – The player to generate moves for.

Yields

list[vec2] – A starting position and then a sequence of positions a piece can, in order, jump to.
Board – The state of the board after executing the sequence of moves.

get_moves

computer.get_moves(board: Board, player: Player, locked_piece: vec2 = None) → tuple[bool, defaultdict[vec2, list[vec2]]]

Generate all possible moves for a player, with respect to a locked piece.

This function is essentially the same as generate_moves(), but without an encapsulating Game object.

Parameters

board (Board) – The board to generate moves for.
player (Player) – The player to generate moves for.
locked_piece (vec2, optional) – A piece which has already captured this turn.

Returns

bool – Whether or the generated moves are capturing.
defaultdict[vec2, list[vec2]] – A mapping of pieces to their possible moves.

minimax

computer.minimax(board: Board, player: Player, depth: int = 7, maximizing: bool = True, alpha: float = - inf, beta: float = inf) → tuple[float, list[vec2]]

The main decision function of the AI.

An alpha-beta pruning minimax algorithm is used to iterate over all possible board states, to a certain depth. When it reaches the max depth or a game end the board state is heuristically evaluated. Caches scores for ending board states to speed up the algorithm.

Parameters

board (Board) – The board to generate moves from.
player (Player) – The computer player.
depth (int, default 7) – The remaining depth to search to.
maximizing (bool, default True) – Whether the current iteration’s player is trying to maximize or minimize the score.
alpha (float, default -float('inf')) – The alpha value for pruning.
beta (float, default float('inf')) – The beta value for pruning.

Returns

float – The best attainable score for the current player.
list[vec2] – The last move made (in reverse) – aka the move to make, to get to this score.

run

computer.run(board: Board, player: Player) → ComputerData

The AI’s entry point function.

Runs the minimax algorithm and returns the result.

Supported debugging levels:

0: No debugging.
1: Prints the algorithm timing. Prints the visited end node count, cached end node count, and the best score.
2: Profiles the algorithm.
3: Dumps data for each visited node.

Parameters

board (Board) – The board to use as a starting point.
player (Player) – The player to run the AI as.

Returns

The result of the AI’s computatio.

Return type

ComputerData