Jaki jest optymalny algorytm dla gry 2048?

1919

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?

nitish712
źródło
84
To może pomóc! ov3y.github.io/2048-AI
cegprakash
5
Nawiasem mówiąc, @ nitish712, twój algorytm jest chciwy, ponieważ masz, choose the move with large number of mergesco szybko prowadzi do lokalnych
optymów
21
@ 500-InternalServerError: Jeżeli ja były wdrożyć AI z alfa-beta gry przycinanie drzew, byłoby to przy założeniu, że nowe bloki są adversarially umieszczone. Jest to założenie najgorszego przypadku, ale może być przydatne.
Charles
6
Zabawne odwrócenie uwagi, gdy nie masz czasu na osiągnięcie wysokiego wyniku: postaraj się uzyskać najniższy możliwy wynik. Teoretycznie występują naprzemiennie 2s i 4s.
Mark Hurd
7
Dyskusję
Jeroen Vannevel

Odpowiedzi:

1266

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:

32768 kafelek, wynik 794076

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 .

nneonneo
źródło
12
@RobL: 2 pojawiają się w 90% przypadków; 4 pojawiają się w 10% przypadków. Jest w kodzie źródłowym : var value = Math.random() < 0.9 ? 2 : 4;.
nneonneo
35
Obecnie portujemy do Cudy, więc GPU działa dla jeszcze lepszych prędkości!
nimsson
25
@nneonneo Przeniesiłem twój kod z emscripten do javascript, i teraz działa całkiem dobrze w przeglądarce ! Fajnie oglądać, bez potrzeby kompilacji i wszystko ... W Firefoksie wydajność jest całkiem dobra ...
reverse_engineer
6
Teoretyczny limit w siatce 4x4 to w rzeczywistości IS 131072, a nie 65536. Wymaga to jednak uzyskania 4 w odpowiednim momencie (tj. Cała plansza wypełniona 4 .. 65536 każdy raz - 15 zajętych pól) i plansza musi być ustawiona moment, abyś mógł się połączyć.
Bodo Thiesen
5
@nneonneo Możesz sprawdzić naszą AI, która wydaje się jeszcze lepsza, osiągając 32k w 60% gier: github.com/a szczepanski
cauchy
1253

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ść.

Idealnie monotoniczna płyta 2048

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 .

Idealnie gładka płyta 2048

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.

4096

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

owalny
źródło
89
Możesz traktować komputer umieszczający płytki „2” i „4” jako „przeciwnika”.
Wei Yen
29
@WeiYen Pewnie, ale uznanie go za problem minmax nie jest zgodne z logiką gry, ponieważ komputer umieszcza płytki losowo z pewnymi prawdopodobieństwami, zamiast celowo minimalizować wynik.
koo
57
Mimo że AI losowo układa płytki, celem nie jest przegrać. Nieszczęście to to samo, co przeciwnik wybierający dla ciebie najgorszy ruch. Część „min” oznacza, że ​​próbujesz grać zachowawczo, aby nie było żadnych okropnych ruchów, które mogłyby mieć pecha.
FryGuy
196
Miałem pomysł, aby stworzyć widelec z 2048 roku, w którym komputer zamiast umieszczać 2 i 4 losowo używa twojej AI do ustalenia, gdzie umieścić wartości. Rezultat: czysta niemożliwość. Można wypróbować tutaj: sztupy.github.io/2048-Hard
SztupY
30
@SztupY Wow, to jest złe. Przypomina mi qntm.org/hatetris Hatetris, który również próbuje umieścić element, który poprawi twoją sytuację w najmniejszym stopniu.
Patashu,
145

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:

Najlepszy wynik

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.

wykres punktowy

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.

Ronenz
źródło
7
+1. Jako student AI uważam to za bardzo interesujące. Przyjrzymy się temu lepiej w wolnym czasie.
Izaak
4
To jest niesamowite! Właśnie spędziłem godziny optymalizując wagi dla dobrej funkcji heurystycznej dla expectimax i wdrażam to w 3 minuty, a to całkowicie niszczy.
Brendan Annable
8
Ładne wykorzystanie symulacji Monte Carlo.
nneonneo
5
Oglądanie tej gry wymaga oświecenia. To przesadza z całą heurystyką, a jednak działa. Gratulacje!
Stéphane Gourichon
4
Zdecydowanie najciekawsze rozwiązanie tutaj.
shebaw
126

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:

