Дополнительно 4. Поиск по дереву Монте-Карло

• Контент предоставлен по лицензии Creative Commons.  

• Поддержка помогает MIT OpenCourseWare продолжать предлагать высококачественные образовательные ресурсы.  

• Для пожертвований и дополнительных материалов посетите сайт MIT OpenCourseWare.  

• Лекция актуальна для вероятностного планирования и больших пространств состояний.  

• Метод Монте-Карло MCT улучшает производительность по сравнению с другими подходами.  

• Совместное исследование и поиск по дереву MCT эффективны благодаря современному уровню техники.  

• Введение в поиск по дереву методом Монте-Карло MCT.  

• Обсуждение плюсов и минусов MCT, а также его применения к играм.  

• Демонстрация на примере Super Mario Bros и ИИ Alphago.  

• Обсуждение различных алгоритмов и их применения.  

• MCT подходит для полностью наблюдаемых и детерминированных игр.  

• Примеры игр: шахматы, шашки, го, крестики-нолики.  

• Алгоритм минимакс минимизирует максимально возможные потери.  

• Пример с крестиками-ноликами: компьютер выбирает ходы, предвосхищая действия противника.  

• Поиск по всему дереву до нахождения выигрышного хода.  

• Альфа-бета-обрезка удаляет ветви, которые не влияют на окончательное решение.  

• В играх с низкими коэффициентами ветвления, таких как крестики-нолики, это работает хорошо.  

• Для игр с высокими коэффициентами ветвления, как у Alphago, альфа-бета-обрезка не подходит.  

• Цель MCT - выборочное создание различных частей дерева.  

• Асимметричное дерево позволяет исследовать только перспективные участки.  

• Пример с шахматами: исследование ходов, которые могут привести к позитивным результатам.  

• Дерево начинается с начального состояния игры.  

• Каждый ход представлен узлом, и на каждый ход есть ответные ходы противника.  

• Расширение дерева для создания асимметричного дерева начинается с самого верха и спускается по нескольким ветвям.  

• Выбор последовательности узлов и создание нового узла при достижении нового местоположения.  

• Моделирование игры с нового узла, что является ключевой частью MCTS.  

• Обсуждение подхода к моделированию игры с более продвинутого состояния.  

• Создание нового узла и обновление дерева.  

• Распространение значения дельты вверх по дереву и обновление информации в узлах.  

• Повторение процесса до остановки или выбора лучшего хода.  

• Обсуждение выбора места для спуска по дереву.  

• Хранение данных в узлах, включая количество сыгранных игр и выигрышей.  

• Важность сохранения данных для анализа прошлых игр.  

• Противоречивые желания: глубокое исследование и избегание упущенных возможностей.  

• Формула UCB для балансировки расширения и исследования.  

• Термин расширения учитывает вероятность выигрыша в определенном узле.  

• Приближение ожидаемого значения от узла.  

• Спуск по дереву и выбор узла с максимальным значением UCB.  

• Учет минимизации эффективности действий противника.  

• Обновление дерева и выбор узлов для исследования.  

• Ограничения компьютерной памяти и количество состояний в игре Го.  

• Возможность изучения только первых нескольких слоев дерева.  

• Построение дерева решений в реальном времени требует значительных ресурсов.  

• В большинстве игр симуляция одиночного прохождения происходит быстро.  

• Построение дерева для компьютера занимает около миллисекунды.  

• На каждом уровне дерева около 400 узлов.  

• Глубина дерева обычно составляет около 250 шагов.  

• Дерево должно посещать все узлы на определенном уровне перед спуском.  

• Посещение всех узлов позволяет избежать упущения потенциальных интересов.  

• Это помогает сохранить базовую линию и избежать случайных симуляций.  

• Создание узла и задание начальных значений.  

• Моделирование игры осуществляется случайным образом.  

• Случайные ходы позволяют эффективно исследовать дерево.  

• Случайная игра коррелирует с качеством позиции на доске.  

• Использование конечных симуляций вместо одной может быть более эффективным.  

• Важно делать частые симуляции для заглушения шума.  

• Обновление дерева результатов после каждой симуляции.  

• Увеличение количества побед и поражений в зависимости от результатов.  

• Итерация поиска по дереву Монте-Карло для углубления дерева.  

• Выбор лучшего хода из начального состояния.  

• Определение лучшего хода по ожидаемому выигрышу.  

• Пример с игрой в крестики-нолики для демонстрации стратегии.  

• Исследование показало, что случайность влияет на результаты в 11 из 20 случаев.  

• Альтернативный критерий: выбор узла с наибольшим ожидаемым значением и наиболее посещаемым узлом.  

• Алгоритм не всегда может прекратить действие по требованию, что требует более детального рассмотрения.  

• Построение дерева Монте-Карло для выбора оптимального узла.  

• Выбор узла с наибольшим коэффициентом расширения и исследование его.  

• Моделирование игры и увеличение значения узла при победе.  

• Учет результатов игры и увеличение значения узла при победе одного из игроков.  

• Исследование узлов с равными вероятностями и выбор узла наугад.  

• Распространение информации о лучших ходах и их влияние на дерево.  

• Дерево становится асимметричным, что отражает несоответствие между исследованными и неисследованными регионами.  

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

• Объяснение, почему результаты моделирования не всегда учитываются.  

• Обсуждение эмпирических правил для выбора ходов и их отсутствие.  

• Варианты MCTS, которые более избирательно нацеливаются на определенные узлы.  

• Обсуждение временных рамок для проведения миллионов симуляций.  

• Экспериментальное определение высоты и его ограничения.  

• Переход к обсуждению алгоритма MCTS.  

• Асимметричное дерево поиска, не растущее экспоненциально.  

• Использование строгих правил игры для принятия решений.  

