Games

Minimax

Its core principle is to minimize the maximum possible loss for the current player, assuming the opponent will always play optimally to maximize their own gain (and thus minimize your score). The name "Minimax" comes from the recursive alternation between two roles:

Game tree

A game tree is a directed graph where:

• Nodes represent a possible state of the game (e.g., a board configuration).
• Edges represent a move from one game state to the next.

Evaluation function — tic-tac-toe

O (MIN) is to move at the root. Values are backed up from the finished games: MAX levels take the maximum of their children, MIN levels the minimum — so the root gets v = −1 and O should play the centre (node 2).

Backtracking through the game tree

import numpy as np

def is_terminal(node):
    # implement logic to check if the game is over
    return isinstance(node, int)

def evaluate(node):
    # if we are evaluating a board for example, this function should calculate a score
    return node

def get_children(node):
    # computing next options from current node
    return node

def minimax(node, maximizingPlayer):
    if is_terminal(node):
        return evaluate(node)

    if maximizingPlayer:
        maxEval = -np.inf
        for child in get_children(node):
            eval = minimax(child, False)
            maxEval = max(maxEval, eval)
        return maxEval
    else:
        minEval = np.inf
        for child in get_children(node):
            eval = minimax(child, True)
            minEval = min(minEval, eval)
        return minEval

game_tree = [
    [
        [-1, 3],
        [5, 1]
    ],
    [
        [-6, -4],
        [0, 9]
    ]
]

optimal_score = minimax(game_tree, True)
print(f"The Optimal Score for the starting MAX player is: {optimal_score}")  # 3

Properties of minimax

Conditions for minimax optimality

The minimax algorithm guarantees the optimal move for the worst-case scenario against a rational opponent, provided the following conditions hold true:

Minimax is typically used in classical games like chess, checkers, and tic-tac-toe.

The moment any of the above conditions are violated, or a practical limitation is introduced, minimax ceases to be the "optimal" strategy:

• Against a suboptimal opponent: minimax will still win, but it might miss an opportunity to win faster or more decisively. If you know your opponent is weak, you could choose a "trap" move that minimax rejects (because a perfect opponent would avoid the trap), but that an imperfect opponent is likely to fall for.
• Limited search depth: if the search is cut short by an arbitrary depth limit (which is necessary for complex games), the result is only as good as the heuristic evaluation function used at the leaves.