Pytanie Jaki jest optymalny algorytm gry 2048?


Niedawno natknąłem się na grę 2048. Połącz podobne płytki, przesuwając je w dowolnym z czterech kierunków, aby uzyskać "większe" kafelki. Po każdym ruchu nowy żeton pojawia się w losowej pustej pozycji z wartością dowolnego z nich 2 lub 4. Gra kończy się, gdy wszystkie pola są wypełnione i nie ma ruchów, które mogą łączyć płytki, lub tworzysz płytkę o wartości 2048.

Po pierwsze, muszę przestrzegać dobrze określonej strategii, aby osiągnąć cel. Pomyślałem więc o napisaniu programu na ten temat.

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
}

To, co robię, w każdym momencie, spróbuję scalić płytki z wartościami 2 i 4to znaczy, próbuję mieć 2 i 4 płytki, możliwie jak najmniej. Jeśli spróbuję tego w ten sposób, wszystkie inne kafelki automatycznie się łączą i strategia wydaje się dobra.

Ale kiedy faktycznie używam tego algorytmu, otrzymuję około 4000 punktów, zanim gra się zakończy. Maksymalna liczba punktów AFAIK wynosi nieco ponad 20 000 punktów, czyli znacznie więcej niż mój obecny wynik. Czy istnieje lepszy algorytm niż powyższy?


1755
2018-03-12 05:37


pochodzenie


To może pomóc! ov3y.github.io/2048-AI - cegprakash
@ Nitish712 przy okazji, twój algorytm jest chciwy, ponieważ masz choose the move with large number of merges które szybko prowadzą do lokalnej optymalności - Khaled.K
@ 500-InternalServerError: If ja mieli zaimplementować sztuczną inteligencję z przycinaniem drzewek w fazie alfa-beta, zakładałoby to, że nowe bloki są umieszczone przeciwstawnie. Jest to najgorsze przypuszczenie, ale może być przydatne. - Charles
Zabawne rozproszenie, gdy nie masz czasu, aby osiągnąć wysoki wynik: staraj się uzyskać jak najniższy wynik. Teoretycznie jest to naprzemiennie 2s i 4s. - Mark Hurd
Dyskusja na temat legitymacji tego pytania można znaleźć w meta: meta.stackexchange.com/questions/227266/... - Jeroen Vannevel


Odpowiedzi:


Opracowałem użycie AI 2048 expectimax optymalizacja zamiast wyszukiwania minimax używanego przez algorytm @ ovolve. AI po prostu wykonuje maksymalizację nad wszystkimi możliwymi ruchami, po której następuje oczekiwanie na wszystkie możliwe spawny płytki (ważone prawdopodobieństwem płytek, tj. 10% dla 4 i 90% dla 2). O ile mi wiadomo, nie jest możliwe przycięcie optymalizacji expectimax (z wyjątkiem usuwania gałęzi, które są wyjątkowo mało prawdopodobne), a więc zastosowanym algorytmem jest starannie zoptymalizowane wyszukiwanie siły brutalnej.

Wydajność

AI w domyślnej konfiguracji (maksymalna głębokość wyszukiwania 8) zajmuje od 10 do 200 ms, aby wykonać ruch, w zależności od złożoności pozycji planszy. Podczas testów, AI osiąga średnią prędkość ruchu 5-10 ruchów na sekundę w ciągu całej gry. Jeśli głębokość przeszukiwania jest ograniczona do 6 ruchów, sztuczna inteligencja może z łatwością wykonać 20+ ruchów na sekundę, co dla niektórych ciekawe oglądanie.

Aby ocenić wynik działania sztucznej inteligencji, wykonałem sztuczną inteligencję 100 razy (połączenie z grą przeglądarkową za pomocą pilota). Dla każdego kafelka, tutaj są proporcje gier, w których ta płytka została osiągnięta co najmniej raz:

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

