AlgoVerse

Minimax with alpha–beta pruning

The best move in a game tree: the players take turns maximizing and minimizing, and branches that cannot change the result are pruned.

In a two-player game, the maximizer wants a high score and the minimizer a low one. The game tree shows every move, and the leaves are the scores at the end of the game. Minimax works up from the leaves: the maximum of the children on a max level, the minimum on a min level.

Read the full explanation ↓
Input:
n=8PDF export

Eight leaves on three levels (max, min, max); two prunings happen and only 5 leaves are seen. The answer is 5.

  1. INF = float("inf")
  4. def alpha_beta(leaves):
  5. return search(leaves, 0, len(leaves) - 1, True, -INF, INF)
  8. def search(leaves, lo, hi, maximizing, alpha, beta):
  9. if lo == hi:
  10. return leaves[lo]
  11. mid = (lo + hi) // 2
  12. if maximizing:
  13. best = search(leaves, lo, mid, False, alpha, beta)
  14. alpha = max(alpha, best)
  15. if alpha >= beta:
  16. return best
  17. best = max(best, search(leaves, mid + 1, hi, False, alpha, beta))
  18. return best
  19. best = search(leaves, lo, mid, True, alpha, beta)
  20. beta = min(beta, best)
  21. if alpha >= beta:
  22. return best
  23. best = min(best, search(leaves, mid + 1, hi, True, alpha, beta))
  24. return best

Invariant: α is the best value the maximizer has guaranteed so far and β the minimizer's; if α ≥ β, this branch will never be chosen.

Start

30516293142506-17

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

leaves list

3569120-1

Call stack

  1. alpha_beta()line 4
Step 1 of 69
Black = max_update, min_update · Orange = key stepleaf: 0/5 · max_update: 0/4 · max_done: 0/3 · min_update: 0/2 · prune: 0/2 · min_done: 0/1
    Explanation

    The idea

    In a two-player game, the maximizer wants a high score and the minimizer a low one. The game tree shows every move, and the leaves are the scores at the end of the game. Minimax works up from the leaves: the maximum of the children on a max level, the minimum on a min level.

    Here the array holds the leaves of a full binary tree: two moves per turn, with the maximizer moving first.

    Alpha–beta pruning

    • α: the score the maximizer has guaranteed so far.
    • β: the score the minimizer has guaranteed so far.

    If α ≥ β somewhere, the opponent will never let the game reach this branch; so the remaining children are pruned. The answer is exactly the minimax value, just found faster.

    Move order

    With a good order (best move first) the number of leaves looked at drops to about n^¾ (for a binary tree); with a bad order nothing is saved.

    What to watch in the trace

    • The call tree is the game tree; the range lo..hi under the array is the current subtree.
    • Compare "a lucky order" with "an unlucky order" by how many leaves are looked at.