Questions tagged [monte-carlo-tree-search]

For questions related to Monte Carlo Tree Search (MCTS), which is a best-first, rollout-based tree search algorithm. MCTS gradually improves its evaluations of nodes in the trees using (semi-)random rollouts through those nodes, focusing a larger proportion of rollouts on the parts of the tree that are the most promising.

Filter by
Sorted by
Tagged with
1 vote
0 answers
162 views

In the MuZero paper, how does backprop in the MCTS account for the immediate reward from each edge?

On page 12 of this paper: Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model, it describes how MCTS works for the MuZero algorithm. It states in equation 4 that during the 'backup' ...
user avatar
1 vote
1 answer
53 views

How can AlphaZero be used in other industries besides gaming?

I'm an AI Engineering student from Belgium and I'm writing my bachelor thesis on the creation of a chess computer with deep reinforcement learning based on AlphaZero. My implementation can be found ...
user avatar
  • 123
1 vote
0 answers
25 views

Is there a benefit to starting with MCTS and switching to minimax as the branching factor decreases?

I've invented a deterministic, perfect-information game with a fairly large branching factor (~150) which tapers out dramatically after the midgame (~30 at worst). I need a strong AI. My understanding ...
user avatar
0 votes
0 answers
44 views

How is a leaf node determined in the "selection" phase of Monte Carlo Tree Search?

How is a leaf node determined in Monte Carlo Tree Search during the "selection" phase? I need a simple example to see Monte Carloo Tree Search in action.
user avatar
2 votes
1 answer
83 views

Can AlphaZero develop significantly different playing styles (depending on the random games from which it learrns)?

There is a quite popular video analysing a chess game AlphaZero vs. AlphaZero, called "the perfect game". It leaves some questions open and I'd like to ask them here: Did the two copies of ...
user avatar
1 vote
0 answers
107 views

What method is better to use for a two-player reinforcement learning environment?

I want to create an RL agent for a mancala-type two-player game as my first actual project in the field. I've already completed the game itself and coded a minimax algorithm. The question is: how ...
user avatar
1 vote
1 answer
171 views

What is a policy training target in AlphaZero?

In AlphaZero's attached pseudocode, they create a training target for the policy network in this way. ...
user avatar
  • 159
2 votes
1 answer
80 views

Which value to propagate in Monte Carlo Tree Search in a non-zero-sum game?

Usually, when I read about Monte Carlo Tree Search, values between 0 and 1 (or values between -1 and 1) are backpropagated, depending on whether the simulation was a win or loss. Now, suppose you have ...
user avatar
  • 121
1 vote
2 answers
149 views

Would AlphaZero work just with a value network?

There is a nice post about the intuition why AlphaZero works. One of the advantages of using a policy network in the games where a perfect simulator is available (such as chess) is to save computation ...
user avatar
  • 159
1 vote
1 answer
101 views

Do you need a terminal state when using double deep q networks?

I just got my agent training, and I'm wondering if the terminal flags are necessary when sampling from the replay buffer. The game I'm implementing the agent in has two different ways the game can end,...
user avatar
1 vote
2 answers
156 views

How does one handle different player turns in MCTS?

Suppose we have a two player game like Tic Tac Toe where the two players take turns to play their moves. It is my understanding that in the game tree that MCTS builds, consecutive levels in the tree ...
user avatar
  • 59
1 vote
0 answers
127 views

Why doesn't this Monte Carlo Tree Search algorithm work properly?

PROBLEM I'm writing a Monte-Carlo tree search algorithm to play chess in Python. I replaced the simulation stage with a custom evaluation function. My code looks perfect but for some reason acts ...
user avatar
1 vote
0 answers
111 views

Too slow search using MCTS in OpenAI Atari games

I'm recently using Monte Carlo Tree Search in OpenAi Gym Atari, but the result isn't satisfying. Without render, the game lasts about 180 steps ( env.step() was called this much time ) with random ...
user avatar
5 votes
1 answer
137 views

In MCTS, what to do if I do not want to simulate till the end of the game?

I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS ...
user avatar
  • 53
3 votes
1 answer
105 views

What is the advantage of using MCTS with value based methods over value based methods only?

I have been trying to understand why MCTS is very important to the performance of RL agents, and the best description I found was from the paper Bootstrapping from Game Tree Search stating: ...
user avatar
  • 33
2 votes
1 answer
60 views

What is this algorithm? Is it a variant of Monte-Carlo Tree Search?

I'm using a Neural Network as an agent in a simple car racing game. My goal is to train the network to imitate a brute-force tree search to an arbitrary depth. My algorithm goes something like the ...
user avatar
  • 197
3 votes
1 answer
151 views

How UCT in MCTS selection phase avoids starvation?

