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.

31 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
2answers
299 views

In this implementation of the Information Set Monte Carlo Tree Search, why can't the players see the cards of each other?

After reading this paper about Monte Carlo methods for imperfect information games with elements of uncertainty, I couldn't understand the application of the determinization step in the author's ...
4
votes
1answer
77 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 ...
3
votes
0answers
41 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 ...
3
votes
0answers
45 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,...
3
votes
0answers
49 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 ...
3
votes
0answers
148 views

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

In a 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 ...
3
votes
0answers
76 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 ...
3
votes
0answers
89 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 ...
2
votes
0answers
23 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 ...
2
votes
0answers
83 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 ...
2
votes
1answer
100 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 ...
2
votes
0answers
165 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 ...
2
votes
0answers
15 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 ...
2
votes
2answers
628 views

Is Monte Carlo Tree Search appropriate for problems with large state and action spaces?

I'm doing a research on a finite-horizon Markov decision process with $t=1, \dots, 40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in ...
1
vote
0answers
28 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 ${...
1
vote
0answers
30 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-...
1
vote
1answer
65 views

Chess Neural Network - Most Optimal Input vector/matrix?

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 ...
1
vote
1answer
58 views

MCTS moves with multiple parents

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 ...
1
vote
0answers
40 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 ...
1
vote
0answers
51 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.
0
votes
0answers
19 views

MCTS: What if all children of a node are terminal?

If all children Nodes of the selected node are terminal in the selection phase - you obviously run into a problem. So how do I prevent a Node to be selected that only has terminal children?
0
votes
0answers
66 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 ...
0
votes
0answers
28 views

How good should I be expecting my Monte Carlo Tree Search to be?

I've been learning how the Monte Carlo Tree Search works and implemented it to play a game of Connect 4. I think I've got the algorithm correct as it plays the game quite well (it can usually beat me ...
0
votes
1answer
103 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 ...
0
votes
0answers
23 views

How does the second phase of the evaluation function described in this article work?

I am trying to create an evaluation function for a general game player based on the research from this article An Automatically-Generated Evaluation Function in General Game Playing. I can't ...
0
votes
0answers
60 views

Monte Carlo Tree search UCB1 for Tic-Tac-Toe help

I am trying to code a MCTS agent for tic tac toe and i have some theoretical questions regarding MCTS. 1)I am using the UCB1 MCTS $UCB(Si)=average value + 2*sqrt(ln(N)/ni)$ . Considering the image ...
0
votes
0answers
48 views

How to set up MCTS and draw by repetition?

I am running a MCTS as part of a game ML algorithm. The game that it is playing can reach the same state via multiple paths. It can also reach states again. This is similar to how a position on a ...
0
votes
1answer
53 views

Why aren’t heuristics for Connect Four Monte Carlo tree search improving the agent?

I’ve created an agent using MCTS to play Connect Four. It wins against humans pretty well, but I’d like to improve upon it. I decided to add domain knowledge to the MCTS rollout stage. My evaluation ...
0
votes
0answers
31 views

How to observe or measure convergence of Monte Carlo Tree Search?

As above: how does one observe/measure a Monte Carlo Tree Search to be able to update the algorithm and compare results?
0
votes
0answers
32 views

Why would you ignore episodes that loop back on the starting state in MCTS?

After reading about MCTS for policy learning and optimization, I don't understand why you would want to ignore episodes that loop back on the starting state. What advantage does this have and why ...
0
votes
0answers
21 views

Train a Neuronal Network with MCTS Data

I failed using PPO to train a multiplayer card game. Thus I tested monte carlo tree search (mcts) to predict good moves. This works now (you can test the game here. As calculating a good move using ...