Gotowy do końca

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:zmiana modelu

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:

Łańcuch zakończony

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ąć:

Wpisz opis zdjęcia tutaj

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
Daren
źródło
execute move with best scorejak możesz ocenić najlepszy wynik z możliwych następnych stanów?
Khaled.K
heurystyka jest zdefiniowana w evaluateResulttobie, po prostu staraj się zbliżyć do najlepszego możliwego scenariusza.
Daren
@Daren Czekam na szczegółowe informacje
ashu
@ashu Pracuję nad tym, nieoczekiwane okoliczności pozostawiły mnie bez czasu na dokończenie. W międzyczasie poprawiłem algorytm, który rozwiązuje go w 75% przypadków.
Daren
13
W tej strategii najbardziej podoba mi się to, że mogę jej używać podczas ręcznej gry, dzięki czemu uzyskałem do 37 tys. Punktów.
Głowonóg
94

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.

Wynik

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: sgdzie 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:

wprowadź opis zdjęcia tutaj

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.

s

s

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

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

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

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 ++.

Nicola Pezzotti
źródło
Nieźle, twoja ilustracja podsunęła mi pomysł przeprowadzenia oceny wektorów scalania
Khaled.K
Witaj. Czy na pewno instrukcje podane na stronie github dotyczą twojego projektu? Chcę spróbować, ale wydaje się, że są to instrukcje do oryginalnej grywalnej gry, a nie autorun AI. Czy możesz je zaktualizować? Dzięki.
JD Gamboa,
41

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

kocioł
źródło
3
Nie jestem pewien, dlaczego to nie ma więcej pozytywnych opinii. Jest naprawdę skuteczny ze względu na swoją prostotę.
David Greydanus
Dzięki, późna odpowiedź i nie działa zbyt dobrze (prawie zawsze w [1024, 8192]), funkcja koszt / statystyki wymaga więcej pracy
klub
Jak oceniłeś puste miejsca?
David Greydanus
1
Po prostu cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid)staramy się zmaksymalizować ten koszt
klub
dzięki @Robusto, pewnego dnia powinienem poprawić kod, można go uprościć
tytuł
38

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.

cauchy
źródło
4
Całkiem imponujący wynik. Czy możesz jednak zaktualizować odpowiedź, aby wyjaśnić (w przybliżeniu, w prostych słowach ... jestem pewien, że pełne szczegóły byłyby zbyt długie, aby opublikować tutaj), w jaki sposób twój program to osiąga? Jak w przybliżeniu wyjaśnienie działania algorytmu uczenia się?
Cedric Mamo
27

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);
}
Vincent Lecrubier
źródło
5
Uruchomiłem 100 000 gier, testując to w porównaniu z banalną cykliczną strategią „góra, prawo, góra, lewo, ...” (i dół, jeśli trzeba). Cykliczna strategia zakończyła „średnią punktację płytek” 770.6, podczas gdy ta się właśnie skończyła 396.7. Czy wiesz, dlaczego tak jest? Myślę, że robi to zbyt wiele wzlotów, nawet jeśli lewo lub prawo połączyłyby się znacznie więcej.
Thomas Ahle,
1
Płytki układają się w stosy w niekompatybilny sposób, jeśli nie są przesuwane w wielu kierunkach. Ogólnie rzecz biorąc, stosowanie cyklicznej strategii spowoduje większe płytki na środku, co znacznie utrudni manewrowanie.
bcdan
25

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.

baltazar
źródło
4
To powinna być najlepsza odpowiedź, ale fajnie byłoby dodać więcej szczegółów na temat implementacji: np. Jak modelowana jest plansza (jako wykres), zastosowana optymalizacja (min-max różnica między kafelkami) itp.
Alceu Costa
1
Dla przyszłych czytelników: jest to ten sam program, który został wyjaśniony przez jego autora (ovolve) w drugiej, najwyższej odpowiedzi tutaj. Ta odpowiedź i inne wzmianki o programie ovolve w tej dyskusji skłoniły ovolve do pojawienia się i napisania, jak działa jego algorytm; ta odpowiedź ma teraz wynik 1200.
MultiplyByZer0
23

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ć.

