3 ms·
> Nonetheless, the classical chess search algorithm is exhaustive. Minimax search is brute-force, exhaustive search. As soon as you add any pruning (such as al
by FartyMcFarter 8y ago
> 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:
https://en.wikipedia.org/wiki/Minimax#Pseudocode https://en.wikipedia.org/wiki/Minimax#Pseudocode
Or for a chess-specific source, see:
https://www.chessprogramming.org/index.php?title=Minimax https://www.chessprogramming.org/index.php?title=Minimax
- dragontamer 8y agoAlpha 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).