Where is the neural network used in MCTS?

Question

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.

Answer 1

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.

Lc0

Answer 2

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.

Answer 3

AlphaZero and Lc0 use a modified version of MCTS.

The neural networks in A0 and Lc0 are actually "two-headed" networks - one is a "value network," and the other is a "policy network." The value network is very simple: Given a position, it provides a probability that either side will win. Note that it is not based on color - in Lc0, 1 means that the side to move is 100% winning, and -1 means that the side that is not moving is 100% winning. The policy network, given a position, produces probabilities for each move being played.

Interestingly enough, the network gives probabilities for all theoretically legal moves, treating each piece as a "superpiece" that can move as both a queen and a knight. Illegal moves are filtered out, their probabilities set to 0 and the probabilities for the othre moves recalculated. In this way, the outputs can of fixed size.

At the beginning of MCTS, you select nodes based on the UCT value, which is a formula that balances "Explotation" (picking nodes you know are pretty good) versus "Exploration" (picking nodes that you haven't seen before.) These engines use a variant called "PUCT," or predictor UCT, which takes into account the policy network's suggestions. Then, rather than using rollouts, the network just uses the evaluation from the value network.

Dominik Klein wrote a really great book about neural networks in chess - I highly recommend you give it a read! The link is here: https://github.com/asdfjkl/neural_network_chess