Minimax

The algorithm constructs a game tree where nodes represent game states and edges represent moves. It recursively explores this tree to terminal states (win, loss, draw) or a predefined depth limit. At each level, it alternates between maximizing and minimizing the returned value, assuming optimal play from both sides.

• Maximizer's Turn: Chooses the move leading to the child node with the highest evaluation.
• Minimizer's Turn: Chooses the move leading to the child node with the lowest evaluation.
• Base Case: At a terminal node or depth limit, a static evaluation function scores the position (e.g., +∞ for win, -∞ for loss, material advantage in chess).

This heuristic function is critical for non-terminal positions. It quantifies the desirability of a game state for the maximizing player. A perfect evaluation function would make Minimax optimal, but it is typically an approximation.

Common components include:

• Material Count: Sum of piece values (e.g., queen=9, pawn=1 in chess).
• Positional Advantage: Control of center, pawn structure, king safety.
• Mobility: Number of legal moves available.

For example, in a simple chess evaluation: Score = (White Material - Black Material) + 0.1 * (White Mobility - Black Mobility). The function must be fast to compute, as it is called thousands of times per search.

Alpha-beta pruning is an optimization technique that dramatically improves Minimax efficiency without affecting the final result. It eliminates branches of the game tree that cannot influence the final decision.

• Alpha (α): The best value the maximizer can guarantee so far along the path to the root. Starts at -∞.
• Beta (β): The best value the minimizer can guarantee so far. Starts at +∞.

A branch is pruned when it is found to be worse than a previously examined option. For example, if the minimizer finds a move that guarantees a score of 3 (β=3), and the maximizer finds a sibling move that leads to a score of 5, the minimizer will ignore further exploration of that sibling, as the maximizer would never allow the minimizer to get a score of 5.

For complex games, searching to terminal states is computationally impossible. Minimax is therefore applied with a depth limit, creating a leaf node where the evaluation function is called.

The Horizon Effect is a major limitation: the algorithm cannot see beyond its fixed search depth. A catastrophic event (like losing a queen) that occurs just beyond the search horizon will be invisible, potentially leading to a tactically poor move that appears good in the short term.

Mitigations include:

• Iterative Deepening: Repeatedly running depth-limited searches with increasing depth, using results to inform move ordering.
• Quiescence Search: Extending search selectively from volatile positions (e.g., during a capture sequence) until a 'quiet' state is reached.

Negamax is a simplified, functionally identical formulation of Minimax. It leverages the zero-sum property: the value of a position for one player is the negative of its value for the opponent.

This allows for a single, recursive function instead of separate maximizer/minimizer functions.

Pseudocode:

codeCopy
function negamax(node, depth, color):
    if depth == 0 or node is terminal:
        return color * evaluate(node)
    value = -∞
    for each child in node.children:
        value = max(value, -negamax(child, depth-1, -color))
    return value

Here, color is +1 for the maximizing player and -1 for the minimizing player. Alpha-beta pruning integrates seamlessly with this formulation.

While classic Minimax relies on a handcrafted evaluation function, modern systems like AlphaZero replace it with a deep neural network. In AlphaZero's framework:

• A value network estimates the expected game outcome from a given state (replacing the static evaluation function).
• A policy network suggests promising moves (replacing brute-force move generation).
• Monte Carlo Tree Search (MCTS) is used instead of full-depth Minimax, guided by these networks to focus exploration on the most promising lines.

This hybrid approach combines the principled lookahead of adversarial search with the pattern recognition and generalization power of deep learning, achieving superhuman performance in games like Go, chess, and shogi.

An evaluation function (or static evaluator) is a heuristic that assigns a numerical score to a non-terminal game state, estimating its favorability for the current player. It is the "intelligence" that guides minimax.

• Purpose: It allows the search to stop at a certain depth (leaf node) and estimate the outcome, as searching to the end of the game is often computationally impossible.
• Design: For chess, it might sum material advantage (e.g., queen=9, pawn=1), positional control, king safety, and pawn structure. A positive score favors the maximizing player.
• Critical Role: The quality of the evaluation function is paramount; a perfect minimax search with a poor evaluator will make poor decisions. Modern systems like AlphaZero replace handcrafted functions with learned neural networks.

Adversarial search is the general category of algorithms, including minimax, designed for environments with opposing agents. The goal is to find a strategy that maximizes the agent's utility assuming the opponent(s) are acting optimally to minimize it.

• Problem Domain: It formalizes problems like two-player zero-sum games (chess, tic-tac-toe) and extends to non-zero-sum and multi-player games with modifications.
• State Space: The algorithm explores a game tree where nodes represent game states and edges represent moves. The size of this tree is defined by the game's branching factor and depth.
• Key Challenge: The exponential growth of the tree (combinatorial explosion). Techniques like pruning, transposition tables, and heuristic evaluation are essential for practical application.

Expectiminimax is an extension of the minimax algorithm for games that involve an element of chance, such as backgammon or dice-based games. It introduces chance nodes into the game tree.

• Tree Structure: The tree now has three types of nodes: Max nodes (AI's turn), Min nodes (opponent's turn), and Chance nodes (random event).
• Calculation: At a chance node, the value is the expected value (probability-weighted average) of its children's values, rather than a simple min or max.
• Complexity: The presence of chance increases the branching factor further. It requires knowledge of the probability distribution of random events (e.g., rolling a specific sum on two dice).