Jaki jest optymalny algorytm dla gry 2048?

Niedawno natknąłem się na grę 2048 . Łączysz podobne płytki, przesuwając je w jednym z czterech kierunków, aby utworzyć „większe” płytki. Po każdym ruchu, nowa dachówka pojawia się losowo pustej pozycji o wartości albo 2albo 4. Gra kończy się, gdy wszystkie pola są wypełnione i nie ma ruchów, które mogłyby scalić kafelki lub utworzysz kafelek o wartości 2048.

Po pierwsze, muszę osiągnąć dobrze określoną strategię, aby osiągnąć cel. Pomyślałem więc o napisaniu do tego programu.

Mój obecny algorytm:

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
}

Co robię to w dowolnym momencie, postaram się połączyć płytki z wartościami 2i 4, że to, staram się mieć 2i 4płytki, jako minimum, jak to możliwe. Jeśli spróbuję w ten sposób, wszystkie inne kafelki zostaną automatycznie scalone, a strategia wydaje się dobra.

Ale kiedy faktycznie używam tego algorytmu, dostaję tylko około 4000 punktów przed zakończeniem gry. Maksymalna liczba punktów AFAIK to nieco ponad 20 000 punktów, czyli znacznie więcej niż mój obecny wynik. Czy istnieje lepszy algorytm niż powyższy?

Opracowałem sztuczną inteligencję 2048 za pomocą optymalizacji expectimax , zamiast wyszukiwania minimax używanego przez algorytm @ ovolve. AI po prostu wykonuje maksymalizację dla wszystkich możliwych ruchów, a następnie oczekiwanie na wszystkie możliwe odrodzenia płytek (ważone prawdopodobieństwem płytek, tj. 10% dla 4 i 90% dla 2). O ile mi wiadomo, nie można przycinać optymalizacji expectimax (z wyjątkiem usuwania rozgałęzień, które są niezwykle mało prawdopodobne), dlatego zastosowany algorytm to starannie zoptymalizowane wyszukiwanie metodą brutalnej siły.

Wydajność

AI w swojej domyślnej konfiguracji (maksymalna głębokość wyszukiwania 8) zajmuje od 10 ms do 200 ms, aby wykonać ruch, w zależności od złożoności pozycji planszy. Podczas testowania AI osiąga średnią szybkość ruchu wynoszącą 5-10 ruchów na sekundę w trakcie całej gry. Jeśli głębokość wyszukiwania jest ograniczona do 6 ruchów, sztuczna inteligencja może z łatwością wykonać ponad 20 ruchów na sekundę, co stanowi ciekawe spojrzenie .

Aby ocenić wydajność punktacji AI, uruchomiłem AI 100 razy (podłączony do gry w przeglądarce za pomocą pilota). Dla każdego kafelka przedstawiamy proporcje gier, w których ten kafelek został osiągnięty przynajmniej raz:

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

Minimalny wynik we wszystkich seriach wynosił 124024; maksymalny osiągnięty wynik to 794076. Mediana wyniku to 387222. AI nigdy nie udało się uzyskać płytki 2048 (więc nigdy nie przegrała gry nawet raz na 100 gier); w rzeczywistości osiągnął płytkę 8192 przynajmniej raz w każdym biegu!

Oto zrzut ekranu z najlepszym biegiem:

Ta gra wymagała 27830 ruchów w ciągu 96 minut, czyli średnio 4,8 ruchów na sekundę.

Realizacja

Moje podejście koduje całą płytkę (16 wpisów) jako pojedynczą 64-bitową liczbę całkowitą (gdzie kafelki to nybbles, tj. 4-bitowe fragmenty). Na komputerze 64-bitowym umożliwia to przejście całej płyty w rejestrze jednego komputera.

Operacje przesunięcia bitów służą do wyodrębnienia poszczególnych wierszy i kolumn. Pojedynczy wiersz lub kolumna jest liczbą 16-bitową, więc tabela o rozmiarze 65536 może kodować transformacje, które działają w jednym wierszu lub kolumnie. Na przykład ruchy są implementowane jako 4 wyszukiwania do wstępnie obliczonej „tabeli efektów ruchu”, która opisuje, w jaki sposób każdy ruch wpływa na pojedynczy wiersz lub kolumnę (na przykład tabela „ruch w prawo” zawiera wpis „1122 -> 0023” opisujący, w jaki sposób wiersz [2,2,4,4] staje się rzędem [0,0,4,8] po przesunięciu w prawo).

