Поиск дерева Монте-Карло - обработка конечных узлов игры
Я реализовал MCTS для игры для 4 игроков, которая работает хорошо, но я не уверен, что понимаю расширение, когда ход окончания игры находится в реальном дереве, а не в развертывании.
В начале игры выигрышные / проигрышные позиции обнаруживаются только в свитке, и я понимаю, как их оценивать и распространять обратно на дерево. Но по ходу игры я в конечном итоге нахожу листовой узел, выбранный UCB1, который не может быть расширен, поскольку он является проигрышной позицией без возможного возможного хода, поэтому расширять нечего, и при этом нет игры для "разворачивания". На данный момент я просто оцениваю это как "победу" для последнего оставшегося игрока и получаю обратно выигрыш для них.
Однако, когда я смотрю на статистику посещений, этот узел повторно посещается тысячи раз, поэтому очевидно, что UCB1 "выбирает" посещение этого узла много раз, но на самом деле это пустая трата, если я буду распространять что-то, кроме одного выиграть для этих "всегда выигрышных" узлов?
У меня был хороший поиск в Google по этому вопросу, и я не могу найти много упоминаний об этом, поэтому я что-то неправильно понимаю или упускаю что-то очевидное, ни один из "стандартных" руководств / алгоритмов MCTS даже не упоминает конечные узлы игры в дереве в качестве особых случаев. Я волнуюсь, что неправильно понял что-то фундаментальное.
2 ответа
На данный момент я просто оцениваю это как "победу" для последнего оставшегося игрока и получаю обратно выигрыш для них.
Однако, когда я смотрю на статистику посещений, этот узел повторно посещается тысячи раз, поэтому очевидно, что UCB1 "выбирает" посещение этого узла много раз, но на самом деле это пустая трата, если я буду распространять что-то, кроме одного выиграть для этих "всегда выигрышных" узлов?
Нет, то, что вы сейчас делаете, правильно.
MCTS по существу оценивает значение узла как среднее из результатов всех путей, которые вы проходили через этот узел. В действительности нас обычно интересуют оценки в минимаксном стиле.
Чтобы средние оценки MCTS стали равными минимаксным оценкам в пределе (после бесконечного промежутка времени), мы полагаемся на фазу выбора (например, UCB1), чтобы отправить так много симуляций (= фазы выбора + фазы воспроизведения) вниз по пути (путям), который был бы оптимальным в соответствии с минимаксными оценками, что средние оценки также стремятся, в пределе, к минимаксным оценкам.
Предположим, например, что есть выигрышный узел непосредственно под корневым узлом. Это крайний пример вашей ситуации, когда терминальный узел уже достигнут на этапе выбора, и после этого воспроизведение не требуется. Минимаксная оценка корневого узла будет выигрышем, поскольку мы можем напрямую получить выигрыш за один шаг. Это означает, что мы хотим, чтобы средний балл MCTS также стал очень близок к выигрышной оценке для корневого узла. Это означает, что мы хотим, чтобы на этапе выбора подавляющее большинство симуляций сразу отправлялось в этот узел. Если, например, 99% всех симуляций сразу же отправляются на этот выигрышный узел из корневого узла, средняя оценка корневого узла также станет очень близкой к выигрышу, и это именно то, что нам нужно.
Этот ответ касается только реализации базового UCT (MCTS с UCB1 для выбора). Более сложные модификации этой базовой реализации MCTS, связанные с этим вопросом, см. В ответе manlio.
ни один из "стандартных" инструкций / алгоритмов MCTS даже не упоминает узлы окончания игры в дереве как особые случаи
Существуют варианты MCTS, способные доказать игровую теоретическую ценность позиции.
MCTS-Solver (вполне) хорошо известен: для этого варианта модифицированы этапы обратного распространения и выбора, а также процедура выбора финального хода для игры.
Терминальные позиции выигрыша и проигрыша, встречающиеся в дереве, обрабатываются по-разному, и при резервном копировании таких проверенных значений вверх по дереву принимается специальное условие.
Вы можете взглянуть на:
Поиск по дереву Монте-Карло Марком Х.М. Винандсом, Ингви Бьёрнссоном, Ян Такеши Сайто (часть серии лекций по компьютерным наукам, том 5131)
для деталей.
так что я волнуюсь, я неправильно понял что-то фундаментальное.
Хотя в долгосрочной перспективе MCTS, оснащенная формулой UCT, может сходиться к теоретическому значению игры, базовый MCTS не может доказать теоретическое значение игры.