AG doesn't actually use minimax, it uses montecarlo tree search, which doesn't even try to simulate a good opponent, it just plays lots of games very fast.

Actually, the cool thing about AG is that it doesn't just use MCTS, but that it adds in deep learning and reinforcement learning :-) I was surprised by how readable their paper was!

Here's a link: http://www.nature.com/nature/journal/v529/n7587/full/nature1...

I think you search on the title, you can find probably find a non paywalled version.

Yup! Their additions to the algorithm are actually super simple, it was really surprising to me, its just very computationally intensive on the front end.

its even more than that of course... the network has to poke its fingers in somewhere, i'd be guessing it prunes those trees - so it is a bit more than playing lots of games really fast

AG does use minimax in the same sense that for example stockfish does (bounded depth and with pruning)

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"

In that case, stockfish doesn't use minimax either right, because it does pruning as well

No, stockfish uses minimax with pruning.

Minimax and MCTS are just different algorithms.

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).