Punktacja odbywa się również przy użyciu wyszukiwania w tabeli. Tabele zawierają wyniki heurystyczne obliczone dla wszystkich możliwych wierszy / kolumn, a wynikowy wynik dla tablicy jest po prostu sumą wartości tabeli dla każdego wiersza i kolumny.

Ta reprezentacja planszy, wraz z podejściem do wyszukiwania ruchu i punktacji na stole, pozwala AI na przeszukiwanie ogromnej liczby stanów gry w krótkim czasie (ponad 10 000 000 stanów gry na sekundę na jednym rdzeniu mojego laptopa z połowy 2011 roku).

Samo oczekiwanieimax jest zakodowane jako wyszukiwanie rekurencyjne, które na przemian obejmuje etapy „oczekiwania” (testowanie wszystkich możliwych lokalizacji i wartości odradzania się kafelków i ważenie ich zoptymalizowanych wyników według prawdopodobieństwa każdej możliwości) oraz etapy „maksymalizacji” (testowanie wszystkich możliwych ruchów) i wybierając ten z najlepszym wynikiem). Wyszukiwanie drzewa kończy się, gdy zobaczy poprzednio widzianą pozycję (przy użyciu tabeli transpozycji ), gdy osiągnie zdefiniowany limit głębokości lub osiągnie stan planszy, który jest bardzo mało prawdopodobny (np. Został osiągnięty poprzez uzyskanie 6 „4” płytek w rzędzie od pozycji początkowej). Typowa głębokość wyszukiwania to 4-8 ruchów.

Heurystyka

Do kierowania algorytmu optymalizacji w kierunku korzystnych pozycji stosuje się kilka heurystyk. Precyzyjny wybór heurystyki ma ogromny wpływ na wydajność algorytmu. Różne heurystyki są ważone i łączone w wynik pozycyjny, który określa, jak „dobra” jest dana pozycja tablicy. Wyszukiwanie optymalizacyjne będzie miało na celu maksymalizację średniego wyniku wszystkich możliwych pozycji na planszy. Rzeczywisty wynik, jak pokazuje gra, nie jest wykorzystywany do obliczania wyniku na planszy, ponieważ jest on zbyt ciężki na korzyść łączenia płytek (gdy opóźnione łączenie może przynieść dużą korzyść).

Początkowo użyłem dwóch bardzo prostych heurystyk, dających „bonusy” dla otwartych kwadratów i posiadających duże wartości na krawędzi. Te heurystyki działały całkiem dobrze, często osiągając 16384, ale nigdy nie osiągając 32768.

Petr Morávek (@xificurk) wziął moją sztuczną inteligencję i dodał dwie nowe heurystyki. Pierwsza heurystyka była karą za posiadanie niemonotonicznych wierszy i kolumn, które rosły wraz ze wzrostem rang, zapewniając, że niemonotoniczne rzędy małych liczb nie będą silnie wpływać na wynik, ale niemonotoniczne rzędy dużych liczb znacznie zranią wynik. Druga heurystyka policzyła liczbę potencjalnych połączeń (sąsiadujących równych wartości) oprócz otwartych przestrzeni. Te dwie heurystyki posłużyły do ​​popchnięcia algorytmu w kierunku tablic monotonicznych (łatwiejszych do scalenia) oraz w kierunku pozycji tablic z dużą ilością połączeń (zachęcając go do wyrównania połączeń tam, gdzie to możliwe, aby uzyskać większy efekt).

Ponadto Petr zoptymalizował także heurystyczne wagi, stosując strategię „metaoptymalizacji” (przy użyciu algorytmu zwanego CMA-ES ), gdzie same wagi zostały dostosowane, aby uzyskać najwyższy możliwy średni wynik.

Skutki tych zmian są niezwykle znaczące. Algorytm przeszedł od osiągnięcia kafelka 16384 około 13% czasu do osiągnięcia go w 90% przypadków, a algorytm zaczął osiągać 32768 w 1/3 czasu (podczas gdy stara heurystyka nigdy nie produkowała kafelka 32768) .

