Главная » Хабрахабр » [Перевод] ИИ и 2048. Часть 1: Метод Монте-Карло

[Перевод] ИИ и 2048. Часть 1: Метод Монте-Карло

«2048» через несколько недель исполняется 5 лет, а значит, пора написать что-нибудь, посвящённое этой замечательной игре.

Способы реализации есть самые разные и сегодня разберём относительно лёгкий из них. Особенно познавательна тема самостоятельной игры искусственного интеллекта в головоломку. А именно — научим компьютерный разум собирать степени двойки с помощью метода Монте-Карло.

По всей видимости, наилучшим способом является метод минимакса с альфа-бета отсечением и через пару дней ему будет посвящена следующая публикация. Вдохновением к данному труду послужило обсуждение на stackoverflow, где умные ребята предложили действенные способы компьютерной игры.

Весь следующий раздел — это перевод с его публикации. Казино-способ предложен пользователем stackoverflow Ronenz в рамках вышеупомянутого обсуждения.

Я заинтересовался идеей ИИ для этой игры, в которой нет жестко запрограммированного интеллекта (то есть отсутствуют эвристики, подсчет очков и т.п.). ИИ должен «знать» только правила игры и «разбираться» в игре. Это отличает его от большинства ИИ (таких, как в этой теме), поскольку игровой процесс, фактически, является грубой силой, управляемой функцией подсчета очков, отражающей человеческое понимание игры.

ИИ алгоритм

Я обнаружил простой, но удивительно хороший игровой алгоритм: чтобы определить следующий ход для данного состояния поля, ИИ разыгрывает в игру в оперативной памяти, делая случайные ходы до тех пор, пока игра не закончится поражением. Это делается несколько раз, при этом отслеживается конечный счет. Затем рассчитывается средний конечный балл с учётом начального хода. В качестве уже реально выбираемого хода выбирается тот начальный ход, который показал наибольший средний результат.

При использовании 10000 прогонов 2048 получается в 100% случаев, 70% — для 4096 и около 1% — для 8192.

Посмотреть в действии При 100 прогонах для каждого начального хода ИИ добирается до плитки 2048 в 80% случаев и плитки 4096 в 50% случаев.

Лучший достигнутый результат показан на скриншоте:

(Вы можете убедиться в этом сами, запустив ИИ и открыв консоль отладки.) Интересным фактом для данного алгоритма является то, что хотя игры с произвольно осуществляемыми ходами ожидаемо довольно плохи, тем не менее выбор лучшего (или наименее плохого, если угодно) хода приводит к очень хорошему игровому процессу: типичная игра ИИ методом Монте-Карло может набрать 70000 очков за 3000 ходов, однако игры с произвольной игрой в памяти из любой заданной позиции дают в среднем 340 дополнительных очка примерно за 40 дополнительных ходов перед проигрышем.

Красная линия показывает лучший результат алгоритма, произвольно делающий ходы с данной позиции до конца игры. Данный график иллюстрирует эту концепцию: синяя линия показывает счет игры после каждого хода. Интересно, что красная линия чуть-чуть выше синей линии в каждой точке, но синяя линия сокращает разрыв все больше и больше. По сути, красные значения «подтягивают» синие вверх, поскольку они являются наилучшими предложениями алгоритма.

Я нахожу довольно удивительным, что алгоритм на самом деле необязательно предвидит хороший игровой процесс, и тем не менее выбирает ходы, которые его (хороший процесс) производят.

Позже я обнаружил, что этот метод может быть классифицирован как алгоритм поиска по дереву Монте-Карло.

Имплементация и ссылки

Сначала я создал версию на JavaScript, которую можно увидеть в действии здесь. Эта версия способна запустить 100 прогонов за приемлемое время. Откройте консоль для дополнительной информации. (исходники)

Эта версия допускает до 100000 пробежек за ход и даже 1000000, если Вы готовы подождать. Позже, чтобы поиграться, я использовал высокооптимизированную инфраструктуру @nneonneo и реализовал свою версию на C++. Всё работает в консоли, а также имеет пульт дистанционного управления для воспроизведения в веб-версии. Инструкция по сборке прилагается. (исходники)

Результаты

Удивительно, но увеличение количества прогонов кардинально не улучшает игровой процесс. Кажется, что у этой стратегии есть предел в 80000 пунктов с плиткой 4096 и всеми меньшими результатами, очень близкими к достижению плитки 8192. Увеличение количества прогонов со 100 до 100000 увеличивает шансы на достижение этого лимита (с 5% до 40%), но не преодолевает его.

