Использование искусственного интеллекта для решения игры 2048 (код JAVA)

• 7 апреля 2014
• Василис Вриниотис
• , 6 комментария

К настоящему времени большинство из вас слышали / играли 2048 игры Габриэле Цирулли. Это простая, но очень затягивающая настольная игра, в которой вам нужно объединить числа ячеек, чтобы достичь числа 2048. Как и ожидалось, сложность игры возрастает по мере того, как все больше ячеек заполняются высокими значениями. Лично, хотя я потратил немало времени, играя в игру, я так и не смог достичь 2048. Поэтому естественная вещь, которую нужно сделать, это попытаться разработать решатель ИИ в JAVA, чтобы победить в игре 2048. 🙂

В этой статье я кратко расскажу о своем подходе к созданию решателя искусственного интеллекта из игры 2048, опишу эвристику, которую я использовал, и предоставлю полный код, написанный на JAVA. Код с открытым исходным кодом под лицензией GPL v3, и вы можете скачать его с Github.

Разработка игры 2048 в JAVA

Исходная игра написана на JavaScript, поэтому мне пришлось переписать ее на JAVA с нуля. Основная идея игры заключается в том, что у вас есть сетка 4 × 4 с целочисленными значениями, каждая из которых является степенью 2. Ячейки с нулевым значением считаются пустыми. В любой момент игры вы можете перемещать значения в 4 направлениях: вверх, вниз, вправо или влево. Когда вы выполняете перемещение, все значения сетки перемещаются в этом направлении и останавливаются либо при достижении границ сетки, либо при достижении другой ячейки с ненулевым значением. Если эта предыдущая ячейка имеет то же значение, две ячейки объединяются в одну ячейку с двойным значением. В конце каждого хода на доске в одной из пустых ячеек добавляется случайное значение, которое равно либо 2 с вероятностью 0.9, либо 4 с вероятностью 0.1. Игра заканчивается, когда игроку удается создать ячейку со значением 2048 (победа) или когда больше нет других ходов (проигрыш).

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

Все классы задокументированы с комментариями Javadoc. Ниже мы предоставляем высокоуровневое описание архитектуры реализации:

1. Доска класса

Класс игрового поля содержит основной код игры, который отвечает за перемещение фигур, подсчет очков, проверку завершения игры и т. Д.

2. ActionStatus и Direction Enum

ActionStatus и Direction - это два существенных перечисления, в которых хранится результат движения и его направление соответственно.

3. Класс ConsoleGame

ConsoleGame - это основной класс, который позволяет нам играть в игру и проверять точность AI Solver.

4. Класс AIsolver

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

Методы искусственного интеллекта: минимакс против альфа-бета-обрезки

Несколько подходов были опубликованы, чтобы автоматически решить эту игру. Наиболее заметным является тот, который разработан Мэтт Оверлан, Чтобы решить эту проблему, я попробовал два разных подхода, используя алгоритм Minimax и обрезку альфа-бета.

Минимаксный алгоритм

Ассоциация Минимакс рекурсивный алгоритм, который можно использовать для решения игр с нулевой суммой для двух игроков. В каждом состоянии игры мы ассоциируем значение. Алгоритм Minimax просматривает пространство возможных игровых состояний, создавая дерево, которое расширяется, пока не достигнет определенной заранее заданной глубины. Как только эти конечные состояния достигнуты, их значения используются для оценки значений промежуточных узлов.

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

[Встраиваемое содержимое]

Ниже вы можете увидеть псевдокод минимаксного алгоритма:

функция минимакс (узел, глубина, максимизацияPlayer)
    if глубина = 0 or узел является терминальным узлом
        возвращают эвристическое значение узла
    if maximizingPlayer bestValue: = -∞
        для каждого дочерний элемент узла val: = minimax (child, depth - 1, FALSE)) bestValue: = max (bestValue, val);
        возвращают лучшее соотношение
    еще
        bestValue: = + ∞
        для каждого дочерний элемент узла val: = minimax (child, depth - 1, TRUE)) bestValue: = min (bestValue, val);
        возвращают лучшее соотношение
(* Первоначальный вызов для максимизации игрока *)
минимакс (происхождение, глубина, ИСТИНА)

Альфа-бета обрезка

Ассоциация Алфа-бета алгоритм обрезки это расширение минимакса, которое сильно уменьшает (сокращает) количество узлов, которые мы должны оценить / расширить. Для достижения этого алгоритм оценивает два значения альфа и бета. Если в данном узле бета меньше альфы, то остальные поддеревья могут быть удалены. Вот хорошая видеопрезентация алгоритма алфавита:

[Встраиваемое содержимое]

Ниже вы можете увидеть псевдокод алгоритма отсечения альфа-бета:

функция алфавит (узел, глубина, α, β, maximizingPlayer)
    if глубина = 0 or узел является терминальным узлом
        возвращают эвристическое значение узла
    if максимизация игрока
        для каждого дочерний элемент узла α: = max (α, алфавит (дочерний элемент, глубина - 1, α, β, ЛОЖЬ))
            if β ≤ α
                перерыв (* β-отсечение *)
        возвращают α
    еще
        для каждого дочерний элемент узла β: = min (β, алфавит (дочерний элемент, глубина - 1, α, β, ИСТИНА))
            if β ≤ α
                перерыв (* отсечение α *)
        возвращают β
(* Первоначальный звонок *)
алфавит (начало координат, глубина, -∞, + ∞, TRUE)

Как ИИ используется для решения Игры 2048?

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

