Поиск по дереву Монте-Карло — наиболее многообещающая функция перемещения

Я попытался внедрить игровой проигрыватель MCTS «крестики-нолики привет-мир», но столкнулся с проблемой.

При моделировании игры и выборе "наиболее перспективной" (exploit/explore) ноды я учитываю только общее количество побед ("exploit" часть) - это создает определенную проблему, полученный алгоритм вообще не является защитным. В результате при выборе между

  • ход, который приводит к (100 ничьих; 10 проигрышей)
  • ход, который приводит к (1 победа; 109 поражений)

выбран худший (1; 109), потому что моя функция uct жадно подсчитывает средние выигрыши вместо «значения».

Я правильно идентифицирую эту проблему? Должен ли я переключиться с «средних побед» на какую-то другую метрику ценности, которая учитывает все типы результатов?

Приветствуются любые советы, спасибо


tic-tac-toe montecarlo game-theory monte-carlo-tree-search
person Kamil Czarnogorski    schedule 16.02.2018    source источник
comment
Зависит от того, пытаетесь ли вы выиграть любой ценой или пытаетесь получить наилучший возможный результат (я бы предпочел второе).   -  person FrankS101    schedule 16.02.2018

Ответы (1)


arrow_upward
3
arrow_downward

Поскольку крестики-нолики — это игра с нулевой суммой (значение состояния для одного игрока всегда равно отрицательному значению для противника), ваша функция счета также должна отражать это.

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

  • +1 за каждую победу
  • 0 за каждый розыгрыш
  • -1 за каждое поражение

В вашем примере это приведет к следующим средним баллам:

  • ход, который приводит к (100 ничьих; 10 проигрышей): ср. оценка = -10/110 = -0.0909...
  • ход, который приводит к (1 выигрыш; 109 проигрышей): в среднем. оценка = -108/110 = -0.98181...

Таким образом, первый вариант будет рассматриваться как лучший вариант

person Dennis Soemers    schedule 16.02.2018