We changed our privacy policy. Read more.
21

tl;dr: None of these algorithms are practical for modern work, but they are good places to start pedagogically. You should always prefer to use Alpha-Beta pruning over bare minimax search. You should prefer to use some form of heuristic guided search if you can come up with a useful heuristic. Coming up with a useful heuristic usually requires a lot of ...


14

Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances. As an example, you could use it for weather forecasts. Predicting long-term weather is quite difficult, because it is a chaotic system where small changes can ...


8

So far, I have considered only three algorithms, namely, minimax, alpha-beta pruning, and Monte Carlo tree search (MCTS). Apparently, both the alpha-beta pruning and MCTS are extensions of the basic minimax algorithm. Given this context, I would recommend starting out with Minimax. Of the three algorithms, Minimax is the easiest to understand. Alpha-Beta, ...


7

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


7

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


7

They are all called Monte Carlo because all of them are a different version of the canonical Monte Carlo algorithm. The canonical version of Monte Carlo algorithm is a stochastic algorithm to determine an action based in a tree representation. The differences among all these version are their exploration and exploitation mechanisms, and it is necessary to ...


7

Note: you mentioned in the comments that you are reading the old, pre-print version of the paper describing AlphaZero on arXiv. My answer will be for the "official", peer-reviewed, more recent publication in Science (which nbro linked to in his comment). I'm not only focusing on the official version of the paper just because it is official, but also because ...


6

The most common strategy is to simply expand exactly one node per iteration; you can view this as expanding the first node of the Play-Out phase ("simulation" in your image), and not expanding any other nodes of the Play-Out phase. This is also what's done in your image. That is the most common and probably most simple strategy, but it's certainly not the ...


6

In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it is a win or loss, and backpropagate accordingly. The same as if you made a simulation step, but in this case the "simulation" is instant. But you can improve that: If the leaf is losing, you can give it a very large negative score or even $-\infty$, so in ...


6

If the state appears twice in the tree, aren't we wasting a lot of resources thinking about it multiple times? You're right. Precisely the same problem was also noticed decades before MCTS existed, in the classic minimax-style tree search algorithms (alpha-beta search, etc.) that were used in games before MCTS. The solution is also mostly the same; ...


6

$Q$-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for single-agent environments. The entire problem setting that these algorithms are developed for (Markov decision processes, or MDPs) is always framed in terms of a single agent situated in some environment, where ...


5

Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available. I don't have experience with the specific game you mentioned (Connect6), but from a quick look ...


4

The most "standard" implementation of MCTS probably involves storing copies of game states inside nodes. This works fine for deterministic games, but not for non-deterministic games due to the reasons you mentioned. In non-deterministic games, one of the easiest ways to make MCTS work is to take the perspective that every node in your tree should map to / ...


4

Assuming you mean a mathematically perfect player, similar to what we can achieve trivially in Tic Tac Toe, then the answer is "maybe". The underlying reinforcement learning algorithms that it uses do have some convergence guarantees, but there are some caveats: Theories of convergence that apply to value and policy functions learned by RL assume ...


4

From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL). Monte Carlo Tree Search is a planning algorithm. It can be considered part of RL, in a similar way to e.g. Dyna-Q. As a planning algorithm MCTS does need access to a model of the environment. Specifically it requires a sampling ...


4

Whether or not MCTS is even a Reinforcement Learning algorithm at all may be up for debate, but let's assume that we view it as an RL algorithm here. For practical purposes, MCTS really should be considered to be a Model-Based method. Below, I'm going to describe how you could view it as a Model-Free RL approach in some way... and then wrap back to why that ...


4

Yes, Monte Carlo tree search (MCTS) has been proven to converge to optimal solutions, under assumptions of infinite memory and computation time. That is, at least for the case of perfect-information, deterministic games / MDPs. Maybe some other problems were covered too by some proofs (I could intuitively imagine the proofs holding up for non-deterministic ...


4

A good choice might be smaller-scale games of Go, like a 9x9 board. This was the original application domain MCTS was designed for, and the original paper by Brugmann from 1993 details parameters that should lead to an agent that can play above beginner level in what is today a minuscule amount of computational time, in a scaled-down 9x9 grid. Go is a good ...


4

If you learn a policy or a value function from experience (that is, interaction with an environment), that's RL. In the case of AlphaGo, the MCTS is used to acquire the experience. RL could in fact be considered supervised learning (SL) or, more specifically, self-supervised learning, where the experience corresponds to the labels in SL, especially nowadays ...


4

You can try using an "Open-Loop" MCTS approach, instead of the standard "closed-loop" one, and eliminate chance nodes altogether. See, for example, Open Loop Search for General Video Game Playing. In a "standard" (closed-loop) implementation, you would store a game state in every normal (non-chance) node. Whenever there is a chance event, you would ...


4

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards: The leaf $s'$ position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, $(P(s′ , \cdot),V(s ′ )) = f_\theta(s′ )$. Each edge $...


3

We cannot tell with certainty whether AlphaGo Zero would become perfect with enough training time. This is because none of the parts (Neural Network) that would benefit from infinite training time (= a nice approximation of "enough" training time) are guaranteed to ever converge to a perfect solution. The main limiting factor is that we do not know whether ...


3

There has indeed been some research towards combining MCTS and minimax-like algorithms. For example, the following two publications: Monte-Carlo Tree Search and minimax hybrids Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions The basic intuition behind such combinations tends to be to use small minimax-like searches inside a ...


3

By far the most common (and likely also the most simple / straightforward) implementation is to expand exactly one node in the Expansion Phase; specifically, the node corresponding to the very first state selected (semi-)randomly by the Play-Out Phase. This is also pretty much the bare minimum you have to do if you want any form of tree growing at all (which ...


3

Your intuition is right. The tree is grown after each game. Before the first play through, the values of each decision point are initialized (randomly or to some constant). Then at the end of one play through, the weights of the decision points are updated using Monte Carlo methods. In this way, on the next play through, the updated weights help the agent ...


3

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" in the 2012 paper you linked. In algorithm 2 of the 2012 paper, they actually use the highest average reward, which corresponds to "Max child". It looks like ...


3

Deep Q Learning is a model-free algorithm. In the case of Go (and chess for that matter) the model of the game is very simple and deterministic. It's a perfect information game, so it's trivial to predict the next state given your current state and action (this is the model). They take advantage of this with MCTS to speed up training. I suppose Deep Q ...


3

Some basic advantages of MCTS over Minimax (and its many extensions, like Alpha-Beta pruning and all the other extensions over that) are: MCTS does not need a heuristic evaluation function for states. It can make meaningful evaluations just from random playouts that reach terminal game states where you can use the loss/draw/win outcome. So if you're faced ...


2

is there a value given for each piece (e.g. 1 for pawn, 3 for knight, 9 for queen, etc.) to train the algorithm, or does the algorithm learn this by himself? No, there are no such explicit values assigned to pieces, no manually-constructed evaluation functions. The paper states that "no domain knowledge" is given to the algorithm other than the game's rules ...


2

Whether the move is found and how quick it is found depends on a few things. If I understand correctly, there is a sequence of many "bad" moves which lead to the "big win" move, and you are afraid that the MCTS algorithm will not get to the "big win" move because it will be selecting more promising moves further up the tree. Some things to think about (read ...


Only top voted, non community-wiki answers of a minimum length are eligible