AlphaZero’s search procedure

Question

I am aware of related questions and great answers on the same topic such as Understanding AlphaZero. My questions are related to the following figure on AlphaZero's search procedure

This figure comes from the Science paper on AlphaZero (Fig. 4, page 4). The search is illustrated for a position from the very nice game 1 AlphaZero (white) and Stockfish (black) after 29. ... Qf8. The rest of note of the figure is as follows

The internal state of AlphaZero's MCTS is summarized after 10^2, ..., 10^6 simulations. Each summary shows the 10 most visited states. The estimated value is shown in each state, from white's perspective, scaled to the range [0, 100]. The visit count of each state, relative to the root state of that tree, is proportional to the thickness of the border circle. AlphaZero considers 30.c6 but eventually plays 30.d5.

I would appreciate some insights regarding the following questions. (Important to note that I am a mere chess player with no knowledge on computer science. I still find this fascinating)

1. What does represent the 10^2, ..., 10^6 simulations? I am very confused because in the Supplementary Material they note that ``During training, each MCTS used 800 simulations''.
2. What does it mean that each MCTS used 800 simulations?
3. I assume that the value of 60 in the red circle in the 10^2 simulations represents a 60% expected score for white, which is the average of all position evaluations. However, the simple average of the 9 moves shown is equal to 61.2. I guess that other moves also considered and simulated. Am I right here?
4. I assume that for simulations 10^3 to 10^6, they only present an illustrative sample of the branches. The simulation 10^5 is not shown after 34.Rce1 or stopped after 34.Rce1? I guess that each simulation goes until an expected score of 100%.

Answer 1

The diagram shows the 10 most visited game states/positions that AlphaZero calculated. It's actually looking at thousands of positions, but they're only showing the 10 positions that it comes back to the most. For your questions:

1) AlphaZero's search algorithm is called Monte Carlo Tree Search (MCTS). The fundamentals of how it works when thinking at some game state:

• Pick a move. The way this move is picked is based off an algorithm favoring:
  • How good a move has performed in past random simulations of it.
  • How infrequently it has been picked (a move played out less ==> more desirable).
• Follow this move to a new game state (i.e., the position that arises when you play the move).
• Repeat step 1, for some time limit or depth limit.

The move that has the best average score in all its playouts is the one that AlphaZero picks. There's more involved than this, but the above is the general idea of MCTS. So something like 10^2 simulations for the root node means that AlphaZero performed the above algorithm 10^2 times for that position.

The part where they mentioned "800 simulations" refers to when AlphaZero was learning (before its games with Stockfish). The way AlphaZero learns heuristics on its own (which allow it to accurately evaluate positions) is by playing itself over and over. So, I assume they mean that during this phase of playing itself, each time it thought on what to play in a position, it only performed 800 simulations from a position. The point of this was probably to have time to get more practice games in. Against Stockfish, playing extremely quickly is unnecessary, and AlphaZero may as well use the time it's been given to playout way more such simulations.

2) Explained above.

3) Yes, thousands of other moves are also considered, they just aren't shown in the diagram. Also, even if the 10 states shown were the only ones reached, you couldn't just average their scores out. The reason is that some game states are reached more often than others, and thus have a higher weight in the average calculation.

• To illustrate this, assume you only had two possible moves you could play in the beginning of a game: 1.e4 and 1.h4. Looking back at the MCTS algorithm I outlined, playouts/simulations on 1.e4 would happen more often since 1.e4 performs better. However, 1.h4 would also be picked once in a while due to how infrequently you look at it. So maybe you do 9 playouts on 1.e4 and get a score of 60%, while do 1 playout on 1.h4 and get a 0% score. Your odds of winning from the starting position are not (60% + 0%) / 2 = 30%, but rather (60% * 9 + 0% * 1) / 10 = 54%.

4) Yes, only an illustrative sample is shown since they only wanted to show the 10 most visited game states. I'm sure AlphaZero continued the MCTS algorithm far past 34.Rce1.