Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
23 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 ...
John Doucette's 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 ...
Disenchanted Lurker's 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 ...
Jaden Travnik's user avatar
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 (...
Dennis Soemers's user avatar
  • 10.3k
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 ...
John Doucette's user avatar
9 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 ...
Dennis Soemers's user avatar
  • 10.3k
9 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, ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Pedro Narloch's 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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
derjack's user avatar
  • 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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
John Doucette's user avatar
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 ...
harwiltz's user avatar
  • 1,136
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Dennis Soemers's user avatar
  • 10.3k
5 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, ...
user3667125's user avatar
  • 1,570
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 ...
DeepQZero's user avatar
  • 1,399
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 ...
Neil Slater's user avatar
  • 32.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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Neil Slater's user avatar
  • 32.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, ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
John Doucette's 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 ...
nbro's user avatar
  • 40.8k
4 votes
Accepted

MCTS: How to choose the final action from the root

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" ...
Dennis Soemers's user avatar
  • 10.3k
4 votes

When should Monte Carlo Tree search be chosen over MiniMax?

Some basic advantages of MCTS over Minimax (and its many extensions, like Alpha-Beta pruning and all the other extensions over that) are: MCTS does not need a heuristic evaluation function for states....
Dennis Soemers's user avatar
  • 10.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'$ ...
Kostya's user avatar
  • 2,534

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