Minimalny wynik we wszystkich przebiegach wynosił 124024; maksymalna uzyskana ocena to 794076. Mediana wynosi 387222. SI nigdy nie udało się uzyskać płytki 2048 (więc nigdy nie straciła gry nawet raz w 100 grach); w rzeczywistości osiągnął on 8192 płytki co najmniej raz w każdym biegu!

Oto zrzut ekranu najlepszego uruchomienia:

32768 tile, score 794076

Ta gra trwała 27830 ruchów przez 96 minut, czyli średnio 4.8 ruchów na sekundę.

Realizacja

Moje podejście koduje całą tablicę (16 wpisów) jako pojedynczą 64-bitową liczbę całkowitą (gdzie kafelki są liczbami nijakimi, tj. 4-bitowymi). Na komputerze 64-bitowym umożliwia to przepuszczenie całej karty w jednym rejestrze maszyn.

Operacje przesunięcia bitowego są używane do wyodrębniania poszczególnych wierszy i kolumn. Pojedynczy wiersz lub kolumna to 16-bitowa ilość, 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 odnośniki 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 jest również wykonywana przy użyciu sprawdzania tabeli. Tabele zawierają wyniki heurystyczne obliczone na wszystkich możliwych wierszach / kolumnach, a wynikowy wynik dla tablicy to po prostu suma wartości w tabelach w każdym wierszu i kolumnie.

Ta reprezentacja planszy, wraz z podejściem do wyszukiwania i przemieszczania się, pozwala AI przeszukiwać ogromną liczbę stanów gry w krótkim czasie (ponad 10 000 000 stanów gry na sekundę w jednym rdzeniu mojego laptopa z połowy 2011 roku).

Samo wyszukiwanie expectimax jest kodowane jako rekursywne wyszukiwanie, które zmienia się pomiędzy krokami "oczekiwania" (testowanie wszystkich możliwych miejsc odrodzenia płytki i wartości oraz ważenie ich zoptymalizowanych wyników według prawdopodobieństwa każdej z możliwości) i kroków "maksymalizacji" (testowanie wszystkich możliwych ruchów i wybierając ten, który ma najlepszy wynik). Przeszukiwanie drzewa kończy się, gdy widzi poprzednio widzianą pozycję (używając a tabela transpozycji), gdy osiągnie on zdefiniowany wcześniej limit głębokości lub gdy osiągnie stan płytki, który jest wysoce nieprawdopodobny (np. został osiągnięty przez uzyskanie płytek 6 "4" w rzędzie od pozycji początkowej). Typowa głębokość wyszukiwania to 4-8 ruchów.

Heurystyka

Kilka heurystyk służy do kierowania algorytmu optymalizacji w kierunku korzystnych pozycji. Dokładny wybór heurystyki ma ogromny wpływ na wydajność algorytmu. Różne heurystyki są ważone i łączone w wynik punktowy, który określa, jak "dobra" jest dana pozycja deski. Wyszukiwanie optymalizacji będzie wówczas zmierzało do maksymalizacji średniego wyniku wszystkich możliwych pozycji na planszy. Rzeczywisty wynik, jak pokazuje gra, to nie używany do obliczania wyniku na tablicy, ponieważ jest zbyt mocno obciążony na rzecz łączenia płytek (gdy opóźnione połączenie może przynieść dużą korzyść).

Początkowo użyłem dwóch bardzo prostych heurystyk, nadających "bonusy" dla otwartych kwadratów i mających duże wartości na krawędzi. Heurystyki te działały całkiem nieźle, często osiągając 16384, ale nigdy nie osiągając poziomu 32768.

Petr Morávek (@xificurk) zabrał moją sztuczną inteligencję i dodał dwie nowe heurystyki. Pierwsza heurystyka była karą za posiadanie niemonotonicznych rzędów i kolumn, które zwiększały się wraz ze wzrostem rang, zapewniając, że niemonotoniczne rzędy małych liczb nie wpłynęłyby silnie na wynik, ale niemonotoniczne rzędy dużych liczb poważnie zaszkodziły wynikowi. 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 ​​przesunięcia algorytmu w kierunku płyt monotonicznych (które łatwiej się scalić), a także w kierunku stanowisk z wieloma scaleniami (zachęcając do wyrównania połączeń tam, gdzie to możliwe, aby uzyskać lepszy efekt).

