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:
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.
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?
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.
- 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.
- 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?