Каков оптимальный алгоритм игры 2048?

Ответ 1

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

Производительность

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

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

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

Минимальный балл по всем прогонам составил 124024; максимальный результат составил 794076. Средний балл - 387222. ИИ никогда не получал 2048 плит (поэтому он никогда не терял игру даже один раз в 100 играх); на самом деле, она достигла 8192 плитки хотя бы один раз в каждом прогоне!

Вот скриншот лучшего запуска:

В этой игре было 27830 ходов за 96 минут или в среднем 4,8 ходов в секунду.

Реализация

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

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

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

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

Сам поиск expectimax кодируется как рекурсивный поиск, который чередуется с шагами "ожидания" (тестирует все возможные места и значения для появления и определения значений тайлов и взвешивает их оптимизированные оценки по вероятности каждой возможности) и шаги "максимизации" (тестирование) все возможные ходы и выбор одного с лучшим счетом). Поиск дерева заканчивается, когда он видит ранее увиденную позицию (используя таблицу транспонирования ), когда она достигает предопределенного предела глубины или когда она достигает состояния платы, которая очень маловероятно (например, это было достигнуто путем получения 6 "4" плиток подряд от начальной позиции). Типичная глубина поиска - 4-8 ходов.

эвристика

Несколько эвристик используются для направления алгоритма оптимизации на выгодные позиции. Точный выбор эвристики оказывает огромное влияние на производительность алгоритма. Различные эвристики взвешиваются и объединяются в позиционный балл, который определяет, насколько "хороша" данная позиция на борту. Затем поиск по оптимизации нацелен на максимизацию среднего балла всех возможных позиций на борту. Фактический балл, как показано в игре, не используется для вычисления оценки доски, поскольку он слишком сильно взвешен в пользу слияния плиток (когда отложенное слияние может принести большую пользу).

Вначале я использовал две очень простые эвристики, предоставляя "бонусы" для открытых квадратов и для больших значений на краю. Эти эвристики выполнялись довольно хорошо, часто достигая 16384, но никогда не добирались до 32768.

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

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

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

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

То, что ИИ достигает 32768 плит в более чем одной трети своих игр, является огромной вехой; Я буду удивлен, если услышу, достигли ли какие-либо игроки в игре 32768 в официальной игре (т.е. Без использования таких инструментов, как savestates или cancel). Я думаю, что плитка 65536 находится в пределах досягаемости!

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

Ответ 2

Я автор программы AI, которую другие упомянули в этой теме. Вы можете просмотреть AI в action или прочитать источник.

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

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

монотонности

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

Вот скриншот совершенно монотонной сетки. Я получил это, запустив алгоритм с установленной функцией eval, чтобы игнорировать другие эвристики и рассматривать только монотонность.

Плавность

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

Комментарии от Hacker News дали интересную формализацию этой идеи в терминах теории графов.

Вот скриншот совершенно гладкой сетки, любезно предоставленной этой отличной вилкой для пародий.

Свободные плитки

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

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

Изменить:

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

Да, это 4096 вместе с 2048. =) Это означает, что трижды проделала неуловимую плиту 2048 на одной доске.

Ответ 3

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

AI алгоритм

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

При 100 ходах (т.е. в играх с памятью) за ход ИИ достигает 2048 плиток в 80% случаев и 4096 тайлов в 50% случаев. При использовании 10000 прогонов 2048 получает 100%, 70% - 4096 и около 1% - 8192.

Увидеть это в действии

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

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

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

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

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

Реализация и ссылки

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

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

Результаты

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

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

улучшения

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

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

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

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

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

2048 Варианты и Клоны

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

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

Ответ 4

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

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

Это модель, которую я выбрал по умолчанию.

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

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

Здесь идет алгоритм. Около 80% побед (кажется, всегда можно выиграть с более "профессиональными" методами ИИ, я не уверен в этом.)

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)
  }

Несколько указателей на недостающие шаги. Здесь:

