But that isn't minimax, its pruning by some evaluation function, where in this case the evaluation function is "blackbox Deep neural net trained on many games"
MCTS simulates games randomly and creates a distribution of expected value for each one based on some cool math. It estimates the value of each state based on a sample. Minimax actually calculates them all (or all of them except for some pruned ones).
That's the whole reason MCTS can work on Go and minimax doesn't. Minimax actually needs to look at all possible branches all the way down. MCTS can just say "well its been 100ms, let's use the estimates I have".
> No, stockfish uses minimax with pruning... Minimax actually needs to look at all possible branches all the way down.
No, I assure you that stockfish definitely does not look "all the way down (ie to states where the game is over)" in most positions, even with pruning - that would take too long. It uses a static evaluation function to evaluate positions without searching down the tree further.
> MCTS simulates games randomly and creates a distribution of expected value for each one based on some cool math.
You described the "Monte Carlo" part of MCTS but not the "Tree Search" part. It's right in the name! See for example the first paragraph on page 20 of https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf, which clearly describes AG constructing a search tree.
Minimax obviously will produce perfect play in both chess and Go, but we can't use it because it takes too long. Hence we prune and truncate the search tree. When we truncate it we use an approximation of the value of the node (the static evaluation function); when we prune we sometimes use the static evaluation function as well. This is true in both MCTS and in Stockfish.
>No, I assure you that stockfish definitely does not look "all the way down (ie to states where the game is over)" in most positions, even with pruning - that would take too long. It uses a static evaluation function to evaluate positions without searching down the tree further
Ehh alright, it calculates the value of a node exactly (or exactly assuming its evaluation function). MCTS does not.
To be clear, what I meant, that you pulled out of context is that Minimax requires an exact calculation of the value of each child before choosing the best and returning it, this requires either simulating every possible game, or an evaluation function (depth-pruning). MCTS uses monte-carlo methods to estimate the best paths instead of trying all of them naively. At t=infinity, MCTS is equivalent to Minimax, because it will try all nodes. But it can run in time constrained systems better because it picks a much smarter order to run in.
>You described the "Monte Carlo" part of MCTS but not the "Tree Search" part. It's right in the name! See for example the first paragraph on page 20 of https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf, which clearly describes AG constructing a search tree.
yes. That has nothing to do with minimax though.
Which is what I said. AlphaGo uses pruning. AlphaGo doesn't use minimax with or without pruning, it uses MCTS (with pruning).
