Minimax

Two players take turns. Max wants the final score as high as possible, min wants it low. The leaves are the scores at the end of every possible game, shown as stars: the brighter the star, the better for max.

Minimax works backwards from the leaves. On a red max ring a node takes the highest value of its children, on a blue min ring the lowest, until the root knows the score both sides can force with perfect play.

Alpha-beta gets the same answer while skipping work. It searches depth first and keeps alpha, the best max can already guarantee, and beta, the best min can guarantee. Once alpha reaches beta, the remaining children cannot change the result, so they are pruned. Sorting the best moves first prunes the most: about the square root of the tree.

In the games below the tree is real. Tic-tac-toe is small enough to search to the end, so minimax and alpha-beta play perfectly. Connect Four is not, so the search stops a few plies ahead and a heuristic scores the position by its open lines and centre control. Monte Carlo tree search skips the heuristic: it plays thousands of random games, spends more of them on moves that keep winning (UCB1), and plays the move it visited most.

a whole forest of futures collapses to one number, and good ordering means you can skip most of it without ever being wrong.