jaki jest optymalny algorytm dla gry 2048?
wprowadzenie
2048 to ekscytująca gra, w której przesuwamy płytki, aby je łączyć, dążąc do coraz większych wartości płytek.
w tym samouczku zbadamy algorytm gry 2048, który pomoże zdecydować, jakie ruchy należy wykonać na każdym kroku, aby uzyskać najlepszy wynik.
Jak grać w 2048
gra w 2048 jest rozgrywana na planszy 4×4., Każda pozycja na planszy może być pusta lub może zawierać kafelek, a każdy kafelek będzie miał numer na nim.
kiedy zaczniemy, plansza będzie miała dwie płytki w losowych miejscach, z których każda ma „2” lub „4” – każda ma niezależne 10% szans na bycie „4”, lub inaczej a jest „2”.
ruchy są wykonywane przez przesunięcie wszystkich płytek w kierunku jednej krawędzi-w górę, w dół, w lewo lub w prawo., Gdy to zrobisz, wszystkie płytki o tej samej wartości, które sąsiadują ze sobą i poruszają się razem, połączą się i otrzymają nowy kafelek równy sumie dwóch wcześniejszych:
Po wykonaniu ruchu, nowy kafelek zostanie umieszczony na planszy. Jest on umieszczony w losowej lokalizacji i będzie to „2” lub „4” w taki sam sposób, jak początkowe płytki – „2” 90% czasu i „4” 10% czasu.
gra toczy się dalej, dopóki nie ma możliwości wykonania kolejnych ruchów.
ogólnie rzecz biorąc, celem gry jest osiągnięcie pojedynczego kafelka o wartości „2048”., Jednak gra nie kończy się na tym i możemy kontynuować grę w miarę możliwości, dążąc do jak największej płytki. Teoretycznie jest to płytka o wartości „131,072”.
wyjaśnienie problemu
rozwiązanie tej gry jest interesującym problemem, ponieważ ma przypadkowy komponent. Nie da się poprawnie przewidzieć nie tylko miejsca, w którym będzie umieszczony każdy nowy kamień, ale także czy będzie to ” 2 ” Czy „4”.
w związku z tym niemożliwe jest posiadanie algorytmu, który za każdym razem poprawnie rozwiąże zagadkę., Najlepsze, co możemy zrobić, to określić, co może być najlepszym posunięciem na każdym etapie i zagrać w grę prawdopodobieństwa.
w każdym momencie możemy wykonać tylko cztery możliwe ruchy. Czasami niektóre z tych ruchów nie mają wpływu na planszę i dlatego nie są warte wykonania – na przykład na powyższej planszy ruch „w dół”nie będzie miał wpływu, ponieważ wszystkie płytki są już na dolnej krawędzi.
wyzwanie polega na określeniu, który z tych czterech ruchów będzie tym, który ma najlepszy długoterminowy wynik.,
Nasz algorytm opiera się na algorytmie Expectimax, który sam w sobie jest odmianą algorytmu Minimax, ale gdzie możliwe trasy przez nasze drzewo są ważone prawdopodobieństwem ich wystąpienia.
zasadniczo traktujemy grę jako grę dla dwóch graczy:
- gracz pierwszy-gracz ludzki – może przesunąć planszę w jednym z czterech kierunków
- gracz drugi – gracz komputerowy – może umieścić kafelek w pustym miejscu na planszy
na tej podstawie możemy wygenerować drzewo wyników z każdego ruchu, ważone prawdopodobieństwem wystąpienia każdego ruchu., To może dać nam szczegóły potrzebne do określenia, który ruch człowieka może dać najlepszy wynik.
3.1. Schemat rozgrywki
ogólny przebieg rozgrywki:
możemy natychmiast zobaczyć losowy aspekt gry w procesie „Dodaj losowy kafelek” – zarówno w tym, że znajdujemy losowy kwadrat, aby dodać kafelek, i wybieramy losową wartość dla kafelka.
naszym wyzwaniem jest podjęcie decyzji, co zrobić w kroku „Określ następny ruch”. To jest nasz algorytm do gry.,
ogólne przepełnienie tego wydaje się zwodniczo proste:
wszystko, co musimy zrobić, to symulować każdy z możliwych ruchów, określić, który z nich daje najlepszy wynik, a następnie użyć tego.
więc teraz zredukowaliśmy nasz algorytm do symulowania każdego ruchu i generowania pewnego wyniku.
jest to proces dwuczęściowy. Pierwszym przejściem jest sprawdzenie, czy ruch jest w ogóle możliwy, a jeśli nie, to przerwać wcześnie z wynikiem „0”., Jeśli ruch jest możliwy, przechodzimy do rzeczywistego algorytmu, w którym określamy, jak dobry jest to ruch:
3.2. Określanie następnego ruchu
kluczową częścią naszego algorytmu jest jak dotąd symulowanie ruchu, a kluczową częścią tego jest generowanie wyniku dla każdego możliwego ruchu. Tutaj właśnie wchodzi nasz algorytm Expectimax.
będziemy symulować każdy możliwy ruch obu graczy przez kilka kroków i zobaczymy, który z nich daje najlepszy wynik. Dla ludzkiego gracza oznacza to każdy z ruchów” w górę”,” w dół”,” w lewo „i” w prawo”.,
dla gracza komputerowego oznacza to umieszczenie zarówno płytki „2”, jak i „4” w każdym możliwym pustym miejscu:
algorytm ten jest rekurencyjny, a każdy rekurencyjny krok zatrzymuje się tylko wtedy, gdy jest to pewna głębokość od rzeczywistego ruchu w prawdziwej grze.,
- Symuluj każdy możliwy ruch człowieka
- dla każdego z nich
- Rekurencja z powrotem do algorytmu
- zwróć wynik obliczony z tego ruchu człowieka
- Dodaj wynik obliczony z tego ruchu komputera, ważony przez prawdopodobieństwo wystąpienia tego ruchu
Kiedy to zakończymy, sumujemy wszystkie obliczone wyniki i jest to ostateczny wynik dla ruchu, który chcemy wykonać z bieżącej planszy., Ponieważ robimy to cztery razy – po jednym za każdy możliwy ruch z bieżącej planszy – otrzymujemy cztery wyniki, a najwyższy z nich to ruch, który należy wykonać.
3.3. Zdobywanie pozycji na planszy
w tym momencie pozostaje tylko obliczyć wynik dla planszy. Nie jest to taka sama punktacja jak w grze, ale musi wziąć pod uwagę, jak dobra jest to pozycja, aby kontynuować grę.
istnieje wiele sposobów, aby to osiągnąć, dodając kilka czynników wraz z odpowiednimi wagami., Na przykład:
- liczba pustych lokalizacji
- liczba możliwych scaleń – tzn. liczba razy ta sama liczba jest w dwóch sąsiednich lokalizacjach
- największa wartość w dowolnej lokalizacji
- suma wszystkich lokalizacji
- Monotoniczność planszy – tak dobrze struktura planszy jest taka, że wartości lokalizacji rosną w jednym kierunku.
Pseudokod
skoro już wiemy, jak będzie działał algorytm, jak to wygląda? Przyjrzyjmy się bliżej pseudokodowi opisującemu algorytm.,
nie interesuje nas prawdziwa rozgrywka, tylko algorytm określania ruchów, więc zacznijmy od tego:
tak jak poprzednio, to prowadzi nas do punktu, w którym symulujemy każdy z możliwych ruchów z planszy startowej i zwracamy ten, który zdobywa najlepszy wynik. Pozostawia nam to potrzebę generowania wyników dla nowo symulowanych plansz.
dodaliśmy limit głębokości, dzięki czemu możemy zatrzymać przetwarzanie po pewnym czasie., Ponieważ pracujemy z algorytmem rekurencyjnym, potrzebujemy sposobu, aby go zatrzymać, w przeciwnym razie będzie działać w nieskończoność:
to daje nam naszą rekurencję, symulując każdy możliwy ruch człowieka i komputera dla określonej liczby kroków i decydując, które ruchy człowieka dają najlepszy możliwy wynik.
pozostaje tylko wypracować ostateczny wynik dla danej pozycji na planszy. Nie ma na to idealnego algorytmu, a różne czynniki dadzą różne wyniki.,
Optymalizacja wydajności
do tej pory mamy algorytm, który spróbuje rozwiązać grę, ale nie jest tak skuteczny, jak mógłby być. Ze względu na losowy charakter gry, niemożliwe jest posiadanie doskonale zoptymalizowanego solvera-zawsze będzie jakiś poziom powtórzeń po prostu ze względu na charakter procesu.
możemy przynajmniej zrobić co w naszej mocy, aby ograniczyć pracę, której nie musimy robić.,
dokonujemy już trochę optymalizacji w powyższym algorytmie, nie przetwarzając żadnych ruchów, które nie mają żadnego wpływu na grę. Istnieją jednak inne sposoby, które możemy ograniczyć pracę do wykonania, takie jak śledzenie skumulowanego prawdopodobieństwa ruchów i zatrzymywanie się, gdy robi się zbyt mało. Wiąże się to z ryzykiem usunięcia idealnego rozwiązania, ale jeśli prawdopodobieństwo jest tak niskie, to prawie na pewno tak się nie stanie.
możemy również dynamicznie określać limit głębokości do pracy., Nasz powyższy pseudokod ma mocno zakodowaną granicę 3, ale możemy to dynamicznie obliczyć na podstawie kształtu planszy na początku naszych obliczeń – na przykład ustawiając ją na liczbę pustych kwadratów lub liczbę odrębnych płytek na planszy. Oznaczałoby to, że przemierzamy mniej ruchów z desek, które mają mniejsze możliwości rozbudowy.
dodatkowo, ponieważ możliwe jest wielokrotne ponowne odwiedzanie tych samych pozycji planszy, możemy je zapamiętać i buforować wynik dla tych pozycji, zamiast za każdym razem je przeliczać., Potencjalnie możemy wygenerować każdą możliwą pozycję planszy z wyprzedzeniem, ale jest ich ogromna liczba – 281 474 976 710 656 różnych możliwych pozycji planszy przy użyciu płytek do 2048 – więc prawdopodobnie nie jest to wykonalne.
jednak najważniejszą optymalizacją, jaką możemy zrobić, jest dostosowanie algorytmu generowania wyników na planszy. To działa, aby zdecydować, jak dobra płyta jest dla kontynuowania gry i czynniki i wagi, które używamy do tego są bezpośrednio związane z tym, jak dobrze nasz algorytm gra.,
2048 to niezwykle ciekawa gra do rozwiązania. Nie ma doskonałego sposobu, aby go rozwiązać, ale możemy napisać heurystykę, która będzie wyszukiwać najlepsze możliwe trasy w grze.
te same ogólne zasady działają w każdej grze dla dwóch graczy-na przykład w szachach – gdzie nie można przewidzieć, co zrobi drugi gracz z żadnym stopniem pewności.
Dlaczego nie spróbować napisać implementacji tego i zobaczyć jak to działa?