Wierzę, że jest jeszcze miejsce na poprawę heurystyki. Ten algorytm zdecydowanie nie jest jeszcze „optymalny”, ale wydaje mi się, że jest już dość blisko.

To, że sztuczna inteligencja osiąga kafelek 32768 w ponad jednej trzeciej swoich gier, jest ogromnym kamieniem milowym; Z zaskoczeniem usłyszę, czy jakikolwiek ludzki gracz osiągnął 32768 w oficjalnej grze (tj. Bez użycia narzędzi takich jak zapisywanie stanu lub cofanie). Myślę, że płytka 65536 jest w zasięgu ręki!

Możesz wypróbować sztuczną inteligencję dla siebie. Kod jest dostępny na https://github.com/nneonneo/2048-ai .

Jestem autorem programu AI, o którym wspominali inni w tym wątku. Możesz zobaczyć AI w akcji lub przeczytać źródło .

Obecnie program osiąga około 90% wygranej w javascript w przeglądarce na moim laptopie, biorąc pod uwagę około 100 milisekund czasu myślenia na ruch, więc chociaż nie jest idealny (jeszcze!), Działa całkiem dobrze.

Ponieważ gra jest dyskretną przestrzenią stanów, doskonałą informacją, turową grą, taką jak szachy i warcaby, zastosowałem te same metody, które sprawdziły się w tych grach, a mianowicie wyszukiwanie minimax z przycinaniem alfa-beta . Ponieważ istnieje już wiele informacji na temat tego algorytmu, porozmawiam tylko o dwóch głównych heurystykach, których używam w funkcji oceny statycznej i które formalizują wiele intuicji wyrażonych tutaj przez innych ludzi.

Monotoniczność

Ta heurystyka stara się zapewnić, że wartości płytek zwiększają się lub maleją zarówno w lewo / w prawo, jak i w górę / w dół. Tylko ta heurystyka oddaje intuicję, o której wspominało wielu innych, że płytki o wyższych wartościach powinny być skupione w rogu. Zazwyczaj zapobiega osieroceniu płytek o mniejszej wartości i utrzymuje porządek na planszy, z mniejszymi płytkami kaskadującymi się i wypełniającymi większe płytki.

Oto zrzut ekranu idealnie monotonicznej siatki. Osiągnąłem to, uruchamiając algorytm z ustawioną funkcją eval, aby zignorować inne heurystyki i rozważyć tylko monotoniczność.

Gładkość

Powyższa heurystyka ma tendencję do tworzenia struktur, w których sąsiadujące płytki tracą na wartości, ale oczywiście w celu scalenia sąsiadujące płytki muszą mieć tę samą wartość. Dlatego heurystyka gładkości mierzy tylko różnicę wartości między sąsiadującymi płytkami, próbując zminimalizować tę liczbę.

Komentator Hacker News przedstawił interesującą formalizację tego pomysłu pod względem teorii grafów.

Oto zrzut ekranu idealnie gładkiej siatki, dzięki uprzejmości tego doskonałego widelca do parodii .

Darmowe kafelki

I wreszcie, grozi kara za posiadanie zbyt małej liczby darmowych płytek, ponieważ opcje mogą się szybko skończyć, gdy plansza stanie się zbyt ciasna.

I to wszystko! Przeszukiwanie przestrzeni gry przy jednoczesnej optymalizacji tych kryteriów daje niezwykle dobrą wydajność. Jedną z zalet korzystania z takiego uogólnionego podejścia zamiast z wyraźnie zakodowaną strategią przenoszenia jest to, że algorytm często może znaleźć interesujące i nieoczekiwane rozwiązania. Jeśli patrzysz, jak biegnie, często wykona zaskakujące, ale skuteczne ruchy, na przykład nagle zmienia ścianę lub narożnik, na którym opiera się.

Edytować:

Oto demonstracja siły tego podejścia. Odblokowałem wartości płytek (więc kontynuowałem po osiągnięciu 2048) i oto najlepszy wynik po ośmiu próbach.

Tak, to 4096 obok 2048. =) Oznacza to, że osiągnął nieuchwytną płytkę 2048 trzy razy na tej samej planszy.

