Каков оптимальный алгоритм для игры 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 очков, что намного больше, чем мой текущий счет. Есть ли лучший алгоритм, чем выше?

14   1777  

14 ответов:

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

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

AI в своей конфигурации по умолчанию (максимальная глубина поиска 8) занимает от 10 мс до 200 мс для выполнения хода, в зависимости от сложности положения доски. При тестировании ИИ достигает средней скорости перемещения 5-10 ходов в секунду в течение всей игры. Если глубина поиска ограничена 6 ходами, ИИ может легко выполнить 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-битное целое число (где плитки-это nybbles, т. е. 4-битные куски). На 64-разрядной машине это позволяет передавать всю плату вокруг в одном машинном регистре.

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

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

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

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

эвристика

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

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

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

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

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

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


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

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

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

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

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

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

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

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

A perfectly monotonic 2048 board

плавность

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

комментатор на Хакер Новости дал интересное оформление этой идеи в терминах теории графов.

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

A perfectly smooth 2048 board

Бесплатные Игры

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

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

Edit:

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

4096

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

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

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

Ready to finish

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

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

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

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

 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

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

AI Алгоритм

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

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

посмотреть его в действии

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

best score

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

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

scoring graph

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

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

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

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

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

результаты

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

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

улучшение

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

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

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

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

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

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

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

я копирую здесь содержимое a пост в моем блоге


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

Score

алгоритм

эвристический алгоритм подсчета очков

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

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

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

enter image description here

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

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

реализация 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

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

в случае T2, четыре теста из десяти генерируют плитку 4096 со средним баллом s 42000

код

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

моя попытка использует expectimax, как и другие решения выше, но без битбордов. Решение Nneonneo может проверить 10 миллионов ходов, что составляет примерно глубину 4 с 6 плитками слева и 4 возможных хода (2*6*4)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]]

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

код ниже или 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>

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

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

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

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

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

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

алгоритм

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)

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

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

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

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

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

  1. монотонности
  2. Свободное Место

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

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

наблюдения:

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

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

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

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

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

enter image description here

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

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

enter image description here

следующие цифры показывают игру исследовано агентом игрока AI предполагая, что компьютер является противником всего за один шаг:

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

Я написал 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

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

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

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

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

например:

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

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

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


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

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

etc...


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