2

AlphaZero searches for moves using Monte Carlo Tree Search (MCTS). As I understand MCTS, it takes the root position, goes to a child node, and then plays random moves until one side wins. Since the moves played are random, does that mean AlphaZero is also random?

Related: this question shows that Stockfish and other conventional engines are indeed deterministic if one looks only at the number of nodes evaluated. I don't know however if the same applies to AlphaZero.

3

No. MCTS is generally not deterministic. However, it's not that bad given how powerful Google's machines were.

  • 3
    I don't think AlphaZero uses random roll-outs. If it just explores branches according to the neural network score, it might well be deterministic. But it's too long since I read the paper, so I'm not sure. – BlindKungFuMaster Dec 10 '18 at 14:04
  • @BlindKungFuMaster I need some time to give you a technical answer. I'm not able to do it now. – SmallChess Dec 10 '18 at 14:05
  • 1
    @BlindKungFuMaster It does randomly explore the tree until a leaf is found, but it is not a uniform random dist., instead it performs an importance sampling as follows: it selects moves either proportionally to the node win probability (estimated over the set of times the node's been sampled) or w.r.t to the visit count of the node (emphasizing rare moves). These two types of selection entail the exploration and exploitation modes respectively. Which type gets chosen at each generation point is inherently random (though non-uniform) and therefore, the set of sampled leaves is randomized. – Phonon Dec 10 '18 at 23:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.