Zainteresowałem się pomysłem sztucznej inteligencji dla tej gry nie zawierającej zakodowanej inteligencji (tj. Bez heurystyki, funkcji oceniania itp.). AI powinna „znać” tylko zasady gry i „rozgryźć” rozgrywkę. Jest to w przeciwieństwie do większości AI (takich jak te w tym wątku), w których gra jest w zasadzie brutalną siłą sterowaną przez funkcję punktacji reprezentującą ludzkie rozumienie gry.

Algorytm AI

Znalazłem prosty, ale zaskakująco dobry algorytm gry: aby określić następny ruch dla danej planszy, AI gra w pamięć za pomocą losowych ruchów, aż gra się skończy. Odbywa się to kilka razy, śledząc końcowy wynik gry. Następnie obliczany jest średni wynik końcowy na ruch początkowy . Początkowy ruch z najwyższym średnim wynikiem końcowym jest wybierany jako następny ruch.

Przy zaledwie 100 przebiegach (tj. W grach pamięciowych) na ruch, AI osiąga płytkę 2048 80% razy, a płytkę 4096 50% razy. Korzystanie z 10000 przebiegów daje kafelek 2048 w 100%, 70% w kafelku 4096 i około 1% w kafelku 8192.

Zobacz to w akcji

Najlepszy osiągnięty wynik pokazano tutaj:

Ciekawym faktem na temat tego algorytmu jest to, że chociaż gry losowe są zaskakująco złe, wybranie najlepszego (lub najmniej złego) ruchu prowadzi do bardzo dobrej gry: Typowa gra AI może osiągnąć 70000 punktów i ostatnie 3000 ruchów, jednak gry losowe w pamięci z dowolnej pozycji dają średnio 340 dodatkowych punktów w około 40 dodatkowych ruchach przed śmiercią. (Możesz to zobaczyć, uruchamiając AI i otwierając konsolę debugowania).

Ten wykres ilustruje ten punkt: niebieska linia pokazuje wynik planszy po każdym ruchu. Czerwona linia pokazuje najlepszy wynik algorytmu w końcowej fazie gry z tej pozycji. Zasadniczo, czerwone wartości „przyciągają” niebieskie wartości w górę w ich kierunku, ponieważ są najlepszym przypuszczeniem algorytmu. Interesujące jest to, że czerwona linia znajduje się nieco powyżej niebieskiej linii w każdym punkcie, ale niebieska linia wciąż rośnie.

Wydaje mi się dość zaskakujące, że algorytm nie musi właściwie przewidywać dobrej gry, aby wybrać ruchy, które go wytwarzają.

Przeszukując później odkryłem, że ten algorytm może zostać sklasyfikowany jako algorytm czystego wyszukiwania drzewa Monte Carlo .

Wdrożenie i linki

Najpierw stworzyłem wersję JavaScript, którą można zobaczyć tutaj w akcji . Ta wersja może uruchomić setki uruchomień w przyzwoitym czasie. Otwórz konsolę, aby uzyskać dodatkowe informacje. ( źródło )

Później, aby się trochę pobawić, skorzystałem z wysoce zoptymalizowanej infrastruktury @nneonneo i zaimplementowałem swoją wersję w C ++. Ta wersja pozwala na maksymalnie 100000 przebiegów na ruch, a nawet 1000000, jeśli masz cierpliwość. Dostarczone instrukcje budowania. Działa w konsoli i ma również zdalne sterowanie do odtwarzania wersji internetowej. ( źródło )

Wyniki

Zaskakujące jest to, że zwiększenie liczby przebiegów nie poprawia drastycznie gry. Wydaje się, że limit tej strategii wynosi około 80000 punktów w przypadku płytki 4096 i wszystkich mniejszych, bardzo zbliżonych do osiągnięcia płytki 8192. Zwiększenie liczby przebiegów ze 100 do 100000 zwiększa szanse na osiągnięcie tego limitu punktów (z 5% do 40%), ale nie do jego przekroczenia.

Uruchomienie 10000 biegów z tymczasowym wzrostem do 1000000 w pobliżu pozycji krytycznych udało się przełamać tę barierę mniej niż 1% razy, osiągając maksymalny wynik 129892 i płytkę 8192.

Ulepszenia

