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
3
votes
2answers
148 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
400 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
215 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) ...
7
votes
1answer
579 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
328 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
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.
2
votes
0answers
190 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
180 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
224 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
857 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
17 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
132 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
181 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
81 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
111 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
78 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 ...
3
votes
0answers
91 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
819 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. ...
3
votes
2answers
785 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
282 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 ...
3
votes
2answers
327 views

How can I design a reinforcement learning model for a game with multiple complex actions taken at a time?

I have a steady hex-map and turn-based wargame featuring WWII carrier battles. On a given turn, a player may choose to perform a large number of actions. Actions can be of many different types, and ...
4
votes
1answer
673 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, ...
6
votes
1answer
112 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 ...
2
votes
1answer
124 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 ...
2
votes
1answer
41 views

Is it meaningful to give more weight to the result of monte carlo search with less turn win?

I'm programming on Connect6 with MCTS. Monte Carlo Tree Search is based on random moves. It counts up the number of wins in certain moves. (Whether it wins in 3 turns or 30 turns) Is the move with ...
3
votes
1answer
72 views

Should I use Monte Carlo or a classifier for this Decision Making problem?

I want to build a model to support decision making for loan insurance proposal. There are three actors in the problem: a bank, a loaner applicant (someone who ask for a loan) and a counselor. The ...
6
votes
3answers
237 views

Would AlphaGo Zero become perfect with enough training time?

Would AlphaGo Zero become theoretically perfect with enough training time? If not, what would be the limiting factor? (By perfect, I mean it always wins the game if possible, even against another ...
4
votes
1answer
662 views

Algorithms for games with very high branching factors (Connect6)

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

Which nodes are expanded in the expansion phase of MCTS?

I'm confused regarding a specific detail of MCTS. To illustrate my question, let's take the simple example of tic-tac-toe. After the selection phase, when a leaf node is reached, the tree is expanded ...
10
votes
3answers
920 views

Does Monte Carlo tree search qualify as machine learning?

To the best of my understanding, the Monte Carlo tree search (MCTS) algorithm is an alternative to minimax for searching a tree of nodes. It works by choosing a move (generally, the one with the ...
16
votes
3answers
8k views

How do I choose the best algorithm for a board game like checkers?

How do I choose the best algorithm for a board game like checkers? So far, I have considered only three algorithms, namely, minimax, alpha-beta pruning, and Monte Carlo tree search (MCTS). Apparently,...
7
votes
3answers
1k views

Why does Monte Carlo work when a real opponent's behavior may not be random

I am learning about Monte Carlo algorithms and struggling to understand the following: If simulations are based on random moves, how can the modeling of the opponent's behavior work well? For ...
5
votes
1answer
1k views

When to expand and when to simulate in Monte Carlo Tree Search?

In Monte Carlo Tree Search (MCTS), we start at root node $R$. Then we select some leaf node $L$. And we expand $L$ by one or more child nodes and simulate from the child to the end of the game. When ...
1
vote
1answer
153 views

How to estimate the AI player's strength in multiplayer game?

I have implemented multiple MCTS based AI players for the Love Letter game (rules). It is a 2-4 players zero sum card game where players make alternating moves. I am struggling with how to properly ...
1
vote
1answer
735 views

Game AI evaluation function and making progress towards winning

In two-player games, the exact value of the evaluation function doesn't matter, as long as it's bigger for better positions. However, for learning, it's customary when it does change when the best ...
3
votes
1answer
472 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 ...
4
votes
1answer
577 views

Is there any value given to each chess piece in AlphaZero? [closed]

Recently, DeepMind's AlphaZero chess algorithm did better than the prior best chess software Stockfish. I read the paper Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning ...
3
votes
1answer
92 views

Do AIs based on MCTS start each game from scratch?

AIs that rely on MCTS - like AlphaGo - create their decision tree as the game progresses. Do they start from scratch each game and build a new tree or do they keep the tree and grow it from game to ...
6
votes
2answers
341 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 ...
2
votes
1answer
418 views

Can we use MCTS without a generative model?

From what I have understood reading the UCT paper Bandit based monte-carlo planning, by Levente Kocsis and Csaba Szepesvári, MCTS/UCT requires a generative model. Does it mean that, in case there is ...
6
votes
1answer
998 views

What should we do when the selection step selects a terminal state?

In Monte Carlo tree search, what should we do when the selection step selects a terminal state (i.e. a won or lost state), which is, by definition, a leaf node? Expansion and simulation is not in ...
1
vote
1answer
119 views

How do you generate the transition probabilities of a non-trivial MDP?

I understand an MDP (Markov Decision Process) model is a tuple of $\{S, A, P, R \}$ where: $S$ is a discrete set of states $A$ is a discrete set of actions $P$ is the transition matrix ie. $P(s' \mid ...
10
votes
1answer
497 views

Monte Carlo Tree Search: What kind of moves can easily be found and what kinds make trouble?

I want to start with a scenario that got me thinking about how well MCTS can perform: Let's assume there is a move that is not yet added to the search tree. It is some layers/moves too deep. But if we ...
6
votes
1answer
170 views

How do I know when to use which Monte Carlo method?

I'm a bit confused with extensive number of different Monte Carlo methods such as: Hamiltonian/Hybrid Monte Carlo (HMC), Dynamic Monte Carlo (DMC), Markov chain Monte Carlo (MCMC), Kinetic Monte ...
16
votes
1answer
2k views

How does “Monte-Carlo search” work?

I have heard about this concept in a Reddit post about Alpha Go. I have tried to go through the paper and the article, but could not really make sense of the algorithm. So, can someone give an easy-...

1
2