Ponadto Petr również zoptymalizował heurystyczne wagi za pomocą strategii "meta-optymalizacji" (używając algorytmu o nazwie CMA-ES), gdzie same ciężary zostały skorygowane, aby uzyskać najwyższy możliwy średni wynik.

Efekt tych zmian jest niezwykle znaczący. Algorytm przeszedł od osiągnięcia płytki 16384 około 13% czasu do osiągnięcia jej w ponad 90% czasu, a algorytm zaczął osiągać 32768 przez 1/3 czasu (podczas gdy stare heurystyki nigdy nie wyprodukowały płytki 32768) .

Wierzę, że wciąż jest miejsce na polepszenie heurystyk. Ten algorytm zdecydowanie nie jest jeszcze "optymalny", ale wydaje mi się, że zbliża się on do końca.


To, że sztuczna inteligencja osiąga liczbę 32768 w ponad jednej trzeciej swoich gier, jest olbrzymim kamieniem milowym; Zaskoczy mnie informacja, czy któryś z graczy osiągnął 32768 w oficjalnej grze (tzn. Bez użycia narzędzi, takich jak savestates czy cofanie). Myślę, że kafelek 65536 jest w zasięgu!

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


1132
2018-03-19 07:22



@RobL: 2 pojawiają się 90% czasu; 4 pojawiają się w 10% przypadków. To jest w kod źródłowy: var value = Math.random() < 0.9 ? 2 : 4;. - nneonneo
Obecnie przesyłane do Cuda, więc GPU wykonuje pracę na jeszcze większe prędkości! - nimsson
@nneonneo Przekierowałem twój kod z emscripten do javascript i działa całkiem nieźle w przeglądarce teraz! Fajne do obejrzenia, bez potrzeby kompilacji i wszystkiego ... W Firefoksie wydajność jest całkiem dobra ... - reverse_engineer
Teoretyczny limit w siatce 4x4 faktycznie wynosi 131072, a nie 65536. Jednak to wymaga uzyskania 4 w odpowiednim momencie (tj. Cała plansza jest wypełniona po 4 .. 65536 za każdym razem - zajęte 15 pól), a tablica musi zostać ustawiona w tym momencie moment, abyś mógł się połączyć. - Bodo Thiesen
@nneonneo Możesz sprawdzić naszą sztuczną inteligencję, która wydaje się jeszcze lepsza, uzyskując 32% w 60% gier: github.com/aszczepanski/2048 - cauchy


Jestem autorem programu AI, o którym inni wspominali w tym wątku. Możesz zobaczyć sztuczną inteligencję w akcja lub przeczytaj źródło.

Obecnie program osiąga około 90% wskaźnika wygranych działających w javascript w przeglądarce na moim laptopie, biorąc pod uwagę około 100 milisekund czasu myślenia na ruch, więc nie jest doskonały (jeszcze!) Działa całkiem nieźle.

Ponieważ gra to dyskretna przestrzeń stanu, doskonała informacja, turowa gra w szachy i warcaby, użyłem tych samych metod, które sprawdzają się w tych grach, a mianowicie: minimax  Szukaj z przycinanie alfa-beta. Ponieważ istnieje już wiele informacji o tym algorytmie, po prostu omówię dwie główne heurystyki, które używam w funkcja oceny statycznej i które formalizują wiele intuicji wyrażanych przez innych.

Monotoniczność

Ta heurystyczna próba zapewnia, że ​​wartości płytek są albo zwiększane, albo maleją wzdłuż kierunków lewo / prawo i góra / dół. Ta heurystyczna wersja sama przechwytuje intuicję, o której wspominało wielu innych, że kafelki o wyższej wartości powinny być skupione w rogu. Zwykle zapobiegnie to osierocaniu płytek o mniejszej wartości i będzie bardzo uporządkowane, a mniejsze płytki będą kaskadować i wypełniać większe płytki.

