22
votes
Accepted
How do I choose the best algorithm for a board game like checkers?
tl;dr:
None of these algorithms are practical for modern work, but they are good places to start pedagogically.
You should always prefer to use Alpha-Beta pruning over bare minimax search.
You ...
- 9,207
15
votes
Accepted
How does "Monte-Carlo search" work?
Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances.
As ...
10
votes
Accepted
Is the new AlphaGo implementation using Generative Adversarial Networks?
No, GANs are not used. It's reinforcement learning at what it does best. The tree search is an interesting addition and assists with navigating the sheer scale of the game.
Although the agent was ...
- 3,787
10
votes
Does Monte Carlo tree search qualify as machine learning?
John's answer is correct in that MCTS is traditionally not viewed as a Machine Learning approach, but as a tree search algorithm, and that AlphaZero combines this with Machine Learning techniques (...
- 10.1k
9
votes
Accepted
Does Monte Carlo tree search qualify as machine learning?
Monte Carlo Tree Search is not usually thought of as a machine learning technique, but as a search technique. There are parallels (MCTS does try to learn general patterns from data, in a sense, but ...
- 9,207
9
votes
Accepted
Why AlphaGo didn't use Deep Q-Learning?
$Q$-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for single-agent environments. The entire problem ...
- 10.1k
8
votes
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, both the alpha-beta pruning and MCTS are extensions of the basic ...
- 10.1k
8
votes
Accepted
What is the appropriate way to deal with multiple paths to same state in MCTS?
If the state appears twice in the tree, aren't we wasting a lot of resources thinking about it multiple times?
You're right. Precisely the same problem was also noticed decades before MCTS existed, ...
- 10.1k
7
votes
Accepted
How do I know when to use which Monte Carlo method?
They are all called Monte Carlo because all of them are a different version of the canonical Monte Carlo algorithm.
The canonical version of Monte Carlo algorithm is a stochastic algorithm to ...
7
votes
Accepted
Does AlphaZero use Q-Learning?
Note: you mentioned in the comments that you are reading the old, pre-print version of the paper describing AlphaZero on arXiv. My answer will be for the "official", peer-reviewed, more recent ...
- 10.1k
7
votes
MCTS for non-deterministic games with very high branching factor for chance nodes
You can try using an "Open-Loop" MCTS approach, instead of the standard "closed-loop" one, and eliminate chance nodes altogether. See, for example, Open Loop Search for General Video Game Playing.
In ...
- 10.1k
6
votes
Accepted
What should we do when the selection step selects a terminal state?
In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it is a win or loss, and backpropagate accordingly. The same as if you made a simulation step, but in ...
- 106
6
votes
Accepted
When to expand and when to simulate in Monte Carlo Tree Search?
The most common strategy is to simply expand exactly one node per iteration; you can view this as expanding the first node of the Play-Out phase ("simulation" in your image), and not expanding any ...
- 10.1k
6
votes
Why didn't champion of the Go game manage to win the last game against AlphaGo, after winning the 4th one?
The technique used by AlphaGo is "Monte Carlo Tree Search", combined with a very well trained neural network. The network's job is to estimate the quality of different board states and moves. This ...
- 9,207
6
votes
Why AlphaGo didn't use Deep Q-Learning?
Deep Q Learning is a model-free algorithm. In the case of Go (and chess for that matter) the model of the game is very simple and deterministic. It's a perfect information game, so it's trivial to ...
- 1,126
5
votes
Accepted
Why does Monte Carlo work when a real opponent's behavior may not be random
First, we need to distinguish plain Monte-Carlo from Monte-Carlo Tree Search. They're different things.
Monte-Carlo search, in the context of game AI search algorithms, is typically understood to ...
- 10.1k
5
votes
Which algorithms can we use on games with high branching factors (e.g. Connect6)?
Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory ...
- 10.1k
5
votes
Accepted
Any interesting ways to combine Monte Carlo tree search with the minimax algorithm?
There has indeed been some research towards combining MCTS and minimax-like algorithms. For example, the following two publications:
Monte-Carlo Tree Search and minimax hybrids
Monte-Carlo Tree ...
- 10.1k
5
votes
Rollout algorithm like Monte Carlo search suggest model based reinforcement learning?
Whether or not MCTS is even a Reinforcement Learning algorithm at all may be up for debate, but let's assume that we view it as an RL algorithm here.
For practical purposes, MCTS really should be ...
- 10.1k
5
votes
Accepted
Does the AlphaZero algorithm keep the subtree statistics after each move during MCTS?
The supplementary material of the AlphaZero paper states the following:
Unless
otherwise specified, the training and search algorithm and parameters are identical to AlphaGo
Zero.
I didn't see any ...
- 1,332
4
votes
Would AlphaGo Zero become perfect with enough training time?
Assuming you mean a mathematically perfect player, similar to what we can achieve trivially in Tic Tac Toe, then the answer is "maybe". The underlying reinforcement learning algorithms that it uses do ...
- 30.4k
4
votes
Accepted
How does Hearthstone AI deal with random events
The most "standard" implementation of MCTS probably involves storing copies of game states inside nodes. This works fine for deterministic games, but not for non-deterministic games due to the reasons ...
- 10.1k
4
votes
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).
Monte Carlo Tree Search is a planning algorithm. It can be considered ...
- 30.4k
4
votes
Accepted
How fast does Monte Carlo tree search converge?
Yes, Monte Carlo tree search (MCTS) has been proven to converge to optimal solutions, under assumptions of infinite memory and computation time. That is, at least for the case of perfect-information, ...
- 10.1k
4
votes
What is a simple game for validation of MCTS?
A good choice might be smaller-scale games of Go, like a 9x9 board. This was the original application domain MCTS was designed for, and the original paper by Brugmann from 1993 details parameters that ...
- 9,207
4
votes
Accepted
How Does AlphaGo Zero Implement Reinforcement Learning?
If you learn a policy or a value function from experience (that is, interaction with an environment), that's RL. In the case of AlphaGo, the MCTS is used to acquire the experience.
RL could in fact ...
- 39.6k
4
votes
Accepted
How does AlphaZero's MCTS work when starting from the root node?
I looked at the Python pseudo-code attached to the Data S1 of the Supplementary Materials of the AlphaZero paper. Here is my findings:
Contrary to the paper, AlphaZero does not store $\{N(s, a), W(S, ...
- 1,510
4
votes
Accepted
In MCTS, what to do if I do not want to simulate till the end of the game?
Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards:
The leaf $s'$ ...
- 2,426
3
votes
Accepted
Can we use MCTS without a generative model?
You either need a generative model or an emulator of the environment. In the later case you don't calculate your transitions and rewards using the model but feed your actions and states to the ...
- 1,684
3
votes
Accepted
Which nodes are expanded in the expansion phase of MCTS?
By far the most common (and likely also the most simple / straightforward) implementation is to expand exactly one node in the Expansion Phase; specifically, the node corresponding to the very first ...
- 10.1k
Only top scored, non community-wiki answers of a minimum length are eligible