Модель изменилась из-за удачи быть ближе к ожидаемой модели. Модель, которую ИИ пытается достичь, - это

 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

O представляют собой запрещенные пробелы...

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

Итак, теперь модель и цепочка вернулись к:

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

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

Здесь модель и цепочка:

  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

Ответ 5

Я копирую здесь содержимое сообщения в моем блоге

Решение, которое я предлагаю, очень просто и легко реализовать. Хотя, он достиг отметки 131040. Представлены несколько эталонных характеристик алгоритма.

Алгоритм

Эвристический алгоритм оценки

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

(Там есть возможность добраться до плитки 131072, если 4-плитка генерируется случайным образом вместо 2-плитки, когда это необходимо)

Два возможных способа организации платы показаны на следующих изображениях:

Чтобы обеспечить координацию плиток в монотонном убывающем порядке, оценка si вычисляется как сумма линеаризованных значений на доске, умноженная на значения геометрической последовательности с общим отношением r < 1.

Несколько линейных путей можно оценить сразу, окончательный счет будет максимальным счетом любого пути.

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

Реализованное правило решения не очень умное, здесь представлен код в 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);

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

Benchmark

• T1 - 121 тест - 8 разных путей - r = 0.125
• T2 - 122 теста - 8-разные пути - r = 0.25
• T3 - 132 теста - 8-разные пути - r = 0.5
• T4 - 211 тесты - 2-разные пути - r = 0.125
• T5 - 274 теста - 2-разные пути - r = 0.25
• T6 - 211 тест - 2-разные пути - r = 0,5

В случае T2 четыре теста из десяти генерируют плиту 4096 со средней оценкой 42000

код

Код можно найти на GiHub по следующей ссылке: https://github.com/Nicola17/term2048-AI Он основан на term2048 и написан на Python. Я как можно скорее реализую более эффективную версию на С++.

Ответ 6

Моя попытка использует expectimax, как и другие решения выше, но без битбордов. Решение Nneonneo может проверять 10 миллионов ходов, что составляет приблизительно 4 глубины, при этом осталось 6 плиток и 4 возможных хода (2 * 6 * 4) ⁴. В моем случае, эта глубина занимает слишком много времени для изучения, я настраиваю глубину поиска expectimax в соответствии с количеством свободных плиток:

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]]

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

код ниже или на github:

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);
updateHint(predict(ai));

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


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(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 {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}

<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

Ответ 7

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

Контроллер использует expectimax-поиск с функцией оценки состояния, полученной с нуля (без экспертизы человека 2048) по варианту временного разностного обучения (метод обучения усилению). Функция state-value использует сеть n-кортежей, которая в основном представляет собой взвешенную линейную функцию шаблонов, наблюдаемых на доске. В нем участвовало более 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-ply:

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

Однако я никогда не видел, чтобы он получал плиту 65536.

Ответ 8

Я думаю, что нашел алгоритм, который работает достаточно хорошо, так как я часто достигаю десятков тысяч, а мое личное преимущество - около 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);
}

Ответ 9

Существует уже реализация ИИ для этой игры здесь. Выдержка из README:

Алгоритм итеративного углубления глубины первого альфа-бета поиска. Функция оценки пытается сохранить монотонность строк и столбцов (либо уменьшая, либо увеличивая), минимизируя при этом количество элементов в сетке.

В Hacker News также обсуждается этот алгоритм, который может оказаться полезным.

Ответ 10

Алгоритм

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Оценка

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Сведения об оценке

128 (Constant)

Это константа, используемая как базовая строка и для других целей, таких как тестирование.

+ (Number of Spaces x 128)

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

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Здесь мы оцениваем грани, у которых есть возможность получить слияние, оценивая их назад, плитка 2 становится значащей 2048, в то время как плитка 2048 оценивается 2.

+ Sum of other faces { log(face) x 4 }

В этом случае нам еще нужно проверить значения в стеке, но в меньшей степени это не прервет параметры гибкости, поэтому мы имеем сумму {x в [4,44]}.

