3

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.

2

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
  • 2
    @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
  • Are you still confident this is the answer? Watching Leela play the TCEC bonus against Stockfish, from the opening position, its moves seemed to be deterministic. In all 50 games it had the white pieces, it played 1.e4 in all of them. – Allure May 6 at 11:21
  • 1
    @Allure: that it always 1.e4 doesn't by itself mean anything about the algorithm being deterministic or not. It could have played many many games with many different moves internally but if 1.e4 consistently comes out with the best average scores over all those games, it'll play 1.e4. – RemcoGerlich May 27 at 8:28
0

It seems Alphazero is deterministic, up to a point. Looking at the details of its implementation, there's nothing inherently random in it. If one looks at the TCEC bookless bonus between Leela (an Alphazero clone) against Stockfish, this particular Leela net always played the same opening move 1.e4 when it was white. Against this Stockfish sometimes played 1...e6 and sometimes 1...c5; Leela always responded with the Steinitz Boleslavsky variation and Najdorf English attack respectively. In fact, almost every time it's Stockfish deviating instead of Leela:

Leela is more stubborn than Stockfish in its opening moves. All the major opening classes in the first few moves - Sicilian, French, Ruy Lopez, Italian, QGD - were determined by Stockfish either in black or in white. Stockfish expanded the opening tree almost every move in at least one opening line, again in both white and black. Leela, on the other hand, almost always played the same move when presented with the same position. In the first 24 plys of 100 games I found only 3 cases where Leela expanded the opening tree, on move 7 as black in QGD (game 29), on move 10 as black in Ruy Lopez (games 45 vs 97), and on move 10 as white in French (game 84).

Although Leela was a lot less random than Stockfish, it wasn't completely deterministic either, presumably because of multithreading & random fluctuations causing a different number of nodes to be evaluated. Take out these factors, and Leela (and hence Alphazero) is deterministic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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