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.

35 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
1k views

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

In the 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 ...
ihavenoidea's user avatar
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 ...
Ahmed 's user avatar
  • 71
6 votes
0 answers
200 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 ...
Alienator's user avatar
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
3 votes
0 answers
80 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 ...
Amar Srivastava's user avatar
3 votes
0 answers
206 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,...
Yohahn Ribeiro's user avatar
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 ...
joshrule's user avatar
3 votes
0 answers
162 views

Feature Selection using Monte Carlo Tree Search

I'm trying to tackle the problem of feature selection as an RL problem, inspired by the paper Feature Selection as a One-Player Game. I know Monte-Carlo tree search (MCTS) is hardly RL. So, I used ...
ATidedHumour's user avatar
3 votes
0 answers
136 views

Understanding an execution of the Monte Carlo tree search algorithm

I have the execution of the Monte Carlo Tree Search (MCTS) below. I need to expand it, but I don't understand steps 1 and 2. Why does it go to the first node and then make a new node, instead of ...
TomaateTip's user avatar
2 votes
0 answers
666 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
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 ...
NaN's user avatar
  • 21
2 votes
0 answers
196 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 ~...
Cyrus Dobbs's user avatar
2 votes
0 answers
386 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 ...
hoffee's user avatar
  • 131
2 votes
0 answers
238 views

What is the time complexity of an unparellelized Monte Carlo tree search?

I am writing a report where I used a slightly modified version of MCTS (not parallelized). I thought It could be interesting if I could calculate its time complexity. I'd appreciate any help I could ...
ATidedHumour's user avatar
2 votes
0 answers
25 views

How is GARB implemented in PGRD-DL to calculate gradients w.r.t. internal rewards?

In section 3 of this paper the author outlines how GARB was adapted to reduce the variance in updating parameters to an internal reward function estimator. I have read it a number of times and ...
Hanzy's user avatar
  • 519
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
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
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
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 ...
JollyOwl's user avatar
1 vote
0 answers
353 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
1 vote
0 answers
61 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
  • 147
1 vote
0 answers
473 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
1 vote
0 answers
268 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-...
markr3656's user avatar
1 vote
0 answers
306 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 ...
Fraser Gilbert's user avatar
1 vote
0 answers
77 views

Proof of Correctness of Monte Carlo Tree Search

I'm trying to write the proof of correctness of Monte Carlo Tree Search. Any help would be really appreciated.
ATidedHumour's user avatar
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 ...
DSPinfinity's user avatar
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/...
user131379's user avatar
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
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
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 ...
Kiran Manicka'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
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 ...
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
-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