Ze względu na charakter pytania muszę podać wiele podstawowych informacji (ponieważ moje pytanie brzmi: jak to zawęzić?) To powiedziawszy, można je streścić (o ile wiem):
Jakie metody istnieją, aby znaleźć lokalne optimum na bardzo dużych kombinatorycznych przestrzeniach poszukiwań?
tło
W społeczności superplay wspieranych narzędziami staramy się zapewnić specjalnie spreparowane (nie generowane w czasie rzeczywistym) dane wejściowe do konsoli lub emulatora gier wideo, aby zminimalizować niektóre koszty (zwykle czas do ukończenia). Obecnie odbywa się to poprzez odtwarzanie gry klatka po klatce i określanie danych wejściowych dla każdej klatki, często wielokrotnie powtarzając części serii (na przykład ostatnio opublikowana seria gry The Legend of Zelda: Ocarina of Time ma łącznie 198 590 ponownych prób).
Osiągnięcie celu tych tras zwykle sprowadza się do dwóch głównych czynników: planowania trasy i przejścia. Pierwsza jest znacznie bardziej „kreatywna” niż druga.
Planowanie trasy określa sposób, w jaki gracz powinien ogólnie nawigować, aby ukończyć grę, i często jest najważniejszą częścią biegu. Jest to analogiczne do wyboru, na przykład, jakiej metody sortowania należy użyć. Najlepszy rodzaj bąbelków na świecie po prostu nie będzie lepszy od szybkiego sortowania na milionie elementów.
Jednak w dążeniu do perfekcji ogromnym czynnikiem jest również podróż (sposób, w jaki przebiega trasa). Kontynuując analogię, w ten sposób implementowany jest algorytm sortowania. Niektórych tras nie można nawet wykonać bez ściśle określonych ramek danych wejściowych. Jest to najbardziej żmudny proces wspomagania narzędzi i sprawia, że produkcja ukończonego cyklu zajmuje miesiące, a nawet lata. Nie jest to trudny proces (dla człowieka), ponieważ sprowadza się do wypróbowania różnych odmian tego samego pomysłu, dopóki nie zostanie uznany za najlepszy, ale ludzie mogą wypróbować tyle różnych wariantów w zakresie uwagi. Zastosowanie maszyn do tego zadania wydaje się tutaj właściwe.
Moim celem jest teraz próba zautomatyzowania procesu przejścia ogólnie dla systemu Nintendo 64 . Przestrzeń poszukiwania tego problemu jest zdecydowanie za duża, aby atakować przy użyciu siły brutalnej. Segment n-ramki przebiegu N64 ma 2 30n możliwych danych wejściowych, co oznacza, że zaledwie 30 ramek wejścia (druga przy 30 klatkach na sekundę) ma 2 900 możliwych danych wejściowych; niemożliwe byłoby przetestowanie tych potencjalnych rozwiązań, nie mówiąc już o tych, które trwają dwie godziny.
Jednak nie jestem zainteresowany próbą (a raczej nie zamierzam nawet próbować) całkowitej globalnej optymalizacji pełnego uruchomienia. Chciałbym raczej, biorąc pod uwagę początkowe dane wejściowe, aproksymować lokalne optimum dla określonego segmentu przebiegu (lub najbliższe n lokalnych optimum dla pewnego rodzaju optymalizacji częściowo globalnej) . To znaczy, biorąc pod uwagę trasę i początkowe przejście tej trasy: przeszukaj sąsiadów tego przejścia, aby zminimalizować koszty, ale nie degeneruj się, aby wypróbować wszystkie przypadki, które mogłyby rozwiązać problem.
Mój program powinien zatem przyjąć stan początkowy, strumień wejściowy, funkcję oceny i wyprowadzić lokalne optimum poprzez zminimalizowanie wyniku oceny.
Stan obecny
Obecnie zajmuję się wszystkimi ramami. Obejmuje to ocenę strumienia wejściowego poprzez manipulację emulatorem, konfigurację i porzucenie, konfigurację itp. A jako swego rodzaju symbol zastępczy, optymalizator jest bardzo podstawowym algorytmem genetycznym. Po prostu ocenia populację strumieni wejściowych, przechowuje / zastępuje zwycięzcę i generuje nową populację poprzez mutowanie strumienia zwycięzcy. Proces ten trwa do momentu spełnienia dowolnych arbitralnych kryteriów, takich jak czas lub numer generacji.
Zauważ, że najwolniejszą częścią tego programu będzie zdecydowanie ocena strumienia wejściowego . Wynika to z emulacji gry dla n klatek. (Gdybym miał czas, napisałbym własny emulator, który zapewniał haczyki do tego rodzaju rzeczy, ale na razie pozostaję z syntezowaniem wiadomości i modyfikowaniem pamięci dla istniejącego emulatora z innego procesu.) Na moim głównym komputerze, który jest dość nowoczesny, ocena 200 klatek zajmuje około 14 sekund. Jako taki wolałbym algorytm (biorąc pod uwagę wybór), który minimalizuje liczbę ocen funkcji.
Stworzyłem system w ramach, który jednocześnie zarządza emulatorami. Jako taki mogę oceniać wiele strumieni jednocześnie za pomocą liniowej skali wydajności, ale praktycznie mówiąc, liczba działających emulatorów może wynosić tylko od 8 do 32 (a 32 to naprawdę naciska), zanim wydajność systemu spadnie. Oznacza to (biorąc pod uwagę wybór), że algorytm, który może przetwarzać dane podczas przeprowadzania oceny, byłby bardzo korzystny, ponieważ optymalizator może wykonać pewne operacje podnoszenia podczas oczekiwania na ocenę.
Jako test, moją funkcją oceny (w przypadku gry Banjo Kazooie ) było sumowanie, na klatkę, odległości od gracza do punktu bramkowego. Oznaczało to, że optymalnym rozwiązaniem było jak najszybsze zbliżenie się do tego punktu. Ograniczenie mutację tylko drążek analogowy, zajęło jeden dzień, aby uzyskać okay rozwiązanie. (Było to przed wdrożeniem współbieżności.)
Po dodaniu współbieżności włączyłem mutację naciśnięć przycisków A i wykonałem tę samą funkcję oceny w obszarze wymagającym przeskoku. Przy uruchomionych 24 emulatorach dotarcie do celu z początkowo pustego strumienia wejściowego zajęło około 1 godziny, ale prawdopodobnie musiałoby trwać kilka dni, aby osiągnąć poziom zbliżony do optymalnego.
Problem
Problem, przed którym stoję, polega na tym, że nie wiem wystarczająco dużo o matematycznym polu optymalizacji, aby wiedzieć, jak właściwie modelować mój problem optymalizacji ! Mogę z grubsza podążać za koncepcją wielu algorytmów opisaną na przykład w Wikipedii, ale nie wiem, jak skategoryzować mój problem lub wybrać najnowocześniejszy algorytm dla tej kategorii.
Z tego, co mogę powiedzieć, mam problem kombinatoryczny z bardzo dużym sąsiedztwem . Na początku, że funkcja oceny jest niezwykle nieciągłe, nie ma gradientu, i ma wiele płaskowyże . Ponadto nie ma wielu ograniczeń, choć chętnie dodam możliwość wyrażenia ich, jeśli pomoże to rozwiązać problem; Chciałbym pozwolić na określenie, że przycisk Start nie powinien być używany, na przykład, ale nie jest to ogólny przypadek.
Pytanie
Więc moje pytanie brzmi: jak to modelować? Jakiego rodzaju problem optymalizacji próbuję rozwiązać? Którego algorytmu mam użyć? Nie boję się czytać prac naukowych, więc daj mi znać, co powinienem przeczytać!
Intuicyjnie algorytm genetyczny nie może być najlepszy, ponieważ wydaje się, że tak naprawdę się nie uczy. Na przykład, jeśli naciśnięcie Start wydaje się zawsze pogarszać ocenę (ponieważ wstrzymuje grę), powinien istnieć jakiś projektant lub mózg, który uczy się: „naciśnięcie Start w dowolnym momencie jest bezużyteczne”. Ale nawet ten cel nie jest tak trywialny, jak się wydaje, ponieważ czasami naciśnięcie przycisku Start jest optymalne, na przykład w tak zwanych „pauzach w tył-długie skoki” w Super Mario 64 ! Tutaj mózg musiałby nauczyć się o wiele bardziej złożonego wzoru: „naciśnięcie przycisku Start jest bezużyteczne, z wyjątkiem sytuacji, gdy gracz znajduje się w tym bardzo specyficznym stanie i będzie kontynuował kombinację naciśnięć przycisków ”.
Wydaje się, że powinienem (lub maszyna mogłaby się tego nauczyć) reprezentować dane wejściowe w inny sposób, bardziej dostosowany do modyfikacji. Dane wejściowe na klatkę wydają się zbyt szczegółowe, ponieważ tak naprawdę potrzebne są „akcje”, które mogą obejmować kilka ramek ... jednak wiele odkryć dokonuje się na zasadzie klatka po klatce, więc nie mogę całkowicie wykluczyć ( wspomniana pauza w tył-skok w dal wymaga precyzji na poziomie klatki). Wydaje się również, że fakt, że dane wejściowe są przetwarzane szeregowo, powinien być czymś, co można wykorzystać, ale nie jestem pewien, jak to zrobić.
Obecnie czytam o (Reaktywnym) wyszukiwaniu Tabu, wyszukiwaniu sąsiedzkim na bardzo dużą skalę, optymalizacji opartej na nauczaniu i optymalizacji oraz optymalizacji kolonii mrówek.
Czy ten problem jest po prostu zbyt trudny do rozwiązania za pomocą innych niż przypadkowe algorytmy genetyczne? Czy jest to tak naprawdę trywialny problem, który został rozwiązany dawno temu? Dziękujemy za przeczytanie i z góry dziękuję za wszelkie odpowiedzi.
