Alpha-beta pruning
Which branches can I skip without changing the answer?
Minimax that stops exploring a branch as soon as it is proven no better than one already found. The same move, after far fewer positions.
Result. The root is 3, the same answer as minimax, with 6 of the 9 leaves looked at. The cuts only skip work that could not change the answer.
Alpha-beta keeps two numbers while it searches. Alpha is the best score the side choosing is already sure of; beta is the best score the opponent is already sure of. Together they form a window.
If a branch can only lead outside that window, nobody sensible would let the game reach it: the opponent already has something better elsewhere. The remaining moves in that branch are never looked at. The result is exactly minimax’s result, never an approximation.
How much it saves depends on the order the moves are tried. Strong moves first and the cuts come early; strong moves last and nothing is saved. With perfect ordering it looks at about the square root of the positions minimax would, which means it can search about twice as deep for the same effort.
Loading the demo…
Connect Four with alpha-beta selected. Press “Compare the algorithms here” mid-game: minimax and alpha-beta pick the same column, after very different numbers of positions.
- 01Run minimax, passing down alpha (starting at minus infinity) and beta (starting at plus infinity).
- 02On your own turn, raise alpha to any better score found; on the opponent’s turn, lower beta.
- 03As soon as alpha is at least beta, stop: the opponent will never allow this branch.
- 04Order the moves so the likely best come first, such as the centre in Connect Four or the corners in Othello. The earlier the good move, the more gets cut.
function alphabeta(position, depth, alpha, beta, me):
if game_over(position) or depth == 0: return evaluate(position, me)
if turn(position) == me:
best = -infinity
for m in ordered_moves(position):
best = max(best, alphabeta(play(position, m), depth - 1, alpha, beta, me))
alpha = max(alpha, best)
if alpha >= beta: break # cut-off
return best
else:
best = +infinity
for m in ordered_moves(position):
best = min(best, alphabeta(play(position, m), depth - 1, alpha, beta, me))
beta = min(beta, best)
if alpha >= beta: break # cut-off
return bestThe worst case is no better than minimax. With the best moves tried first it is about the square root of that. Good move ordering gets most of the way.
- Returns exactly the move minimax would.
- Often lets the search go twice as deep for the same time.
- Costs a couple of comparisons and a move ordering.
- Without a good move order it saves little.
- Still exponential, so large games still need an evaluation function and a depth limit.
- It has to see the whole window, so it is awkward to run in parallel.
- 01Tic-tac-toeThe same perfect play as minimax with far fewer positions; the demo prints both counts side by side.
- 02HEXSearches only the cells near existing stones, best first by the shortest-connection evaluation, so the cuts come early.
- 03OthelloMoves are tried corners first, then edges, so a bad branch is dropped quickly.
- 04Connect FourThe centre column is tried first, because it takes part in the most lines.