Таблица транспозиции в алгоритме поиска по методу Монте-Карло непреднамеренно влияет на оценку UCT - PullRequest
Новая
       28

Таблица транспозиции в алгоритме поиска по методу Монте-Карло непреднамеренно влияет на оценку UCT

0 голосов
/ 06 мая 2018

Итак, я реализовал таблицу транспонирования в алгоритме поиска по дереву Монте-Карло, используя UCT. Это позволяет сохранить совокупное значение вознаграждения для игрового состояния, независимо от того, где и сколько раз оно встречается по всему дереву. Это повышает качество информации, собранной о конкретном игровом состоянии.

Увы, я заметил, что это создает определенную проблему на этапе выбора UCT для эксплуатации и разведки. Короче говоря, оценка UCT, назначенная состоянию, учитывает соотношение между количеством посещений родительского состояния и количеством посещений ребенка (для которого мы рассчитываем оценку UCT). Как видно из этой диаграммы, enter image description here при извлечении состояния из таблицы транспонирования во вновь созданную ветвь дерева, это соотношение не в порядке, при посещении дочернего состояния большое количество раз (откуда-то еще в дереве) и посещение родительского состояния гораздо меньшее количество раз, что технически невозможно;

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

1 Ответ

0 голосов
/ 06 мая 2018

Интуитивно, я ожидаю, что вы захотите попробовать следующее.

Для части , используемой в UCT, вы захотите сохранить и использовать средние оценки W / V дочерних узлов. Это среднее во всей полноте можно разделить с помощью транспозиции. Таким образом, в вашем примере вы не обязательно хотите раздельно разделять W = 300 и V = 600, а вместо этого просто делитесь средним баллом W / V = 300 / 600 = 0.5. Это означает, что благодаря транспонированию вы можете поделиться более точными оценками оценок (оценки, основанные на больших размерах выборки).

Для разведки части UCT, я думаю, вы захотите использовать статистику "с точки зрения" родительского узла (где у вас нет транспозиции), а не дочернего узла (который является транспонированием узла в другом месте дерева). Вместо использования количества посещений дочерних узлов при выборе дочернего узла это означает, что вы будете использовать количество посещений, собранных по паре state + action в родительском узле.

Например, представьте, что мы находимся в узле, где вы написали V: 2, W: 300 (обозначаем этот узел как P), и нам нужно выбрать дочерний узел. Более стандартная реализация будет зацикливать дочерние элементы и использовать количество посещений дочерних узлов. В вашей ситуации, я думаю, было бы лучше вместо этого выполнить цикл по действиям в узле P и отслеживать количество посещений для этих действий, а не для дочерних узлов. В P вы еще никогда не выполняли действие, ведущее к дочернему узлу транспонирования, поэтому этот счетчик посещений для пары (P + action) будет по-прежнему равен 0.

У меня лично нет опыта работы с комбинацией транспозиций MCTS +, поэтому вы можете провести дополнительное исследование, чтобы увидеть, что другие придумали в прошлом. Например, есть следующие документы:

...