Выполнение 10000 прогонов с временным увеличением до 1000000 вблизи критических позиций позволило преодолеть этот барьер менее чем в 1% случаев с достижением максимального количества набранных очков 129892 и плитки 8192.

Улучшения и оптимизации

После реализации этого алгоритма я попробовал много улучшений, включая использование минимальных или максимальных оценок или комбинации минимальных, максимальных и средних значений. Я также пытался использовать глубину: вместо того, чтобы пытаться выполнить K прогонов за ход, я пробовал K ходов за список ходов заданной длины (например, «вверх, вверх, влево») и выбирал первый ход из списка ходов с лучшим выигрышем.

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

Я оставил закомментироанный код для этих идей в исходниках C++. Однако ни одна из этих идей не показала реального преимущества перед простой первой идеей.

Это привело к улучшению по временным показателям. Я добавил механизм «Глубокий поиск», который временно увеличивал число прогонов до 1000000, когда любой из прогонов сумел случайно достичь следующей наивысшей плитки.

Мне было бы интересно узнать, есть ли у кого-нибудь другие идеи по улучшению, которые поддерживают независимость ИИ от предметной области?

Ради интереса, я также реализовал ИИ в виде букмарклета, подключив его к элементам управления игры. Это позволяет работать как с оригинальной игрой, так и со многими ее вариациями.

Некоторые из вариантов довольно оригинальны, такие как гексагональный клон. Это возможно благодаря доменно-независимой природе ИИ.

На этом перевод завершён, но не только ради него затеяна данная публикация. До коликов захотелось самому проверить различные идеи для ИИ в 2048. С этой целью реализовал игру в Excel, написав приложение с макросами. Сама по себя реализация на VBA подвигом не является — погуглив, можно быстро обнаружить с дюжину различных эксцельных поделок. А вот не только состряпать 2048 в виде электронных таблиц, но и реализовать компьютерную самостоятельную игру — этого мне пока на глаза не попадалось.

Само Excel-приложение можно скачать с гугл-диска.

Картинка кликабельна — откроется полноформатное изображение.

Кратко по интерфейсу и функционалу приложения.

При повторных нажатиях на эту кнопку надпись меняется с "Пользователь: начать игру" на "Пользователь: завершить игру" и обратно, то есть в любой момент можно останавливать игру и затем запускать её снова. Чтобы начать играть, нужно нажать на кнопку "Пользователь: начать игру". При остановке игры можно вручную поменять расклад на поле, улучшив или ухудшив свою позицию в целях тестирования или проверки каких-то идей.

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

  • Клавиатурно: просто нажимая клавиши «вверх», «вниз», «влево», «вправо».
  • С помощью мыши: щёлкая по клеткам с большими стрелочками, указывающими на нужное направление.

Кнопка "Новое поле" очищает игровое поле и на нём в случайном порядке размещает «двойку» и «четвёрку».

На каждой позиции компьютер в памяти перебирает случайные ответвления для каждого первого хода («вверх», «вниз», «влево», «вправо») до тех пор пока это не приведёт к проигрышу. Самое интересное — метод Монте-Карло удалось реализовать, именно в том виде, в каком его предложил чувак со stackoverflow. Можно использовать как подсказку, если видите что Ваша собственная игра заходит в тупик и нужно как-то спасаться. Статистически самое выгодное направление подсвечивается красным цветом в специальной таблице внизу. 😉

На данный момент решён только Монте-Карло, остальные будут добавлены в ближайшие дни (по итогам чего будут ещё хабрастатьи с обновлением excel-приложения и пояснениями по теории). Над таблицей находятся чекбоксы с вариантами анализа.

Щёлкнув по ней, компьютерный помошник сделает один ход в соответствии с методом Монте-Карло или каким-то другим, который выбран в группе переключателей (минимакс и нейронная сеть будут в этом списке работать чуть позже). Также есть кнопка "ИИ: игра".

EDISON Software - web-development
Статья написана при поддержке компании EDISON Software, которая занимается разработкой мобильных приложений и предоставляет услуги по тестированию программного обеспечения.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

В MIT научились передавать звук с помощью лазера

Группа исследователей из MIT представила новый метод передачи направленного звука при помощи лазера. Под катом, рассказываем, на чем построена эта технология. Фото PxHere / PD Лазер для передачи звука Технология направленного звука, способная формировать аудиопоток, слышимый в небольшой области пространства, ...

Ускоряем неускоряемое или знакомимся с SIMD

Есть класс задач, которые нельзя ускорить за счёт оптимизации алгоритмов, а ускорить надо. В этой практически тупиковой ситуации к нам на помощь приходят разработчики процессоров, которые сделали команды, позволяющие выполнять операции на большим количеством данных за одну операцию. В случае ...