Можете ли вы объяснить мне, как построить дерево?
Я понял, как выбираются узлы, но лучшее объяснение действительно поможет мне реализовать этот алгоритм. У меня уже есть доска, представляющая состояние игры, но я не знаю (понимаю), как сгенерировать дерево.
Может ли кто-то указать мне на хорошо реализованную реализацию алгоритма (мне нужно использовать его для ИИ)? Или лучшее объяснение/примеры этого?
Я не нашел много ресурсов в сети, этот алгоритм довольно новый...
Лучший способ генерировать дерево - это серия случайных воспроизведения. Хитрость заключается в том, чтобы балансировать между разведкой и эксплуатацией (вот где идет UCT). Есть несколько хороших примеров кода и множество ссылок на научные статьи здесь: https://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html
Когда я реализовал алгоритм, я использовал случайные воспроизведения до тех пор, пока не ударил конечную точку или состояние завершения. У меня была функция статической оценки, которая вычисляла бы выигрыш в этой точке, тогда оценка с этой точки распространяется на дерево. Каждый игрок или "команда" предполагает, что другая команда будет играть лучший ход для себя, а худший вариант для противника.
Я также рекомендовал бы проверить документы Часлота и его докторскую диссертацию, а также некоторые исследования, которые ссылаются на его работу (в основном все MCTS работают с тех пор).
Например: Первый игрок 1-го уровня может имитировать 10 ходов в будущем, чередуя между ходом игрока 1 и движением игрока 2. Каждый раз, когда вы должны предположить, что противник попытается свести к минимуму ваш балл, максимизируя свой собственный счет. Существует целая область, основанная на этом, известном как Теория игр. Как только вы имитируете до конца 10 игр, вы снова инете начинаете с начала (потому что нет смысла только имитировать один набор решений). Каждая из этих ветвей дерева должна быть забита, где оценка размножается по дереву, а оценка представляет собой наилучшую возможную выгоду для игрока, выполняющего симуляцию, предполагая, что другой игрок также выбирает лучшие ходы для себя.
MCTS состоит из четырех стратегических шагов, повторяющихся до тех пор, пока осталось время. Эти шаги заключаются в следующем.
На этапе выбора дерево перемещается от root node, пока мы не достигнем node E, где мы выберем позицию, которая еще не добавлена в дерево.
Далее, во время шага воспроизведения ходы воспроизводятся в режиме самостоятельного воспроизведения до тех пор, пока не будет достигнут конец игры. Результат R этой "моделируемой" игры - +1 в случае победы для Черного (первый игрок в LOA), 0 в случае ничьей и -1 в случае победы для белых.
Затем на этапе расширения к дереву добавляются дети из E.
Наконец, R распространяется по пути от E до корня node на этапе обратного распространения. Когда время увеличивается, ход, выполняемый программой, является дочерним по отношению к корню с самым высоким значением. (Этот пример взят из этой статьи - PDF
www.ru.is/faculty/yngvi/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
Из 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.
Я написал это, если вы заинтересуетесь: https://github.com/avianey/mcts4j