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.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
30 views

When should Monte Carlo Tree search be chosen over MiniMax?

I would like to ask whether MCTS is usually chosen when the branching factor for the states that we have available is large and not suitable for Minimax. Also, other than MCTS simluates actions, where ...
4
votes
1answer
62 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 ...
4
votes
2answers
235 views

Determinization step in Information Set Monte Carlo Tree Search

After reading this paper about Monte Carlo methods for imperfect information games with elements of uncertainty, I couldn't understand the application of determinization step in author's ...
3
votes
0answers
59 views

Why AlphaGo didn't use Deep Q-Learning?

In the previous research, in 2015, Deep Q-Learning shows its great performance on single player Atari Games. But why do AlphaGo's researchers use CNN + MCTS instead of Deep Q-Learning? is that because ...
3
votes
0answers
21 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
36 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
93 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
60 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
82 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
20 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 ...
2
votes
0answers
17 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
52 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
103 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
14 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 ...
1
vote
1answer
26 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
45 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.
1
vote
2answers
426 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 ...
0
votes
1answer
16 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
18 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
23 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
13 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 ...
0
votes
0answers
22 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 ...
0
votes
0answers
24 views

Tweaking MCTS to account for opponent knowing the state of the game

I'm making an artificial intelligence for a card game using MCTS. With a standard 52-cards deck, 4 hands are dealt: 1 for each of the 3 players and one extra hand. Then, each player gets the choice to ...