Po wdrożeniu tego algorytmu wypróbowałem wiele ulepszeń, w tym użycie wyników minimalnych lub maksymalnych lub kombinacji wartości minimalnych, maksymalnych i średnich. Próbowałem także użyć głębokości: Zamiast próbować K ruchów na ruch, próbowałem K ruchów na listę ruchów o danej długości (na przykład „góra, góra, lewo”) i wybrałem pierwszy ruch z listy ruchów z najlepszą punktacją.

Później zaimplementowałem drzewo oceniania, które uwzględniało warunkowe prawdopodobieństwo zagrania ruchu po danej liście ruchów.

Jednak żaden z tych pomysłów nie wykazał żadnej rzeczywistej przewagi nad prostym pierwszym pomysłem. Zostawiłem kod dla tych pomysłów skomentowany w kodzie C ++.

Dodałem mechanizm „Głębokiego wyszukiwania”, który tymczasowo zwiększył liczbę przebiegów do 1000000, gdy którykolwiek z przebiegów zdołał przypadkowo dotrzeć do następnego najwyższego kafelka. To zapewniło poprawę czasu.

Chciałbym usłyszeć, czy ktoś ma inne pomysły na ulepszenia, które utrzymują niezależność AI od domeny.

2048 wariantów i klonów

Dla zabawy zaimplementowałem również AI jako bookmarklet , który kontroluje grę. Umożliwia to AI pracę z oryginalną grą i wieloma jej wariantami .

Jest to możliwe ze względu na niezależny od domeny charakter AI. Niektóre warianty są dość wyraźne, na przykład klon heksagonalny.

EDYCJA: Jest to naiwny algorytm modelujący ludzki świadomy proces myślowy i uzyskuje bardzo słabe wyniki w porównaniu do sztucznej inteligencji, która wyszukuje wszystkie możliwości, ponieważ patrzy tylko o jedną płytkę do przodu. Zostało przesłane wcześnie na osi czasu odpowiedzi.

Udoskonaliłem algorytm i pokonałem grę! Może się nie udać z powodu zwykłego pecha pod koniec (jesteś zmuszony zejść w dół, czego nigdy nie powinieneś robić, a kafelek pojawi się tam, gdzie powinna być najwyższa. Po prostu staraj się zapełnić górny rząd, aby poruszanie się w lewo nie było złamać wzór), ale w gruncie rzeczy ostatecznie masz stałą i ruchomą część do zabawy. To jest twój cel:

To jest model, który wybrałem domyślnie.

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

Wybrany róg jest dowolny, w zasadzie nigdy nie naciskasz jednego klawisza (zabroniony ruch), a jeśli to zrobisz, naciskasz ponownie przeciwnie i próbujesz go naprawić. W przypadku przyszłych kafelków model zawsze oczekuje, że następny losowy kafelek będzie równy 2 i pojawi się po przeciwnej stronie niż obecny model (podczas gdy pierwszy rząd jest niekompletny, w prawym dolnym rogu, po zakończeniu pierwszego rzędu, w lewym dolnym rogu kąt).

Oto algorytm. Około 80% wygrywa (wydaje się, że zawsze można wygrać dzięki bardziej „profesjonalnym” technikom sztucznej inteligencji, ale nie jestem tego pewien).

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

Kilka wskazówek na temat brakujących kroków. Tutaj:

Model zmienił się ze względu na szczęście zbliżenia się do oczekiwanego modelu. Model, który stara się osiągnąć AI

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

I łańcuch, aby się tam dostać, stał się:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

OStanowią zakazane przestrzenie ...

Więc naciska w prawo, następnie w prawo ponownie, a następnie (w prawo lub w górę w zależności od tego, gdzie utworzono 4), a następnie przejdzie do zakończenia łańcucha, dopóki nie uzyska:

Teraz model i łańcuch powracają do:

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

Drugi wskaźnik, miał pecha i zajęto jego główne miejsce. Prawdopodobnie zawiedzie, ale nadal może to osiągnąć:

Oto model i łańcuch:

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

Gdy uda mu się dotrzeć do 128, zyskuje cały rząd:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

Tutaj kopiuję treść posta na moim blogu

Rozwiązanie, które proponuję, jest bardzo proste i łatwe do wdrożenia. Chociaż osiągnął wynik 131040. Przedstawiono kilka testów wydajności algorytmu.

Algorytm

Heurystyczny algorytm punktacji

Założenie, na którym opiera się mój algorytm, jest dość proste: jeśli chcesz osiągnąć wyższy wynik, tablica musi być utrzymywana tak schludnie, jak to możliwe. W szczególności optymalną konfigurację zapewnia liniowy i monotoniczny malejący porządek wartości płytek. Ta intuicja da ci również górną granicę wartości kafelka: gdzie n jest liczbą kafelków na planszy.

(Istnieje możliwość dotarcia do kafelka 131072, jeśli 4-kafelek jest generowany losowo zamiast 2-kafelka w razie potrzeby)

Dwa możliwe sposoby organizacji tablicy pokazano na następujących obrazach:

Aby wymusić uporządkowanie płytek w monotonicznym porządku malejącym, wynik obliczono jako sumę zlinearyzowanych wartości na planszy pomnożonych przez wartości sekwencji geometrycznej o wspólnym stosunku r <1.

Jednocześnie można ocenić kilka ścieżek liniowych, końcowy wynik będzie maksymalnym wynikiem dowolnej ścieżki.

Reguła decyzyjna

Zaimplementowana reguła decyzyjna nie jest całkiem sprytna, kod w Pythonie jest przedstawiony tutaj:

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

Implementacja minmax lub Expectiminimax z pewnością poprawi algorytm. Oczywiście bardziej wyrafinowana reguła decyzyjna spowolni algorytm i zajmie to trochę czasu. W najbliższej przyszłości spróbuję implementacji minimax. (bądźcie czujni)

Reper

• T1 - 121 testów - 8 różnych ścieżek - r = 0,125
• T2 - 122 testy - 8 różnych ścieżek - r = 0,25
• T3 - 132 testy - 8 różnych ścieżek - r = 0,5
• T4 - 211 testów - 2 różne ścieżki - r = 0,125
• T5 - 274 testy - 2 różne ścieżki - r = 0,25
• T6 - 211 testów - 2 różne ścieżki - r = 0,5

W przypadku T2 cztery testy na dziesięć generują płytkę 4096 ze średnią oceną 42000

Kod

Kod można znaleźć na GiHub pod następującym linkiem: https://github.com/Nicola17/term2048-AI Opiera się na term2048 i jest napisany w Pythonie. Jak najszybciej zaimplementuję bardziej wydajną wersję w C ++.

Moja próba wykorzystuje expectimax jak inne rozwiązania powyżej, ale bez bitboardów. Rozwiązanie Nneonneo może sprawdzić 10 milionów ruchów, co jest w przybliżeniu głębokością 4 z 6 pozostałymi płytkami i możliwymi 4 ruchami (2 * 6 * 4) ⁴ . W moim przypadku odkrywanie tej głębokości trwa zbyt długo, dostosowuję głębokość wyszukiwania expectimax do liczby wolnych płytek:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Punkty na planszach są obliczane na podstawie sumy ważonej kwadratu liczby wolnych płytek i iloczynu punktowego siatki 2D z tym:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

co zmusza do układania płytek w sposób malejący w rodzaju węża z lewej górnej płytki.

kod poniżej lub na 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>

Jestem autorem kontrolera 2048, który osiąga lepsze wyniki niż jakikolwiek inny program wymieniony w tym wątku. Wydajna implementacja kontrolera jest dostępna na github . W osobnym repozytorium znajduje się również kod używany do szkolenia funkcji oceny stanu kontrolera. Metodę szkolenia opisano w artykule .

Kontroler wykorzystuje wyszukiwanie expectimax z funkcją oceny stanu wyuczoną od zera (bez wiedzy fachowej człowieka 2048) przez wariant uczenia się różnic czasowych (technika uczenia wzmacniającego). Funkcja stanu-wartości wykorzystuje sieć n-krotną , która jest w zasadzie ważoną funkcją liniową wzorców obserwowanych na płycie. Obejmował ponad 1 miliard ciężarówŁącznie .

Wydajność

Przy 1 ruchach / s: 609104 (średnio 100 gier)

Przy 10 ruchach / s: 589355 (średnio 300 gier)

Przy 3 warstwach ( około 1500 ruchów / s): 511759 (średnio 1000 gier)