Oto zrzut ekranu z idealnie monotonicznej siatki. Osiągnąłem to, uruchamiając algorytm z ustawioną funkcją eval, aby zignorować inne heurystyki i brać pod uwagę monotonię.

A perfectly monotonic 2048 board

Gładkość

Powyższa heurystyka ma tendencję do tworzenia struktur, w których sąsiednie kafelki zmniejszają wartość, ale oczywiście w celu scalenia sąsiednie płytki muszą mieć taką samą wartość. Dlatego też heurystyka gładkości mierzy różnicę wartości pomiędzy sąsiadującymi płytkami, starając się zminimalizować tę liczbę.

Powiedział komentator Hacker News interesująca formalizacja tego pomysłu pod względem teorii grafów.

Oto zrzut ekranu z idealnie gładkiej siatki, dzięki uprzejmości to znakomite widowisko parodii.

A perfectly smooth 2048 board

Darmowe kafelki

I na koniec istnieje kara za posiadanie zbyt małej ilości darmowych żetonów, ponieważ opcje szybko się kończą, gdy plansza gry jest zbyt ciasna.

I to wszystko! Przeszukiwanie przestrzeni gry przy jednoczesnej optymalizacji tych kryteriów zapewnia wyjątkowo dobrą wydajność. Jedną z korzyści zastosowania raczej uogólnionego podejścia niż jawnie zakodowanej strategii przenoszenia jest to, że algorytm często znajduje interesujące i nieoczekiwane rozwiązania. Jeśli obejrzysz go, często będzie wykonywał zaskakujące, ale skuteczne ruchy, takie jak nagłe przełączanie się na ścianę lub narożnik, na którym się opiera.

Edytować:

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

4096

Tak, to 4096 wraz z 2048. =) Oznacza to, że trzykrotnie osiągnął nieporęczny kafelek 2048 na tej samej planszy.


1224
2018-03-13 20:04



Możesz traktować komputer umieszczając kafelki "2" i "4" jako "przeciwnika". - Wei Yen
@ WeiYen Pewnie, ale uważając to za problem minmax nie jest wierny logice gry, ponieważ komputer umieszcza kafelki losowo z pewnymi prawdopodobieństwami, zamiast celowo minimalizować wynik. - koo
Nawet jeśli sztuczna inteligencja losowo umieszcza kafelki, celem nie jest przegrana. Pechowe jest to samo, co przeciwnik wybierający najgorszy ruch dla ciebie. Część "min" oznacza, że ​​starasz się grać ostrożnie, aby nie było żadnych okropnych ruchów, które mogłyby doprowadzić do pecha. - FryGuy
Miałem pomysł utworzenia widelca 2048, w którym komputer zamiast umieszczać 2s i 4s losowo wykorzystuje twoją sztuczną inteligencję, aby ustalić, gdzie umieścić wartości. Rezultat: nieprzewidywalność. Można go wypróbować tutaj: sztupy.github.io/2048-Hard - SztupY
@SztupY Wow, to zło. Przypomina mi qntm.org/hatetris Hatetris, który również stara się umieścić element, który poprawi Twoją sytuację w najmniejszym stopniu. - Patashu


EDYTOWAĆ: Jest to naiwny algorytm, modelujący ludzki proces myślowy i uzyskujący bardzo słabe wyniki w porównaniu z sztuczną inteligencją, która przeszukuje wszystkie możliwości, ponieważ wygląda tylko o jeden kafelek przed sobą. Został przesłany na wczesnym etapie harmonogramu odpowiedzi.

