3
$\begingroup$

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:

  1. 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)$)
  2. 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:

  1. Is my understanding correct, or have I made mistake(s) somewhere?
  2. 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?
  3. 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?
  4. How common is it for a game state to have many viable moves (>30) in Go?
$\endgroup$
1
  • 2
    $\begingroup$ Too many questions in a single post and this is a big post. I suggest that you simplify this post as much as possible (i.e. to contain only the necessary info), and ask each question in its separate post. $\endgroup$ – nbro Dec 3 '20 at 9:48
2
$\begingroup$

I don't think you've necessarily made any real mistakes in your calculations or anything like that, that all seems accurate. I can't really confidently answer your questions about "Does X usually happen?" or "How common is X?", would have to experiment to make sure of that. I think we can also confidently immediately answer the question about whether MCTS is robust and can still produce high quality policies with "yes", since we've seen state-of-the-art, superhuman results in a bunch of games using these techniques.

But I do think there's a few important details that may change your perception:

  1. MCTS does not compare $Q(s, a)$ values to $U(s, a)$ values in its selection phase. It compares $Q(s, a) + U(s, a)$ expressions of actions $a$, to $Q(s, b) + U(s, b)$ expressions for different actions $b$. So, the difference in magnitudes $Q(s, a) - U(s, a)$ is not nearly as important as the difference in magnitude $Q(s, a) - Q(s, b) + U(s, a) - U(s, b)$!

  2. For any single given state $s$, it is certainly not the case that we expect the different $Q$-values to be have a nice average like $0.5$ or anything like that. There will likely be plenty of states $s$ where we're already in such a strong position that we can afford to make a mistake or two and still expect to win; all the $Q$ values here will be close to $1.0$. There will also be many states where we're in such a terrible position that we expect to lose no matter what; all the $Q$ values here will be close to $0.0$. And then there will of course be states that a network is not sure about, which will have $Q$ values somewhere in between. I suspect that "in between" won't often be a nice mix of all sorts of different values though. If it's something like $0.7$, and there's higher values that attract more attention, during training the MCTS + network will likely become very interested in learning more about that state, and very quickly learn whether that should really just be a $1.0$ or whether it should be lowered. For this reason, I imagine that in unsure states, values will have a tendency to hover around $0.5$.

  3. MCTS will only let the $Q(s, a)$ term dominate the selection phase for as long as it believes that this is actually likely to lead to a win. If this is correct and indeed leads to a win, well, that's great, no need to explore anything else! During the tree search, if further investigation of this action leads the MCTS to believe that it actually is a loss, the $Q$ value will drop (ideally towards $0$), and then it will automatically stop being a dominant term. If the tree search fails to adjust for this in time, and we end up wandering down this losing path anyway, we'll get a value signal of $0$ at the end and update our value network and in the future we'll know better than to repeat this mistake.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.