Minimax

The idea

Minimax is a decision rule for two-player, zero-sum games (one player's gain is the other's loss), like tic-tac-toe or chess. You explore possible future moves as a tree and assume both players play perfectly: on your turns you pick the move that maximizes your score (you are MAX), and you assume the opponent picks the move that minimizes it (they are MIN). You look ahead to some depth, score those far-off positions, then bring those values back up the tree so the move you make right now already accounts for the opponent's best replies.

How it works

1. Model the game as a tree: the current position is the root, and each branch is a legal move leading to a new position.
2. Alternate the layers by whose turn it is: a MAX layer (you) then a MIN layer (opponent), then MAX again, and so on.
3. Stop growing the tree at a depth limit (or at a finished game). These stopping positions are called leaves.
4. Score each leaf with an evaluation function: high numbers are good for MAX, low numbers are good for MIN (e.g. +1 win, 0 draw, -1 loss).
5. Back the values up one layer at a time. At a MAX node, take the highest child value; at a MIN node, take the lowest child value.
6. Keep folding values upward until every node has a value that assumes perfect play from both sides.
7. At the root (your turn), pick the move whose branch produced the best backed-up value, then actually play that move.
8. On the opponent's real reply, repeat the whole search from the new position.

OPEN, CLOSED & the data structures

["A game tree of positions, expanded on the fly by recursion (no explicit tree object needed — the call stack IS the tree).", "A turn flag per node marking whether it is a MAX layer or a MIN layer.", "A depth counter that decreases each level and triggers the leaf evaluation when it hits 0.", "An evaluation function that turns a non-terminal position into a single number.", "The recursion returns a backed-up value per node; the root also remembers which move gave the best value."]

Pseudocode

function minimax(state, depth, isMaxPlayer):
    if depth == 0 or state is terminal:
        return evaluate(state)          # score from MAX's point of view

    if isMaxPlayer:                      # MAX wants the highest value
        best = -infinity
        for each move in legalMoves(state):
            value = minimax(apply(state, move), depth - 1, false)
            best = max(best, value)
        return best
    else:                                # MIN wants the lowest value
        best = +infinity
        for each move in legalMoves(state):
            value = minimax(apply(state, move), depth - 1, true)
            best = min(best, value)
        return best

# To choose the actual move at the root:
# pick the move whose minimax(child, depth-1, false) value is largest.

At a glance