Как работает дерево поиска Монте-Карло?

1. Фаза выбора: MCTS итеративно выбирает дочерний узел с наивысшей оценкой текущего состояния. Если текущим состоянием является корневой узел, то откуда взялись эти дочерние элементы? Разве у вас не было бы дерева с одним корневым узлом для начала? Имея всего один корневой узел, вы сразу переходите к этапам расширения и моделирования?

Шаг выбора обычно реализуется, чтобы фактически не выбирать среди узлов, которые действительно существуют в дереве (были созданы на шаге расширения). Обычно реализуется выбор среди всех возможных состояний-преемников игрового состояния, соответствующего вашему текущему узлу.

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

2. Если MCTS выбирает дочерний узел с наивысшей оценкой на этапе выбора, вы никогда не исследуете другие дочерние элементы или, возможно, даже совершенно новые дочерние элементы, спускаясь по уровням дерева?

«Оценка», используемая на этапе «Выбор», обычно не должна быть просто средним значением всех результатов моделирования, проходящих через этот узел. Обычно это должна быть оценка, состоящая из двух частей; часть «исследования», которая высока для узлов, которые посещались относительно редко, и часть «эксплуатации», которая высока для узлов, которые до сих пор кажутся хорошими ходами (где многие симуляции, проходящие через этот узел, закончились выигрышем для игрока, которому разрешено выбирать ход). Это описано в разделе 3.4 документа, на который вы ссылаетесь. W(s, a) / N(s, a) — это часть эксплуатации (просто средний балл), а B(s, a) — часть исследования.

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

Шаг расширения обычно реализуется для простого добавления узла, соответствующего конечному состоянию игры, выбранному на шаге выбора (следуя тому, что я ответил на ваш первый вопрос, шаг выбора всегда заканчивается выбором одного игрового состояния, которое никогда не выбиралось ранее). .

4. На этапе моделирования используется стохастическая политика для выбора допустимых ходов для обоих игроков до окончания игры. Является ли эта стохастическая политика жестко запрограммированным поведением, и вы, по сути, бросаете кости в симуляции, чтобы выбрать один из возможных ходов, которые по очереди делаются каждым игроком до конца?

Самая простая (и, вероятно, самая распространенная) реализация — играть полностью случайным образом. Хотя это можно сделать и по-другому. Например, вы можете использовать эвристику, чтобы создать предвзятость к определенным действиям. Как правило, полностью случайное воспроизведение происходит быстрее, позволяя запускать больше симуляций за то же время обработки. Однако обычно это также означает, что каждая отдельная симуляция менее информативна, а это означает, что вам действительно нужно запускать больше симуляций, чтобы MCTS работал хорошо.

5. Насколько я понимаю, вы начинаете с одного корневого узла и, повторяя описанные выше фазы, строите дерево до определенной глубины. Затем вы выбираете ребенка с лучшим результатом на втором уровне в качестве следующего хода. Размер дерева, которое вы хотите построить, в основном является вашим жестким требованием к отзывчивости ИИ, верно? Так как пока дерево строится игра останавливается и вычисляет это дерево.

MCTS не одинаково исследует все части дерева на одинаковую глубину. Он имеет тенденцию исследовать части, которые кажутся интересными (сильные ходы), глубже, чем те, которые кажутся неинтересными (слабые ходы). Таким образом, обычно вы не используете ограничение глубины. Вместо этого можно использовать ограничение по времени (например, продолжать выполнять итерации до тех пор, пока не будет потрачена 1 секунда, или 5 секунд, или 1 минута, или любое разрешенное вами время обработки) или ограничение количества итераций (например, позвольте ему запустить 10K или 50K или любое количество симуляций, которое вам нравится).

По сути, метод Монте-Карло заключается в следующем: попробуйте случайным образом много раз (*), а затем сохраните ход, который в большинстве случаев приводил к наилучшему результату.

(*) : количество раз и глубина зависит от скорости принятия решения, которого вы хотите достичь.

Таким образом, корневой узел всегда является текущим состоянием игры, а ближайшие дочерние узлы являются вашими возможными ходами. Если вы можете сделать 2 хода (да/нет, влево/вправо,...), то у вас есть 2 подузла.

Если вы не можете сделать никаких ходов (это может случиться в зависимости от игры), то вам не нужно принимать никаких решений, тогда Монтек-Карло бесполезен для этого хода.

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

Затем (в игре для 2 игроков) на каждом уровне чередуются ваши ходы, ходы противника и так далее.

Способ обхода дерева должен быть случайным (равномерным).

Ваш ход 1 (случайный ход подуровня 1)

Его ход 4 (случайный ход подуровня 2)

Ваш ход 3 (случайный ход подуровня 3) -> выиграть yay

Выберите эталонную максимальную глубину и оцените, сколько раз вы выиграли или проиграли (или используйте функцию оценки, если игра не закончена после X глубины).

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

Это нужно для того, чтобы оценить, какой ход вы должны сделать сейчас. После этого противник ходит, и снова наступает ваша очередь. Таким образом, вы должны заново создать дерево с корневым узлом, являющимся новой текущей ситуацией, и повторить метод Монте-Карло, чтобы угадать, какой ваш лучший возможный ход. И так далее.