AlphaGo Zero
AlphaGo Zero uses a Monte-Carlo Tree Search where the selection phase is governed by $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, where:
- the exploitation parameter is $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (i.e. the mean of the values $v_i$ of all simulations that passes through edge $(s_t, a)$)
- the exploration parameter is $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (i.e. the prior probability $P(s_t, a)$, weighted by the constant $c_{puct}$, the number of simulations that passes through $(s_t, a)$, as well as the number of simulations that passes through $s_t$).
The prior probability $P(s_t, a)$ and simulation value $v_i$ are both outputted by the deep neural network $f_{\theta}(s_t)$:
This neural network takes as an input the raw board representation s of the position and its history, and outputs both move probabilities and a value, (p, v) = fθ(s). The vector of move probabilities p represents the probability of selecting each move a (including pass), pa = Pr(a| s). The value v is a scalar evaluation, estimating the probability of the current player winning from position s.
My confusion
My confusion is that $P(s_t, a)$ and $v_i$ are probabilities normalized to different distributions, resulting in $v_i$ being about 80x larger than $P(s_t,a)$ on average.
The neural network outputs $(p, v)$, where $p$ is a probability vector given $s_t$, normalized over all possible actions in that turn. $p_a = P(s_t, a)$ is the probability of choosing action $a$ given state $s_t$. A game of Go has about 250 moves per turn, so on average each move has probability $\frac{1}{250}$, i.e. $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$
On the other hand, $v$ is the probability of winning given state $s_t$, normalized over all possible end-game conditions (win/tie/lose). For simplicity sake, let us assume $\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, where the game is played randomly and each outcome is equally likely.
This means that the expected value of $v_i$ is at least 80x larger than the expected value of $P(s_t, a)$. The consequence of this is that $Q(s_t, a)$ is at least 80x larger than $U(s_t, a)$ on average.
If the above is true, then the selection stage will be dominated by the $Q(s_t, a)$ term, so AlphaGo Zero should tend to avoid edges with no simulations in them (edges where $Q(s_t, a) = 0$) unless all existing $Q(s_t, a)$ terms are extremely small ($< \frac{1}{250}$), or the MCTS has so much simulations in them that the $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ term in $U(s_t, a)$ evens out the magnitudes of the two terms. The latter is not likely to happen since I believe AlphaGo Zero only uses $1,600$ simluations per move, so $\sqrt{\sum_b N(s_t, b)}$ caps out at $40$.
Selecting only viable moves
Ideally, MCTS shouldn't select every possible move to explore. It should only select viable moves given state $s_t$, and ignore all the bad moves. Let $m_t$ is the number of viable moves for state $s_t$, and let $P(s_t, a)$ = 0 for all moves $a$ that are not viable. Also, let's assume the MCTS never selects a move that is not viable.
Then the previous section is partly alleviated, because now $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. As a result, $Q(s_T, a)$ should only be $\frac{m_t}{3}$ times larger than $U(s_t, a)$ on average. Assuming $m_t \le 6$, then there shouldn't be too much of an issue
However, this means that AlphaGo Zero works ideally only when the number of viable moves is small. In a game state $s_t$ where there are many viable moves ($>30$) (e.g. a difficult turn with many possible choices), the selection phase of the MCTS will deteriorate as described in the previous section.
Questions
I guess my questions are:
- Is my understanding correct, or have I made mistake(s) somewhere?
- Does $Q(s_t, a)$ usually dominate $U(s_t, a)$ by this much in practice when the game state has many viable moves? Is the selection phase usually dominated by $Q(s_t, a)$ during these game states?
- Does the fact that $Q(s_t, a)$ and $U(s_t, a)$ being in such different orders of magnitude (when the game state has many viable moves) affect the quality of the MCTS algorithm, or is MCTS robust to this effect and still produces high quality policies?
- How common is it for a game state to have many viable moves (>30) in Go?
