Мы можем улучшить качество моделирования, используя хорошую политику выбора ходов. В этом выпуске мы собираемся объяснить и реализовать такие алгоритмы, как решающий ход, последний хороший ответ (LGR) и алгоритмы PoolRave.
И снова здравствуйте. Мы вернулись с еще одной статьей, объясняющей MCTS и то, как мы можем сделать ее сильнее в игровом процессе. До сих пор мы реализовали алгоритмы UCT и RAVE в предыдущих частях. Код этой статьи основан на реализации RAVE, поэтому я рекомендую вам убедиться, что вы понимаете код, реализованный в предыдущих частях:
В этой статье мы рассматриваем и реализуем три полезных алгоритма, которые легко объединить с нашим модулем RaveMctsAgent.
Решительный ход
В каждой игре бывают ситуации, когда происходят действия, которые могут немедленно привести к победе или имеют решающее значение для победы. Фабьен Тейто и др. назвали их решающими шагами [1].
Тейто предложил этот алгоритм в своей статье:
Другими словами, выбирая действие во время игры, мы всегда проверяем, приведут ли доступные ходы к завершению игры с проигрышем/выигрышем. если он найден, то это критический шаг. если он не найден, мы выбираем ходы на основе политики по умолчанию (например, случайный выбор).
Чтобы это закодировать, нам нужен механизм обнаружения критических ходов. Итак, мы открываем файл gamestate.py и добавляем эту функцию would_lose, которая может проверять, приведет ли выбранное cell к выигрышу с преимуществом color или нет:
Теперь мы реализовали DecisiveMoveAgent :
Как видите, во время воспроизведения мы выбираем ходы один за другим и каждый раз проверяем все доступные ходы (строки 12 — 24), являются ли они критическими или нет (строка 18). Если не найден, выбираем случайным образом (строки 26 — 29). В конце концов, после перехода состояний, мы меняем местами хорошие ходы игроков (строка 33). а затем наступает время рейв-алгоритма (строки 38 — 43).
Последний хороший ответ (LGR)
Этот алгоритм был первоначально представлен Байером и Дрейком в 2010 году. Идея проста, но эффективна. В нем говорится, что могут быть успешные ответы на действия оппонента. Поэтому после симуляций мы сохраняем в памяти действия оппонента и последующие ответы. Затем для следующих симуляций мы используем эти ответы (эта стратегия используется с некоторой вероятностью), как если бы они могли быть хорошими немедленными ответами на действия оппонентов.
Вот код для LGRMctsAgent :
Сохраним белые и черные ответы в словарях и инициируем их в методе __init__ и set_gamestate (строки 5 — 6 и 15 — 16).
В методе roll_out мы инициализируем current_reply и other_reply как переменные для отслеживания ответов игроков. Затем во время выбора хода мы выбираем ходы с вероятностью 0,5 на основе предыдущих ответов, хранящихся в памяти (политика LGR в строках 36–40), если таковые существуют.
В строках 55 — 60 начинается раздел алгоритма рейва. Затем, в конце, мы продолжаем обновлять ходы и ответы на них.
БассейнРейв
Хук и др. [3] описывают усовершенствование пула RAVE, которое изменяет этап моделирования MCTS следующим образом:
- Создайте пул из k лучших ходов по версии RAVE.
- Выберите один ход m из пула.
- Играть m с вероятностью p, иначе политика по умолчанию.
Хук и др. [4] обнаружили, что это приводит к улучшению программ Havannah и Go.
Теперь давайте посмотрим на код:
Мы инициируем класс с помощью black_rave и white_rave (строки 5–6 и 15–16). В методе roll_out мы сортируем их все и выбираем m лучших ходов на основе оценок poolrave (строки 26–44). Затем мы начинаем фазу roll_out , пока не дойдем до конца игры (строки 45–60).
В строках 65 — 91 сохраняем рейв-очки для черно-белых игроков. Затем, если выдача завершилась победой, мы увеличиваем их рейтинг пула за этот ход (строки 71–74 для черных и 83–86 для белых), а если нет, мы уменьшаем его балл (строки 75–79 для черных и 87). –91 для белых).
Заключение
Все алгоритмы, представленные в этой статье, представляют собой усовершенствования, предназначенные для этапа моделирования MCTS. Алгоритмы, представленные в этой статье, потребуют больше времени для обработки, поэтому мы увидим, что количество симуляций будет уменьшаться с каждой секундой по сравнению с UCT и RAVE, но они помогают дереву становиться умнее. В следующей статье мы собираемся реализовать еще один алгоритм, который изменит фазы backup и roll_out и применим как к алгоритмам UCT, так и к RAVE, и называется он Вознаграждение на основе качества.
Рекомендации
- [1] Ф. Тейто и О. Тейто, «Об огромной пользе решающих ходов в алгоритмах поиска по дереву Монте-Карло», Труды конференции IEEE 2010 г. по вычислительному интеллекту и играм, Копенгаген, Дания, 2010 г., стр. 359– 364, номер домена: 10.1109/ITW.2010.5593334.
- [2] Х. Байер и П. Д. Дрейк, «Сила забывания: улучшение политики последнего хорошего ответа в Monte Carlo Go», в IEEE Transactions on Computational Intelligence and AI in Games, vol. 2, нет. 4, стр. 303–309, декабрь 2010 г., doi: 10.1109/TCIAIG.2010.2100396.
- [3] Ж.-Б. Хук, К.-С. Ли, А. Риммель, Ф. Тейто, О. Тейто и М.-Х. Ван, «Интеллектуальные агенты для игры в го», IEEE Comput. Интел. Маг., вып. 5, нет. 4, стр. 28–42, 2010.
- [4] CB Browne и др., «Обзор методов поиска в дереве Монте-Карло», в IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, нет. 1, стр. 1–43, март 2012 г., doi: 10.1109/TCIAIG.2012.2186810.
