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
1 answer
33 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
44 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
54 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
73 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
125 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
85 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
158 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
51 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
47 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
276 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
107 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
76 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
52 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
128 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
  • 390
1 vote
1 answer
288 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
206 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
124 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
  • 300
1 vote
3 answers
183 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
250 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
181 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
49 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
272 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
349 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
1k 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
306 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
315 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
2 votes
1 answer
264 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
  • 133
1 vote
0 answers
161 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
175 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
436 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
378 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
274 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
512 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
372 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
816 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
338 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
368 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
512 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
367 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
147 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
490 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
712 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
903 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
660 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
5 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
  • 137
1 vote
0 answers
60 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 ...
sb3's user avatar
  • 137
2 votes
1 answer
572 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 ...
Marlo's user avatar
  • 123
2 votes
0 answers
540 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 ${...
Gilad Felsen's user avatar
1 vote
0 answers
459 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 ...
maven's user avatar
  • 31
3 votes
1 answer
229 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 ...
user3667125's user avatar
  • 1,530