The first step of MCTS is to keep choosing nodes based on Upper Confidence Bound applied to trees (UCT) until it reaches a leaf node where UCT is defined as $$\frac{w_i}{n_i}+c\sqrt{\frac{ln(t)}{n_i}},...
user avatar
1 vote
1 answer
253 views

Does Monte Carlo Tree Search not work on games without the same initial state?

I'm curious how you would apply Monte Carlo Tree Search to a game that has a random initial state. You generate a tree where the root node is the initial state, then you expand if the options from ...
user avatar
5 votes
1 answer
249 views

What should the initial UCT value be with MCTS, when leaf's simulation count is zero? Infinity?

I am implenting a Monte Carlo Tree Search algorithm, where the selection process is done through Upper Confidence Bound formula: ...
user avatar
  • 153
0 votes
1 answer
187 views

Alpha Zero does not converge for Connect 6, a game with huge branching factor - why?

I have a problem with applying alpha zero self-play to a game (Connect 6) with a huge branching factor (30,000 on average). I have implemented the MCTS as described but I found that during the MCTS ...
user avatar
3 votes
1 answer
389 views

How does AlphaZero's MCTS work when starting from the root node?

From the AlphaGo Zero paper, during MCTS, statistics for each new node are initialized as such: ${N(s_L, a) = 0, W (s_L, a) = 0, Q(s_L, a) = 0, P (s_L, a) = p_a}$. The PUCT algorithm for selecting ...
user avatar
  • 107
1 vote
0 answers
47 views

Are inputs into AlphaZero the same during the evaluate step in MCTS and during test time?

From the AlphaZero paper: The input to the neural network is an N × N × (M T + L) image stack that represents state using a concatenation of T sets of M planes of size N × N . Each set of planes ...
user avatar
  • 107
2 votes
1 answer
226 views

Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search

I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most ...
user avatar
  • 123
2 votes
0 answers
129 views

Why is the ideal exploration parameter in the UCT algorithm $\sqrt{2}$?

From Wikipedia, in the Monte-Carlo Tree Search algorithm, you should choose the node that maximizes the value: $${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}},$$ where ${...
user avatar
1 vote
0 answers
265 views

What would be the AlphaGo's performance in continuous action space?

During my research for Google DeepMind's Go-playing program Alpha Go and its successor Alpha Go Zero, I discovered that the system uses a clever pipeline and an interplay of blocks of both policy and ...
user avatar
  • 21
3 votes
1 answer
115 views

AlphaGo Zero: does $Q(s_t, a)$ dominate $U(s_t, a)$ in difficult game states?

AlphaGo Zero AlphaGo Zero uses a Monte-Carlo Tree Search where the selection phase is governed by $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, where: the exploitation ...
user avatar
  • 1,230
2 votes
1 answer
61 views

How to choose the first action in a Monte Carlo Tree Search?

I'm working on reimplementing the MuZero paper. In the description of the MCTS (page 12), they indicate that a new node with associated state $s$ is to be initialized with $Q(s,a) = 0$, $N(s,a) = 0$ ...
user avatar
  • 150
2 votes
1 answer
100 views

How can I improve the performance of my approach to solving a 1-player version of the card game "The Game" by Steffen Benndorf?

I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf). The ...
user avatar
  • 23
2 votes
1 answer
156 views

Why is tree search/planning used in reinforcement learning?

In AlphaGo Zero, MCTS is used along with policy networks. Some sources say MCTS (or planning in general) increases the sample efficiency. Assumed the transition model is known and the computational ...
user avatar
  • 163
1 vote
0 answers
102 views

Is Monte Carlo tree search guaranteed to converge to the optimal solution in two player zero-sum stochastic games?

I'm aware that convergence proofs for Monte Carlo tree search exist in the case of deterministic zero sum games and Markov decision processes. I have come across research which applies MCTS to zero-...
user avatar
1 vote
1 answer
210 views

How does the MCTS tree look like?

I have come across the Monte Carlo tree search (MCTS) algorithm, but I can't find what the tree should look like. For example, does it still represent a minimax process, i.e. player 1 from the root ...
user avatar
1 vote
0 answers
143 views

To solve chess with deep RL and MCTS, how should I represent the input (the state) to a neural network?

I'm wanting to build a NN that can create a policy for each possible state. I want to combine this with MCTS to eliminate randomness so when expansion occurs, I can get the probability of the move to ...
user avatar
0 votes
1 answer
130 views

What is the search depth of AlphaGo and AlphaGo Zero?

I cannot find reliable sources but someone says it is 40 moves and someone else says it is 50+ moves. I read their papers and they use value function (NN) and policy function to trim the tree, so more ...
user avatar
  • 141
