Что за игра 2048?
Игра 2048 показана на рисунке ниже, она состоит из 4*4 всего 16 блоков. Игроки могут перемещать блоки в четырех направлениях «вверх, вниз, влево и вправо».При перемещении два соседних блока с одинаковым значением объединятся, а новый блок будет иметь значение суммы двух. Когда значение любого блока в игре достигает 2048, это победа.
Мы будем использовать «метод Монте-Карло» для создания ИИ 2048 года.
Что такое метод Монте-Карло?
Проблем много, математическая формула очень сложная, а математическую формулу не найти даже за короткое время. Например, область неправильной формы внизу.
Аппроксимацию области неправильной формы, описанную выше, можно получить на практике с помощью «статистического моделирования». Метод заключается в следующем: 1) составить множество случайных точек в квадрате; 2) подсчитать количество точек неправильной фигуры; 3) вычислить отношение числа, полученного на шаге 2, к общему числу; 4) умножить шаг на площадь квадрата. Полученное отношение три является приближением площади неправильной формы.
Описанный выше подход является типичным методом Монте-Карло. Когда количество случайных точек, которые мы генерируем, достаточно велико, приближение, которое мы получаем, ближе к теоретически рассчитанному значению, а ошибка меньше. Как показано на рисунке ниже, процесс моделирования метода Монте-Карло для нахождения площади сектора в квадрате:
Две приведенные выше картинки — всего лишь два применения метода Монте-Карло. На самом деле метод Монте-Карло имеет широкий спектр применений, и любое пропорциональное распределение, которое можно смоделировать и статистически, можно смоделировать с помощью метода Монте-Карло. Например, проверить, достаточно ли структурно сбалансирована монета.
Теоретически вероятность выпадения орла и решки при подбрасывании монеты одинакова, по 50%. Однако в реальном процессе абсолютной однородности достичь не удается, и всегда имеют место отклонения. Чтобы узнать, смещено ли это смещение в сторону орла или решки, можно использовать метод Монте-Карло. Непрерывно подбрасывайте монету, а затем подсчитывайте соотношение орла и решки.Когда количество подбрасываний монеты бесконечно, это соотношение отражает однородность монеты. На самом деле мы не можем подбрасывать монету бесконечно, поэтому мы можем получить оценку четности монеты только в пределах определенной погрешности.
В целом, метод Монте-Карло дает нам это удобство на практике: мы можем использовать моделирование и статистику, чтобы заменить процесс работы математических формул для получения решений, близких к теоретическим значениям.
Методы Монте-Карло и игра 2048
Мы можем применить метод Монте-Карло к игре 2048.
Для любого состояния игры 2048 есть четыре направления «вверх, вниз, влево и вправо» на выбор; хотя иногда движение в определенном направлении не изменит состояние доски, но это также ход, поддерживаемый игра, и не будет судить, чтобы проиграть, так что это тоже вариант.
Это «вверх, вниз, влево и вправо», какое направление хорошее, какое плохое, и каковы соответствующие проценты выигрышей? Мы не знаем, но знаем, что объективно они имеют распространение. Сумма всех четырех из них должна равняться 100%.
Эти «вверх, вниз, влево и вправо» можно представить себе как четырехгранную игральную кость, и это неравномерная четырехгранная игральная кость, или их можно представить разделенными на четыре части в положительном направлении, причем четыре части неравномерны. Есть ли у нас «формула 2048» для применения? Можем ли мы напрямую рассчитать процент выигрышной области в каждом направлении? Я не математик и не нашел, но знаю о методах Монте-Карло, которые могут оценивать приближенные решения. Так что попробуйте.
Крайний случай метода Монте-Карло эквивалентен грубому перебору сил, когда берутся четыре направления, четыре направления после четырех направлений и четыре направления из четырех направлений после четырех направлений, и берется каждая перестановка и комбинация. время, вы знаете, проиграть или выиграть; затем подсчитайте количество побед каждого при ходьбе «вверх, вниз, влево и вправо» и разделите его на общее количество раз, чтобы получить процент выигрыша.
Сильное истощение слишком грубо? Неважно. После 400 симуляций уровень точности может достигать 90%, а в оставшееся бесконечное время уровень точности с 90% может повышаться только до 100%.
Код метода Монте-Карло
Следуйте описанию метода Монте-Карло.
Первым шагом является написание класса с методом запуска.Метод запуска принимает итерации параметра, который указывает, сколько раз симулировать.Метод симуляции - это симуляция.
После завершения моделирования getBestAction получает действие с наибольшим количеством очков.
Как написать метод имитации? Это постоянно выбирать направление наугад и идти на смерть. Метод board.getActions должен возвращать пустой массив при выигрыше или проигрыше, указывая на то, что у игрока нет допустимых действий в игре. Таким образом, цикл while может быть освобожден.
Предполагается, что board.doAction переводит игру в следующее состояние. Если игровые шаги бесконечны, то нам нужно контролировать продолжительность симуляции или количество doActions.Для игр с небесконечными шагами, таких как 2048, этот шаг можно опустить.
При симуляции вам нужно скопировать board.clone, чтобы не влиять на текущее состояние игры. Если у нас нет доступа к игровому симулятору, метод Монте-Карло не очень удобен.
Переменная массива путей записывает последовательность действий, которую мы моделировали на этот раз.
Когда мы умираем в симуляции, мы сохраняем текущее первое действие и результат этой симуляции (выигрыш или проигрыш 01 или счет) в таблице статистики для накопления. Почему первое действие? Поскольку наша цель — найти следующее действие в текущей игре, первое действие симуляции соответствует следующему действию, которое мы фактически выполняем.
Последний метод, updateStatistic, заключается в том, что мы обновляем статистическую таблицу. Его реализация также очень проста, то есть определить, существует ли уже действие, аккумулировать его, если оно существует, и создать его, если оно не существует.
Не знаю, заметили ли вы, что в нашем коде нет контента, ограниченного 2048, а есть доска и весьма абстрактные методы, такие как clone, getActions, doAction и getResult?
Правильно, метод Монте-Карло, который мы только что реализовали, не адаптирован для 2048 года, его можно использовать в различных настольных играх, видеоиграх или играх, связанных с последовательностью шагов. Просто напишите адаптер для экспорта состояния игры и действий в интерфейсы clone, getActions, doAction, getResult и другие.
2048 Игровая адаптация метода Монте-Карло
Требуется всего несколько коротких строк кода, чтобы предоставить метод, позволяющий экземпляру платы 2048 соответствовать «классу метода Монте-Карло», который мы реализовали.
В getActions оцените, выигрывает ли в данный момент доска 2048 (hasWon) или терпит неудачу (hasLost). Если да, верните пустой массив. Если нет, верните массив [0, 1, 2, 3], чтобы указать «вверх, вниз, Лево и право".
Результат, возвращаемый getResult: сначала запишите счет board.score перед симуляцией как startScore, после симуляции, когда getResult поместите текущий board.score - startScore, чтобы получить фактическую оценку, полученную в этой симуляции.
Метод doAction просто вызывает board.move для изменения направления. Зачем абстрагировать его в doAction вместо doMove? Потому что действия некоторых игр не ограничиваются движением, ход слишком специфичен, а действие более абстрактно и может представлять больше возможных действий.
После написания адаптера вы можете вывести метод getBestAction, пока вводится текущая плата 2048, использовать метод Монте-Карло для моделирования 400 раз, а затем вернуть действие с наивысшей статистической оценкой в качестве следующего действия.
Запускайте метод Монте-Карло на каждом этапе пути. Хотя он повторяется много раз, это не имеет значения. Повторяйте его до тех пор, пока производительность сохраняется. Повторение увеличивает время моделирования, а это означает, что теория более точно соответствует .распределение по площади.
Если 400 симуляций, то точности недостаточно, можно увеличить до 800, 2000, всегда есть порядок, можно добиться удовлетворительных результатов.
результат победы
На картинке ниже показан скриншот успешного достижения 2048 после симуляции на моей машине. Вы также можете наблюдать за процессом на своей машине. Конечно, лучше всего реализовать алгоритм метода Монте-Карло для усиления впечатления.
Нажмите здесь, чтобы посетить ДЕМО.Нажмите здесь, чтобы получить доступ к исходному коду.
Пожалуйста, обратите внимание на мой публичный аккаунт WeChat. Когда будет возможность, мы представим «Поиск по дереву Монте-Карло (MCTS)», основанный на методе Монте-Карло. Это фактически структурная оптимизация метода Монте-Карло в программировании, и суть метода Монте-Карло.