Формула UCB для поиска по дереву Монте-Карло, когда счет находится между 0 и n

Я реализую ИИ, который воспроизводит 2048, используя поиск по дереву Монте-Карло. Согласно википедии https://en.wikipedia.org/wiki/Monte_Carlo_tree_search и всем другим источникам. что я проверил на шаге расширения, вы должны использовать формулу UCB, чтобы определить, какой узел посетить wi/ni + c*sqrt(ln(N)/ni). Эта формула хорошо работает, когда счет в конце равен 0 или 1 (победа или поражение), однако эта формула не работает в 2048 году, потому что счет представляет собой значение между 0 и n, которое мы хотим максимизировать.

Кто-нибудь знает, какая оптимальная формула используется для UCB в MCTS, когда счет представляет собой значение между 0 и n, чтобы я мог использовать ее в игре 2048?

Спасибо.


artificial-intelligence algorithm monte-carlo-tree-search 2048
person joan capell    schedule 05.08.2019    source источник
comment
Этот вопрос, вероятно, не по теме здесь. ai.stackexchange.com подойдет лучше, поскольку речь идет не столько о конкретной проблеме программирования, сколько о концепциях, лежащих в основе алгоритм.   -  person Dennis Soemers    schedule 16.08.2019

Ответы (1)


arrow_upward
0
arrow_downward

Максимально возможная оценка для 2048 кажется где-то около 4000000 баллов.

Поэтому вам просто нужно масштабировать максимально возможный балл до 1:

game_score / 3932156

Сжатие до диапазона [0, 1] довольно распространено.

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

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

Вы должны попробовать: это также случается, когда точность сжатия оказывает минимальное влияние (взгляните на Использование знаний о предметной области для улучшения Монте-Карло дерево Эффективность поиска в параметризованных покерных квадратах — Роберт Аррингтон, Клэй Лэнгли и Стивен Богартс для получения дополнительной информации).

person manlio    schedule 04.09.2019
comment
Использование логарифмической шкалы может помочь избежать проблемы, когда большинство нормализованных показателей близки к 0. - person myrtlecat; 04.09.2019
comment
Использование этой полной нормализации максимального теоретического балла на практике может быть плохим (если на практике вознаграждение в действительности имеет тенденцию быть в гораздо меньшем масштабе). Может быть лучше динамически нормализовать на основе того, что вы наблюдаете, и это также можно сделать локально внутри дерева поиска (нормализация на основе разных границ в разных поддеревьях). См., например, верхнюю часть страницы 21 в этой статьи (а также дополнительные обсуждения нормализации далее в статье) - person Dennis Soemers; 04.09.2019