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
2 votes
1 answer
622 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 ...
0 votes
1 answer
63 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?
0 votes
0 answers
26 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 ...
-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?
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 ...
3 votes
1 answer
245 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 ...
0 votes
0 answers
99 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/...
1 vote
1 answer
86 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 ...
1 vote
1 answer
84 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 ...
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 ...
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. ...
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 ...
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 ...
2 votes
3 answers
110 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 ...
1 vote
2 answers
227 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 ...
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. ...
7 votes
1 answer
213 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
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 (...
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 ...
14 votes
3 answers
4k 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 ...
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 ...
0 votes
0 answers
74 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
516 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 ...
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/...
3 votes
1 answer
193 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 ...
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 ...
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 ...
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) ...
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 ...
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 ...
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 ...
0 votes
0 answers
51 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 ...
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 ...
1 vote
1 answer
441 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 ...
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 ...
4 votes
1 answer
363 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....
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' ...
2 votes
1 answer
428 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 ...
3 votes
1 answer
719 views

Which Reinforcement Learning algorithms are efficient for episodic problems?

I have some episodic datasets extracted from a turn-based RTS game in which the current actions leading to the next state doesn’t determine the final solution/outcome of the episode. The learning is ...
1 vote
2 answers
569 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 ...
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 ...
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 ...
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,...
0 votes
1 answer
733 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
1 answer
2k views

How fast does Monte Carlo tree search converge?

How fast does Monte Carlo Tree Search converge? Is there a proof that it converges? How does it compare to temporal-difference learning in terms of convergence speed (assuming the evaluation step is a ...
5 votes
1 answer
1k views

Is the new AlphaGo implementation using Generative Adversarial Networks?

I read through the publication Mastering the game of Go without Human Knowledge. It doesn't seem to use GANs, just a new form of search and reinforcement learning.
1 vote
0 answers
484 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 ...
2 votes
1 answer
203 views

Is there a better way of calculating the chance of winning than $\mu * (1 - (\sigma * f)) * 100$ for the card game schnapsen?

My AI (for the card game schnapsen) currently calculates every possible way the game could end and then evaluates the percentage of winning for every playable card / move. The calculation is done ...
5 votes
1 answer
1k views

Which algorithms can we use on games with high branching factors (e.g. Connect6)?

Connect6 is an example of a game with a very high branching factor. It is about 45 thousand, dwarfing even the impressive Go. Which algorithms can we use on games with such high branching factors? I ...
5 votes
1 answer
122 views

Why didn't champion of the Go game manage to win the last game against AlphaGo, after winning the 4th one?

In the documentary about the match, it is said that after losing the 4th game, AlphaGo came back stronger and started to play in a weird way (not human-like) and it was pretty impossible to be beaten. ...