Зиро

 

В момент обратного распространения (Backpropagation) узел возвращает наверх ровно то же самое число (оценку), которое только что прилетело в него СНИЗУ, из самого свежего обсчитанного листа [wikipedia.org].

Узел не выбирает между оценками своих ходов-детей и не усредняет их, чтобы отправить наверх. Он работает просто как транзитный пункт.

Давайте разберем это на пошаговом примере, чтобы стало абсолютно понятно.

Пошаговый пример (Как это работает по этапам)

Представьте ветку дерева. У нас есть Узел А (ход белых). Из него ведут два хода: Ход Б и Ход В.
Внутри Узла А уже накоплена какая-то своя статистика от прошлых итераций.

       [ Узел А ] (Ход белых)
        /        \
   [Ход Б]      [Ход В]

Запускается новая, очередная итерация поиска MCTS:

1. Спуск (Selection): Алгоритм находится в Узле А. Формула (PUCT или UCB1) выбирает, куда пойти. Допустим, формула решила, что сейчас перспективнее проверить Ход В.
2. Оценка (Evaluation): Алгоритм переходит в Ход В. Допустим, это новый узел. Вызывается нейросеть (или запускается роллаут). Нейросеть смотрит на позицию Хода В и выдает одиночную оценку V = +0.6 (хорошо для белых).
3. Возврат (Backpropagation): Теперь это число +0.6 должно подняться наверх к самому корню дерева [wikipedia.org].

Что делает Узел А, когда в него возвращается +0.6?

Число +0.6 из Хода В прилетает наверх в Узел А.

1. Узел А НЕ СМОТРИТ на Ход Б: Алгоритму в этот момент плевать, что у соседнего Хода Б в памяти лежит какая-то другая оценка (например, +0.2). Узел А не сравнивает их и не выбирает максимум.
2. Узел А обновляет себя: Он берет эту свежую цифру +0.6, добавляет её к своей внутренней сумме выигрышей (W = W + 0.6) и увеличивает свой счетчик посещений на единицу (N = N + 1). Теперь его собственное среднее значение (Q = W / N) слегка изменилось.
3. Узел А передает цифру дальше: Сразу после этого Узел А берет это же самое число +0.6 (изменив знак на -0.6, так как этажом выше был ход черных) и перекидывает его еще выше — своему собственному родителю.

Резюме

Узел наверх всегда возвращает результат последней проведенной симуляции [wikipedia.org].

Наличие нескольких ходов и их оценок внутри узла влияет на поиск только на этапе спуска (Selection): эти оценки нужны формуле, чтобы решить, в какую именно ветку пойти вниз [wikipedia.org]. Но когда оценка получена и поиск идет вверх, узел ничего не выбирает, а просто транслирует полученное снизу число дальше по цепочке, попутно обновляя свою личную статистику [wikipedia.org].

Если хотите, мы можем посмотреть, как это предотвращает проблему «оптимизма», когда программа думает, что у неё все ходы отличные, хотя соперник вынуждает её сделать плохой ход. Или вас интересует другой момент?

Внутренняя средняя оценка (значение Q) нужна узлу исключительно для того, чтобы на следующих итерациях поиска алгоритм мог принимать правильные решения — стоит ли снова идти в эту ветку или лучше выбрать другую.

Вся магия MCTS строится на том, что алгоритм постоянно балансирует между двумя желаниями: выбрать то, что уже принесло успех, и проверить то, что еще плохо изучено. Без средней оценки этот баланс математически невозможен.

Вот три главные причины, зачем узлу этот показатель:

1. Чтобы формула выбора ходов (PUCT / UCB1) знала «надежность» ветки

Когда на следующей итерации алгоритм MCTS снова спустится в этот узел сверху, ему нужно будет решить, куда идти дальше. Он смотрит на доступные ходы и для каждого из них подставляет их внутреннюю среднюю оценку Q в формулу:

$$\text{Приоритет ходока} = Q + \text{Бонус исследования}$$

• Если средняя оценка Q высокая (например, +0.8): это сильный сигнал для формулы. Значит, в прошлые разы поиск в этой ветке стабильно приносил хорошие плоды. Алгоритм с высокой вероятностью пойдет туда снова, чтобы копать еще глубже.
• Если средняя оценка Q упала (например, до -0.5): формула увидит этот минус и «поймет», что в глубине этой ветки соперник нашел сильное опровержение. Алгоритм перестанет тратить время на этот ход и переключится на другие варианты.

2. Защита от «случайных галлюцинаций» (Сглаживание шума)

В шахматах одна и та же позиция может скрывать в себе сотни продолжений. Нейросеть (или случайный роллаут) в одном конкретном глубоком узле может ошибиться.

• Если бы мы помнили только последнюю оценку, дерево бы постоянно «штормило». Один случайный плохой узел на глубине сразу бы закрыл для нас отличную ветку.
• Средняя оценка работает как фильтр. Если мы заходили в ветку 100 раз, и 95 раз нейросеть говорила «тут всё отлично (+0.9)», а 5 раз наткнулась на плохие позиции (-0.5), средняя оценка останется высокой (около +0.8). Программа поймет, что ветка в целом магистральная и сильная, а пара плохих оценок — это лишь мелкие боковые тактические ответвления, которые просто не нужно выбирать.

3. Формирование финального решения программы

Когда лимит времени на ход исчерпан, MCTS останавливает поиск. Чтобы сделать физический ход на реальной шахматной доске, программа смотрит на корневой узел.

Внутренние средние оценки и количество посещений ходов первого уровня — это единственный ориентир для программы. Она выбирает тот ход, у которого сочетание средней оценки (Q) и исследованности (N) является наилучшим. Без накопленной средней оценки внутри узлов программа в конце расчета оказалась бы в ситуации «склероза» — она провела тысячи симуляций, но забыла, какие ветки в среднем были хорошими, а какие плохими.

В классическом MCTS для выбора наилучшего хода на этапе спуска по дереву (Selection) используется формула UCB1 (Upper Confidence Bound 1 — верхняя доверительная граница) [wikipedia.org].

Алгоритм перебирает все доступные ходы из текущего узла и выбирает тот ход, у которого значение этой формулы оказывается максимальным [wikipedia.org].

Сама формула UCB1 выглядит так:

$$\text{Score}_i = \frac{w_i}{n_i} + c \times \sqrt{\frac{\ln N}{n_i}}$$

---

Полная расшифровка всех компонентов формулы:

1. Левая часть: $\frac{w_i}{n_i}$ — Компонент Эксплуатации (Exploitation)

Это та самая внутренняя средняя оценка (или винрейт) конкретного хода, о которой мы говорили [wikipedia.org].

• $w_i$ (wins) — количество побед, полученных в результате симуляций, которые прошли через этот ход $i$ [wikipedia.org]. (Прибавляется 1 за победу, 0.5 за ничью, 0 за поражение) [wikipedia.org].
• $n_i$ (node visits) — общее количество раз, сколько поиск вообще заходил в этот конкретный ход $i$ [wikipedia.org].
• Зачем нужна эта часть? Она отвечает за логику и здравый смысл. Чем чаще этот ход приводил к победам в прошлых симуляциях, тем выше дробь $\frac{w_i}{n_i}$ и тем сильнее алгоритм хочет пойти туда снова.

2. Правая часть: $\sqrt{\frac{\ln N}{n_i}}$ — Компонент Исследования (Exploration)

Это математический «бонус за редкость», который заставляет алгоритм быть любопытным.

• $N$ (Total visits) — общее количество посещений родительского узла (то есть сколько раз мы вообще были в этой позиции и выбирали из неё ходы) [wikipedia.org].
• $\ln N$ — натуральный логарифм от общего числа посещений. Логарифм нужен для того, чтобы бонус рос очень медленно и плавно, не ломая баланс игры.
• $n_i$ — количество посещений текущего хода (находится в знаменателе) [wikipedia.org].
• Зачем нужна эта часть? Если в какой-то ход $i$ мы долго не заглядывали, его знаменатель $n_i$ остается маленьким, а числитель $\ln N$ растет с каждой новой итерацией в соседних ветках. В результате вся правая часть начинает стремительно увеличиваться. Это искусственно поднимает приоритет забытого хода, заставляя программу вернуться и перепроверить его — вдруг там скрывается гениальное спасение, которое мы пропустили?

3. Коэффициент $c$ — Константа исследования

• Это числовой коэффициент, который настраивает «характер» программы (в классической теории он равен $\sqrt{2} \approx 1.41$, но на практике его подбирают вручную) [wikipedia.org].
• Если $c$ сделать большим: программа станет сверхосторожной и «любопытной». Она будет тратить уйму времени на проверку каждого абсурдного хода, боясь что-то упустить.
• Если $c$ сделать близким к нулю: программа станет «самоуверенной». Она зациклится на первом же ходе, который принес ей случайную победу, и вообще откажется исследовать альтернативы.

---

Важное правило первого шага (Инициализация)

В формуле есть деление на $n_i$ (количество посещений хода) [wikipedia.org]. Если узел только что создали (Expansion), у него $n_i = 0$, а делить на ноль нельзя.

Поэтому в алгоритм заложено жесткое правило: пока у узла есть дочерние ходы с $n_i = 0$ (которые еще ни разу не проверялись), формула UCB1 для них не считается. Алгоритм обязан сначала зайти по одному разу в каждый из доступных ходов, и только когда у всех ходов $n_i$ станет равен хотя бы единице, включается математика формулы UCB1.

