14

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


12

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


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


6

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


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


5

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


5

N.B The reason why I only chose these three algorithms was due to time I have available in understanding them. From a little research, I found that these algorithms are basically interweaved into the minimax algorithm. So if I can understand one then the other two will just fall into place. Given this context, I would recommend starting out with Minimax. Of ...


5

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


4

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


4

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


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

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


3

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


3

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


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

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


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

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


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


2

You either need a generative model or an emulator of the environment. In the later case you don't calculate your transitions and rewards using the model but feed your actions and states to the emulator and work with the results. The emulator can be a black box as long as it returns the next state and the reward when provided with the current state and an ...


2

First, we need to distinguish plain Monte-Carlo from Monte-Carlo Tree Search. They're different things. Monte-Carlo search, in the context of game AI search algorithms, is typically understood to mean that we search randomly many times, and average the results, and nothing else. If this is all we're doing, then yes, your understanding is correct. This is ...


2

The following are extremely simple ways of tackling this problem. A very simple way It can simply be strength of AI=(# of games won)/(total # of games). In case data for each move is available Something like score per game=# of correct decisions/total number of decisions. Then strength of AI=sum(score per game)/total # of games. If each move/decision ...


2

It can make sense to incorporate the standard deviation of Monte-Carlo-based evaluations in some ways to reduce risk, but I don't think the way of using it that you described would work well. For MCTS evaluations, if you're taking a zero-sum-style approach (which you are if you are trying to estimate win/loss probabilities), it is very important that your ...


2

Traditionally (when not considering your idea), the evaluation function for terminal game states would be implemented to return $1$, $0$, or $-1$ for wins, draws, or losses, respectively. Changing that in a naive/straightforward way to make short-term wins more rewarding, long-term wins less rewarding, short-term losses more negative, and long-term losses ...


2

A classifier seems to me to not really fit the problem. I am not really sure. Actually, I don't see how a classifier like a decision tree, for example, would work here. Because I have to predict decision of the counselor to propose or not based on the decision of banks (and I don't know their criteria) to refuse or accept applicants who were proposed loan ...


2

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


2

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


2

You're right that AlphaGo Zero doesn't perform rollouts in its MCTS. It does complete many, many games, though. Realize that AlphaGo Zero only iterates MCTS 1,600 times before taking an action. The next state resulting from that action becomes the root of future search trees. Since a typical game of Go only lasts a few hundred moves, the board will very ...


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