21 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
9 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 (...
user avatar
  • 9,419
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 ...
user avatar
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 ...
user avatar
  • 9,419
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 ...
user avatar
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 ...
user avatar
  • 9,419
7 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, ...
user avatar
  • 9,419
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 ...
user avatar
  • 86
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 ...
user avatar
  • 9,419
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 ...
user avatar
6 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 ...
user avatar
  • 9,419
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 ...
user avatar
  • 9,419
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 ...
user avatar
  • 9,419
5 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 ...
user avatar
  • 9,419
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 ...
user avatar
  • 24.5k
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 ...
user avatar
  • 9,419
4 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 ...
user avatar
  • 9,419
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 ...
user avatar
  • 24.5k
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, ...
user avatar
  • 9,419
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 ...
user avatar
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 ...
user avatar
  • 34.3k
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'$ ...
user avatar
  • 1,833
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 ...
user avatar
  • 9,419
3 votes
Accepted

Would AlphaGo Zero become perfect with enough training time?

We cannot tell with certainty whether AlphaGo Zero would become perfect with enough training time. This is because none of the parts (Neural Network) that would benefit from infinite training time (= ...
user avatar
  • 9,419
3 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 ...
user avatar
  • 9,419
3 votes
Accepted

Which Reinforcement Learning algorithms are efficient for episodic problems?

When applying techniques like SARSA(which are on-policy), one needs to have control over a simulator. If one is able to access only the episodic dataset, then the only choice is to opt for Q-learning ...
user avatar
  • 46
3 votes
Accepted

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

is there a value given for each piece (e.g. 1 for pawn, 3 for knight, 9 for queen, etc.) to train the algorithm, or does the algorithm learn this by himself? No, there are no such explicit values ...
user avatar
  • 9,419
3 votes
Accepted

Do AIs based on MCTS start each game from scratch?

Your intuition is right. The tree is grown after each game. Before the first play through, the values of each decision point are initialized (randomly or to some constant). Then at the end of one ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible