Skip to main content

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
0 votes
1 answer
57 views

What are disadvantages/limitations of Monte Carlo Tree Search in RL?

What are disadvantages/limitations of Monte Carlo Tree Search in RL, and hence for what kind of applications might its use not be appropriate?
DSPinfinity's user avatar
0 votes
0 answers
24 views

Confusing convention in Sutto-Barto on Monte Carlo Tree Search: is a leaf node a state leaf node or state-action leaf node?

Figure 8.10: Monte Carlo Tree Search. When the environment changes to a new state, MCTS executes as many iterations as possible before an action needs to be selected, incrementally building a tree ...
DSPinfinity's user avatar
-2 votes
0 answers
23 views

Advantage of Monte Carlo Tree Search over Rollout

Why should the action chosen by Monte Carlo Tree Search tend to be better than the action the underlying rollout policy would choose?
DSPinfinity's user avatar
0 votes
0 answers
97 views

How is pass@k metric defined for automated theorem provers if we have a verifier?

The pass@k metric was proposed to measure the percentage of successful code samples (https://arxiv.org/abs/2107.03374), but it has also been used in automated theorem proving such as https://arxiv.org/...
user131379's user avatar
1 vote
1 answer
84 views

Gymnasium/Petting Zoo: Creating a copy of the board/env

I'm attempting to create a Tic Tac Toe player using MCTS. For the game environment, I'm using Tic Tac Toe from the Gymnasium/Petting Zoo environment. Running MCTS on Tic Tac Toe requires simulating ...
Ben G's user avatar
  • 123
1 vote
1 answer
82 views

In MCTS, does a simulation create new nodes

I am trying to implement a Monte-Carlo-Tree-Search algorithm. My question is, during the simulation/playout/rollout phase, are new nodes added as children to the node C from which the simulation ...
JohnT's user avatar
  • 11
0 votes
0 answers
45 views

What algorithm should I use to train an antichess agent?

I will implement an antichess agent and am not sure about which algorithm to use. My current candidates are minimax with alpha-beta pruning, MCTS and proximal policy optimization. Should I consider ...
heyula's user avatar
  • 1
1 vote
0 answers
55 views

RL agent focusses too much on early rewards, even with no discounting

How can I guide my RL agent to solve tasks in the correct order? I'm trying to train an agent using reinforcement learning, similar to MuZero. The goal is to solve 4 tasks, A/B/C/D. Each task involves ...
Christopher's user avatar
1 vote
1 answer
84 views

How to deal with infinite loops in the MCTS search of AlphaTensor when using a transposition table?

In the published version of the AlphaTensor algorithm, there are two mentions of a transposition table: In addition, a transposition table is used to recombine different action sequences if they ...
Tristan Nemoz's user avatar
1 vote
2 answers
226 views

How does Alpha Go Zero MCTS work in parallel?

I am trying to better understand the article "Mastering the Game of Go without Human Knowledge" (link) and I'm confused about the parallel implementation of Monte-Carlo-Tree-Search. On page ...
martinkunev's user avatar
2 votes
1 answer
111 views

Why does training a NN using MCTS work even if the number of simulations isn't much larger than the number of actions?

tl;dr If the visit rates of children generated by MCTS is biased because not enough samples were taken, why doesn't the network learn random behavior? My understanding of combining MCTS and NNs (e.g. ...
Christopher's user avatar
2 votes
2 answers
267 views

Monte Carlo Tree Search for trick taking games, such as Whist, Bridge

I'm just learning the concepts and was interested in MCTS techniques. I can see in a simple game like tic-tac-toe how you would replace negamax say with MCTS. It looks more complicated in card games. ...
Michael Lewis's user avatar
0 votes
0 answers
57 views

Justification for the MCTS backpropagation rule?

In Monte Carlo Tree Search, we back-propagate the results of a simulation with reward $R$ to a parent node N like this $$ V_N \leftarrow \frac{\text{visits}(N)\cdot V_N + R}{\text{visits}(N)+1} $$ and ...
Venna Banana's user avatar
0 votes
0 answers
71 views

How are Target Values Generated in Alpha Zero Architecture

I am a little confused as to how the target values are generated to train the neural network with the Alpha Zero architecture(in specific to a chess game). I understand how the improved policy is ...
Kiran Manicka's user avatar
1 vote
1 answer
513 views

Deep Q Networks v Monte Carlo Tree Search in Alpha Zero

Recently I've been studying how Deep Q Networks work, and as I was reading I just assumed that game engines like Alpha Zero use Deep Q Learning to choose actions. But as I was reading the Alpha Zero ...
Kiran Manicka's user avatar
2 votes
3 answers
109 views

MCTS: Units away from the action

I'm trying to implement Monte Carlo Tree Search for (a simplified version of) the boardgame Commands and Colors -- I'm setting up a scenario where the AI side has overwhelming force: 6 units vs 3 ...
xpmatteo's user avatar
0 votes
0 answers
95 views

Policy Value network predictions in Alpha Zero with ranked rewards

So I have been trying to implement the ranked rewards (R2) algorithm from the paper "Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization" http://arxiv.org/...
Darkdragon84's user avatar
1 vote
1 answer
56 views

Monte Carlo Tree Search for Robo Rally AI

I want to implement an AI capable of playing the game RoboRally (https://en.wikipedia.org/wiki/RoboRally) using Monte Carlo Tree Search (MCTS). In RoboRally, there are 2-8 characters controlled by (...
dport's user avatar
  • 11
3 votes
1 answer
192 views

How does Monte-Carlo Tree Search Compare to MCMC?

Monte-Carlo Tree Search was the method used for AlphaGo my understanding is: it would randomly search the state space of possible moves where the probability of choosing a move was proportional to the ...
profPlum's user avatar
  • 434
1 vote
1 answer
366 views

Reproducing AlphaZero/MuZero: Failed to beat initial model in arena

I am trying to reproduce AlphaZero's algorithm on the board game Carcassonne. Since I want to use the final game score differences (i.e. victory point of player 1 - victory point of player 2) as the ...
TommyX's user avatar
  • 13
1 vote
1 answer
262 views

Adding a Transposition Table to Monte Carlo Tree Search

I think I'm having a bit of trouble wrapping my head around how a transposition table functions: As I understand it you can store a value (simulation result?) for a given game state in this (hash) ...
NG.'s user avatar
  • 139
1 vote
0 answers
173 views

What method to use for Monte-Carlo Tree Search to prefer depth search

The basic Monte-Carlo Tree Search algorithm uses the tree policy: while v is nonterminal: if v is not fully expanded: expand v else: v = v.best_child ...
allo's user avatar
  • 310
1 vote
3 answers
220 views

MCTS players keep replaying identical games

I am currently training a self-playing Monte-Carlo-Tree-Search (MCTS) algorithm with a neural network prior, and it seems to be working pretty well. However one problem I have is when I compare my new ...
Tue's user avatar
  • 111
0 votes
1 answer
335 views

MCTS: How to select children when none of them are visited?

I am trying to implement MCTS for a custom word game I am working on. I feel like I have got all the pieces of code needed, but the algorithm seems to always return the first available move (first ...
nikord's user avatar
  • 1
2 votes
1 answer
206 views

Why does AlphaZero not use vanilla MCTS?

I understand main difference between AlphaZero and the classic Monte Carlo tree search is the playout (simulation) step is replaced with a neural network prediction which itself is trained from the ...
user2309803's user avatar
0 votes
0 answers
50 views

What is the theory behind rejecting too good heuristics in search problems?

Currently I have found that there is an article in which a search problem is posed and to solve it a heuristic is proposed which, in essence, is the solution of the problem itself. I seem to remember ...
Angelo's user avatar
  • 211
0 votes
0 answers
308 views

MCTS for trick-taking game?

I'm trying to implement a MCTS-based AI for a trick-taking card game. The game : (Belote) The play consists of 8 tricks. A trick consists in each of the 4 players play successively 1 (legal) card ...
Betcha's user avatar
  • 1
1 vote
1 answer
440 views

MCTS with multi actions

I know that MCTS usually is meant for games where each player plays turn by turn and the canonical form of the board is passed through the tree but is it possible for one player to make multiple moves ...
Anik Patel's user avatar
2 votes
1 answer
2k views

The reason behind using MCTS over Alpha Beta Pruning in Alphazero

I am not really satisfied with the available analysis of why AlphaZero uses MCTS instead of Alpha Beta search. Some analysis claim that its because MCTS is a lot more humanlike. I disagree because I ...
Dimanjan's user avatar
  • 123
4 votes
1 answer
361 views

Does the AlphaZero algorithm keep the subtree statistics after each move during MCTS?

This question is regarding the Monte Carlo Tree Search (MCTS) algorithm presented in the AlphaZero paper (arXiv). As described in the paper, each MCTS used 800 simulations to determine the next action....
julian's user avatar
  • 43
2 votes
1 answer
327 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' ...
Matrix001's user avatar
  • 123
3 votes
1 answer
290 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 ...
zjeffer's user avatar
  • 143
1 vote
0 answers
189 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 ...
crass_sandwich's user avatar
2 votes
1 answer
178 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 ...
Hans-Peter Stricker's user avatar
1 vote
0 answers
482 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 ...
JollyOwl's user avatar
1 vote
1 answer
415 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. ...
Druudik's user avatar
  • 149
2 votes
1 answer
320 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 ...
pepijno's user avatar
  • 121
1 vote
2 answers
639 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 ...
Druudik's user avatar
  • 149
1 vote
1 answer
425 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,...
Arlo Rostirolla's user avatar
1 vote
2 answers
992 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 ...
Michael's user avatar
  • 159
1 vote
0 answers
352 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 ...
Ifeanyi Obinelo's user avatar
1 vote
0 answers
392 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 ...
Dibbla's user avatar
  • 11
5 votes
1 answer
577 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 ...
Sami's user avatar
  • 53
3 votes
1 answer
437 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: ...
Hossam's user avatar
  • 33
2 votes
1 answer
220 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 ...
Kricket's user avatar
  • 197
3 votes
1 answer
537 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}},...
user8714896's user avatar
2 votes
1 answer
753 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 ...
user8714896's user avatar
5 votes
1 answer
1k 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: ...
semyd's user avatar
  • 153
0 votes
1 answer
732 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 ...
javaPhobic's user avatar
6 votes
2 answers
2k 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 ...
sb3's user avatar
  • 147