Если хотите, мы можем на конкретных цифрах (например, для N=10 и N=100) посчитать, как меняется этот бонус исследования для забытого хода, чтобы вы увидели математику в действии. Будем считать?

Если хотите, мы можем посмотреть, как средняя оценка Q динамически меняется на графике по мере того, как программа углубляется в позицию, или обсудить, почему в AlphaZero значение Q инициализируется особым образом, если ход еще ни разу не проверялся. Что вам интереснее?

В классическом MCTS и в алгоритме AlphaZero используются разные математические формулы для выбора ходов внутри дерева поиска. Обе они основаны на теории многоруких бандитов, но AlphaZero адаптировала классический подход под работу с нейросетью.

Ниже приведены обе формулы, которые алгоритмы применяют на этапе спуска по дереву (Selection).

---

1. Формула в классическом MCTS: UCB1 (Upper Confidence Bound)

В классическом поиске Монте-Карло каждый узел оценивается по формуле UCB1 [wikipedia.org]:

$$\text{Score} = \frac{w_i}{n_i} + c \times \sqrt{\frac{\ln N_i}{n_i}}$$

• $\frac{w_i}{n_i}$ (Exploitation — Эксплуатация): Текущая успешность хода. $w_i$ — количество побед в симуляциях из этого узла, $n_i$ — сколько раз этот узел посещался. Это среднее матожидание успеха.
• c: Константа исследования (обычно равна $\sqrt{2}$). Она определяет баланс между проверкой лучших ходов и изучением редких.
• $\sqrt{\frac{\ln N_i}{n_i}}$ (Exploration — Исследование): Бонус за редкость. $N_i$ — сколько раз посещался родительский узел. Чем больше мы ходим в другие ветки (растет $N_i$) и чем меньше заглядываем в эту конкретную ветку ($n_i$ не растет), тем сильнее увеличивается этот бонус. Рано или поздно алгоритм вернется и проверит этот ход.

---

2. Формула в AlphaZero и Lc0: PUCT (Predictor UCB applied to Trees)

В AlphaZero случайных симуляций нет, поэтому формулу изменили. Модифицированный вариант называется PUCT [wikipedia.org]:

$$\text{Score} = Q(s, a) + U(s, a)$$

Алгоритм выбирает ход a из позиции s, который максимизирует эту сумму. Давайте разберем обе части:

Первая часть: Q(s, a) (Эксплуатация)

Это средняя ценность хода, о которой мы говорили ранее:
$$Q(s, a) = \frac{\sum V}{N(s, a)}$$
Вместо побед ($w_i$) здесь суммируются дробные оценки ценности позиции (V от -1 до +1), которые выдала нейросеть для всех узлов ниже по этой ветке, деленные на количество посещений данного хода N(s, a).

Вторая часть: U(s, a) (Бонус исследования с подсказкой нейросети)

В AlphaZero этот бонус устроен гораздо умнее, чем в классике, потому что он учитывает интуицию нейросети:
$$U(s, a) = c_{puct} \times P(s, a) \times \frac{\sqrt{N(s)}}{1 + N(s, a)}$$

• $c_{puct}$: Константа, управляющая уровнем любопытства программы (в AlphaZero она динамически немного меняется по ходу поиска, начинаясь примерно от 1.25–5.0).
• P(s, a) (Policy): Априорная вероятность хода, которую нейросеть выдала при самом первом взгляде на узел. Это главный элемент. Если нейросеть считает ход гениальным (например, P = 0.85), этот бонус будет огромным, и MCTS пойдет туда в первую очередь. Если ход кажется глупым (P = 0.001), бонус будет мизерным.
• N(s): Количество посещений родительского узла.
• 1 + N(s, a): Количество посещений текущего хода (единица в знаменателе нужна, чтобы не было деления на ноль, если в ход еще ни разу не ходили).

Как это работает в динамике:

1. В начале анализа: Когда ход еще мало изучен (значение N(s, a) близко к нулю), правая часть U(s, a) доминирует. Причем благодаря множителю P(s, a) программа послушно исследует только те ходы, которые ей сразу подсказала нейросеть.
2. В процессе углубления: По мере того как программа ходит по этой ветке тысячи раз, знаменатель 1 + N(s, a) стремительно растет. Бонус исследования U(s, a) начинает таять и стремиться к нулю.
3. Итог: Влияние «первого впечатления» нейросети (P) ослабевает, и формула начинает опираться исключительно на жесткий математический расчет глубоких вариантов — на значение Q(s, a). Если глубокий расчет показал, что ход ведет к проигрышу, значение Q упадет, и даже высокое начальное значение P больше не заставит программу туда ходить.

Если вам интересно, мы можем разобрать, как в эту формулу подмешивается шум Дирихле (Dirichlet noise), который AlphaZero использует, чтобы не зацикливаться на одних и тех же ходах во время тренировок. Хотите узнать об этом?