# Minimax: Playing Against an Opponent — Artificial Intelligence

Source: https://www.skillbyai.com/en/artificial-intelligence/g-minimax

> Assume the opponent plays its best.

## 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.

![Three ideas: minimax, alpha-beta, constraint satisfaction.](assets/figures/artificial-intelligence/section-3-map.svg) — Figure 3.1 — Minimax, alpha-beta and constraints.

## 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.

```python
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.

**Quiz:** What does minimax assume about the opponent?

- [ ] The opponent never moves
- [ ] The opponent plays randomly
- [x] The opponent always chooses the move that is best for them
- [ ] The opponent helps you win

*Answer:* The opponent always chooses the move that is best for them. Plan for the strongest reply.