Statystyki kafelków dla 10 ruchów / s są następujące:

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

(Ostatnia linia oznacza posiadanie podanych płytek jednocześnie na planszy).

Dla 3 warstw:

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

Jednak nigdy nie zauważyłem, aby uzyskał płytkę 65536.

Wydaje mi się, że znalazłem algorytm, który działa całkiem dobrze, ponieważ często osiągam wyniki powyżej 10000, a mój osobisty najlepszy wynik to około 16000. Moje rozwiązanie nie ma na celu utrzymania największych liczb w rogu, ale utrzymanie go w górnym rzędzie.

Zobacz poniższy kod:

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

Jest już implementacja AI w tej grze tutaj . Fragment README:

Algorytm polega na iteracyjnym pogłębianiu głębokości pierwszego wyszukiwania alfa-beta. Funkcja oceny stara się zachować monotoniczność wierszy i kolumn (wszystkie zmniejszają się lub zwiększają), jednocześnie minimalizując liczbę płytek na siatce.

W Hacker News toczy się także dyskusja na temat tego algorytmu, który może okazać się przydatny.

Algorytm

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

    choose the maximum evaluation
}

Ocena

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)

Szczegóły oceny

128 (Constant)

Jest to stała używana jako podstawa i do innych zastosowań, takich jak testowanie.

+ (Number of Spaces x 128)

Więcej przestrzeni uelastycznia stan, mnożymy przez 128 (co jest medianą), ponieważ siatka wypełniona 128 ścianami jest optymalnym stanem niemożliwym.

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

Tutaj oceniamy twarze, które mają możliwość scalenia, oceniając je wstecz, kafelek 2 staje się wartościowy 2048, podczas gdy kafelek 2048 jest oceniany 2.

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

Tutaj nadal musimy sprawdzać wartości skumulowane, ale w mniejszym stopniu, który nie zakłóca parametrów elastyczności, więc mamy sumę {x w [4,44]}.

+ (Number of possible next moves x 256)

Stan jest bardziej elastyczny, jeśli ma większą swobodę możliwych przejść.

+ (Number of aligned values x 2)

Jest to uproszczone sprawdzenie możliwości połączenia w tym stanie bez uprzedzeń.

Uwaga: Stałe można dostosować.

To nie jest bezpośrednia odpowiedź na pytanie OP, to jest więcej rzeczy (eksperymentów), które próbowałem dotychczas rozwiązać ten sam problem i uzyskałem pewne wyniki i mam pewne spostrzeżenia, którymi chcę się podzielić, jestem ciekawy, czy możemy mieć jakieś dalsze spostrzeżenia z tego.

Właśnie wypróbowałem implementację minimax z przycinaniem alfa-beta z odcięciem głębokości drzewa wyszukiwania przy 3 i 5. Próbowałem rozwiązać ten sam problem dla siatki 4x4 jako zadanie projektu dla kursu edX ColumbiaX: CSMM.101x Sztuczna inteligencja ( AI) .

Zastosowałem wypukłą kombinację (wypróbowałem różne wagi heurystyczne) kilku heurystycznych funkcji oceny, głównie z intuicji i z omówionych powyżej:

1. Monotoniczność
2. Dostępne wolne miejsce

W moim przypadku odtwarzacz komputerowy jest całkowicie losowy, ale mimo to przyjąłem ustawienia przeciwnika i zaimplementowałem agenta AI jako maksymalnego gracza.

Mam siatkę 4x4 do gry.

Obserwacja:

Jeśli przypiszę zbyt dużą wagę pierwszej funkcji heurystycznej lub drugiej funkcji heurystycznej, oba przypadki, które uzyska gracz AI, są niskie. Grałem z wieloma możliwymi przypisaniami wagi do funkcji heurystycznych i wybrałem wypukłą kombinację, ale bardzo rzadko gracz AI jest w stanie zdobyć 2048. W większości przypadków zatrzymuje się na 1024 lub 512.

Próbowałem również heurystykę narożną, ale z jakiegoś powodu pogarsza to wyniki, a jakaś intuicja, dlaczego?