Udoskonaliłem algorytm i pokonałem grę! Może się to nie udać z powodu zwykłego pecha pod koniec (jesteś zmuszony do zejścia w dół, którego nigdy nie powinieneś zrobić, a kafelek pojawia się tam, gdzie powinien być twój najwyższy poziom) Po prostu staraj się trzymać górny rząd wypełniony, więc poruszanie się w lewo nie przełamać wzór), ale w zasadzie kończy się to posiadaniem stałej części i części mobilnej do zabawy. To jest twój cel:

Ready to finish

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 arbitralny, w zasadzie nigdy nie naciskasz jednego klawisza (zakazanego ruchu), a jeśli to zrobisz, ponownie naciskasz przeciwnie i próbujesz go naprawić. W przypadku przyszłych płytek model zawsze oczekuje, że kolejna losowa płytka będzie 2 i pojawi się po przeciwnej stronie bieżącego modelu (podczas gdy pierwszy wiersz jest niekompletny, w prawym dolnym rogu, po zakończeniu pierwszego wiersza, w lewym dolnym rogu) kąt).

Oto algorytm. Około 80% wygrywa (wydaje się, że zawsze można wygrać z bardziej "profesjonalnymi" technikami sztucznej inteligencji, 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 change

Model zmienił się ze względu na szczęście bycia bliżej oczekiwanego modelu. Model, który próbuje AI, jest

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

A łańcuchem, który się tam dostał stał się:

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

The O reprezentują zakazane przestrzenie ...

Więc będzie naciskać w prawo, potem znowu w prawo, następnie (w prawo lub w górę, w zależności od miejsca, w którym utworzono 4), a następnie przystąpi do ukończenia łańcucha, aż do momentu:

Chain completed

Teraz model i łańcuch powracają do:

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

Druga wskazówka, miała pecha, a jej główne miejsce zostało zrobione. Prawdopodobnie zakończy się niepowodzeniem, ale nadal może go osiągnąć:

Enter image description here

Oto model i łańcuch:

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

Kiedy uda mu się osiągnąć 128, zyskuje cały rząd, zdobywa się ponownie:

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

119
2018-03-12 16:05



execute move with best score jak możesz ocenić najlepszy wynik z możliwych następnych stanów? - Khaled.K
heurystyka jest zdefiniowana w evaluateResult w zasadzie starasz się zbliżyć do możliwie najlepszego scenariusza. - Daren
@Daren Czekam na twoje szczegółowe informacje - ashu
@ashu Pracuję nad tym, niespodziewane okoliczności opuściły mnie bez czasu, aby to zakończyć. Tymczasem ulepszyłem algorytm i teraz rozwiązuje to 75% czasu. - Daren
To, co naprawdę podoba mi się w tej strategii, to to, że jestem w stanie jej używać podczas ręcznej gry, co pozwoliło mi osiągnąć 37 punktów. - Cephalopod


Zainteresował mnie pomysł AI dla tej gry zawierającej bez zakodowanej inteligencji (tj. bez heurystyki, funkcji oceniania itp.). AI powinna "wiedzieć" tylko zasady gry, i "rozwiązać" gra. Jest to przeciwieństwo większości AI (takich jak te w tym wątku), w których gra jest zasadniczo brutalną siłą kierowaną przez funkcję punktowania reprezentującą ludzkie zrozumienie gry.

Algorytm AI

Znalazłem prosty, ale zaskakująco dobry algorytm gry: Aby ustalić następny ruch dla danej planszy, AI odtwarza grę w pamięci używając losowe ruchy dopóki gra się nie skończy. Odbywa się to kilka razy, jednocześnie śledząc końcowy wynik gry. Następnie średni wynik końcowy za ruch początkowy jest wyliczone. Ruch początkowy z najwyższym średnim wynikiem końcowym jest wybierany jako następny ruch.

Przy zaledwie 100 przebiegach (to znaczy w grach pamięciowych) na jeden ruch, AI osiąga 2048 płytek w 80% razy, a 4096 w 50% razy. Przy użyciu 10000 przebiegów otrzymuje się płytkę 2048 100%, 70% dla płytki 4096 i około 1% dla płytki 8192.

Zobacz to w akcji

Najlepszy osiągnięty wynik jest pokazany tutaj:

best score

Ciekawostką tego algorytmu jest to, że podczas gdy gry losowe nie są zaskakująco złe, wybór 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 losowe gry w pamięci z dowolnej pozycji dają średnio 340 dodatkowych punktów w około 40 dodatkowych ruchów przed śmiercią. (Możesz to zobaczyć samodzielnie, uruchamiając AI i otwierając konsolę debugowania.)

Ten wykres ilustruje ten punkt: Niebieska linia pokazuje wynik płyty po każdym ruchu. Czerwona linia pokazuje algorytm Najlepiej losowy wynik końcowy z tej pozycji. W istocie, czerwone wartości "przyciągają" niebieskie wartości w górę w ich kierunku, ponieważ są to najlepsze przypuszczenia algorytmu. Interesujące jest to, że czerwona linia znajduje się tuż nad niebieską linią w każdym punkcie, ale niebieska linia wciąż wzrasta.

scoring graph

Zaskakujące jest to, że algorytm nie musi właściwie przewidywać dobrej gry, aby wybrać ruchy, które ją produkują.

Wyszukując później, stwierdziłem, że ten algorytm może być sklasyfikowany jako Szukaj w czystym drzewie Monte Carlo algorytm.

Implementacja i linki

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

Później, aby zagrać jeszcze trochę, użyłem wysoce zoptymalizowanej infrastruktury @nneonneo i zaimplementowałem swoją wersję w C ++. Ta wersja pozwala na wykonanie do 100 000 operacji na ruch, a nawet 1000000, jeśli masz cierpliwość. Dostarczone instrukcje budowlane. Działa w konsoli, a także ma pilota do gry w wersji internetowej. (źródło)

Wyniki

Co zaskakujące, zwiększenie liczby biegów nie drastycznie poprawia grę. Wydaje się, że limit tej strategii wynosi około 80000 punktów przy płytce 4096 i wszystkich mniejszych, bardzo blisko osiągnięcia 8192 pola. Zwiększenie liczby serii od 100 do 100000 zwiększa szansa dotarcia do tego limitu punktów (od 5% do 40%), ale nie do przełamania tego.

Uruchomienie 10000 biegów z tymczasowym wzrostem do 1000000 w pobliżu pozycji krytycznych pozwoliło pokonać tę barierę mniej niż 1% razy, osiągając maksymalną liczbę punktów równą 129892 i liczbę 8192.

Ulepszenia

Po wdrożeniu tego algorytmu próbowałem wielu usprawnień, w tym używania minimalnych lub maksymalnych wyników lub kombinacji min, max i avg. Próbowałem też używać głębi: zamiast próbować biegów K na ruch próbowałem K ruchów na ruch lista o określonej długości (na przykład "w górę, w górę, w lewo") i wybierając pierwszy ruch z listy najlepszych wyników.

Później zaimplementowałam drzewo punktacji, które uwzględniało warunkowe prawdopodobieństwo, że można odtwarzać ruch po danej liście ruchów.

Jednak żadna z tych koncepcji nie pokazała żadnej realnej przewagi nad prostym pierwszym pomysłem. Zostawiłem kod dla pomysłów skomentowanych w kodzie C ++.

Dodałem mechanizm "Głębokiego wyszukiwania", który tymczasowo zwiększył liczbę uruchomień do 1000000, gdy którykolwiek z przebiegów przypadkowo dotarł do następnego najwyższego pola. Zapewniło to poprawę czasu.

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

2048 Warianty i klony

Dla zabawy też zaimplementował sztuczną inteligencję jako skryptozakładkę, podłączenie do kontrolek gry. To pozwala AI pracować z oryginalną grą i wiele jego wariantów.

Jest to możliwe z powodu niezależnego od domeny charakteru sztucznej inteligencji. Niektóre warianty są dość wyraźne, np. Klon heksagonalny.


114
2018-05-25 09:25



+1. Jako student AI uznałem to za naprawdę interesujące. Przyjrzymy się temu w czasie wolnym. - Isaac
To jest niesamowite! Właśnie spędziłem godziny optymalizując wagi dla dobrej funkcji heurystycznej dla expectimax i implementuję to w 3 minuty, a to całkowicie psuje. - Brendan Annable
Fajne wykorzystanie symulacji Monte Carlo. - nneonneo
Oglądanie tej gry wymaga oświecenia. To dmucha wszystkie heurystyki, a jednak działa. Gratulacje! - Stéphane Gourichon
Zdecydowanie najciekawsze rozwiązanie tutaj. - shebaw


Kopiuję tutaj treść a zamieścić na moim blogu


Proponowane przeze mnie rozwiązanie jest bardzo proste i łatwe do wdrożenia. Mimo, że osiągnął wynik 131040. Przedstawiono kilka testów wydajności algorytmu.

Score

Algorytm

Heurystyczny algorytm punktowy

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 w porządku. W szczególności optymalna konfiguracja jest określona przez liniowy i monotoniczny porządek malejący wartości płytek. Ta intuicja da ci również górną granicę dla wartości kafelka: s gdzie n jest liczbą płytek na planszy.

(Istnieje możliwość dotarcia do płytki 131072, jeśli w razie potrzeby 4-pole zostanie losowo wygenerowane zamiast 2-kafelkowego)

Dwa możliwe sposoby organizacji planszy pokazano na poniższych obrazkach:

enter image description here

W celu wymuszenia koordynacji płytek w monotonicznym porządku malejącym, wynik jest obliczany jako suma zlinearyzowanych wartości na tablicy pomnożonej przez wartości sekwencji geometrycznej o wspólnym współczynniku r <1.

s

s

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

Reguła decyzji

Wprowadzona reguła decyzyjna nie jest dość inteligentna, kod w Pythonie przedstawiono 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, że więcej wyrafinowana reguła decyzyjna spowolni działanie algorytmu i będzie wymagać trochę czasu, aby zostać wdrożonym. W niedalekiej przyszłości wypróbuję wdrożenie 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
  • Testy T4 - 211 - 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

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

W przypadku T2, cztery testy na dziesięć generują płytkę 4096 ze średnim wynikiem s 42000

Kod

Kod można znaleźć na stronie GiHub pod następującym linkiem: https://github.com/Nicola17/term2048-AI Opiera się na term 2048 i jest napisany w Pythonie. Wdrożę bardziej wydajną wersję w C ++ tak szybko, jak to możliwe.


88
2018-03-26 22:13



Nieźle, twoja ilustracja dała mi pewien pomysł, do wykorzystania wektorów scalających do oceny - Khaled.K


Moja próba używa expectimax jak inne rozwiązania powyżej, ale bez bitderów. Rozwiązanie Nneonneo może sprawdzić 10 milionów ruchów, które są w przybliżeniu głębokością 4 z 6 płytkami i 4 możliwymi ruchami (2 * 6 * 4)4. W moim przypadku ta głębokość zajmuje zbyt wiele czasu na badanie, dostosowuję głębokość wyszukiwania expectimax w zależności od liczby wolnych płytek po lewej:

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

Wyniki tablic są obliczane za pomocą ważonej sumy kwadratów liczby wolnych płytek i iloczynu punktowego siatki 2D z następującymi wartościami:

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

który zmusza do porządkowania płytek malejących w rodzaju węża z górnej lewej płytki.

Kod poniżej lub jsbin:

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Nie wiem, dlaczego nie ma większej liczby pobrań. Jest naprawdę skuteczny ze względu na swoją prostotę. - David Greydanus
Dzięki, spóźniona odpowiedź i działa niezbyt dobrze (prawie zawsze w [1024, 8192]), funkcja kosztów / statystyk potrzebuje więcej pracy - caub
Jak ważysz puste przestrzenie? - David Greydanus
To po prostu cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid) i staramy się maksymalizować te koszty - caub
To wymaga znacznie więcej Upvotes! Świetny kod! - Smartis


Myślę, że znalazłem algorytm, który działa całkiem dobrze, ponieważ często osiągam wyniki powyżej 10000, mój osobisty najlepszy wynik to około 16000. Moje rozwiązanie nie ma na celu utrzymywania największych liczb w kącie, 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);
}

25
2018-03-12 18:57



Uruchomiłem 100 000 gier testujących to w porównaniu do trywialnej cyklicznej strategii "w górę, w prawo, w górę, w lewo, ..." (i w dół, jeśli to konieczne). Cykliczna strategia zakończyła "średni wynik kafla" 770.6, podczas gdy ten był sprawiedliwy 396.7. Czy zgadujesz, dlaczego tak się dzieje? Myślę, że robi zbyt wiele poprawek, nawet jeśli lewo lub prawo scalą się o wiele więcej. - Thomas Ahle
Płytki mają tendencję do układania się w stos w niekompatybilny sposób, jeśli nie są przesuwane w wielu kierunkach. Ogólnie rzecz biorąc, użycie cyklicznej strategii spowoduje, że większe płytki w środku będą sprawiały, że manewrowanie będzie znacznie bardziej ciasne. - bcdan


Jestem autorem kontrolera 2048, który osiąga lepsze wyniki niż jakikolwiek inny program wspomniany w tym wątku. Sprawna implementacja kontrolera jest dostępna na stronie github. W oddzielne repozytorium istnieje również kod służący do szkolenia funkcji oceny stanu kontrolera. Metoda szkolenia jest opisana w papier.

