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
29 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
33 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
75 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
56 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
38 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
27 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
27 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
34 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
58 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
59 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
47 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
56 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 ...
0
votes
0answers
38 views

MCTS: What if all children of a node are terminal?

If all children Nodes of the selected node are terminal in the selection phase - you obviously run into a problem. So how do I prevent a Node to be selected that only has terminal children?
3
votes
1answer
92 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
37 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
72 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
51 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
143 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
81 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
43 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$ ...
1
vote
1answer
69 views

AI to play a solo card game

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
75 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
56 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-...
0
votes
0answers
35 views

How good should I be expecting my Monte Carlo Tree Search to be?

I've been learning how the Monte Carlo Tree Search works and implemented it to play a game of Connect 4. I think I've got the algorithm correct as it plays the game quite well (it can usually beat me ...
1
vote
1answer
132 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
121 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
91 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
90 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 ...
0
votes
0answers
25 views

How does the second phase of the evaluation function described in this article work?

I am trying to create an evaluation function for a general game player based on the research from this article An Automatically-Generated Evaluation Function in General Game Playing. I can't ...
0
votes
0answers
91 views

Monte Carlo Tree search UCB1 for Tic-Tac-Toe help

I am trying to code a MCTS agent for tic tac toe and i have some theoretical questions regarding MCTS. 1)I am using the UCB1 MCTS $UCB(Si)=average value + 2*sqrt(ln(N)/ni)$ . Considering the image ...
3
votes
1answer
463 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
83 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
44 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
71 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
111 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 ...
6
votes
1answer
1k 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
257 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
68 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
133 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
63 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
88 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
182 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
126 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
54 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
656 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 ...
4
votes
1answer
92 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
59 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
420 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,...
4
votes
0answers
240 views

How is the rollout from the MCTS implemented in both of the AlphaGo Zero and the AlphaZero algorithms?

In a vanilla Monte Carlo tree search (MCTS) implementation, the rollout is usually implemented following a uniform random policy, that is, it takes random actions until the game is finished and only ...
9
votes
2answers
1k views

MCTS for non-deterministic games with very high branching factor for chance nodes

I'm trying to use a Monte Carlo Tree Search for a non-deterministic game. Apparently, one of the standard approaches is to model non-determinism using chance nodes. The problem for this game is that ...