Ponadto próbowałem zwiększyć wartość graniczną głębokości wyszukiwania z 3 do 5 (nie mogę jej zwiększyć, ponieważ wyszukiwanie miejsca przekracza dozwolony czas nawet przy przycinaniu) i dodałem jeszcze jedną heurystykę, która patrzy na wartości sąsiadujących płytek i daje więcej punktów, jeśli można je połączyć, ale nadal nie jestem w stanie zdobyć 2048.

Myślę, że lepiej będzie użyć Expectimax zamiast minimax, ale nadal chcę rozwiązać ten problem tylko z minimax i uzyskać wysokie wyniki, takie jak 2048 lub 4096. Nie jestem pewien, czy czegoś mi brakuje.

Poniższa animacja pokazuje kilka ostatnich kroków gry rozgrywanej przez agenta AI z graczem komputerowym:

Wszelkie spostrzeżenia będą naprawdę bardzo pomocne, z góry dzięki. (To jest link do mojego postu na blogu do artykułu: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-game-with-computer / i film na youtube: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

Poniższa animacja pokazuje kilka ostatnich etapów rozgrywki, w których agent gracza AI może uzyskać 2048 punktów, tym razem dodając również wartość heurystyczną wartości bezwzględnej:

Poniższe liczby pokazują drzewo gry zbadane przez agenta AI gracza, zakładając, że komputer jest przeciwnikiem tylko na jeden krok:

Napisałem solver 2048 w Haskell, głównie dlatego, że teraz uczę się tego języka.

Moja implementacja gry nieco różni się od faktycznej gry, ponieważ nowy kafelek to zawsze „2” (zamiast 90% 2 i 10% 4). I że nowy kafelek nie jest losowy, ale zawsze pierwszy dostępny z lewego górnego rogu. Ten wariant jest również znany jako Det 2048 .

W rezultacie ten solver jest deterministyczny.

Użyłem wyczerpującego algorytmu, który faworyzuje puste kafelki. Działa dość szybko na głębokości 1-4, ale na głębokości 5 robi się dość wolno, około 1 sekundy na ruch.

Poniżej znajduje się kod implementujący algorytm rozwiązywania. Siatka jest reprezentowana jako tablica liczb całkowitych o długości 16. Ocenianie odbywa się po prostu przez zliczenie liczby pustych kwadratów.

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

Myślę, że jest dość udany ze względu na swoją prostotę. Wynik, który osiąga, rozpoczynając od pustej siatki i rozwiązując na głębokości 5, jest następujący:

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

Game Over

Kod źródłowy można znaleźć tutaj: https://github.com/popovitsj/2048-haskell

Ten algorytm nie jest optymalny do wygrania gry, ale jest dość optymalny pod względem wydajności i ilości potrzebnego kodu:

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

Wiele innych odpowiedzi wykorzystuje sztuczną inteligencję do kosztownego wyszukiwania możliwych przyszłości, heurystyki, uczenia się i tym podobnych. Są imponujące i prawdopodobnie słuszne, ale chciałbym wnieść kolejny pomysł.

Modeluj strategię, z której korzystają dobrzy gracze.

Na przykład:

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

Czytaj kwadraty w kolejności pokazanej powyżej, aż następna wartość kwadratów będzie większa niż bieżąca. Stwarza to problem próby połączenia kolejnej płytki o tej samej wartości z tym kwadratem.

Aby rozwiązać ten problem, istnieją 2 sposoby poruszania się, które nie zostały pozostawione ani gorzej, a zbadanie obu możliwości może natychmiast ujawnić więcej problemów, tworzy to listę zależności, z których każdy wymaga rozwiązania innego problemu w pierwszej kolejności. Wydaje mi się, że mam ten łańcuch lub, w niektórych przypadkach, drzewo zależności wewnętrznie przy podejmowaniu decyzji o kolejnym ruchu, szczególnie gdy utknęłam.

Kafelek wymaga scalenia z sąsiadem, ale jest zbyt mały: Scal z innym sąsiadem.

Większy kafelek w drodze: Zwiększ wartość mniejszego otaczającego kafelka.

itp...

Całe podejście będzie prawdopodobnie bardziej skomplikowane niż to, ale niewiele bardziej skomplikowane. Może to być mechaniczny brak odczuć, obciążeń, neuronów i głębokich poszukiwań możliwości. Drzewo możliwości po prostu musi być wystarczająco duże, aby w ogóle potrzebować rozgałęzienia.