Dlaczego niektóre gry są kompletne?

Przeczytałem wpis w Wikipedii na temat „ Listy problemów z NP-complete ” i odkryłem, że gry takie jak Super Mario, Pokemon, Tetris lub Saga Crush Candy są na przykład kompletne. Jak mogę sobie wyobrazić np. Kompletność gry? Odpowiedzi nie muszą być zbyt precyzyjne. Chcę tylko uzyskać przegląd tego, co oznacza, że ​​gry mogą być na przykład kompletne.

Oznacza to po prostu, że możesz tworzyć poziomy lub puzzle w tych grach, które kodują problemy NP-Hard. Możesz rozwiązać problem z kolorem wykresów, utworzyć powiązany poziom Super Mario Bros., a ten poziom jest do pokonania tylko wtedy, gdy wykres jest trójkolorowy.

Jeśli chcesz zobaczyć konkretny sposób NP-complete problemy są przeliczane na grach, polecam papier „Klasyczne Gry Nintendo są (obliczeniowo) Dysk” . Jest dobrze napisany i łatwy do naśladowania.

Ważnym zastrzeżeniem, o którym należy pamiętać, jest to, że twardość NP wymaga uogólnienia gier w „oczywisty” sposób. Na przykład Tetris zwykle ma planszę o stałym rozmiarze, ale dowód na twardość wymaga, aby gra pozwalała na dowolnie duże plansze. Innym przykładem są wrogowie spoza ekranu w Super Mario Bros: dowodem jest wariant gry, w którym wrogowie spoza ekranu nadal poruszają się, jakby byli na ekranie, zamiast przestać istnieć i powrócić do pozycji wyjściowej, gdy Mario wróci .

Szczerze mówiąc, nie wiem dokładnie, jakiego rodzaju modelu używają ludzie zgłaszający te twierdzenia; Jednak to, co wydaje się rozsądne, aby mnie byłoby mówić o -completeness decydowania coś o sytuacji w grze.$\mathcal{NP}$

Weźmy jako przykład Tetris, ponieważ jest to jedyny z tych, które cytujesz, o których rozumiem wystarczająco dużo, aby mówić. Tetris ma zasadę zwaną „idealnie czyste”, która daje graczowi dużą premię, jeśli upuszczenie pionka całkowicie wyczyści planszę. Można się zastanawiać, czy przy uporządkowanej sekwencji elementów i liczbie całkowitej k istnieje prawna sekwencja ruchów dla części P, która osiąga co najmniej k idealnych wartości. Takie stwierdzenia problemów są wystarczająco abstrakcyjne, aby można je było modelować za pomocą narzędzi teorii złożoności.$\{P_i\}$$k$$P$$k$

Krótko mówiąc, „ -Complete” oznacza jedno i tylko jedno, fantazyjne roszczeń, takie jak „Super Mario jest N P -Complete” muszą być przetłumaczone na język formalnego oświadczenia przed podjęciem jakiegokolwiek rzeczywistego sensu.$\mathcal{NP}$$\mathcal{NP}$

Oto proste objaśnienie machania ręką:

$O(n \log(n))$

Takie gry są trudne dla NP, ponieważ zachowanie gracza jest bardzo ekspresyjne. Podczas gdy w danym momencie gracz może mieć tylko ograniczoną, a nawet stałą liczbę możliwych akcji, to wystarczy, aby stworzyć przestrzeń zachowań lub strategii wykładniczych w długości gry; i chociaż możesz być w stanie podać prosty warunek lub logiczną formułę ważności / korzyści / poprawności działań gracza lokalnie, na całym świecie uzyskujesz podobny efekt jak w przypadku dużego obwodu kombinatorycznego lub formuły k-CNF.

Mam nadzieję, że ma to jakiś intuicyjny sens, a także wystarczającą ilość dzwonków teorii CS.

PS - Niektóre gry są znacznie bardziej złożone (obliczeniowo). Na przykład gry planszowe Hex , Go i Reversi są kompletne z PSPACE. Jest tak zasadniczo dlatego, że formuła, którą musisz spełnić, aby wygrać strategię, to formuła kwantyfikatora o naprzemiennym naprzemiennym działaniu: istnieje ruch gracza 1, taki że dla każdego ruchu gracza 2 istnieje ruch gracza 1 itd. Itp. tak, że po wykonaniu wszystkich tych ruchów, niektóre ruchy gracza 2 są nieprawidłowe lub mamy prawidłową sekwencję, którą gracz 1 wygrał. W grach NP jest to zazwyczaj zachowanie jednego gracza / strategia / wybór ruchów.

W przypadku gier dla jednego gracza zawsze możesz zadać pytanie: „czy istnieje strategia wygrywająca dla gracza”, a pytanie to często zawiera odpowiedź „TAK”, którą można zweryfikować w czasie wielomianowym, i może być bardzo kompletna.

