My understanding is that Alpha Zero's algorithm was fixed after the "learning" phase, so would it come up with the same move for every position? Was the variability in the match entirely due to a Stockfish setting, or did Alpha Zero also display an element of randomness in its move selection?
5
-
2Monte Carlo tree search used by alpha zero sounds pretty random.– hoacinDec 16, 2017 at 7:31
-
1Monte Carlo is not a deterministic algorithm.– ABCDDec 16, 2017 at 7:33
-
My understanding is the mcst was used in the "learning" phase to train the neural net, while the algorithm was bedded down for the actual match. Seems like I'm missing a trick.– firtydankDec 16, 2017 at 10:16
-
3I think mcts was used all the time.– hoacinDec 16, 2017 at 11:55
-
Another possible if someway unlikely source of variation is time. While the same time may be used on the same move there is always some ability to take a different about of time to do some computation, thus maybe it ran a bit faster one time over another and then the faster time it came up with a better answer because it got further then the slower time.– Benji AltmanDec 18, 2017 at 22:03
Add a comment
|
2 Answers
I've noticed AlphaZero played 1.d4 and 1.Nf3 in http://www.chessgames.com/perl/chess.pl?tid=91944&crosstable=1. Possibilities:
- Mutlithreading (any software engineer can tell you it's not deterministic)
- Monte Carlo Tree Search (the algorithm draws random paths, so it can't be deterministic)
Please note while the model's parameters are "fixed" (your own words), the actual move might be different. We don't have the source code for AlphaZero, but multithreading and MCTS are likely two major casues.
-
1What do you mean multi-threading isn't deterministic? Isn't that dependent on how it is used. We may not know what thread finishes first, but for the most part people tend to (or at least try to) be careful about making sure that any inconsistencies with order that things are executed don't effect the final outcome of the program. Dec 18, 2017 at 17:41
-
@BenjiAltman I wrote we don’t have source code. You are welcome to contribute for your own answer.– ABCDDec 18, 2017 at 21:58
-
3
-
1@BenjiAltman Threads can finish processing and different times. Unless the program somehow waits for every thread to finish and returns them deterministically, the actual result can depend on which thread is given higher priority by the scheduler.– user14142Dec 20, 2017 at 23:05
-
1@rec Correct. High performance applications such as chess don't wait for threads to finish (they are not business applications!), and therefore deterministic. For example, Stockfish running on multi-core is 100% non-deterministic.– ABCDDec 20, 2017 at 23:14
The LC0 authors studied the AlphaZero paper very carefully, ran their own experiments, and they came to the following conclusion. AlphaZero, despite calling it's algorithm Monte Carlo tree search (All Monte Carlo methods are by definition explicitly random), does not employ any explicit non-determinism after a certain number of moves (I believe this is 15 moves).
There are two different parts to MCTS that could introduce randomness into move selection.
During the search phase, AlphaZero assigns weights on which moves to explore based on 2 factors: the win probability as evaulated by the neural network, and also some sub-tree size statistics of the parent and child move sub-trees. The first factor ensures that more promising lines are evaluated first, and the second factor ensures that less promising lines are eventually searched. In a natural implementation of MCTS, it would use weighted random choices between these weighted possibilities. In reality, AlphaZero chooses between these completely deterministicly, by just choosing the max weight every time. It does this because the randomness in this step does not turn out to be helpful, and only distracts the engine from the more important variations, on average.
During the moving phase, it can make a weighted choice between move candidates which already have deep and accurate evaluations calculated by the search phase. The idea is to make slightly suboptimal moves to try to introduce diversity in its play, so it doesn't play the same game every time. This is especially important during training, but also leads to more interesting match results. It turns out that AlphaZero only does this for the first 15 moves or so, after that it always chooses the best move. This determinism turns out to be essential for its extremely accurate endgame play, where tiny differences in evaluation turn out to be the difference between draws and wins.
This is true during both training and evaluation.
In other words, once it is out of the opening, its play is as deterministic as a traditional engine.
However, note that it will have the same sort of multithreading and time control non-determinism as traditional engines.