+ (Number of possible next moves x 256)

Состояние более гибкое, если оно имеет больше свободы возможных переходов.

+ (Number of aligned values x 2)

Это упрощенная проверка возможности слияния внутри этого состояния, не задумываясь.

Примечание: константы могут быть изменены..

Ответ 11

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

Я только что попробовал свою минимаксную реализацию с альфа-бета-отсечкой с ограничением глубины дерева поиска в 3 и 5. Я пытался решить ту же проблему для сетки 4x4, что и проектное задание для курса edX ColumbiaX: CSMM.101x Artificial Intelligence ( AI)

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

1. Монотонность
2. Свободное место доступно

В моем случае, компьютерный проигрыватель абсолютно случайный, но я все же принял противоборствующие настройки и реализовал агент AI-игрока в качестве максимального игрока.

У меня есть сетка 4х4 для игры.

Наблюдение:

Если я назначу слишком много весов первой эвристической функции или второй эвристической функции, в обоих случаях оценки, которые получает AI-игрок, низкие. Я играл со многими возможными назначениями веса для эвристических функций и брал выпуклую комбинацию, но очень редко ИИ-игрок мог набрать 2048. В большинстве случаев он останавливается на 1024 или 512.

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

Кроме того, я попытался увеличить отсечку глубины поиска с 3 до 5 (я не могу увеличить ее больше, так как поиск, пространство которой превышает разрешенное время даже с обрезкой), и добавил еще одну эвристику, которая смотрит на значения соседних плиток и дает больше очков, если они сливаются, но я все равно не могу получить 2048.

Я думаю, что будет лучше использовать Expectimax вместо минимакса, но все же я хочу решить эту проблему только с минимаксом и получить высокие оценки, такие как 2048 или 4096. Я не уверен, что я что-то упускаю.

Ниже на анимации показаны последние несколько шагов игры, в которую агент ИИ играл с компьютерным игроком:

Любые идеи будут действительно очень полезны, спасибо заранее. (Это ссылка на мой пост в блоге для статьи: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-игра-с-компьютером/ и видео на YouTube: https://www.youtube.com/watch?v=VnVFilfZ0r4)

Следующая анимация показывает последние несколько шагов игры, в которых агент ИИ-игрока мог набрать 2048 баллов, на этот раз добавив также эвристику абсолютного значения:

На следующих рисунках показано игровое дерево, исследуемое агентом ИИ игрока, который за один шаг рассматривал компьютер как противника:

Ответ 12

Я написал 2048-решатель в Haskell, главным образом потому, что сейчас изучаю этот язык.

Моя реализация игры немного отличается от реальной игры тем, что новая плитка всегда "2" (а не 90% 2 и 10% 4). И то, что новая плитка не случайна, но всегда первая из доступных слева вверху. Этот вариант также известен как Det 2048.

Как следствие, этот решатель детерминирован.

Я использовал исчерпывающий алгоритм, который поддерживает пустые плитки. Он работает довольно быстро для глубины 1-4, но на глубине 5 он замедляется примерно на 1 секунду за ход.

Ниже приведен код, реализующий алгоритм решения. Сетка представлена ​​как массив из 16-ти целых чисел. И подсчет очков производится просто путем подсчета количества пустых квадратов.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Я считаю, что это довольно успешно для его простоты. Результат, который он достигает при запуске с пустой сеткой, и решение на глубине 5:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Исходный код можно найти здесь: https://github.com/popovitsj/2048-haskell

Ответ 13

Этот алгоритм не является оптимальным для выигрыша игры, но он достаточно оптимален с точки зрения производительности и количества необходимого кода:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

Ответ 14

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

Моделируйте стратегию, которую используют хорошие игроки игры.

Например:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

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

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

Плитка требует слияния с соседом, но слишком мала: слейте другого соседа с этим.

Более крупная плитка в пути: Увеличьте значение меньшего окружающего плитка.

и т.д...

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