Minimax: Playing Against an Opponent

Max and min take turns

In two-player, zero-sum games with perfect information (tic-tac-toe, chess, Go), minimax searches the game tree: the maximising player picks the move with the highest value, assuming the minimising opponent replies with the move that is worst for them, recursively down to finished games (or to a depth limit with an evaluation function estimating who is winning). The resulting value tells you the outcome under perfect play. Memoising repeated positions (a transposition table) avoids recomputing them.

Opponents and rules

Adversarial search plans against an opponent; constraint satisfaction finds assignments that obey rules.

Solving tic-tac-toe with minimax, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. Searching the full game shows that tic-tac-toe is a draw (value 0) with perfect play. In the position XX.OO.... minimax picks square 2 to win immediately. With memoisation, 5,478 distinct positions are evaluated.

from functools import lru_cache
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)]
def winner(b):
    for a, c, d in LINES:
        if b[a] != "." and b[a] == b[c] == b[d]: return b[a]
    return None
calls = 0
@lru_cache(maxsize=None)
def minimax(b, player):
    global calls; calls += 1
    w = winner(b)
    if w: return 1 if w == "X" else -1
    if "." not in b: return 0
    scores = [minimax(b[:i] + player + b[i + 1:], "O" if player == "X" else "X")
              for i, ch in enumerate(b) if ch == "."]
    return max(scores) if player == "X" else min(scores)
print("value of the empty board with perfect play:", minimax("." * 9, "X"), "(0 = draw)")
board = "XX.OO...."   # X to move: can win at square 2
best = max((i for i, ch in enumerate(board) if ch == "."),
           key=lambda i: minimax(board[:i] + "X" + board[i + 1:], "O"))
print("from XX.OO.... X should play square", best)
print("distinct positions evaluated (with memoisation):", minimax.cache_info().currsize)

Output:

value of the empty board with perfect play: 0 (0 = draw)
from XX.OO.... X should play square 2
distinct positions evaluated (with memoisation): 5478

Use depth limits for big games

Chess cannot be searched to the end; real engines search to a depth and score positions with an evaluation function.

Quick check: What does minimax assume about the opponent?

• The opponent never moves
• The opponent plays randomly
• The opponent always chooses the move that is best for them
• The opponent helps you win