7
$\begingroup$

To the best of my understanding, Monte Carlo Search is an alternative method to Minimax for searching a tree of nodes. It works by choosing a move (generally the one with the highest chance of being the best), and then performing a random playout on the move to see what the result is. This process keeps continuing for however much time is allotted.

This doesn't sound like Machine Learning, but rather a way to traverse a tree. However, I've heard that AlphaZero uses Monte Carlo search, so I'm confused. Is using Monte Carlo search why AlphaZero learns? Or did AlphaZero do some kind of machine learning before it played any matches, and then use the intuition it gained from Machine learning to know which moves to spend more time playing out with Monte Carlo search?

$\endgroup$
6
$\begingroup$

Monte Carlo Tree Search is not usually thought of as a machine learning technique, but as a search technique. There are parallels (MCTS does try to learn general patterns from data, in a sense, but the patterns are not very general), but really MCTS is not a suitable algorithm for most learning problems.

AlphaZero was a combination of several algorithms. One was MCTS, but MCTS needs a function to tell it how good different states of the game might be (or else, it needs to simulate entire games). One way to handle this function in a game like chess or Go is to approximate it by training a neural network, which is what the Deep Mind researchers did. This is the learning component of AlphaZero.

$\endgroup$
4
$\begingroup$

John's answer is correct in that MCTS is traditionally not viewed as a Machine Learning approach, but as a tree search algorithm, and that AlphaZero combines this with Machine Learning techniques (Deep Neural Networks and Reinforcement Learning).

However, there are some interesting similarities between MCTS itself and Machine Learning. In some sense, MCTS attempts to "learn" the value of nodes from experience generated through those nodes. This is very similar to how Reinforcement Learning (RL) works (which itself is typically described as a subset of Machine Learning).

Some researchers have also experimented with replacements for the traditional Backpropagation phase of MCTS (which, from an RL point-of-view, can be described as implementing a Monte-Carlo backups) based on other RL methods (e.g., Temporal-Difference backups). A comprehensive paper describing these sorts of similarities between MCTS and RL is: On Monte Carlo Tree Search and Reinforcement Learning.

Also note that the Selection phase of MCTS is typically treated as a sequence of small Multi-Armed Bandit problems, and those problems also have strong connections with RL.


TL;DR: MCTS is not normally viewed as a Machine Learning technique, but if you inspect it closely, you can find lots of similarities with ML (in particular, Reinforcement Learning).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.