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

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

Представление

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

Чтобы оценить результативность ИИ, я запускал ИИ 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] при перемещении вправо).

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

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

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

Эвристика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ровность

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

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

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

Бесплатные плитки

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

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

Редактировать:

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

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

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

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 как букмарклет , подключив его к элементам управления игры. Это позволяет ИИ работать с оригинальной игрой и многими ее вариантами .

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

РЕДАКТИРОВАТЬ: Это наивный алгоритм, моделирующий сознательный мыслительный процесс человека, и дает очень слабые результаты по сравнению с ИИ, который ищет все возможности, так как он смотрит только вперед на одну плитку. Он был представлен в начале срока ответа.

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

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

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Представляют запрещенные места ...

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

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

 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

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

Решение, которое я предлагаю, очень просто и легко реализуемо. Тем не менее, он достиг 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, несомненно, улучшит алгоритм. Очевидно, что более сложное правило принятия решений замедлит алгоритм и потребует некоторого времени для его реализации. Я постараюсь реализовать минимаксную реализацию в ближайшем будущем. (Следите за обновлениями)

эталонный тест

• 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. Я буду реализовывать более эффективную версию в C ++ как можно скорее.

Моя попытка использует 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>

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

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

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

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

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

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

Алгоритм

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)

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

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

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

Я только что попробовал свою минимаксную реализацию с альфа-бета-отсечкой с отсечкой глубины дерева поиска в 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 )

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

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

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

Моя реализация игры немного отличается от реальной игры тем, что новая плитка всегда равна 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

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

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

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

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

так далее...

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