Python · Course navigation

Adversarial search: minimax and alpha-beta pruning

Choose moves in a two-player game and prune branches that cannot change the result.

On this page

Before you start

Recursion and strings.

Choose moves in a two-player game and prune branches that cannot change the result.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

In a two-player, turn-taking game with perfect information, such as tic-tac-toe, one player's gain is the other's loss. Minimax search assumes both players play optimally. The maximizing player, X here, picks the move with the highest value, and the minimizing player, O, picks the lowest. Leaf positions are scored +1 if X has won, −1 if O has won, and 0 for a draw, and the scores are passed up the tree.

Minimax must visit every position in the game tree. Alpha-beta pruning returns the same value while skipping branches that cannot affect it. It carries two bounds: alpha, the best value the maximizer is already guaranteed, and beta, the best the minimizer is already guaranteed. When alpha is at least beta, the remaining moves at that node cannot change the final result, so the search cuts them off.

The program evaluates a position in which X is in a corner and O is in the center, with X to move. Both methods return 0, a draw with best play. Plain minimax visits 7332 positions while alpha-beta visits only 844. How much pruning you get depends on move ordering: examining the best moves first prunes the most. For large games such as chess, programs combine alpha-beta with depth limits and evaluation functions rather than searching to the end.

Code example

Python

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
nodes = 0


def winner(board):
    for a, b, c in LINES:
        if board[a] != "." and board[a] == board[b] == board[c]:
            return board[a]
    return None


def terminal_score(board):
    won = winner(board)
    if won:
        return 1 if won == "X" else -1
    return 0 if "." not in board else None


def minimax(board, player):
    global nodes
    nodes += 1
    score = terminal_score(board)
    if score is not None:
        return score
    other = "O" if player == "X" else "X"
    scores = [minimax(board[:i] + player + board[i + 1:], other) for i, cell in enumerate(board) if cell == "."]
    return max(scores) if player == "X" else min(scores)


def alphabeta(board, player, alpha, beta):
    global nodes
    nodes += 1
    score = terminal_score(board)
    if score is not None:
        return score
    other = "O" if player == "X" else "X"
    value = -2 if player == "X" else 2
    for i, cell in enumerate(board):
        if cell != ".":
            continue
        child = alphabeta(board[:i] + player + board[i + 1:], other, alpha, beta)
        if player == "X":
            value = max(value, child)
            alpha = max(alpha, value)
        else:
            value = min(value, child)
            beta = min(beta, value)
        if alpha >= beta:
            break
    return value


start = "X...O...."
nodes = 0
plain = minimax(start, "X")
plain_nodes = nodes
nodes = 0
pruned = alphabeta(start, "X", -2, 2)
print(plain, pruned)
print(plain_nodes, nodes)

Output

0 0
7332 844

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]

2nodes = 0

5def winner(board):

6 for a, b, c in LINES:

7 if board[a] != "." and board[a] == board[b] == board[c]:

8 return board[a]

9 return None

12def terminal_score(board):

13 won = winner(board)

14 if won:

15 return 1 if won == "X" else -1

16 return 0 if "." not in board else None

19def minimax(board, player):

20 global nodes

21 nodes += 1

22 score = terminal_score(board)

23 if score is not None:

24 return score

25 other = "O" if player == "X" else "X"

26 scores = [minimax(board[:i] + player + board[i + 1:], other) for i, cell in enumerate(board) if cell == "."]

27 return max(scores) if player == "X" else min(scores)

30def alphabeta(board, player, alpha, beta):

31 global nodes

32 nodes += 1

33 score = terminal_score(board)

34 if score is not None:

35 return score

36 other = "O" if player == "X" else "X"

37 value = -2 if player == "X" else 2

38 for i, cell in enumerate(board):

39 if cell != ".":

40 continue

41 child = alphabeta(board[:i] + player + board[i + 1:], other, alpha, beta)

42 if player == "X":

43 value = max(value, child)

44 alpha = max(alpha, value)

45 else:

46 value = min(value, child)

47 beta = min(beta, value)

48 if alpha >= beta:

49 break

50 return value

53start = "X...O...."

54nodes = 0

55plain = minimax(start, "X")

56plain_nodes = nodes

57nodes = 0

58pruned = alphabeta(start, "X", -2, 2)

59print(plain, pruned)

60print(plain_nodes, nodes)

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Minimax tries every legal move and recursively scores the resulting position.	`visits every position`	—
X chooses the highest value, O the lowest: each assumes the opponent replies optimally.	`visits every position`	—
When the maximizer's guaranteed value reaches the minimizer's, the remaining moves cannot change the result, so they are skipped.	`prune`	—
Both algorithms agree: with best play from this position the game is a draw.	`prune`	0 0
Minimax visited 7332 positions and alpha-beta only 844, with the same answer.	`prune`	0 0 7332 844

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

Minimax is O(b^d) for branching factor b and depth d. Alpha-beta with ideal ordering reaches about O(b^(d/2)), which doubles the depth you can search in the same time.

Alpha-beta never changes the minimax value. It only avoids work that cannot affect it.
Pruning quality depends on move ordering. In the worst ordering nothing is pruned.
Minimax assumes a perfect opponent and complete information. Games with chance or hidden information need other methods such as expectimax or sampling.

Try it yourself

What would minimax return for a position where X can win in one move?

Reveal answer and reasoning

+1. The winning move yields a terminal score of +1, and the maximizing player picks the maximum of the child values.