Khaled.K
źródło
2
Zmienię to później, aby dodać kod na żywo @ nitish712
Khaled.K
9
Jaki jest procent wygranych tego algorytmu?
cegprakash
Dlaczego potrzebujemy constant? Jeśli wszystko, co robisz, to porównywanie wyników, jak to wpływa na wynik tych porównań?
bcdan
@bcdan heurystyka (inaczej wynik-porównanie) zależy od porównania oczekiwanej wartości przyszłego stanu, podobnie jak działa heurystyka szachowa, z wyjątkiem tego, że jest to heurystyka liniowa, ponieważ nie budujemy drzewa, aby znać najlepsze następne N ruchów
Khaled.K
12

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:

wprowadź opis zdjęcia tutaj

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:

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Sandipan Dey
źródło
9

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

wvdz
źródło
Spróbuj rozszerzyć go o rzeczywiste zasady. Poznanie losowego generatora Haskella jest dużym wyzwaniem!
Thomas Ahle,
Byłem bardzo sfrustrowany tym, że Haskell próbował to zrobić, ale prawdopodobnie spróbuję jeszcze raz! Przekonałem się, że gra staje się znacznie łatwiejsza bez randomizacji.
wvdz
Bez randomizacji jestem pewien, że można znaleźć sposób na uzyskanie zawsze 16 lub 32 000. Jednak losowość w Haskell nie jest taka zła, potrzebujesz tylko sposobu na ominięcie „ziarna”. Zrób to jawnie lub za pomocą losowej monady.
Thomas Ahle,
Udoskonalenie algorytmu tak, aby zawsze osiągało 16k / 32k dla nielosowej gry, może być kolejnym interesującym wyzwaniem ...
wvdz 9.04.14
Masz rację, to trudniejsze niż myślałem. Udało mi się znaleźć następującą sekwencję: [GÓRA, LEWO, LEWO, GÓRA, LEWO, DÓŁ, ​​LEWO], która zawsze wygrywa grę, ale nie przekracza 2048. (W przypadku braku legalnego ruchu algorytm cyklu po prostu wybiera następny w kolejności
zgodnej z
6

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")
  }
API-Beast
źródło
10
działa lepiej, jeśli powiesz, że random from (right, right, right, down, down, up) nie wszystkie ruchy mają jednakowe prawdopodobieństwo. :)
Daren
3
W rzeczywistości, jeśli jesteś zupełnie nowy w grze, to naprawdę pomaga używać tylko 3 klawiszy, w zasadzie to, co robi ten algorytm. Więc nie tak źle, jak się wydaje na pierwszy rzut oka.
Cyfry
5
Tak, opiera się na moich własnych spostrzeżeniach z grą. Dopóki nie będziesz musiał użyć czwartego kierunku, gra praktycznie rozwiąże się bez żadnej obserwacji. To „AI” powinno być w stanie dostać się do 512/1024 bez sprawdzania dokładnej wartości dowolnego bloku.
API-Beast
3
Właściwa sztuczna inteligencja starałaby się uniknąć przejścia do stanu, w którym za wszelką cenę mogłaby się poruszać tylko w jednym kierunku.
API-Beast
3
Korzystanie tylko z 3 kierunków jest naprawdę bardzo przyzwoitą strategią! Właśnie doprowadziło mnie to do 2048 r. Ręcznego grania w grę. Jeśli połączysz to z innymi strategiami decydującymi między 3 pozostałymi ruchami, może to być bardzo potężne. Nie wspominając o tym, że zmniejszenie wyboru do 3 ma ogromny wpływ na wydajność.
wvdz
4

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.

alan2here
źródło
5
Opisujesz lokalne wyszukiwanie za pomocą heurystyki. Utkniesz, więc musisz planować z wyprzedzeniem kolejne ruchy. To z kolei prowadzi do wyszukiwania i oceniania rozwiązań (w celu podjęcia decyzji). Tak więc to naprawdę nie różni się od innych prezentowanych rozwiązań.
runDOSrun,