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.
122
questions
1
vote
2
answers
20
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 ...
- 245
1
vote
1
answer
42
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. ...
- 113
0
votes
0
answers
32
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. ...
0
votes
0
answers
29
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 ...
- 376
0
votes
0
answers
32
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 ...
1
vote
1
answer
74
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 ...
2
votes
2
answers
92
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 ...
- 21
0
votes
0
answers
58
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/...
- 101
1
vote
1
answer
40
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 (...
- 11
3
votes
1
answer
70
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 ...
- 360
1
vote
1
answer
198
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 ...
- 13
0
votes
1
answer
129
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) ...
- 119
0
votes
0
answers
62
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
...
- 270
0
votes
3
answers
113
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 ...
- 101
0
votes
1
answer
158
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 ...
- 1
2
votes
1
answer
119
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 ...
- 121
0
votes
0
answers
45
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 ...
- 201
0
votes
0
answers
217
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 ...
- 1
1
vote
1
answer
236
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 ...
- 125
0
votes
0
answers
79
views
How to formulate Monte Carlo Tree Search in a stochastic environment with a changing action space
Can we efficiently solve a problem in which:
the valid actions at any given time are changing
the environment is stochastic
we have an infinite time horizon
using MCTS?
To be more specific, I'm ...
- 101
1
vote
1
answer
916
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 ...
- 113
4
votes
1
answer
252
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....
- 43
2
votes
1
answer
296
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' ...
- 23
2
votes
1
answer
209
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 ...
- 133
1
vote
0
answers
128
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 ...
- 111
2
votes
1
answer
161
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 ...
1
vote
0
answers
336
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 ...
- 11
1
vote
1
answer
327
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.
...
- 159
2
votes
1
answer
199
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 ...
- 121
1
vote
2
answers
392
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 ...
- 159
1
vote
1
answer
304
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
2
answers
573
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 ...
- 159
1
vote
0
answers
299
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
0
answers
326
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 ...
- 11
5
votes
1
answer
399
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 ...
- 53
3
votes
1
answer
285
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:
...
- 33
2
votes
1
answer
127
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 ...
- 197
3
votes
1
answer
413
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}},...
- 717
1
vote
1
answer
615
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 ...
- 717
5
votes
1
answer
757
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:
...
- 153
0
votes
1
answer
541
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 ...
- 103
5
votes
2
answers
1k
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 ...
- 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 ...
- 137
2
votes
1
answer
494
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 ...
- 123
2
votes
0
answers
361
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
${...
- 21
1
vote
0
answers
422
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 ...
- 31
3
votes
1
answer
206
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 ...
- 1,510
2
votes
1
answer
117
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$ ...
- 128
2
votes
1
answer
120
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 ...
- 123
2
votes
1
answer
389
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 ...
- 153