How does AlphaZero use its value and policy heads in conjunction?

Question

I have a question about how the value and policy heads are used in AlphaZero (not Alphago Zero), and where the leaf nodes are relative to the root node. Specifically, there seem to be several possible interpretations:

1. Policy estimation only. This would be most similar to DFS in which an average evaluation is computed through MCTS rollouts (though as others have noted the AlphaZero implementation actually seem to be deterministic apart from the exploration component, so 'rollout' may not be the most appropriate term) after reaching the . Here each leaf node would be at the end of the game.

2. Value estimation only. It seems that if the value network is to be used effectively, there should be a limit on the depth to which any position is searched, e.g. 1 or 2 ply. If so, what should the depth be?

3. They are combined in some way. If I understand correctly, there is a limit on the maximum number of moves imposed - so is this really the depth? By which I mean, if the game has still not ended, this is the chance to use the value head to produce the value estimation? The thing is that the paper states that the maximum number of moves for Chess and shogi games was 512, while it was 722 moves for Go. These are extremely deep - evaluations based on these seem to be rather too far from the starting state, even when averaged over many rollouts.

My search for answers elsewhere hasn't yielded anything definitive, because they've focused more on one side or the other. For example, https://nikcheerla.github.io/deeplearningschool/2018/01/01/AlphaZero-Explained/ the emphasis seems to be on the value estimation.

However, in the Alphazero pseudocode, e.g. from https://science.sciencemag.org/highwire/filestream/719481/field_highwire_adjunct_files/1/aar6404_DataS1.zip the emphasis seems to be on the policy selection. Indeed, it's not 100% clear if the value head is used at all (value seems to return -1 by default).

Is there a gap in my understanding somewhere? Thanks!

Edit: To explain this better, here's the bit of pseudocode given that I found slightly confusing:

class Network(object):

  def inference(self, image):
    return (-1, {})  # Value, Policy

  def get_weights(self):
    # Returns the weights of this network.
    return []

So the (-1,{}) can either be placeholders or -1 could be an actual value and {} a placeholder. My understanding is that they are both placeholders (because otherwise the value head would never be used), but -1 is the default value for unvisited nodes (this interpretation is taken from here, from the line about First Play Urgency value: http://blog.lczero.org/2018/12/alphazero-paper-and-lc0-v0191.html). Now, if I understand correctly, inference is called in both during training and playing by the evaluate function. So my core question is: how deep into the tree are the leaf nodes (i.e. where the evaluate function would be called)?

Here is the bit of code that confused me. In the official pseudocode as below, the 'rollout' seems to last until the game is over (expansion stops when a node has no children). So this means that under most circumstances you'll have a concrete game result - the player to move doesn't have a single move, and hence has lost (so -1 also makes sense here).

def run_mcts(config: AlphaZeroConfig, game: Game, network: Network):
  root = Node(0)
  evaluate(root, game, network)
  add_exploration_noise(config, root)

  for _ in range(config.num_simulations):
    node = root
    scratch_game = game.clone()
    search_path = [node]

    while node.expanded():
      action, node = select_child(config, node)
      scratch_game.apply(action)
      search_path.append(node)

    value = evaluate(node, scratch_game, network)
    backpropagate(search_path, value, scratch_game.to_play())
  return select_action(config, game, root), root

But under such conditions, the value head still doesn't get very much action (you'll almost always return -1 at the leaf nodes). There are a couple of exceptions to this.

1. When you reach the maximum number of allowable moves - however, this number is a massive 512 for chess & Shogi and 722 for Go, and seems to be too deep to be representative of the 1-ply positions, even averaged over MCTS rollouts.
2. When you are at the root node itself - but the value here isn't used for move selection (though it is used for the backprop of the rewards)

So does that mean that the value head is only used for the backprop part of AlphaZero (and for super-long games)? Or did I misunderstand the depth of the leaf nodes?

Answer 1

I am also a bit confused by your wording but I will try to clear some things up.

During MCTS the policy head is used to guide the search while the value head is used as a replacement for roll outs to estimate how good the game position looks. One iteration of the search procedure in MCTS finds a new leaf node which has not been evaluated by the network yet. This leaf node does not have to be a terminal state of the actual game. In fact, in the rare cases towards the end of the game where it IS a terminal state then the network evaluation can be skipped and the real value is used instead.

In the code you find slightly confusing -1 and {} are both place holders. The value -1 is a placeholder for the value head output and {} a placeholder for the policy head output of the neural network evaluation. The policy head output should be a vector of values (one value for each child of the node). It is not related to FPU at all, the code you linked uses FPU 0.

  def value(self):
    if self.visit_count == 0:
      return 0
    return self.value_sum / self.visit_count

The maximum number of moves (512 for chess and 722 for GO) you mention are used when creating training games to train the neural network. The current network is playing against itself and the goal is to create many useful training samples so the games are cut off if they take too long (lots of repetition in chess for example). Note that for chess the actual number of maximum moves is 5899 or an infinite number if draw is not mandatory.

Maybe you will find these illustrations regarding AlphaZero's MCTS search useful:

http://tim.hibal.org/blog/alpha-zero-how-and-why-it-works/