How does the AlphaGo Zero policy decide what move to execute?

Question

I was going through the AlphaGo Zero paper and I was trying to understand everything, but I just can't figure out this one formula:

$$ \pi(a \mid s_0) = \frac{N(s_0, a)^{\frac{1}{\tau}}}{\sum_b N(s_0, b)^{\frac{1}{\tau}}} $$

Could someone decode how the policy makes decisions following this formula? I pretty much understood all of the other parts of the paper, and also the temperature parameter is clear to me.

It might be a simple question, but can't figure it out.

Answer 1

The formula in question uses a function N(state, action) that defines a visit count of a state-action pair (introduced on page 3). To describe how it is used, lets first describe the steps of AlphaGo Zero as a whole.

There are 4 "phases" to the Monte-Carlo tree search in AlphaGo Zero as depicted in Figure 2. The first 3 expand and update the tree and together are the "search" in Monte-Carlo tree "search" in AlphaGo Zero.

1. Select an edge (action) in the tree with maximum action-value Q (plus upper confidence bound U)

2. Expand and evaluate the leaf node using the network

3. Backup Action-values Q are updated to track the evaluations of the Value in the subtree.

4. Play - After the "search" is complete, the search probabilities are returned proportional to the visitation count of the nodes of the tree.*

* This is where the formula in question comes into play (pun intended). During the "search", nodes that looked good were expanded on and thus their visitation counts were updated. So the formula is essentially describing this logic:

Good nodes have higher counts, so choose the nodes with higher counts often

But what if there is a really good node but it hasn't been visited a lot so its not chosen?

This is where the temperature parameter comes in:

• If the temperature is 1, this selects moves proportionally to their visit counts.
• If the temperature is 0 (not actually but rather in infinitesimal that approaches 0), and with some added noise, it "ensures that all moves may be tried, but the search may still overrule bad moves."

So altogether, the formula is saying : Pick good things most of the time

The mathematical evaluation of the formula is described below:

AlphaGo Zero defines the probability of each action (aka the policy) by that formula. If there are 3 nodes, A, B and C, and they have each been visited 10, 70, and 20 times (100 times in total), respectively, then the probability of taking those actions is:

• P(A) = 10/100 = .10
• P(B) = 70/100 = .7
• P(C) = 20/100 = .2

Answer 2

Intuitively:

1. Larger Q means larger probability that the node (s'|s,a) would be chosen. When we selected most visited node, we selected a node with good Q.
2. More visited count means more accurate estimation. And the chosen node proved itself as a good choice even after more trials than other nodes.
3. Less computation in some cases (integer/long vs float/double)