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
0
votes
0answers
28 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 ...
2
votes
0answers
18 views

How to run a Monte Carlo Tree Search MCTS for stochastic environment?

For MCTS there is an expansion phase where we make a move and list down all the next states. But this is complicated by the fact that for some games, after making the move, there is a stochastic ...
0
votes
0answers
57 views

How AlphaGo Zero is learning from $\pi_t$ when $z_t = -1$?

I have questions on the way AlphaGo Zero is trained. From original AlphaGo Zero paper, I knew that AlphaGo Zero agent learns a policy, value functions by the gathered data $\{(s_t, \pi_t, z_t)\}$ ...
0
votes
0answers
37 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 ...
2
votes
0answers
35 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 ...
0
votes
1answer
40 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
27 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?
2
votes
1answer
67 views

Should Monte Carlo tree search be able to consistently beat me in the connect four game?

I've implemented the Monte Carlo tree search (MCTS) algorithm for a connect four game I've built. The MCTS agent beats a random choice agent 90-100% of the time, but I’m still able to beat it pretty ...
5
votes
1answer
77 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
2answers
161 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 ...
0
votes
0answers
30 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 ...
3
votes
0answers
33 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,...
2
votes
0answers
40 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 ...
1
vote
1answer
40 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 ...
2
votes
1answer
60 views

How to apply hyperparameter optimization on Monte Carlo Tree Search?

I have a basic MCTS agent for the game of Hex (a turn based game). I want to tune the parameters of UCT (the Cp parameter) and the number of rollouts parameter. Where do I have to begin? The problem ...
2
votes
1answer
60 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
0answers
19 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 ...
3
votes
0answers
44 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 ...
6
votes
1answer
191 views

MCTS: How to choose the final action from the root

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root? The original UCT paper (2006) says bestAction in their ...
4
votes
1answer
65 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
0answers
26 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
2answers
118 views

How to understand the 4 steps of Monte Carlo Tree Search

From many blogs and this one https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html We know that the process of MCTS algorithm has 4 steps. Selection: Starting at root node R,...
3
votes
0answers
108 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 ...
0
votes
0answers
25 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 ...
6
votes
2answers
482 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 ...
3
votes
2answers
142 views

What is the appropriate way to deal with multiple paths to same state in MCTS?

Many games have multiple paths to the same states. What is the appropriate way to deal with this in MCTS? If the state appears once in the tree, but with multiple parents, then it seems to be ...
3
votes
2answers
129 views

How can we efficiently and unbiasedly decide which children to generate in the expansion phase of MCTS?

When executing MCTS' expansion phase, where you create a number of child nodes, select one of the numbers, and simulate from that child, how can you efficiently and unbiasedly decide which child(ren) ...
3
votes
1answer
211 views

Several questions related to UCT and MCTS

In Bandit Based Monte-Carlo Planning, the article where UCT is introduced as a planning algorithm, there is an algorithm description in page 285 (4 of the pdf). Comparing this implementation of UCT (a ...
3
votes
1answer
168 views

Is the playout started from a leaf or child of leaf in Monte Carlo Tree Search?

On Wikipedia, the MCTS algorithm is described Selection: start from root $R$ and select successive child nodes until a leaf node $L$ is reached. A leaf is any node from which no simulation (playout) ...
6
votes
1answer
308 views

Does AlphaZero use Q-Learning?

I was reading the AlphaZero paper Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm, and it seems they don't mention Q-Learning anywhere. So does AZ use Q-...
6
votes
1answer
195 views

When does the selection phase exactly end in MCTS?

All sources I can find provide a similar explanation to each phase. In the Selection Phase, we start at the root and choose child nodes until reaching a leaf. Once the leaf is reached (assuming the ...
1
vote
0answers
46 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.
2
votes
0answers
110 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 ...
3
votes
1answer
137 views

How Does AlphaGo Zero Implement Reinforcement Learning?

AlphaGo Zero (https://deepmind.com/blog/alphago-zero-learning-scratch/) has several key components that contribute to it's success: A Monte Carlo Tree Search Algorithm that allows it to better search ...
5
votes
2answers
158 views

What is a simple game for validation of MCTS?

What is a simple turn-based game, that can be used to validate a Monte-Carlo Tree Search code and it's parameters? Before applying it to problems where I do not have a possiblity to validate its ...
3
votes
1answer
424 views

How fast does Monte Carlo tree search converge?

How fast does Monte Carlo Tree Search converge? Is there proof that it does converge? How does it compare to Temporal Difference learning in terms of convergence speed (assuming the evaluation step ...
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 ...
3
votes
1answer
61 views

How does Monte Carlo Tree Search UCT exploitation value change based on perspective?

In this blog toward the end, the author writes the following: For the sake of my question, let’s assume that a terminal state gives a reward of +1 for a win and -1 for a loss. When the author says “...
8
votes
2answers
121 views

How can alpha zero learn if the tree search stops and restarts before finishing a game?

I am trying to understand how alpha zero works, but there is one point that I have problems understanding, even after reading several different explanations. As I understand it (see for example https:/...
3
votes
0answers
73 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
1answer
97 views

Why is Monte Carlo used as the tree search algorithm for AlphaGo?

Could a better algorithm other than Monte Carlo be used for the AlphaGo computer? Why didn't the DeepMind team think of choosing another kind of algorithm rather than spending time on their neural ...
2
votes
1answer
63 views

Similarities and differences between UCT algorithms in (i), (ii), (iii) and (iv)?

I am trying to understand the similarities and differences between: (i) the UCT algorithm in Kocsis and Szepesvári (2006); (ii) the UCT algorithm in Section 3.3 of Browne et al (2012); (iii) the MCTS ...
2
votes
1answer
89 views

Chess Engine for low clock cycle CPU

I'm looking for a simple chess algorithm that works well on a ~132MHz CPU. I know that MiniMax would take too long to go deep in order to find good moves. Is Monte Carlo Tree Search working well on ...
3
votes
0answers
86 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 ...
4
votes
2answers
542 views

Rollout algorithm like Monte Carlo search suggest model based reinforcement learning?

From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL). Model free RL means agent doesnt know the transition and reward model. ...
1
vote
2answers
474 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 ...
3
votes
1answer
212 views

Why do neural nets and machine learning tend to work well with MCTS, but not with regular Minimax game-playing AI?

I've often heard MCTS grouped together with neural nets and machine learning. From what I gather, MCTS uses a refined intuition (from maching learning) to evaluate positions. This allows it to better ...
4
votes
1answer
377 views

Any interesting ways to combine Monte Carlo tree search with the minimax algorithm?

I've been working on a game-playing engine for about half a year now, and it uses the well known algorithms. These include minimax with alpha-beta pruning, iterative deepening, transposition tables, ...
5
votes
1answer
99 views

How does Hearthstone AI deal with random events

I want to learn a lot about the AI of CCG, such as Hearthstone. And now I have known one of the main algorithms that used in this kind of games, MCTS. It analyses the most promising moves, and expands ...
3
votes
1answer
104 views

Weighted move rating for AI

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 ...