Використання штучного інтелекту для вирішення гри 2048 (код JAVA)

• Квітень 7, 2014
• Василіс Врініотис
• . 6 коментарі

На даний момент більшість із вас чули/грали 2048 гра Габріеле Сіруллі. Це проста, але дуже захоплююча настільна гра, яка вимагає від вас об’єднати числа клітинок, щоб досягти числа 2048. Як і очікувалося, складність гри зростає, оскільки все більше клітинок заповнюються високими значеннями. Особисто, незважаючи на те, що я провів досить багато часу, граючи в гру, я так і не зміг досягти 2048. Тож природним є спробувати розробити розв’язувач AI на 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 здійснює пошук у просторі можливих станів гри, створюючи дерево, яке розширюється, поки воно не досягне певної заздалегідь визначеної глибини. Після досягнення цих станів листів їх значення використовуються для оцінки одиниць проміжних вузлів.

Цікава ідея цього алгоритму полягає в тому, що кожен рівень представляє хід одного з двох гравців. Для перемоги кожен гравець повинен вибрати такий хід, який мінімізує максимальну виплату суперника. Ось гарна відеопрезентація мінімаксного алгоритму:

[Вбудоване вміст]

Нижче ви можете побачити псевдокод мінімаксного алгоритму:

функція мінімакс (вузол, глибина, maximizingPlayer)
    if глибина = 0 or вузол - це термінальний вузол
        повертати евристичне значення вузла
    if maximizingPlayer bestValue := -∞
        для кожного дочірній вузол val := мінімакс(дочірня, глибина - 1, FALSE)) bestValue := max(bestValue, val);
        повертати найкраща ціна
    ще
        найкраще значення := +∞
        для кожного дочірній вузол val := мінімакс(дочірня, глибина - 1, TRUE)) bestValue := min(bestValue, val);
        повертати найкраща ціна
(* Початковий виклик для максимізації гравця *)
мінімакс (початок, глибина, TRUE)

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

Команда Альфа-бета-алгоритм обрізання є розширенням мінімаксу, яке значно зменшує (зрізає) кількість вузлів, які ми повинні оцінити/розширити. Щоб досягти цього, алгоритм оцінює два значення альфа та бета. Якщо в даному вузлі бета-версія менша за альфа, то інші піддерева можна обрізати. Ось гарна відеопрезентація алгоритму алфавіту:

[Вбудоване вміст]

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

функція alphabeta(вузол, глибина, α, β, maximizingPlayer)
    if глибина = 0 or вузол - це термінальний вузол
        повертати евристичне значення вузла
    if maximizingPlayer
        для кожного дочірній вузол α := max(α, алфавіт(дочірня, глибина - 1, α, β, FALSE))
            if β ≤ α
                перерву (* β відрізок *)
        повертати α
    ще
        для кожного дочірній вузол β := min(β, алфавіт(дочірня, глибина - 1, α, β, TRUE))
            if β ≤ α
                перерву (* α зріз *)
        повертати β
(* Початковий дзвінок *)
алфавіт (початок, глибина, -∞, +∞, TRUE)

Як AI використовується для вирішення гри 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. 🙂