2048-ci il oynayan üçün optimal alqoritm nədir?

Bu yaxınlarda mən 2048-ci il matçına qaçdım . Siz "böyük" plitələr etmək üçün onları dörd istiqamətdən hər hansı birinə hərəkət edərək bu plitələr birləşdirirsiniz. Hər bir hərəkətdən sonra yeni bir parça 2 və ya 4 dəyəri ilə təsadüfi boş bir yerdə görünür. Oyun bütün sahələr dolduqda və plitələr birləşdirə biləcək hərəkətlər yoxdursa və ya 2048 dəyərində bir 2048 bitir.

Birincisi, müəyyən bir məqsəd nailiyyət strategiyasına riayət etmək lazımdır. Beləliklə, onun üçün bir proqram yazmağı düşünürdüm.

Mənim cari alqoritmim:

 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 } 

Nə etdiyimi, bir nöqtədə, plitələrimi 24 dəyərləri ilə birləşdirməyə çalışacağam, yəni 24 plitənin mümkün qədər az olmasına çalışıram. Bunu cəhd edərsənsə, bütün digər plitələr avtomatik olaraq birləşir və strategiya yaxşı görünür.

Amma əslində bu alqoritmi istifadə edərkən, oyunun bitməsinə qədər 4000 bal ala bilərəm. AFAIK maksimum balları yalnız 20.000-dən çox baldır, bu mənim cari hesabımdan daha çoxdur. Daha yüksək bir alqoritm varmı?

1815
12 марта '14 в 8:37 2014-03-12 08:37 nitish712 12 mart 'da saat 14: 00-da başlayacaq
@ 14 cavab

Mən, @ovolve alqoritminin istifadə etdiyi minimax axtarışın əvəzinə, optimimax optimallaşdırılması ilə 2048 AI-ni işləyib hazırladım. AI sadəcə mümkün olan bütün hərəkətlərə maksimum dərəcədə nail olur, sonra bütün mümkün plastinka görünüşlərini gözləyir (ağırlıqlı plitələr, yəni 10% 4 və 90% üçün 2). Bilirəm ki, gözləmələrin optimallaşdırılması optimallaşdırıla bilməz (istisna olduqca çətin olan filiallar istisna olmaqla), beləliklə istifadə olunan alqoritm kobud güc üçün diqqətlə optimallaşdırılmış bir axtarışdır.

Performans

AI, default konfiqurasiyasında (maksimum axtarış dərinliyi 8) rəhbərliyin mürəkkəbliyindən asılı olaraq hərəkəti başa çatdırmaq üçün 10 ms-dən 200 ms-ə çatır. Test zamanı AI oyun boyunca saniyədə 5-10 hərəkətin orta sürətinə çatır. Axtarış dərinliyi 6 hərəkət ilə məhdudlaşdıqda, AI asanlıqla saniyədə 20 + hərəkətini asanlıqla həyata keçirə bilər ki, bu da maraqlı bir görüntü yaratmağa imkan verir .

Aİ-nin effektivliyini qiymətləndirmək üçün AI-ni 100 dəfə işə saldım (uzaqdan idarə etməklə oyun brauzerinə qoşulmuşdur). Hər bir kafel üçün bu kafelin ən azı bir dəfə əldə olunduğu oyunların nisbəti verilir:

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

Bütün işlərin minimum hesabı 124024 idi; maksimum nəticə 794076 idi. Orta hesab 387222 idi. AI heç vaxt 2048 plitə almadı (belə ki, 100 oyunda bir dəfə hətta oyununu heç vaxt itirmədi); Əslində, hər koşuda ən azı bir dəfə 8192 plitə çatdı!

Ən yaxşı çalışmanın bir ekran görüntüsü:

2019

1183
19 марта '14 в 10:22 2014-03-19 10:22 cavab 19 mart '14 'də saat 10:22' də verildi. 2014-03-19 10:22

Mən başqalarının bu işdə göstərdiyi AI proqramının müəllifiyəm. AI-ni hərəkətə keçirmək və ya mənbəyi oxuya bilərsiniz.

Hazırda proqram mənim noutbukda brauzerdə javascript üzrə qazanan sürətin təxminən 90% -ə çatır, beləliklə mükəmməl olmur (bax!), Baxmayaraq ki, bu, çox yaxşı işləyir, baxmayaraq ki, öz növbəsində təxminən 100 millisecond düşünmə vaxtı verir.

Oyun ayrı bir dövlət məkanı, mükəmməl məlumat, şahmat və dama kimi addım-addım oyun olduğundan, bu oyunlar üzərində işləmək üçün sübut edilən eyni metodlardan istifadə edirəm, yəni alfa-beta əkilməsi ilə minimax axtarışı . Bu alqoritmdə artıq çox məlumat olduğundan, mən statik qiymətləndirmə funksiyasından istifadə etdiyim və digər insanların burada ifadə etdiyin çoxsaylı intuisiyaları formalaşdırdığınız iki əsas üslub haqqında danışıram.

monotoniya

