Краткое содержание

Рассмотрим это однопользовательское дерево решений: Ход 1: действие 1 или действие 2. Если действие 2, выигрыш равен 0.8. Ход 2: если действие 1 на ходу 1, то выбираем между действием 1a и 1b, с выигрышами 0 и 0.9 соответственно. 1 -- 1a (0) \- 1b (0.9) 2 (0.8) Выше – расчет UCB, который я сделал в таблице (с параметром исследования = 1.5). Как видите, требуется 90 прогонов, чтобы найти решение для игрового дерева, которое имеет всего 3 листа. Это всего лишь пример. Я столкнулся с подобным поведением при реализации MCTS для более крупных игровых деревьев, поэтому minimax здесь не подходит. Я знаю, что проблема в том, что действие 1b и действие 2 имеют схожие выигрыши, если бы выигрыши были только ноль/один, это не было бы проблемой. Но во многих приложениях (Go, пари, спидран видеоигр, решения в реальной жизни...) цель – получить счет, а не просто выиграть/проиграть. В этих приложениях разница между 0.8 и 0.9 была бы огромной (36 очков в Go!). В AI для Go эта проблема решается путем установки порогового значения для счета, поэтому мы преобразуем результат.