Так почему же мы используем методы ИИ, которые решают игры с нулевой суммой и которые предполагают, что оба игрока выбирают лучший ход для них? Ответ прост; несмотря на то, что это только первый игрок, который пытается максимизировать свой счет, выбор компьютера может заблокировать прогресс и помешать пользователю завершить игру. Моделируя поведение компьютера как ортологического неслучайного игрока, мы гарантируем, что наш выбор будет надежным независимо от того, что играет компьютер.

Вторая важная часть - это присвоение значений состояниям игры. Эта проблема относительно проста, потому что сама игра дает нам счет. К сожалению, попытка максимизировать счет сама по себе не является хорошим подходом. Одна из причин этого заключается в том, что положение значений и количество пустых значащих ячеек очень важны для победы в игре. Например, если мы рассредоточим большие значения в удаленных ячейках, нам будет очень сложно их объединить. Кроме того, если у нас нет свободных ячеек, мы рискуем проиграть игру в любую минуту.

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

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

Разработка эвристической функции оценки

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

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

Вышеприведенная функция объединяет фактическую оценку доски, количество пустых ячеек / плиток и метрику, называемую оценкой кластеризации, которую мы обсудим позже. Давайте рассмотрим каждый компонент более подробно:

1. Фактическая оценка: По понятным причинам, когда мы рассчитываем стоимость доски, мы должны учитывать ее оценку. Доски с более высокими баллами обычно предпочтительнее по сравнению с досками с более низкими баллами.
2. Количество пустых ячеек: Как мы упоминали ранее, сохранение нескольких пустых ячеек важно для того, чтобы мы не потеряли игру в следующих ходах. Состояния доски с большим количеством пустых ячеек обычно предпочтительнее по сравнению с другими с меньшим количеством ячеек Возникает вопрос, как бы мы оценили эти пустые клетки? В моем решении я взвешиваю их по логарифму фактической оценки. Это имеет следующий эффект: чем ниже счет, тем менее важно иметь много пустых ячеек (это потому, что в начале игры объединить ячейки довольно легко). Чем выше оценка, тем важнее обеспечить наличие в нашей игре пустых ячеек (это потому, что в конце игры вероятность проигрыша из-за отсутствия пустых ячеек выше).
3. Оценка кластеров: Мы используем показатель кластеризации, который измеряет, насколько разбросаны значения нашей доски. Когда ячейки с одинаковыми значениями близки, их легче комбинировать, а значит, сложнее проиграть. В этом случае показатель кластеризации имеет низкое значение. Если значения доски разбросаны, то эта оценка получает очень большое значение. Этот балл вычитается из двух предыдущих баллов и действует как штраф, гарантирующий предпочтение кластеризованным доскам.

В последней строке функции мы гарантируем, что результат будет неотрицательным. Оценка должна быть строго положительной, если оценка доски положительная, и равна нулю только тогда, когда оценка доски равна нулю. Функции max и min построены так, чтобы мы получили этот эффект.

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

Подробнее о баллах кластеров

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

Давайте посмотрим, как оценивается оценка кластеризации. Для каждой ячейки доски мы оцениваем сумму абсолютных отличий от соседей (исключая пустые ячейки) и берем среднюю разницу. Причина, по которой мы берем средние значения, состоит в том, чтобы избежать повторного подсчета влияния двух соседних ячеек. Общая оценка кластеризации является суммой всех этих средних.

Оценка кластеризации имеет следующие атрибуты:

1. Он получает высокое значение, когда значения платы разбросаны, и низкое значение, когда ячейки с одинаковыми значениями находятся близко друг к другу.
2. Это не перевешивает эффект двух соседних клеток.
3. Клетки на полях или в углах имеют меньше соседей и, следовательно, более низкие оценки. В результате, когда высокие значения размещаются рядом с полями или углами, они имеют меньшие оценки и, следовательно, штраф меньше.

Точность алгоритма

Как и ожидалось, точность (или процент выигранных игр) алгоритма сильно зависит от глубины поиска, которую мы используем. Чем выше глубина поиска, тем выше точность и тем больше времени требуется для запуска. В моих тестах поиск с глубиной 3 длится менее 0.05 секунды, но дает 20% шансов на победу, глубина 5 длится около 1 секунды, но дает 40% шансов на победу и, наконец, глубина 7 длится 27-28 секунд и дает около 70-80% шансов на победу.

Будущие расширения

Для тех из вас, кто заинтересован в улучшении кода, есть несколько вещей, которые вы можете посмотреть:

1. Улучшить скорость: Улучшение скорости алгоритма позволит вам использовать большую глубину и, следовательно, получить лучшую точность.
2. Создать графику: Есть веская причина, почему реализация Габриэле Цирулли стала настолько известной. Это приятно смотреть! Я не беспокоился о разработке графического интерфейса, а скорее печатал результаты на консоли, что усложняло игру и следить за ней. Создание хорошего графического интерфейса является обязательным.
3. Настройка эвристики: Как я упоминал ранее, несколько пользователей предложили разные эвристики. Можно поэкспериментировать с тем, как рассчитываются баллы, веса и характеристики доски, которые учитываются. Предполагается, что мой подход к измерению оценки кластера объединяет другие предложения, такие как монотонность и гладкость, но все еще есть возможности для улучшения.
4. Настройка глубины: Можно также попытаться настроить / настроить глубину поиска в зависимости от состояния игры. Также вы можете использовать Итеративное углубление поиска в глубину алгоритм, который, как известно, улучшает алгоритм отсечения альфа-бета.

Не забудьте скачать код JAVA с Github и эксперимент. Я надеюсь, вам понравился этот пост! Если вы сделали, пожалуйста, найдите время, чтобы поделиться статьей в Facebook и Twitter. 🙂