Why do neural nets and machine learning tend to work well with MCTS, but not with regular Minimax game-playing AI?

Question

I've often heard MCTS grouped together with neural nets and machine learning. From what I gather, MCTS uses a refined intuition (from maching learning) to evaluate positions. This allows it to better guess which moves are worth playing out more.

But I've almost never heard of using machine learning for Minimax+alpha-beta engines. Couldn't machine learning be used for the Engine to better guess which move is best, and then look at that move's subtree first? A major optimization of the minimax algorithm is move-ordering, and this seems like a good way to accomplish that.

Answer 1

It just does. Take a look at this post explaining how MCTS works.

In both Alpha Go Lee and Alpha Zero the tree traversal follows the nodes that maximize the following UCT variant:

\begin{equation} UCT(v_i,v) = \frac{Q(v_i)}{N(v_i)} + cP(v_i, v)\sqrt{\frac{N(v)}{1+N(v_i)}} \end{equation}

where P(vi,v) is prior probability of the move (transition from v to vi ), its value comes from the output of deep neural network called Policy Network . Policy Network is a function that consumes game state and produce probability distribution over possible moves.

As you can see the Policy Network(it is actually just one neural network for both the value and the policy) is used to guide the search tree. Not all possible moves are explored. Also during the learning phase the policy network uses the "visit count" of the MCTS Nodes to learn. Moves that were explored more are the better ones. The state-of-the-art chess engine Stockfish evaluates about 1000 times more positions per second than Alpha Zero. It relies on exploring "most of" the possible positions. Calculating the score using heuristics is much faster than using Alpha Zero's 19 layer residual network. If Google were to use minimax then they wouldn't be able to look very far ahead. Alpha Zero explores about 70K moves per second which would be only a couple ply deep. MCTS allows it to explore only the more promising moves and simulate those positions.