Minimax and game trees — the machine that looked ahead
Every game of tic-tac-toe that could ever happen, counted from the rules. A machine that cannot lose, an idea that skips 97% of the work without approximating anything, and the wall the whole approach hits.
Somewhere around the age of seven, everybody works out that tic-tac-toe is pointless. Play properly and it is always a draw.
That childhood discovery is a real result, and it is the first thing in this course a machine can do better than you. Not because the machine is clever. Because it can look at every game that could ever happen.
There are 255,168 complete games of tic-tac-toe
Not a sample. All of them. The notebook starts from an empty board and walks the whole tree of possibilities to the end of every line.
Nine choices become two hundred thousand in eight moves.
| Count | |
|---|---|
| complete games | 255,168 |
| positions reached | 549,946 |
| X wins | 131,184 |
| O wins | 77,904 |
| drawn | 46,080 |
complete games
- Count
- 255,168
positions reached
- Count
- 549,946
X wins
- Count
- 131,184
O wins
- Count
- 77,904
drawn
- Count
- 46,080
That number was counted, not looked up. 255,168 is a famous figure you can find in a hundred articles. The notebook derives it from the rules in 0.3 seconds, at about 1,572,546 positions a second.
Score the endings, then work backwards assuming the opponent plays against you
Seeing every future is different from knowing what to do. You have to score the futures, and the scoring has to account for an opponent who wants the opposite of what you want.
A finished game is worth +1 if you won, −1 if you lost, 0 for a draw. Then work backwards. On your turn take the best score available. On their turn assume they take the worst one for you.
You take the maximum. They take the minimum. That is the whole algorithm, and its whole name: minimax.
Run it from an empty board and it reports what perfect play is worth: a draw. Which is what you worked out when you were seven, except now it is proved.
It played 1,000 games and lost none
Claiming is cheap. The notebook plays it 1,000 times against an opponent that moves at random, five hundred games as each side.
- 913 wins
- 87 draws
- 0 losses
Zero, and not “very few”. It cannot lose, and the reason is that it already looked. Every trap you could set, it has already walked to the end of.
You can prove a branch cannot matter without reading it
Suppose you have found a move that guarantees a draw. You start examining a second move and, two replies in, you find a reply that loses.
Stop. You do not need to see the rest of that branch. Your opponent will simply choose that reply, so the branch is worth at most a loss, and you already have a draw in hand. That is alpha-beta pruning.
From 549,946 positions down to 18,297. That is 96.7%% of the work skipped, about 30 times less. And the answer is identical, which the notebook checks.
Nothing was approximated. This is a proof that certain work is pointless, rather than a shortcut that trades accuracy for speed. Almost everything else in this course buys speed by giving something up.
Chess has about 120 zeroes. The universe has about 80 zeroes of atoms.
So run the same program on chess.
Tic-tac-toe has about 5.4 zeroes. Chess has around a hundred and twenty. That puts chess forty orders of magnitude beyond counting every atom in existence.
At the rate this notebook managed, walking the chess tree would take about 2e+106 years. The universe is roughly 1.4 × 10¹⁰ years old.
A faster computer removes twelve zeroes from a hundred and twenty
This is not a hardware problem, and it never will be. A computer a trillion times faster gets you twelve zeroes. The approach does not need optimising. It needs replacing.
And yet a machine plays chess better than any human who has ever lived
It does that without seeing the end of the game. So it must be doing something other than what you just watched. That is the next lesson.
One thing worth carrying out of here first. This lesson built a machine that cannot lose at a game, using an idea a beginner could implement in an afternoon. That same machine cannot pick up one of the pieces.
content/notebooks/introduction-to-ai/the-machine-that-looked-ahead.ipynb
Walk the tree yourself, then turn pruning on and off. Worth trying: change the move order the search considers and watch how much pruning saves change with it.
Show the code7 cells
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)]
EMPTY = (None,) * 9
def winner(b):
for i, j, k in LINES:
if b[i] is not None and b[i] == b[j] == b[k]:
return b[i]
return None
def moves(b):
return [i for i, c in enumerate(b) if c is None]
def play(b, i, mark):
return b[:i] + (mark,) + b[i+1:]depth_nodes = [0] * 10
stats = {'nodes': 0, 'games': 0, 'x': 0, 'o': 0, 'draw': 0}
def walk(b, mark, d):
stats['nodes'] += 1
depth_nodes[d] += 1
w = winner(b)
if w or not moves(b):
stats['games'] += 1
stats['x' if w == 'X' else 'o' if w == 'O' else 'draw'] += 1
return
for m in moves(b):
walk(play(b, m, mark), 'O' if mark == 'X' else 'X', d + 1)
t0 = time.time()
walk(EMPTY, 'X', 0)
elapsed = time.time() - t0
record('total_games', f"{stats['games']:,}")
record('total_nodes', f"{stats['nodes']:,}")
record('games_x_wins', f"{stats['x']:,}")
record('games_o_wins', f"{stats['o']:,}")
record('games_drawn', f"{stats['draw']:,}")
record('walk_seconds', f'{elapsed:.1f}')
record('nodes_per_second', f"{stats['nodes']/elapsed:,.0f}")def plot(ax):
d = list(range(9))
v = depth_nodes[:9]
ax.bar([str(i) for i in d], v)
for i, val in enumerate(v):
ax.text(i, val * 1.15, f'{val:,}', ha='center', fontsize=8.5)
ax.set_yscale('log')
ax.set_ylim(0.6, max(v) * 6)
ax.set_xlabel('moves played')
ax.set_ylabel('positions to consider (log scale)')
save_fig('tree-by-depth', plot, figsize=(7, 4.0))
record('nodes_move_1', f'{depth_nodes[1]:,}')
record('nodes_move_4', f'{depth_nodes[4]:,}')
record('nodes_move_7', f'{depth_nodes[7]:,}')def minimax(b, mark, counter):
counter[0] += 1
w = winner(b)
if w == 'X': return 1
if w == 'O': return -1
if not moves(b): return 0
scores = [minimax(play(b, m, mark), 'O' if mark == 'X' else 'X', counter)
for m in moves(b)]
return max(scores) if mark == 'X' else min(scores)
plain = [0]
value = minimax(EMPTY, 'X', plain)
record('perfect_play_value', {1: 'X wins', -1: 'O wins', 0: 'a draw'}[value])
record('minimax_nodes', f'{plain[0]:,}')def best_move(b, mark):
c = [0]
scored = [(minimax(play(b, m, mark), 'O' if mark == 'X' else 'X', c), m)
for m in moves(b)]
return (max if mark == 'X' else min)(scored)[1]
rng = random.Random(7)
res = {'win': 0, 'draw': 0, 'loss': 0}
for game in range(1000):
ai = 'X' if game % 2 == 0 else 'O'
b, mark = EMPTY, 'X'
while winner(b) is None and moves(b):
m = best_move(b, mark) if mark == ai else rng.choice(moves(b))
b = play(b, m, mark)
mark = 'O' if mark == 'X' else 'X'
w = winner(b)
res['draw' if w is None else 'win' if w == ai else 'loss'] += 1
record('vs_random_games', f"{sum(res.values()):,}")
record('vs_random_wins', f"{res['win']:,}")
record('vs_random_draws', f"{res['draw']:,}")
record('vs_random_losses', f"{res['loss']:,}")def ab(b, mark, alpha, beta, counter):
counter[0] += 1
w = winner(b)
if w == 'X': return 1
if w == 'O': return -1
if not moves(b): return 0
if mark == 'X':
best = -2
for m in moves(b):
best = max(best, ab(play(b, m, 'X'), 'O', alpha, beta, counter))
alpha = max(alpha, best)
if beta <= alpha: break
return best
best = 2
for m in moves(b):
best = min(best, ab(play(b, m, 'O'), 'X', alpha, beta, counter))
beta = min(beta, best)
if beta <= alpha: break
return best
pruned = [0]
value_ab = ab(EMPTY, 'X', -2, 2, pruned)
record('alphabeta_nodes', f'{pruned[0]:,}')
record('alphabeta_same_answer', 'yes' if value_ab == value else 'NO')
record('pruning_factor', f'{plain[0] / pruned[0]:.0f}')
record('pruning_saved_pct', f'{100 * (1 - pruned[0] / plain[0]):.1f}%')
def plot(ax):
bars = ax.bar(['look at everything\n(minimax)', 'prove what cannot matter\n(alpha-beta)'],
[plain[0], pruned[0]])
bars[1].set_alpha(.55)
for b_, v in zip(bars, [plain[0], pruned[0]]):
ax.text(b_.get_x() + b_.get_width()/2, v * 1.06, f'{v:,}', ha='center', fontsize=10)
ax.set_ylabel('positions examined')
ax.set_ylim(0, plain[0] * 1.2)
save_fig('what-pruning-saves', plot, figsize=(7, 3.6))import math
TTT = stats['games']
CHESS = 1e120 # Shannon 1950, game-tree complexity
ATOMS = 1e80 # observable universe, standard estimate
def plot(ax):
labels = ['tic-tac-toe\n(counted here)', 'atoms in the\nobservable universe', 'chess\n(Shannon)']
vals = [math.log10(TTT), math.log10(ATOMS), math.log10(CHESS)]
bars = ax.barh(labels, vals)
bars[0].set_alpha(1.0); bars[1].set_alpha(.45); bars[2].set_alpha(.75)
for i, v in enumerate(vals):
ax.text(v + 1.5, i, f'10^{v:.0f}', va='center', fontsize=10)
ax.set_xlim(0, 138)
ax.set_xlabel('zeroes (each step right is ten times bigger)')
save_fig('the-wall', plot, figsize=(7, 3.0))
record('ttt_zeroes', f'{math.log10(TTT):.1f}')
years = CHESS / (stats['nodes'] / elapsed) / (60*60*24*365)
record('chess_years', f'{years:.0e}')Related lessons
Base rates — what a piece of evidence is actually worth
A face-recognition system that is 99.9% accurate and almost entirely wrong, and a number that sent an innocent woman to prison. Both are the same arithmetic, and it is the arithmetic that decides what any piece of evidence is worth.
ReadConfirmation and survivorship — what you never looked for
Two questions about evidence you did not go looking for. One is a rule you have to discover, and one is a pattern in five famous people — and in both, the thing that would have told you the truth is the thing nobody checks.
ReadLoss aversion, sunk cost and regression — what it costs you
Four questions you answer about yourself rather than about a scenario, and your own answers are the finding. Then the pattern that makes praise look useless and criticism look like it works, whatever you actually do.
Read