AlphaGo Zero: делает $Q(s_t, a)$ доминировать $U(s_t, a)$ в сложных игровых состояниях?

Dec 03 2020

AlphaGo Zero

AlphaGo Zero использует поиск по дереву Монте-Карло, где этап выбора регулируется $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, где:

параметр эксплуатации $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (т.е. среднее значение $v_i$ всех симуляций, проходящих через край $(s_t, a)$)
параметр исследования $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (т.е. априорная вероятность $P(s_t, a)$, взвешенный на константу $c_{puct}$, количество симуляций, которое проходит через $(s_t, a)$, а также количество симуляций, которые проходят через $s_t$).

Априорная вероятность $P(s_t, a)$ и значение моделирования $v_i$ оба выводятся глубокой нейронной сетью $f_{\theta}(s_t)$:

Эта нейронная сеть принимает в качестве входных данных необработанное представление s позиции и ее истории на доске и выводит как вероятности хода, так и значение (p, v) = fθ (s). Вектор вероятностей ходов p представляет собой вероятность выбора каждого хода a (включая проход), pa = Pr (a | s). Значение v представляет собой скалярную оценку, оценивающую вероятность того, что текущий игрок выиграет из позиции s.

Мое замешательство

Мое замешательство в том, что $P(s_t, a)$ а также $v_i$ - вероятности, нормированные на разные распределения, в результате чего $v_i$ будучи примерно в 80 раз больше, чем $P(s_t,a)$ в среднем.

Выходы нейронной сети $(p, v)$, где $p$ является вектором вероятности, заданным $s_t$, нормализованная по всем возможным действиям в этом ходу. $p_a = P(s_t, a)$ вероятность выбора действия $a$ данное состояние $s_t$. В игре Го около 250 ходов за ход, поэтому в среднем каждый ход имеет вероятность.$\frac{1}{250}$, т.е. $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

С другой стороны, $v$ вероятность выигрыша в данном состоянии $s_t$, нормализованные по всем возможным условиям конечной игры (победа / ничья / поражение). Для простоты предположим, что$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, где игра ведется случайным образом и каждый исход одинаково вероятен.

Это означает, что ожидаемое значение $v_i$ как минимум в 80 раз больше ожидаемого значения $P(s_t, a)$. Следствием этого является то, что$Q(s_t, a)$ как минимум в 80 раз больше, чем $U(s_t, a)$ в среднем.

Если вышесказанное верно, то на этапе отбора преобладают $Q(s_t, a)$ термин, поэтому AlphaGo Zero должен стараться избегать краев без моделирования (края, где $Q(s_t, a) = 0$) если все существующие $Q(s_t, a)$ сроки крайне малы ($< \frac{1}{250}$), или в MCTS так много симуляций, что $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ срок в $U(s_t, a)$выравнивает величины двух членов. Последнее вряд ли произойдет, поскольку я считаю, что AlphaGo Zero использует только$1,600$ моделирования на ход, так что $\sqrt{\sum_b N(s_t, b)}$ кепки на $40$.

Выбор только жизнеспособных ходов

В идеале MCTS не должен выбирать для изучения все возможные ходы. Он должен выбирать только жизнеспособные ходы в данном состоянии.$s_t$и игнорируйте все плохие ходы. Позволять$m_t$ количество жизнеспособных ходов для государства $s_t$, и разреши $P(s_t, a)$ = 0 для всех ходов $a$которые нежизнеспособны. Также предположим, что MCTS никогда не выбирает нежизнеспособный ход.

Тогда предыдущий раздел частично смягчен, потому что теперь $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. Как результат,$Q(s_T, a)$ должно быть только $\frac{m_t}{3}$ раз больше, чем $U(s_t, a)$в среднем . Предполагая$m_t \le 6$, тогда особых проблем быть не должно.

Однако это означает, что AlphaGo Zero идеально работает только тогда, когда количество жизнеспособных ходов невелико. В игровом состоянии$s_t$ где есть много жизнеспособных ходов ($>30$) (например, сложный поворот с множеством возможных вариантов выбора), фаза выбора MCTS ухудшится, как описано в предыдущем разделе.

Вопросов

Думаю, мои вопросы:

Я правильно понимаю, или я где-то допустил ошибку (и)?
Делает $Q(s_t, a)$ обычно доминируют $U(s_t, a)$так много на практике, когда в игровом состоянии много жизнеспособных ходов? На этапе отбора обычно преобладают$Q(s_t, a)$ во время этих игровых состояний?
Есть ли тот факт, что $Q(s_t, a)$ а также $U(s_t, a)$ нахождение в таких разных порядках величины (когда состояние игры имеет много жизнеспособных ходов) влияет на качество алгоритма MCTS, или MCTS устойчив к этому эффекту и по-прежнему производит политики высокого качества?
Насколько часто в игровом состоянии много жизнеспособных ходов (> 30) в го?

Ответы

2 DennisSoemers Dec 05 2020 at 03:08

Я не думаю, что вы обязательно сделали какие-то реальные ошибки в своих расчетах или что-то в этом роде, все кажется точным. Я не могу с уверенностью ответить на ваши вопросы о том, "А бывает ли Х обычно?" или «Насколько распространен X?», пришлось бы поэкспериментировать, чтобы убедиться в этом. Я думаю, что мы также можем с уверенностью сразу же ответить на вопрос о том, является ли MCTS надежным и может ли он по-прежнему создавать политики высокого качества с положительным ответом, поскольку мы видели самые современные, сверхчеловеческие результаты во множестве игр, использующих эти методы. .

Но я думаю, что есть несколько важных деталей, которые могут изменить ваше восприятие: