Питання Який оптимальний алгоритм для гри 2048?


Нещодавно я спіткнувся на гру 2048. Ви об'єднуєте подібні плитки, переміщаючи їх в будь-якому з чотирьох напрямків, щоб зробити "більшу" плитку. Після кожного переміщення нова черепиця з'являється у випадковому порожньому місці з значенням будь-якого 2 або 4. Гра закінчується, коли всі поля заповнені, і немає рухів, які можуть об'єднувати плитки, або ви створюєте плитку з значенням 2048.

Один, мені потрібно дотримуватися чітко визначеної стратегії досягнення мети. Отже, я думав написати програму для цього.

Мій поточний алгоритм:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Що я роблю в будь-який момент, я спробую об'єднати плитки цінностями 2 і 4, тобто, я намагаюся мати 2 і 4 плитки, якнайменше. Якщо я спробую це таким чином, всі інші плитки автоматично зливаються, і стратегія виглядає добре.

Але, коли я фактично використовую цей алгоритм, я отримую лише 4000 балів, перш ніж гра закінчується. Максимальна кількість балів AFAIK складає трохи більше 20 000 балів, що набагато більше, ніж моя поточна оцінка. Чи є кращий алгоритм, ніж вищесказане?


1755
2018-03-12 05:37


походження


Це може допомогти! ov3y.github.io/2048-AI - cegprakash
@ nitish712 до речі, ваш алгоритм є жадібним, оскільки у вас є choose the move with large number of merges які швидко призводять до локальних оптимумів - Khaled.K
@ 500-InternalServerError: якщо Я повинні були реалізувати AI з обрізанням дерев дерева ігор альфа-бета, це буде припускати, що нові блоки розташовані змагально. Це найгірше припущення, але це може бути корисним. - Charles
Забавна відволікання, коли у вас немає часу, щоб прагнути до високої оцінки: спробуйте отримати найнижчу кількість очок. Теоретично це чергування 2 і 4 с. - Mark Hurd
Обговорення легітимності цього питання можна знайти на мета: meta.stackexchange.com/questions/227266/... - Jeroen Vannevel


Відповіді:


Я розробив 2048 AI очікуваний замість мінімаксного пошуку, що використовується алгоритмом @ ovolve. AI просто виконує максимізацію за всіма можливими ходів, за якими очікується над усіма можливими плитки (зважуються ймовірністю плитки, тобто 10% для 4 і 90% для 2). Наскільки я знаю, неможливо обрізати оптимізацію очікування (за винятком видалення гілок, що є надзвичайно малоймовірними), і тому використовуваний алгоритм - ретельно оптимізований пошук грубої сили.

Продуктивність

AI в його налаштуваннях за замовчуванням (максимальна глибина пошуку 8) займає від 10 мс до 200 мс, щоб виконати переміщення залежно від складності позиції плати. Під час тестування AI досягає середньої швидкості руху 5-10 переходів у секунду протягом всієї гри. Якщо глибина пошуку обмежена 6 рухами, AI може легко виконати 20 + переміщень у секунду, що робить для деяких цікаво дивитися.

Щоб оцінити показники роботи AI, я запустив AI 100 разів (підключений до браузерної гри за допомогою пульта дистанційного керування). Для кожної плитки ось пропорції ігор, в яких ця плитка була досягнута принаймні один раз:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Мінімальний бал за всі пробіжки становив 124024; досягнута максимальна оцінка - 794076. Медіана - 387222. AI ніколи не змогла отримати плитку 2048 (так що вона ніколи не програла гру навіть раз на 100 ігор); насправді це досягало 8192 плитку принаймні один раз на кожному забігу!

Ось знімок екрану найкращого пробігу:

32768 tile, score 794076

Ця гра зайняла 27830 переміщень протягом 96 хвилин або в середньому 4,8 переміщення в секунду.

Реалізація

Мій підхід кодує всю дошку (16 записів) як єдине 64-розрядне ціле число (де плитки - це nibbles, тобто 4-бітні шматки). На 64-розрядній машині це дає змогу передавати всю дошку в одному реєстрі машин.

Операції бітового зсуву використовуються для вилучення окремих рядків і стовпчиків. Одним рядком або стовпчиком є ​​16-бітна кількість, тому таблиця розміру 65536 може кодувати перетворення, які працюють в одному рядку або стовпчику. Наприклад, рухи реалізуються як 4 пошукових запиту на попередньо «таблицю ефектів переміщення», яка описує, як кожний перехід впливає на окремий рядок або стовпець (наприклад, у таблиці "переміщення праворуч" міститься запис "1122 -> 0023", що описує, як рядок [2,2,4,4] стає рядком [0,0,4,8] при переміщенні вправо).

Оцінювання також виконується за допомогою пошуку таблиці. Таблиці містять евристичні оцінки, обчислені по всіх можливих рядках / стовпцях, а результуючий рахунок для дошки - це просто сума значень таблиці у кожному рядку та стовпчику.

Представлення цієї дошки разом із підходом до пошуку таблиці для руху та забивання дозволяє AI в короткий проміжок часу шукати велику кількість ігрових станів (понад 10 000 000 ігрових станів в секунду на одній ядрі мого ноутбука середини 2011 р.).

Сам очікуваний пошук кодується як рекурсивний пошук, який чергується між кроками «очікування» (тестування всіх можливих місць і значень спадів плитки та оцінювання їх оптимізованих балів за ймовірністю кожної можливості) та «максимізація» (тестування всіх можливих кроків і вибравши з найкращим балом). Пошук дерева закінчується, коли він бачить раніше розглянуту позицію (використовуючи a таблиця перенесення), коли вона досягає визначеної межі глибини або коли він досягає рівня штату, що є малоймовірним (наприклад, це було досягнуто шляхом отримання 6 "4" плиток поспіль із початкової позиції). Типова глибина пошуку 4-8 рухів.

Евристика

Кілька евристичних методів використовуються для направлення алгоритму оптимізації до сприятливих позицій. Точний вибір евристики має величезний вплив на продуктивність алгоритму. Різні евристики зважуються і об'єднуються в позиційну оцінку, яка визначає, наскільки "добре" є задане положення плати. Потім оптимізація пошуку буде спрямована на максимізацію середньої оцінки всіх можливих позицій на борту. Фактична оцінка, як показує гра, є ні використовується для розрахунку бортового балу, оскільки воно надто сильно важить на користь об'єднання плиток (коли відкладене злиття може принести велику вигоду).

Спочатку я використовував дві дуже прості евристики, що надають "бонуси" для відкритих квадратів і мають великі значення на краю. Ці евристики виконували досить добре, часто досягаючи 16384, але ніколи не отримуючи 32768.

Петро Моравек (@xificurk) взяв мій AI і додав два нових евристики. Першим евристичним було покарання за наявність немонотонних рядків і стовпців, які збільшилися за рахунок збільшення чисел, що гарантує, що немонотонні рядки малих чисел не сильно вплинуть на рахунок, але немонотонні рядки великих розмірів суттєво постраждають. Другий евристичний інструмент враховував кількість потенційних об'єднань (сусідніх рівних значень) на додаток до відкритих просторів. Ці дві евристики служили для того, щоб підштовхнути алгоритм до монотонних плат (які легше об'єднати) та до позицій плати з великою кількістю об'єднань (заохочуючи їх вирівнювати, де це можливо, для більшого ефекту).

Крім того, Петро також оптимізував евристичні ваги, використовуючи стратегію "мета-оптимізації" (використовуючи алгоритм під назвою CMA-ES), де самі ваги були скориговані, щоб отримати максимально можливу середню оцінку.

Ефект цих змін надзвичайно значний. Алгоритм перейшов від досягнення 16384 плитки приблизно в 13% часу до досягнення цього протягом 90% часу, а алгоритм став досягти 32768 більше, ніж 1/3 часу (тоді як старі евристики ніколи не виробляли 32768 плиток) .

Я вірю, що на евристику все ще є можливості для поліпшення. Цей алгоритм, безумовно, ще не "оптимальний", але я відчуваю, що він досить близько.


Те, що AI досягає 32768 черепиці в більш ніж третині своїх ігор, є величезною віхою; Я здивуюсь, якщо будь-які гравці в офіційній грі досягнули 32768 (наприклад, не використовуючи такі інструменти, як збереження чи скасування). Я думаю, що плитка 65536 знаходиться в межах досяжності!

Ви можете спробувати AI для себе. Код доступний на https://github.com/nneonneo/2048-ai.


1132
2018-03-19 07:22



@RobL: 2 з'являються 90% часу; 4 - це 10% часу. Це в вихідний код: var value = Math.random() < 0.9 ? 2 : 4;. - nneonneo
В даний час порт для Cuda, тому GPU робить роботу для ще кращих швидкостей! - nimsson
@nneonneo Я переніс ваш код з emscripten в javascript, і він працює досить добре в браузері зараз! Прохолодно дивитися, без необхідності компілювати і все ... У Firefox продуктивність непогана ... - reverse_engineer
Теоретичний ліміт у сітці 4x4 фактично становить 131072, а не 65536. Проте це вимагає отримання 4 у правильному моменті (тобто вся плата наповнена 4 .. 65536 кожен раз - 15 зайнятих полів), і плата має бути встановлена ​​на цьому момент, щоб ви могли об'єднати. - Bodo Thiesen
@nneonneo Можливо, ви захочете перевірити наш AI, який, здається, ще краще, досягаючи 32k у 60% ігор: github.com/aszczepanski/2048 - cauchy


Я автор програми AI, про яку інші згадували у цій темі. Ви можете переглянути AI в дія або прочитайте джерело.

В даний час програма досягає приблизно 90% виграшу, що працює в javascript у браузері на моєму ноутбуці, що дає близько 100 мілісекунд мислення часу на переміщення, а поки не ідеально (поки що!) Він виконує досить добре.

Оскільки гра - це дискретний простір стану, чудова інформація, гра на основі ігор, як шахи та шашки, я використовував ті ж методи, які, як доведено, працювали на цих іграх, а саме мінімакс  пошук з альфа-бета обрізка. Оскільки вже існує багато інформації про цей алгоритм, я просто поговоримо про дві основні евристики, які я використовую в статична оцінка функції і які формалізують багато інтуїцій, які тут висловили інші люди.

Монотонність

Ця евристика намагається забезпечити, щоб значення плиток або збільшувалося, або зменшувалось як по лівому / правому, так і вгору / вниз напрямками. Цей евристичний поодинці фіксує інтуїцію, про яку згадували багато інших, що плитки з високою цінністю повинні бути об'єднані в кут. Як правило, це дозволяє запобігти посиленню плитки з меншою цінністю та забезпечувати вельми організовану плату, причому каскадне наповнення невеликих плиток і збільшення кількості плиток.

Ось знімок екрану абсолютно монотонної сітки. Я отримав це, запустивши алгоритм з eval функцією, встановленим, щоб ігнорувати інші евристики, і розглядати тільки монотонність.

A perfectly monotonic 2048 board

Гладкості

Вищезгадані евристичні одиниці прагнуть створювати структури, в яких сусідні плитки зменшуються у вартості, але, звичайно, для того, щоб об'єднати, сусідні плитки мають бути однаковими. Тому евристична гладкість просто вимірює різницю в вартості сусідніх плиток, намагаючись мінімізувати цей підрахунок.

Коментатор на Hacker News дав цікава формалізація цієї ідеї в термінах теорії графів.

Ось знімок екрана ідеально гладкої сітки з люб'язністю це чудова пародійна вилка.

A perfectly smooth 2048 board

Безкоштовні плитки

І нарешті, існує штраф за те, що занадто мало вільних плиток, оскільки варіанти можуть швидко закінчуватися, коли ігрова панель стає надто стиснутою.

І це все! Пошук за ігровим простором під час оптимізації цих критеріїв дає надзвичайно високу продуктивність. Однією з переваг використання загальним підходом, подібним до цієї, а не явно кодованої стратегії переміщення, є те, що алгоритм часто може знайти цікаві та несподівані рішення. Якщо ви подивитеся, що це запустить, він часто зробить дивовижні, але ефективні кроки, як раптово перемикання стіни або кута, на якій вона стікає.

Редагувати:

Ось демонстрація сили такого підходу. Я відокремлював цінність плитки (тому він продовжував йти після досягнення 2048), і ось найкращий результат після восьми випробувань.

4096

Так, це 4096 поряд з 2048 роком. =) Це означає, що тричі досягнуто невловимого плитки 2048 на одній дошці.


1224
2018-03-13 20:04



Ви можете ставитися до комп'ютера, розмістивши "2" та "4" плитки як "противника". - Wei Yen
@WeiYen Звичайно, але враховуючи це, проблема minmax не є вірною логіці гри, оскільки комп'ютер розміщує плитки випадковим чином з певною ймовірністю, а не навмисне мінімізує оцінку. - koo
Незважаючи на те, що AI випадковим розміщенням плиток, мета не втрачати. Пощастило те ж саме, що противник вибирає найгірший крок для вас. Частка "min" означає, що ви намагаєтеся грати консервативно, щоб не було жодних жахливих кроків, які вам не пощастило б. - FryGuy
Я мав ідею створити вилку 2048 року, де комп'ютер замість розміщення 2 та 4 випадково використовує ваш АІ, щоб визначити, де розмістити значення. Результат: абсолютна неможливість. Можна спробувати тут: sztupy.github.io/2048-Hard - SztupY
@ SztupY Ух, це зло. Нагадує мені qntm.org/hatetris Hatetris, який також намагається помістити твір, який покращить вашу ситуацію. - Patashu


EDIT: Це наївний алгоритм, що моделює процес свідомого людського свідомості, і отримує дуже слабкі результати в порівнянні з АІ, який шукає всі можливості, оскільки воно виглядає лише на одному шаблоні вперед. Він був представлений на початку термінів відповіді.

Я поліпшив алгоритм і побив гру! Це може виникнути з-за простого невдачі, близького до кінця (ви змушені рухатися вниз, що ніколи не слід робити, а плитка з'являється там, де повинна бути найвища точка). Просто спробуйте залишити верхній рядок, так що рухати вліво не розбити шаблон), але в основному в кінцевому підсумку ви маєте фіксовану частину та мобільну частину, щоб грати. Це ваша мета:

Ready to finish

Це модель, яку я вибрала за умовчанням.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Вибраний кут є довільним, ви ніколи не натискаєте одну клавішу (заборонене переміщення), і якщо ви це зробите, ви знову натискаєте протилежне і намагаєтеся його виправити. Для майбутніх плиток модель завжди сподівається, що наступна випадкова плитка буде 2 і відображатиметься на протилежній стороні поточної моделі (тоді як перша рядок неповна, у нижньому правому куті, після завершення першого рядка, внизу ліворуч кут)

Тут іде алгоритм. Близько 80% виграє (здається, завжди можна виграти з більш "професійними" методами AI, я не впевнений у цьому, хоча і.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Кілька вказівників на відсутні кроки. Тут: model change

Модель змінилася завдяки удачі бути ближче до очікуваної моделі. Модель, яку намагається досягти AI, є

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

І ланцюг, щоб потрапити туди стало:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

The O представляти заборонені простори ...

Тоді він натискатиме право, потім знову, потім знову (праворуч або вгорі залежно від того, де створив 4), після чого продовжить ланцюг, поки не отримає:

Chain completed

Отже, тепер модель і ланцюг повертаються до:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

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

Enter image description here

Тут модель і ланцюжок:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Коли йому вдасться досягти 128, він отримує цілий ряд знову:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

119
2018-03-12 16:05



execute move with best score як ви можете оцінити кращий результат з можливих наступних держав? - Khaled.K
евристичний визначається в evaluateResult ви в основному намагаєтеся максимально наблизитися до найкращого сценарію. - Daren
@ Дарен Я чекаю вашої докладної специфіки - ashu
@ashu Я працюю над цим, несподівані обставини залишили мене без часу, щоб закінчити це. Тим часом я поліпшив алгоритм, і тепер він вирішує це 75% часу. - Daren
Те, що мені дуже подобається у цій стратегії, полягає в тому, що я можу використати його під час гри вручну, це дало мені до 37 тисяч очок. - Cephalopod


Я зацікавився ідеєю AI для цієї гри, що містить немає жорсткого кодування інтелекту (тобто немає евристики, функціонування і т.д.). ПІ повинен "знаю" тільки правила гри, і "здогадатися" гра в гру. Це на відміну від більшості індивідуальних інтерфейсів (наприклад, у цій темі), де гра - суттєва груба сила, керована цільовою функцією, що відображає людське розуміння гри.

Алгоритм А.І.

Я знайшов простий, але дивно хороший алгоритм гри: Щоб визначити наступний крок для заданої плати, AI грає в пам'ять, використовуючи випадкові ходи поки гра закінчиться. Це робиться кілька разів під час відстеження кінцевої оцінки гри. Потім середня оцінка кінця за стартовий рух розраховується. Початковий рух із найвищим середнім рахунком кінцевої позиції вибирається як наступний крок.

При кожному переміщенні лише 100 операцій (тобто в іграх пам'яті), AI досягає 2048 плитки в 80% випадків, а 4096 плиток - у 50% випадків. Використовуючи 10000 циклів, ви отримуєте 2048 плитки 100%, 70% для 4096 плиток та близько 1% для плитки 8192.

Подивіться в дії

Найкращий досягнутий показник показано тут:

best score

Цікавий факт про цей алгоритм полягає в тому, що, хоча ігри з випадковими іграми несподівано досить погані, вибір найкращого (або найменш поганого) руху веде до дуже хорошої гри: типова ІІ гра може досягти 7000 балів і останні 3000 рухів, проте У випадкових ігрових іграх у пам'яті з будь-якої заданої позиції в середньому дорівнює 340 додаткових балів приблизно в 40 додаткових рухах перед смертю. (Ви можете це побачити самостійно, запустивши AI та відкривши налагоджену консоль.)

Цей графік ілюструє цю точку: блакитна лінія показує рейтинг борту після кожного переміщення. Червона лінія показує алгоритм найкраще довільна оцінка кінцевої гри з цієї позиції. По суті, червоні значення "тягнуть" сині значення до них вгору, оскільки вони є найкращими уявленнями алгоритму. Цікаво побачити, що червона лінія є лише трохи вище синьої лінії в кожній точці, але синя лінія продовжує зростати все більше і більше.

scoring graph

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

Шукаючи пізніше, я знайшов, що цей алгоритм може бути класифікований як a Чистий пошук дерева Монте-Карло алгоритм

Реалізація та посилання

Спочатку я створив версію JavaScript, яка може бути побачившись у дії тут. Цю версію можна запустити в 100-ти випадках в пристойний час. Відкрийте консоль для додаткової інформації. (джерело)

Пізніше, для того, щоб грати навколо деяких більше, я використав @ nneonneo високо оптимізовану інфраструктуру та впровадив мою версію в C ++. Ця версія дозволяє до 100000 балів за переміщення і навіть 1000000, якщо у вас є терпіння. Наведено інструкції з будівництва. Вона працює в консолі, а також має пульт дистанційного керування для відтворення веб-версії. (джерело)

Результати

Дивно, але збільшення кількості запусків не суттєво покращує гру. Здається, ця стратегія обмежується приблизно в 80 000 точках з 4096 плитки та всіх менших, дуже близько до досягнення 8192 плитки. Збільшення числа пробігів від 100 до 100000 збільшується шанси від досягнення цієї межі ліміту (від 5% до 40%), але не прориваючи його.

Запуск 10000 працює з тимчасовим збільшенням до 1000000 біля критичних позицій, вдалося зламати цей бар'єр менш як 1% разів, досягнувши максимального значення 129892 і 8192 черепиці.

Поліпшення

Після впровадження цього алгоритму я спробував багато поліпшень, включаючи використання мінімальних або максимальних балів або комбінацію мінімумів, макс та середньої частоти. Я також намагався використовувати глибину: замість того, щоб намагатися K бігати за переміщення, я намагався K рухається за один хід список заданої довжини (наприклад, "вгору, вгору, ліворуч") і вибравши перший крок кращого списку переміщень.

Пізніше я реалізував дерево, яке враховувало умовну ймовірність того, що ви зможете грати після певного переміщення.

Проте жодна з цих ідей не продемонструвала ніякої реальної переваги перед простою першою ідеєю. Я залишив код для цих ідей, прокоментував у коді C ++.

Я додав "Глибокий пошук" механізм, який тимчасово збільшив число виконання до 1000000, коли який-небудь із завдань вдалося випадково досягти наступної найвищої плитки. Це дозволило поліпшити час.

Мені було б цікаво почути, чи є у кого-небудь інші ідеї вдосконалення, які підтримують незалежність домену AI.

2048 варіанти та клони

Просто для веселощів, я також реалізував AI як букмарклет, підключившись до елементів управління. Це дозволяє АІ працювати з оригінальною грою і багато його варіантів.

Це можливо завдяки доменній самостійності ІІ. Деякі варіанти досить відмінні, такі як гексагональний клон.


114
2018-05-25 09:25



+1 Як студент AI я знайшов це дійсно цікаве. Поглянемо на це вільний час. - Isaac
Це дивно! Я просто витратив години на оптимізацію ваг для хорошої евристичної функції для expecttimax, і я реалізую це через 3 хвилини, і це повністю розбиває його. - Brendan Annable
Красиве використання симуляції Монте-Карло. - nneonneo
Дивлячись на цю гру, ви закликаєте до просвітління. Це вражає всі евристики, але воно працює. Вітаю! - Stéphane Gourichon
Безперечно, найцікавіше рішення тут. - shebaw


Я копіюю тут вміст a пост в моєму блозі


Рішення, яке я пропоную, дуже просте та легко реалізується. Хоча, він досяг 131040. Отримано кілька тестів алгоритму виступу.

Score

Алгоритм

Евристичний алгоритм скорингу

Припущення, на якому грунтується мій алгоритм, досить просте: якщо ви хочете досягти більшої оцінки, плата повинна бути максимально охайною. Зокрема, оптимальна установка дається лінійним і монотонним послідовністю зменшення значень плитки. Ця інтуїція дасть вам також верхню межу для значення черепиці: s де n - кількість плитки на дошці.

(Там є можливість досягти 131072 плитки, якщо 4-плитка випадково сформована замість 2-плитки, коли це необхідно)

Два способи організації плати показані на наступних зображеннях:

enter image description here

Для того, щоб забезпечити розподіл плиток у монотонному порядку зменшення, коефіцієнт іг обчислюється як сума лінеаризованих значень на дошці, помножена на значення геометричної послідовності з загальним співвідношенням r <1.

s

s

Можна одночасно оцінити кілька лінійних шляхів, остаточна оцінка буде максимальною оцінкою будь-якого шляху.

Правило прийняття рішення

Реалізація правил рішення не є досить розумною, тут представлений код у Python:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Реалізація мінімакс або Expectiminimax безумовно покращить алгоритм. Очевидно більше Складне правило вирішення сповільниться алгоритму, і це вимагатиме деякого часу для реалізації. Я спробую здійснити мінімакс в найближчому майбутньому. (перебування налаштовано)

Орієнтир

  • T1 - 121 тест - 8 різних шляхів - r = 0,125
  • Т2 - 122 випробування - 8 різних шляхів - r = 0,25
  • Т3 - 132 випробування - 8 різних шляхів - r = 0,5
  • T4 - 211 тест - 2-різні шляхи - r = 0,125
  • T5 - 274 проби - 2 різних шляху - r = 0,25
  • T6 - 211 тест - 2-різні шляхи - r = 0,5

enter image description here enter image description here enter image description here enter image description here

У випадку Т2 чотири випробування в десять генерують 4096 плиток із середнім балом s 42000

Код

Код можна знайти на GiHub за наступною посиланням: https://github.com/Nicola17/term2048-AI Вона заснована на term2048 і це написано в Python. Я буду реалізувати більш ефективну версію в C ++ якомога швидше.


88
2018-03-26 22:13



Непогано, ваша ілюстрація дала мені ідею, щоб взяти векторів злиття в оцінку - Khaled.K


Моя спроба використовує очікування, як інші рішення вище, але без бітбордів. Рішення Nneonneo може перевірити 10millions ходів, який становить приблизно глибину 4 з 6 плитками ліворуч і 4 рухами можливо (2 * 6 * 4)4. У моєму випадку, ця глибина займає надто довго, щоб вивчити, я коригую глибину очікуваного пошуку в залежності від кількості вільних плиткових залишків:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Бали дощок обчислюються з вагою сумою квадрата кількості вільних плиток та точкового продукту 2D сіткою з таким:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

який змушує організувати плитку впорядкованій формі у вигляді змії з верхньої лівої плитки.

Код нижче або jsbin:

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Не впевнений, чому у цього немає більше оновлень. Це дійсно ефективно для простоти. - David Greydanus
Спасибі, запізненна відповідь, і вона виконує не дуже добре (майже завжди в [1024, 8192]), функція «вартість / статистика» потребує більшої роботи - caub
Як ви важили порожні простори? - David Greydanus
Це просто cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid) і ми намагаємося максимально збільшити цю вартість - caub
Це потребує набагато більше Upvotes! Великий кодекс! - Smartis


Я думаю, що знайшов алгоритм, який працює дуже добре, оскільки я часто досягаю десятків відсотків, моє особисте краще становить близько 16000. Моє рішення не спрямоване на збереження більшої кількості в куті, але щоб зберегти його у верхньому рядку.

Будь ласка, перегляньте код нижче:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

25
2018-03-12 18:57



Я провів 100 000 ігор, які перевіряли це проти тривіальної циклічної стратегії "вгору, вправо, вгору, вліво ..." (і якщо це потрібно). Циклічна стратегія закінчила "середній бал" плитки " 770.6, хоча цього просто вийшло 396.7. У вас є припущення, чому це може бути? Я думаю, що це дуже багато підходів, навіть коли вліво або вправо зливаються набагато більше. - Thomas Ahle
Плитки, як правило, складаються несумісними способами, якщо вони не зміщені в декількох напрямках. Загалом, використовуючи циклічну стратегію, в центрі з'являться великі плитки, які роблять маневр набагато сумуючими. - bcdan


Я є автором контролера 2048, який оцінює краще, ніж будь-яка інша програма, згадана в цій темі. Ефективна реалізація контролера доступна на github. В окремий репо існує також код, який використовується для навчання функціонування державного контролера. Метод навчання описаний у папір.

Контролер використовує метод expecttimax з функцією оцінки стану, яка вивчається з нуля (без експертної оцінки 2048) за варіантом часова різниця навчання (методика навчання зміцнення). Функція state-value використовує функцію n-tuple мережа, що в основному є зваженою лінійною функцією шаблонів, що спостерігаються на дошці. Вона задіяла більше, ніж 1 млрд. Ваг, загалом.

Продуктивність

На 1 рух / с: 609104 (В середньому 100 ігор)

На 10 рухів / с: 589355 (В середньому 300 ігор)

На 3-х поверховому (приблизно 1500 рухів / с): 511759 (В середньому 1000 ігор)

Статистика плитки за 10 кроків / с виглядає наступним чином:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Остання рядок означає наявність даних плиток одночасно на дошці).

Для 3-х слотів:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Однак я ніколи не спостерігав за отриманням плитки 65536.


25
2017-12-21 10:49



Дуже вражаючий результат. Однак, можливо, ви можете оновити відповідь на пояснення (грубо, простими словами ... Я впевнений, що повна інформація буде занадто довга для публікації тут), як ваша програма це досягає? Як у грубому поясненні, як працює алгоритм навчання? - Cedric Mamo
@ CedricMamo: є посилання на github: arxiv.org/abs/1604.05085 - Florian Castellane


Існує вже реалізація AI для цієї гри: тут. Витяг з README:

Алгоритм ітеративний поглиблення глибини першого альфа-бета-пошуку. Функція оцінки намагається зберегти рядки та стовпці одноманітними (або всі зменшуються або збільшуються), а мінімізуючи кількість плиток на сітку.

Існує також обговорення ycombinator про цей алгоритм, який може виявитись корисним.


21
2018-03-13 09:16



Це має бути найпопулярнішою відповіддю, але було б приємно додати більше подробиць щодо реалізації: наприклад, як моделюється ігрова дошка (як графік), використовувана оптимізація (мінімальна різниця між плитки) і т. д. - Alceu Costa