# Tag Info

18

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

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

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

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

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

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

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

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

5

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

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

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

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

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

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

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

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

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

3

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

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

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

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

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

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

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