• Возможность адаптации к новым играм без внешней эвристики.  

• Возможность включения эвристики в MCTS.  

• Параллельное выполнение задач для повышения эффективности.  

• Проблемы при экстремальной глубине и ветвлении.  

• Ограничения в шутерах от первого лица.  

• Простое и воспроизводимое моделирование.  

• Зависимость от вычислительных ресурсов.  

• Необходимость настройки для различных игр.  

• Недостаток литературы о свойствах MCTS.  

• Вопросы о плюсах и минусах алгоритма.  

• Решение шашек с помощью MCTS.  

• Применение MCTS к "Поселенцам Катана".  

• Возможность использования MCTS в военных стратегиях.  

• Обсуждение необходимости вложений в симуляции для получения качественной игры.  

• Вопрос о возможности кодирования торговли ресурсами в играх для двух игроков.  

• Возможность использования MCTS для игр с несколькими игроками.  

• Обсуждение влияния MCTS на производительность в шахматных играх.  

• Важность эвристической информации для улучшения MCTS.  

• Пример использования MCTS в игре Rome: Total War II.  

• Обсуждение использования MCTS в стратегической игре Rome: Total War II.  

• Искусственный интеллект в игре основан на MCTS.  

• Важность дискретизации действий в MCTS.  

• Введение в модификации и дополнения MCTS.  

• Пример использования MCTS для игры Super Mario Bros.  

• Необходимость добавления одиночного игрока и использования стратегии симуляции.  

• Описание игры Super Mario Bros и её особенностей.  

• Введение в узлы и действия в MCTS.  

• Важность знания предметной области для улучшения результатов моделирования.  

• Обсуждение оценки результатов в симуляциях.  

• Введение знания предметной области для улучшения ИИ.  

• Процесс распространения значений в MCTS и их суммирование.  

• Расстояние, которое вы получаете, равно 0,1.  

• Первоначальная версия имела награду в пять баллов, но Марио изменил оценку.  

• Осталось два оставшихся времени, что имеет вес.  

• В MCTS можно использовать счет для распространения значения Q.  

• Сумма баллов на узлах зависит от количества игр.  

• Средний балл на узле зависит от количества симуляций.  

• Марио может стать огненным Марио, что дает ему больше шансов на выживание.  

• Огненное дыхание помогает Марио справляться с врагами.  

• Параметры настраиваются для достижения желаемого поведения.  

• Изменение значений влияет на результаты симуляций и выбор узлов.  

• Обычная версия выбирает случайный узел на каждом уровне.  

• Наилучшая из n выбирает три случайных узла и придерживается лучшего.  

• Мультисимуляция запускает несколько симуляций и выбирает лучшую.  

• Чем больше симуляций, тем точнее результат.  

• Время вычислений влияет на количество выполняемых симуляций.  

• Разные бюджеты времени на вычисления зависят от количества кадров.  

• Видео показывает, как контроллер Марио использует MCTS.  

• Контроллер наносит серьезный ущерб и собирает монеты.  

• Демонстрация показывает, как контроллер использует разные стратегии для достижения успеха.  

• Графики показывают оценку и бюджет вычислений.  

• UCT и UCT multi используют MCTS и мультисимуляцию.  

• UCT multi plus добавляет механизм подсчета очков за переноску.  

• Вопросы о показателях оценки и эвристике.  

• Эвристика важна для игр такого типа.  

• Использование эвристики помогает достигать лучших результатов.  

• AlphaGo - сложная игра с множеством вариантов ходов.  

• Игра длится около 150 ходов, что позволяет сыграть около 10 из 761 партии.  

• В отличие от шахмат, где есть 35 вариантов хода, в AlphaGo их около 250.  

• Deep Blue использует эвристику для поиска наилучшего хода.  

• AlphaGo использует модифицированную версию MCTS и нейронные сети.  

• В AlphaGo есть две сети политик и одна сеть ценностей.  

• Сети политик используют сверточные нейронные сети CNN.  

• Входные данные для сетей - изображения игры.  

• Сети предсказывают вероятности ходов, а не детерминируют их.  

• Сети обучены на 30 миллионах позиций из игр Go.  

• Медленная политика предсказывает действия эксперта с точностью 57%.  

• Быстрая политика работает быстрее, но менее точно.  

• Сети используются для предсказания выигрышных ходов.  

• AlphaGo выигрывает 85% игр без поиска по дереву.  

• Интуиция в Go может быть важнее долгих размышлений.  

• Сеть ценностей оценивает вероятность выигрыша.  

• Она помогает управлять поиском в дереве.  

• Сеть быстрой политики используется для моделирования.  

• Медленная политика используется для управления поиском.  

• Быстрая политика используется для моделирования.  

• Сеть ценностей дополняет результаты моделирования.  

• Использование только одной сети не дает лучших результатов.  

• Сети работают вместе для улучшения поиска.  

• Сеть ценностей помогает направлять поиск по дереву.  

• MCTS улучшает сеть policy network.  

• Нейронные сети помогают корректировать политику.  

• Симуляции отражают реальные игры, дополняя друг друга.  

• Сеть ценностей отражает медленную политику, а симуляция - быструю.  

• Распределенный Alphago выиграл 77% игр у обычного Alphago.  

• В матче-реванше против Pay с добавлением MCTS и сети ценностей, Alphago сократил Pay на 100%.  

• Google выиграл у людей со счетом 4:1, рейтинг BCDA составил 3.52, что оценивается в 3586 баллов.  

• Alphago выиграл две игры в крестики-нолики за 50 лет.  

• В 2015 году Alphago обыграл Фана Ли, который считается более низким уровнем профессионального го.  

• Alphago смог победить его в прошлом месяце.  

• Отличная работа.  

• Мы закончили.