Sterownik wykorzystuje wyszukiwanie expectimax z funkcją oceny stanu poznaną od podstaw (bez wiedzy człowieka 2048) za pomocą wariantu uczenie się różnic temporalnych (technika uczenia się wzmacniania). Funkcja wartości stanu korzysta z Sieć n-tup, która jest zasadniczo ważoną liniową funkcją wzorów obserwowanych na tablicy. Wymagało to więcej niż 1 miliardowy ciężar, razem.

Wydajność

Przy 1 ruchach / s: 609104 (Średnia 100 gier)

Przy 10 ruchach / s: 589355 (Średnia 300 gier)

Przy 3-warstwowym (około 1500 ruchów / s): 511759 (Średnia 1000 gier)

Statystyki płytek 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 danych płytek w tym samym czasie na planszy).

Dla 3-warstwowego:

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

Jednak nigdy go nie zauważyłem, uzyskując płytkę 65536.


25
2017-12-21 10:49



Dość imponujący wynik. Czy mógłbyś jednak zaktualizować odpowiedź, aby wyjaśnić (w przybliżeniu, w prostych słowach ... Jestem pewien, że wszystkie szczegóły byłyby zbyt długie, aby zamieścić tutaj), w jaki sposób twój program to osiąga? Jak w przybliżeniu wyjaśnienie, jak działa algorytm uczenia się? - Cedric Mamo
@CedricMamo: istnieje odniesienie do github: arxiv.org/abs/1604.05085 - Florian Castellane


Istnieje już implementacja sztucznej inteligencji dla tej gry: tutaj. Fragment z README:

Algorytm jest iteracyjnym pogłębianiem pierwszego wyszukiwania alfa-beta. Funkcja oceny próbuje monotonicznie zachować rzędy i kolumny (wszystkie malejące lub rosnące), jednocześnie minimalizując liczbę płytek w siatce.

Istnieje również dyskusja na temat ycombinator o tym algorytmie, który może ci się przydać.


21
2018-03-13 09:16



To powinna być najlepsza odpowiedź, ale byłoby miło dodać więcej szczegółów na temat implementacji: np. w jaki sposób plansza gry jest modelowana (jako wykres), stosowana optymalizacja (minimalna różnica między płytkami) itp. - Alceu Costa