W przypadku gier dwuosobowych odpowiedzi bardzo często nie można zweryfikować w czasie wielomianowym, ponieważ aby zweryfikować, że ruch dla A jest ruchem wygrywającym, musisz wykazać, że dla każdej odpowiedzi B będzie znowu ruch wygrywający dla A i wkrótce.

Cóż, z pewnością jest w NP, ponieważ możliwym rozwiązaniem jest po prostu skończona liczba danych wejściowych (w każdej ramce wejściowej możesz wybrać dowolny z przycisków k, reprezentujemy każdy wybór przycisków dla każdej ramki za pomocą litery), która prowadzi do ekran wygranej. Wiemy, że ta gra została wcześniej pokonana, więc wiemy, że istnieje rozwiązanie. NTM przegląda taśmę i magicznie zgaduje prawidłowy certyfikat długości n. Następnie symuluje Super Mario z danymi wejściowymi i weryfikuje je. Weryfikacja może być przeprowadzona w czasie wielomianowym (faktycznie czas liniowy, jeśli rozwiązanie jest poprawne, zwycięstwo zajmie dokładnie n klatek).

Aby pokazać kompletność NP, moglibyśmy zredukować do niej 3-SAT, budując kontroler 3-Sat z generatorem poziomu (który jest zbudowany przez wykonanie dowolnego kodu https://www.youtube.com/watch?v=IOsvuEA2h4w ).

Mamy więc wejście CNF 3-SAT, które najpierw sprawdzamy poprawność formatowania. Jeśli jest źle sformatowany, po prostu tłumaczymy go na jedno wejście „skokowe” (nie można pokonać Super Mario w jednej klatce wykonując skok).

Długość wejścia 3-CNF nazywamy n.

Jeśli jest poprawnie sformatowany, tłumaczymy go na szereg danych wejściowych, które budują dla nas sprawdzanie 3-CNF (zawsze ten sam kod długości k), tłumaczą 3-CNF na ciąg danych wejściowych, który buduje specyficzne 3- CNF w kontrolerze (w O (n)) i sprawdza wszystkie możliwe rozwiązania za pomocą brutalnej siły. Nie pracuje i nic nie robi, jeśli po przejściu wszystkich rozwiązań nie zostanie znalezione żadne. Ponownie uruchamia grę i używa znanego rozwiązania dla Super Mario do pokonania gry (kod do wykonania tego ma długość j). Nasza transformacja odbywa się zatem w O (n), więc mieści się w czasie wielomianowym.

Jeśli CNF jest źle sformatowany, nie wygrywamy (z definicji nasz wkład nie wygrywa, jeśli nie wygraliśmy jednej klatki po jego wykonaniu). Jeśli CNF nie jest satysfakcjonujący, nie wygrywamy (nie możesz wygrać, pracując bezczynnie dla jednej ramki w generatorze poziomów, zapewniliśmy to w naszym kodzie). Jeśli CNF jest zadowalający, kontroler stwierdzi, że rozwiązanie uruchamia się ponownie i wygrywa grę. Zatem wielomianowa redukcja 3-Sat do Super Mario jest kompletna i udowodniliśmy, że Super Mario jest NP-zupełny.

(Mam nadzieję, że gdzieś tego nie pomieszałem. Mamy problem z przechowywaniem, jeśli 3-CNF jest zbyt długi, ale ograniczone przechowywanie jest zwykle ignorowane w tych kontekstach)

Przepisałem tę odpowiedź, aby spróbować odnieść się do komentarzy na temat poprzedniej wersji.

Zakładam, że przeczytałeś definicję Wikipedii dotyczącą kompletności NP, która tak naprawdę nie koncentruje się na grach. Rozetrę trochę znaczenie dokładności NP i teorii gier i wyjaśnię istotę gry NP-Complete.

Rozważmy grę dla dwóch graczy z naprzemiennymi ruchami, bardziej restrykcyjnie dotyczy to głównie gier kombinatorycznych . Zasadniczo gra, w której masz pewną liczbę ruchów, które można wykonać i musisz wybrać jeden z nich. Chciałbyś grać „idealnie”, co oznacza, że ​​nigdy nie zrobiłbyś „złego” ruchu. Więc spośród dozwolonych ruchów chcesz wybrać najlepszy. (Oczywiście twój przeciwnik ma ten sam cel ...)

Pamiętaj, że idealna gra nie oznacza, że ​​zawsze wygrasz. Zasady gry mogą być takie, że pierwszy lub drugi gracz powinien wygrać. Również niektóre gry, takie jak kółko i krzyżyk, powinny zakończyć się remisem. Zatem „idealna gra” oznacza w tej dyskusji:
(1) Że nigdy nie będziesz na wygranej pozycji, a następnie przegrasz grę, ponieważ wykonałeś „zły” ruch
(2) Nigdy nie przegapisz okazji, aby zdobyć do zwycięskiej pozycji, jeśli pojawi się taka możliwość.

Biorąc pod uwagę obecny stan gry, chciałbyś użyć „wydajnego algorytmu” do obliczenia najlepszego ruchu. Z drugiej strony zauważmy, że algorytm, który musi przeszukiwać całe drzewo gry, jest „nieefektywnym algorytmem”.

$C$$B$$n$$T$

• 
  $T \varpropto aB^a + bB^{\alpha-1} + cB^{\alpha-2} + ... + hB^0$
  $\alpha$
• 
  $T \varpropto aB^n$
  $n$

Ważną kwestią jest to, że nie można mieć wydajnego algorytmu, czasu wielomianowego, który doskonale sprawdza się w grze, która jest kompletna NP. Aby grać doskonale, problem NP-zupełny musi być z definicji rozwiązany przez nieefektywny algorytm działający w czasie niepolarnym.

Należy pamiętać, że czas wykonywania zależy od wewnętrznej liczby obliczeń, a nie czasu reakcji postrzeganego przez człowieka. W przypadku małej gry, takiej jak kółko i krzyżyk, komputer może odtwarzać wszystkie możliwe przyszłe ruchy i nadal szybko reagować w sposób postrzegany przez człowieka.

Dla Nima możliwe jest utworzenie algorytmu wielomianowego czasu. W dowolnym momencie gry algorytm może obliczyć, który gracz ma zwycięski ruch i jaki powinien być ten ruch.

Z drugiej strony weźmy grę Qubic . (Próbujesz utworzyć linię 4 na siatce 3D. Więc jest to zasadniczo kółko i krzyżyk na siatce 4x4x4). Qubic jest NP-kompletny, więc nie ma algorytmu wielomianu czasowego do obliczenia następnego idealnego ruchu. Jedynym sposobem, aby dowiedzieć się, czy obecnie wygrywasz, jest wypróbowanie wszystkich możliwych ruchów obu graczy, aby sprawdzić, czy dany ruch jest zwycięzcą, a przynajmniej przegranym.

Prawdę mówiąc, całe drzewo gry w Qubic jest na tyle małe, że można je zakodować w programie komputerowym, który może grać doskonale. Kodowanie oznacza, że ​​całe drzewo gry zostało zbadane, a wszystkie ruchy opracowane wcześniej. Tak więc program może zasadniczo wykonać szybkie wywołanie bazy danych przy użyciu bieżącego stanu tablicy i odzyskać najlepszy ruch dla tego stanu tablicy bez konieczności wyszukiwania drzewa za każdym razem, gdy ma zostać wykonany ruch. To jest naprawdę „oszustwo” dla naszych celów tutaj.

Porozmawiajmy teraz o szachach, aby omówić funkcję oceny, ignorując niektóre inne funkcje programów do gry w szachy. Szachy to wciąż nierozwiązana gra . Nie wiadomo, czy pierwszy lub drugi gracz powinien wygrać. Niemożliwe jest przyznanie żadnej pozycji na planszy i przewidzenie z pewnością, kto wygra. W rzeczywistości szachy mają tak duże drzewo gry, że przeszukiwanie całego drzewa gry jest po prostu niemożliwe. Potrzebujesz komputerów, które są nie tylko 10 lub 100 razy szybsze, ale miliardy miliardów czasu szybciej niż jakikolwiek inny komputer. (Istnieje nadzieja, że obliczenia kwantowe mogłyby przeciąć ten węzeł gordyjski).

Pomyśl o funkcji oceny szachowej, która daje każdemu możliwemu następnemu ruchowi prawdopodobieństwo bycia najlepszym ruchem. Program szachowy polega na połączeniu perspektyw z funkcją oceny. W ten sposób program analizuje wszystkie możliwe przyszłe ruchy, aż dojdzie do punktu, w którym „dobry” wynik może zostać przyznany pozycji tablicy. Komputer ocenia w ten sposób wszystkie możliwe ścieżki przez drzewo, a następnie wybiera ścieżkę z najlepszym wynikiem. Ponieważ wyszukiwanie nigdy nie zakończyło się oceną wszystkich ocenianych ścieżek, wszystkie programy szachowe ostatecznie używają niedoskonałej funkcji oceny. (Jeśli zbliżasz się do końca gry, komputer może być w stanie spojrzeć na wszystkie możliwe przyszłe ruchy.) Oznacza to, że można pokonać program, nawet jeśli program miał kiedyś wygraną.