> Its an exhaustive search, like a breadth-first search.
It's actually neither of those.
An exhaustive search would definitely not be able to search as deeply as state of the art alpha-beta chess engines can. There's a lot of pruning going on.
Minimax search (with or without alpha beta pruning) is depth-first search, not breadth-first. Iterative deepening means that you start with a low depth search and progressively increase depth, using the results from the previous depth to do move ordering which increases the efficiency of pruning.
The pruning in Alpha-beta is very much a heuristic that is applied on top of the template. For example, Stockfish may recognize that some moves are "forced" and will iterate a specific variation deeper.
Nonetheless, the classical chess search algorithm is exhaustive. Breadth-first search with Alpha-Beta pruning is how it is taught at universities. Stockfish uses iterated deepening as you've said, but that's very similar to Breadth-first search.
Stockfish is also multithreaded and got a hash-table to remember previously searched positions (even positions from "another" branch of the tree).
I think my point is that Quiescence search is an explicitly programmed feature of Stockfish. Under certain conditions, Stockfish will search deeper (but not all conditions).
MCTS on the other hand is almost ENTIRELY a quiescence search. MCTS analyzes "deeper" positions, while Stockfish analyzes more exhaustively.
------
And again: classical MCTS (probably not AlphaZero) will keep going until it evaluates a position as "win", "loss", or "draw". It will NOT return until it gets that kind of evaluation.
Positions of "win" are seen as a "win" with a multi-armed bandit, and are explored further and analyzed further. Positions of "loss" or "draw" will be seen as a miss in the multi-armed bandit, but the "exploration" phase of the algorithm will randomly search a position anyway.
The multiarmed bandit heuristic is to search "winning" positions more, but to "explore" losing positions less. Ex: every time you search a winning position 10,000 times, you want to search losing positions 100 times. The precise formula involves a logarithm, division, and I think a square-root. The formula has some statistical guarantees about finding results that I never really understood, but hope to research and math-out one day.
MCTS has a more elegant statistical theory behind it. But its still very much a manually tweaked process: how much time to dedicate "exploring" bad moves, and how much time spent "exploiting" good moves (analyzing and making sure a "good" move is as good as you think it is). Alpha-Beta search doesn't have any concept of this, and requires a Quiescence search engine "tacked on" for the feature. AlphaZero was interesting in that this manual tweaking of MCTS was left to the neural network training. Its a very elegant use of neural nets to improve the MCTS template.
> Nonetheless, the classical chess search algorithm is exhaustive.
Minimax search is brute-force, exhaustive search. As soon as you add any pruning (such as alpha-beta pruning, or the myriad search tricks used in chess engines), that's no longer the case. That is unless we're quibbling on the semantics of "exhaustive".
> Breadth-first search with Alpha-Beta pruning is how it is taught at universities.
Again, no. Minimax search (regardless of any applied pruning) proceeds by visiting the possible successors of a node one at a time, immediately recursing on each of them. See wikipedia's pseudocode for it:
Alpha Beta pruning results in the same answer as classical Minimax search.
Alpha Beta pruning is an optimization: there's no need to search the whole tree to know that a branch can be pruned (but still result in the same answer as minimax).
Minimax with Alpha Beta pruning gives you the best position for a given depth. ("Best" as defined by Minimax to the same depth without pruning).
It's actually neither of those.
An exhaustive search would definitely not be able to search as deeply as state of the art alpha-beta chess engines can. There's a lot of pruning going on.
Minimax search (with or without alpha beta pruning) is depth-first search, not breadth-first. Iterative deepening means that you start with a low depth search and progressively increase depth, using the results from the previous depth to do move ordering which increases the efficiency of pruning.