Внедрение UCT в Монте-Карло - PullRequest
Новая
       54

Внедрение UCT в Монте-Карло

20 голосов
/ 30 января 2012

Можете ли вы объяснить мне, как построить дерево?

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

Может кто-нибудь указать мне на хорошо прокомментированную реализацию алгоритма (мне нужно использовать его дляAI)?Или лучше объяснение / примеры этого?

Я не нашел много ресурсов в сети, этот алгоритм довольно новый ...

Ответы [ 3 ]

24 голосов
/ 30 января 2012

Лучший способ создать дерево - это серия случайных игр. Хитрость заключается в том, чтобы балансировать между разведкой и эксплуатацией (вот где приходит UCT). Здесь есть несколько хороших примеров кода и множество ссылок на научные статьи: https://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html

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

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

Например: первый ход игрока 1 может имитировать 10 ходов в будущем, чередуя ходы игрока 1 и игрока 2. Каждый раз вы должны предполагать, что противоборствующий игрок будет пытаться минимизировать ваш счет, в то же время максимизируя свой собственный счет. Существует целое поле, основанное на этой теории игр. Как только вы симулируете до конца 10 игр, вы снова выполняете итерацию с начальной точки (потому что нет смысла симулировать только один набор решений). Каждая из этих ветвей дерева должна оцениваться там, где счет распространяется по дереву, и счет представляет наилучшую возможную отдачу для игрока, выполняющего симуляцию, при условии, что другой игрок также выбирает для себя лучшие ходы.

MCTS состоит из четырех стратегических шагов, повторяемых до тех пор, пока остается время. Шаги следующие.

  1. На шаге выбора дерево перемещается из корневой узел, пока мы не достигнем узла E, где мы выбираем позицию, которая еще не добавлена ​​в дерево.

  2. Далее, во время шага разыгрыша ходы разыгрываются в режиме самовоспроизведения, пока не будет достигнут конец игры. Результат R этой «симулированной» игры равен +1 в случае победы черных (первый игрок в LOA), 0 в случае ничьей и -1 в случае победы белых.

  3. Впоследствии, на этапе расширения, дочерние элементы E добавляются в дерево.

  4. Наконец, R распространяется обратно по пути от E до корневого узла на этапе обратного распространения. Когда время истекло, ход, выполняемый программой, является дочерним элементом корня с наибольшим значением. (Этот пример взят из этой статьи - PDF

www.ru.is / факультет / Ингви / PDF / WinandsBS08.pdf

Вот несколько реализаций:

Список библиотек и игр, использующих некоторые реализации MCTS http://senseis.xmp.net/?MonteCarloTreeSearch

и независимая от игры UCT MCTS библиотека с открытым исходным кодом под названием Fuego http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html

3 голосов
/ 02 марта 2015

Я написал это, если вы заинтересованы: https://github.com/avianey/mcts4j

3 голосов
/ 05 апреля 2014

С http://mcts.ai/code/index.html:

Below are links to some basic MCTS implementations in various
programming languages. The listings are shown with timing, testing
and debugging code removed for readability.

Java

Python

...