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
0answers
30 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 ...
1
vote
1answer
127 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. ...
2
votes
1answer
33 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 ...
1
vote
2answers
110 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 ...
1
vote
1answer
43 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,...
1
vote
2answers
87 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 ...
1
vote
0answers
49 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 ...
1
vote
0answers
62 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 ...
5
votes
1answer
91 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 ...
3
votes
1answer
78 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: ...
2
votes
1answer
48 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 ...
0
votes
0answers
40 views

In MCTS, if we encounter an already visited node stored in the transposition table, should we backpropagate?

During the playout phase, we might encounter an already visited node stored in the transposition table. We could either utilize this information or ignore it (simply continue the simulation as usual). ...
0
votes
0answers
40 views

Where to store and how to sort the AMAF values (RAVE) for Monte Carlo Tree Search?

I am building an agent for a board game and would like to use Rapid Action Value Estimation (RAVE), which is an alternative selection approach to UCT. There are different variations of the UCT like ...
0
votes
0answers
47 views

Which method is the most efficient for memory-bounded MCTS with a transposition table?

I am building an agent for a board game that can have a relatively lot of time to think. Therefore, memory management should be efficient. I am using a transposition table, where the nodes are stored ...
2
votes
1answer
80 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}},...
0
votes
1answer
147 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 ...
3
votes
1answer
101 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: ...
0
votes
0answers
77 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 ...
3
votes
1answer
196 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 ...
1
vote
0answers
43 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 ...
1
vote
1answer
139 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 ...
1
vote
0answers
80 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 ${...
1
vote
0answers
203 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 ...
3
votes
1answer
92 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 ...
2
votes
1answer
50 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$ ...
2
votes
1answer
92 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 ...
2
votes
1answer
97 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 ...
1
vote
0answers
80 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-...
1
vote
1answer
178 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 ...
1
vote
0answers
133 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 ...
0
votes
1answer
110 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 ...
1
vote
1answer
112 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 ...
3
votes
1answer
685 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 ...
1
vote
1answer
89 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)\}$ ...
3
votes
0answers
55 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 ...
2
votes
1answer
74 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 ...
2
votes
1answer
209 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 ...
7
votes
1answer
2k 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 ...
5
votes
2answers
366 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 ...
3
votes
0answers
87 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,...
2
votes
0answers
186 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 ...
2
votes
0answers
83 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 ~...
1
vote
1answer
98 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 ...
2
votes
1answer
249 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 ...
2
votes
1answer
146 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 ...
3
votes
0answers
58 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 ...
6
votes
1answer
841 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 ...
5
votes
1answer
138 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 ...
1
vote
0answers
93 views

Formulating MCTS with random outcomes of actions?

I am working on implementing MCTS for a scheduling problem where MCTS is formulated each time there are multiple jobs that need to be scheduled. When a job is executed, the resulting state of the ...
1
vote
2answers
575 views

How to understand the 4 steps of Monte Carlo Tree Search

From many blogs and this one https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html We know that the process of MCTS algorithm has 4 steps. Selection: Starting at root node R,...