Bu heuristik, plitələrin dəyərlərini hər iki istiqamətdə artıra və ya aşağıya / sağa və yuxarı / aşağıya endirdiklərinə əmin etməyə çalışır. Yalnız bu heuristik bir çoxu söyləyən sezgi əks etdirir ki, daha qiymətli plitələr bir küncdə qruplaşdırılmalıdır. Bu, bir qayda olaraq, yetim qiymətli kağızları daha kiçik dəyərlərlə qarşısını alır və şuranı çox təşkil edir və kiçik plitələr cascaded və böyük plitələr ilə doldurulur.

Burada tamamilə monoton bir şəffaf bir ekran görüntüsüdür. Bunu digər heuristikaları görməməzliklə qiymətləndirmə funksiyası ilə bir alqoritmi işləyib və təkcə monotonizm hesab edirəm.

2019

1233
13 марта '14 в 23:04 2014-03-13 23:04 cavab 13 mart 2014-cü il saat 23: 33-də verilir. 2014-03-13 23:04

Mən bu oyun üçün AI ideyası ilə maraqlandım, orada hard-kodlu kəşfiyyat yoxdur (yəni heuristika, qol və s.). Aİ yalnız oyun qaydalarını "bilmək" və oyunu "anlamaq" lazımdır. Bu, bir oyunun anlayışını əks etdirən bir qol funksiyası ilə idarə olunan gameplay, əsasən qüvvətli bir qüvvə olduğu Aİ-lərin əksəriyyətinə (məsələn, bu mövzuya) ziddir.

AI alqoritmi

Sadə, lakin təəccüblü yaxşı oyun alqoritmini tapdım: müəyyən bir board üçün sonrakı hərəkətləri müəyyən etmək üçün, oyun AI oyunun bitməsinə qədər təsadüfi hərəkətlərdən istifadə edərək oyunu yaddaşda oynayır. Oyunun sonunda hesabı izlərkən bir neçə dəfə edilir. Sonra ilk növbədə orta yekun nöqtə hesablanır. Növbəti addım ən yüksək orta nəticə ilə başlama hərəkətidir.

100 hərəkətlə (yəni, yaddaş ilə oyunlarda) AI hərəkət üçün, halların 80% -i 2048 plitələrə və halların 50% -ində 4096 plitələrə çatır. 10.000 qaçış istifadə edərkən 2048, 100% alır, 70% 4096 alır və təxminən 1% 8192 alır.

Hərəkətə baxın

Ən yaxşı nəticə burada göstərilib:

2019

125
25 мая '14 в 12:25 2014-05-25 12:25 Cavab 25-27 may tarixində saat 12: 25-də Ronenzə verilir

EDIT :. Bu, insan şüurlu düşüncə prosesini simulyasiya edən sadəlövh bir alqoritmdir və bütün imkanlar axtaran Aİ ilə müqayisədə çox zəif nəticə verir, çünki o, yalnız qabaqda bir qabağa baxır. Cavabın erkən mərhələsində təqdim edildi.

Alqoritmi aydınlaşdırdım və oyunu döydüm! Bu sona yaxın sadə bir uğursuzluqdan ötəri uğursuz ola bilər (aşağı hərəkət etmək məcburiyyətindəsiniz, heç vaxt etməməli olmalısınız və kafel ən yüksək olduğu yerdə görünür). şablon), ancaq əsasən oyun üçün sabit bir hissə və mobil hissə var. Bu sizin məqsədi:

2019

122
ответ дан Daren 12 марта '14 в 19:05 2014-03-12 19:05

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


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

2019

93
ответ дан Nicola Pezzotti 27 марта '14 в 1:13 2014-03-27 01:13

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

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

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

 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; } 
36
ответ дан caub 03 марта '15 в 8:35 2015-03-03 08:35

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

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

Performans

В 1 ход/с: 609104 (100 игр в среднем)

В 10 ходов/сек: 589355 (300 игр в среднем)

При 3-слойном (около 1500 ходов/с): 511759 (в среднем 1000 игр)

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

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

(Последняя строка означает наличие заданных фрагментов одновременно на плате).

Для 3-ply:

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

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

30
ответ дан cauchy 21 дек. '15 в 13:49 2015-12-21 13:49

Я думаю, что нашел алгоритм, который работает достаточно хорошо, так как я часто достигаю десятков тысяч, а мое личное преимущество - около 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); } 
27
ответ дан Vincent Lecrubier 12 марта '14 в 21:57 2014-03-12 21:57

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

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

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

25
ответ дан baltazar 13 марта '14 в 12:16 2014-03-13 12:16

Alqoritmi

 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) 

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

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

23
ответ дан Khaled.K 12 марта '14 в 23:15 2014-03-12 23:15

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

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

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

2019

ответ дан Sandipan Dey 07 марта '17 в 0:37 2017-03-07 00:37

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

9
ответ дан wvdz 04 апр. '14 в 3:49 2014-04-04 03:49

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

  if(can move neither right, up or down) direction = left else { do { direction = random from (right, down, up) } while(can not move in "direction") } 
6
ответ дан API-Beast 15 марта '14 в 0:53 2014-03-15 00:53

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

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

Məsələn:

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

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

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


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

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

və s ..


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

4
ответ дан alan2here 10 авг. '15 в 17:39 2015-08-10 17:39

Другие вопросы по меткам или Задайте вопрос