3 ms·
Minmax as used in chess is nothing more than a Depth First Search constrained within the space of moves of agents acting in their own self interest. It searches
by BoiledCabbage 9y ago
Minmax as used in chess is nothing more than a Depth First Search constrained within the space of moves of agents acting in their own self interest. It searches the maximum number of plies it can (you can think of a ply as a move by a single player in chess[0]) within the time & memory it has allowed.
This approach is brute forcing the search space restricted by computational limits. Alpha-Beta is just an optimization to minmax and not a fundamental change in the search approach.
Chess and Go are very different games and need to be treated as such. Lots of the recent excitement about Go is due to the innovations in machine learning and specifically deep learning that have been discovered. Particularly their performance on such a complex game - significantly more complex than chess. It was predicted that Go wouldn't be able to match top strength professionals for another 5 to 10 years.
AlphaGo Played Lee Sedol last year (considered one of the top players of the past decade) and won.[1] AlphaGo beating this prediction by so much was a large part of the excitement for last year's event.
The reason for the excitement was demonstrating that Monte Carlo search, which was originally dismissed as inferior, was a significantly better approach for the game of Go. Monte Carlo is a probabilistic based approach that uses random sampling - this is very different from the DFS approach used in chess.[2] It has proven be to very effective and without another breakthrough will almost certainly be the option used going forward.
[0] -
https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol
[1] - https://en.wikipedia.org/wiki/Ply_(game_theory) https://en.wikipedia.org/wiki/Ply_(game_theory)
[2] - https://en.wikipedia.org/wiki/Monte_Carlo_method https://en.wikipedia.org/wiki/Monte_Carlo_method