1 vote
2 answers
189 views

In Alpha(Go)Zero, why is the policy extracted from MCTS better than the network one?

I've read through the Alpha(Go)Zero paper and there is only one thing I don't understand. The paper on page 1 states: The MCTS search outputs probabilities π of playing each move. These search ...
user avatar
  • 43
3 votes
1 answer
917 views

How to run a Monte Carlo Tree Search MCTS for stochastic environment?

For MCTS there is an expansion phase where we make a move and list down all the next states. But this is complicated by the fact that for some games, after making the move, there is a stochastic ...
user avatar
  • 131
1 vote
1 answer
90 views

How AlphaGo Zero is learning from $\pi_t$ when $z_t = -1$?

I have questions on the way AlphaGo Zero is trained. From original AlphaGo Zero paper, I knew that AlphaGo Zero agent learns a policy, value functions by the gathered data $\{(s_t, \pi_t, z_t)\}$ ...
user avatar
3 votes
0 answers
60 views

Where does reinforcement learning actually show up in Deepmind's game engines?

From the brief research I've done on the topic, it appears that the way Deepmind's Alphazero or Muzero makes decisions is through Monte Carlo tree searches, where in the randomized simulations allows ...
user avatar
2 votes
1 answer
90 views

Why aren’t heuristics for Connect Four Monte Carlo tree search improving the agent?

I’ve created an agent using MCTS to play Connect Four. It wins against humans pretty well, but I’d like to improve upon it. I decided to add domain knowledge to the MCTS rollout stage. My evaluation ...
user avatar
  • 573
2 votes
1 answer
277 views

Should Monte Carlo tree search be able to consistently beat me in the connect four game?

I've implemented the Monte Carlo tree search (MCTS) algorithm for a connect four game I've built. The MCTS agent beats a random choice agent 90-100% of the time, but I’m still able to beat it pretty ...
user avatar
  • 573
8 votes
1 answer
3k views

When should Monte Carlo Tree search be chosen over MiniMax?

I would like to ask whether MCTS is usually chosen when the branching factor for the states that we have available is large and not suitable for Minimax. Also, other than MCTS simluates actions, where ...
user avatar
  • 81
5 votes
2 answers
496 views

Why AlphaGo didn't use Deep Q-Learning?

In the previous research, in 2015, Deep Q-Learning shows its great performance on single player Atari Games. But why do AlphaGo's researchers use CNN + MCTS instead of Deep Q-Learning? is that because ...
user avatar
  • 2,551
3 votes
0 answers
109 views

Is Monte Carlo tree search needed in partially observable environments during gameplay?

I understand that with a fully observable environment (chess / go etc) you can run an MCTS with an optimal policy network for future planning purposes. This will allow you to pick actions for gameplay,...
user avatar
2 votes
0 answers
249 views

MCTS RAVE performing badly in Board Game AI

I'm using Monte Carlo Tree Search with UCT selection to try and build an AI player for a complex multiplayer board game. My regular UCT MCTS seems to be working fine, winning with random and basic ...
user avatar
  • 21
2 votes
0 answers
103 views

Is this a good approach to evaluate the game state with a neural network?

I've written a Monte Carlo Tree Search player for the game of Castle (AKA Shithead, Shed, Palace...). I have set this MCTS player to play against a basic rule-based AI for ~30000 games and collected ~...
user avatar
1 vote
1 answer
115 views

MCTS moves with multiple parents

I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples. My initial plan is for nodes to represent programs and for the search ...
user avatar
2 votes
1 answer
314 views

How to apply hyperparameter optimization on Monte Carlo Tree Search?

I have a basic MCTS agent for the game of Hex (a turn based game). I want to tune the parameters of UCT (the Cp parameter) and the number of rollouts parameter. Where do I have to begin? The problem ...
user avatar
3 votes
1 answer
166 views

How can I reduce combinatorial explosion in an MCTS-like algorithm for program induction?

I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples. My initial plan is for nodes to represent programs and for the search ...
user avatar
4 votes
0 answers
76 views

How exactly does self-play work, and how does it relate to MCTS?

I am working towards using RL to create an AI for a two-player, hidden-information, a turn-based board game. I have just finished David Silver's RL course and Denny Britz's coding exercises, and so am ...
user avatar
7 votes
1 answer
1k views

MCTS: How to choose the final action from the root

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root? The original UCT paper (2006) says bestAction in their ...
user avatar
  • 337
6 votes
1 answer
159 views

How could an AI detect whether an enemy in a game can be blocked off/trapped?

Imagine a game played on a 10x10 grid system where a player can move up down left or right and imagine there are two players on this grid: An enemy and you. In this game, there are walls on the grid ...
user avatar
  • 61