Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [monte-carlo-tree-search]

This tag should be used for questions about the MCTS algorithm (how/why it works, potential applications, enhancements, combinations with other algorithms, implementation, etc.)

1
vote
1answer
30 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
74 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 ...
3
votes
1answer
37 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 ...
3
votes
1answer
38 views

Monte Carlo Tree Search Expansion Phase

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

Does Monte Carlo Search (specifically used by AlphaZero) Qualify as Machine Learning?

To the best of my understanding, Monte Carlo Search is an alternative method to Minimax for searching a tree of nodes. It works by choosing a move (generally the one with the highest chance of being ...
10
votes
5answers
2k views

How do I choose which algorithm is best for something like a checkers board game?

I am currently new to artificial intelligence but I am very intrigued by it. I am currently researching three algorithms, namely: Minimax, Alpha-beta pruning and Monte Carlo tree search. As you may ...
5
votes
3answers
466 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 ...
-3
votes
1answer
68 views

Are recent advances in machine learning really “artificial” intelligence, or merely brute force and human design?

It sounds like people boast of something being "artificial" about machine learning when actually people boast that humans implemented algorithms like e.g. Monte Carlo Search (MCST) etc. I think the ...
3
votes
1answer
135 views

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

In MCTS, we start at root node R. Then we select some leaf node L. And we expand it by one or more child nodes and simulate from the child to end of game.image link My question is when to expand? and ...
1
vote
1answer
92 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 ...
3
votes
1answer
128 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 ...
1
vote
1answer
185 views

AlphaZero chess algorithm, Monte Carlo search

Recently, DeepMind's AlphaZero chess algorithm did better than the prior best chess software Stockfish. I read an arxiv paper about it but I'm not sure if: is there a value given for each piece (e.g. ...
2
votes
1answer
56 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 ...
4
votes
1answer
71 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 ...
1
vote
1answer
262 views

Can we use MCTS/UCT without a generative model?

From what I have understood reading the UCT paper "Bandit based monte-carlo planning", MCTS/UCT requires a generative model. Does it mean, in case there is no generative model of the environment, we ...
5
votes
1answer
202 views

MCTS: Terminal (leaf) nodes in selection step

In Monte Carlo Tree Search: What does one do when the Selection step selects a node that is a Terminal state, i.e. a won/lost state (it's by definition a leaf node)? Expansion/Simulation is not in ...
0
votes
1answer
55 views

What techniques are used in practice to generate MDP models?

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' | s, a) -> [0,1] ...
10
votes
1answer
246 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 ...
5
votes
1answer
117 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 ...
15
votes
1answer
742 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-...