Поиск дерева Монте-Карло - обработка конечных узлов игры

Question

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

ВВ начале игры выигрышные / проигрышные позиции можно найти только в свитке, и я понимаю, как их оценивать и распространять обратно в дерево.Но по ходу игры я в конечном итоге нахожу листовой узел, выбранный UCB1, который не может быть расширен, поскольку он является проигрышной позицией без возможного возможного хода, поэтому расширять нечего, и при этом нет игры для «разворачивания».На данный момент я просто оцениваю это как «выигрыш» для последнего оставшегося игрока и получаю обратно выигрыш для него.

Однако когда я смотрю на статистику посещений, этот узел повторно посещается тысячи раз, так что, очевидно, UCB1 'выбирает «посещать этот узел много раз, но на самом деле это пустая трата времени, должен ли я распространять что-то, кроме однократного выигрыша для этих« всегда выигрышных »узлов?»

У меня былхороший поиск в Google для этого и не могу найти много упоминаний об этом, поэтому я что-то неправильно понимаю или упускаю что-то очевидное, ни один из «стандартных» учебников / алгоритмов MCTS даже не упоминает конечные узлы игры в дереве как особые случаи, так что ябеспокоюсь, что я неправильно понял что-то фундаментальное.

Answer 1

ни один из «стандартных» учебных пособий / алгоритмов MCTS даже не упоминает конечные узлы игры в дереве как особые случаи

Существуют варианты MCTS, способные доказать теоретическую ценность позиции в игре.

MCTS-Solver (вполне) хорошо известен: для этого варианта модифицированы этапы обратного распространения и выбора, а также процедура выбора финального хода для игры.

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

Вы можете взглянуть на:

Дерево Монте-КарлоИщите Solver Марка Х.М. Винанда, Ингви Бьёрнссона, Яна Такеши Сайто (часть серии лекций по компьютерным наукам, том 5131)

для подробностей.

, поэтому яЯ беспокоюсь, что неправильно понял нечто фундаментальное.

Хотя в долгосрочной перспективе MCTS, оснащенная формулой UCT, может сходиться с игройТеоретическая ценность, базовая MCTS не может доказать теоретическую ценность игры.

Answer 2

В данный момент я просто оцениваю это как «выигрыш» для последнего оставшегося игрока и получаю обратно выигрыш для него.

Однако, когда я смотрю на статистику посещений, этот узел возвращается к тысячамвремя, поэтому очевидно, что UCB1 «выбирает» посещение этого узла много раз, но на самом деле это пустая трата, стоит ли мне распространять что-то иное, кроме однократной победы для этих «всегда выигрышных» узлов?

Нет, то, что вы в настоящее время уже делаете, правильно.

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

Чтобы средние оценки MCTS стали равными минимаксным оценкам в пределе (после бесконечного промежутка времени), мы полагаемся на фазу выбора (например, UCB1) для отправки стольких симуляций(= Фазы выбора + воспроизведения) вниз по пути (путям), который был бы оптимальным в соответствии с минимаксными оценками, что средние оценки также в пределе стремятся к минимаксным оценкам.

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

---

Этот ответ касается только реализации базового UCT (MCTS с UCB1 для выбора).Более сложные модификации этой базовой реализации MCTS, связанные с этим вопросом, см. В ответе manlio