Where does an engine (such as AlphaZero) use its neural network in MCTS? It shouldn't be needed to evaluate positions reached via MCTS, since I'm under the impression that only terminal game states are evaluated (checkmate or draws). Is the neural network used in the expansion portion of the MCTS algorithm? I.e., choosing which new move to expand on a leaf node, rather than randomly choosing a new move? If that's the case then it doesn't seem like the neural network plays such an important role.
Neither AlphaZero, nor Lc0 (an open source project based on the AlphaZero paper), use MCTS in its pure form, because they do not perform game rollouts - the search is simply called MCTS because the way that it expands its tree is similar to MCTS.
Here are the main differences:
- MCTS performs random rollouts to a termination condition (e.g. win, draw, loss) at leaf nodes to estimate to value of that node, whereas AlphaZero and Lc0 simply use the neural network to estimate the win value. They do not perform rollouts.
- MCTS uses UCT to decide which node should be expanded. AlphaZero and Lc0 use the output of the neural network as an additional parameter in their versions of UCT: the neural network generates a probability associated with every possible move in the position, which allows the neural network to control the expansion of the search tree to some degree.
Disclaimer, not an expert.
As I understand it, the process runs something like this:
- Given current position, ask the neural network for a prediction on 1) the move and 2) the win probability arising from that move.
- Make that move. This gets to a leaf node. Query neural network for new prediction on 1) the move and 2) the win probability arising from that move.
- And so on ...
- Because it's Monte Carlo Tree Search, at some points the program will back up and search the move with the next-highest win probability.
- When time is up, make the move that leads to the highest win probability.
See this link for an infographic.