Какой оптимальный алгоритм для игры 2048 г.

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




Answer 1 nneonneo


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

Performance

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

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

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

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

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

32768 tile, score 794076

Эта партия заняла 27830 ходов за 96 минут,или в среднем 4,8 хода в секунду.

Implementation

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

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

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

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

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

Heuristics

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

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

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

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

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

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


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

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




Answer 2 ovolve


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

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

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

Monotonicity

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

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

A perfectly monotonic 2048 board

Smoothness

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

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

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

A perfectly smooth 2048 board

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

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

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

Edit:

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

4096

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




Answer 3 Ronenz


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

алгоритм искусственного осеменения

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

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

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

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

best score

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

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

scoring graph

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

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

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

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

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

Results

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

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

Improvements

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

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

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

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

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

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

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

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




Answer 4 Daren


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

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

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

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



Answer 5 Nicola Pezzotti


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


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

Score

Algorithm

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

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

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

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

enter image description here

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

s

s

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

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

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

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

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

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

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

Реализация 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 here enter image description here enter image description here enter image description here

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

Code

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