Algorytm ewolucyjny przewyższa maszyny do głębokiego uczenia się w grach wideo

Przy całym ekscytacji sieciami neuronowymi i technikami głębokiego uczenia, łatwo sobie wyobrazić, że świat informatyki składa się z niewiele więcej. W końcu sieci neuronowe zaczęły przewyższać ludzi w zadaniach, takich jak rozpoznawanie obiektów i twarzy, oraz w grach, takich jak szachy, Go i różnych arkadowych grach wideo.

Sieci te opierają się na sposobie działania ludzkiego mózgu. Nic nie może mieć większego potencjału, prawda?

Nie do końca. Całkowicie inny rodzaj przetwarzania może być znacznie potężniejszy niż sieci neuronowe i głębokie uczenie. Ta technika opiera się na procesie, który stworzył ludzki mózg — ewolucji. Innymi słowy, sekwencja iteracyjnych zmian i selekcji, która stworzyła najbardziej złożone i wydajne maszyny znane ludzkości — oko, skrzydło, mózg i tak dalej. Potęga ewolucji jest cudem do zobaczenia.

Dlatego informatycy od dawna próbują wykorzystać jego możliwości. Tak zwane przetwarzanie ewolucyjne osiągnęło kilka niezwykłych osiągnięć w ciągu 30 lat, odkąd po raz pierwszy zastosowano w nich optymalizację fabrycznych linii produkcyjnych dla ciągników.

Ale w ciągu ostatnich kilku lat ta dziedzina informatyki musiała odgrywać drugie skrzypce w stosunku do maszyn głębokiego uczenia i ich ogromnego sukcesu.

Dziś sytuacja wygląda na odwróconą dzięki pracy Dennisa Wilsona i kilku kolegów z Uniwersytetu w Tuluzie we Francji. Ci faceci pokazali, w jaki sposób obliczenia ewolucyjne mogą dorównać wydajności maszynom głębokiego uczenia się w emblematyczne zadanie, które po raz pierwszy zapewniło im sławę w 2013 roku — umiejętność przewyższania ludzi w arkadowych grach wideo takich jak Pong, Breakout i Space Invaders. Prace sugerują, że obliczenia ewolucyjne powinny być tak samo szeroko promowane, jak ich relacje oparte na głębokim uczeniu się.

Obliczenia ewolucyjne działają w zupełnie inny sposób niż sieci neuronowe. Celem jest stworzenie kodu komputerowego, który rozwiąże określony problem przy użyciu podejścia, które jest nieco sprzeczne z intuicją.

Konwencjonalnym sposobem tworzenia kodu jest pisanie go od pierwszych zasad z myślą o konkretnym celu.

Obliczenia ewolucyjne wykorzystują inne podejście. Zaczyna się od kodu wygenerowanego całkowicie losowo. I to nie tylko jedna wersja, ale wiele wersji, czasem setki tysięcy losowo złożonych fragmentów kodu.

Każdy z tych kodów jest testowany, aby sprawdzić, czy osiąga wymagany cel. I oczywiście cały kod jest okropny, ponieważ jest generowany losowo.

Ale przez przypadek niektóre fragmenty kodu są trochę lepsze od innych. Te fragmenty są następnie reprodukowane w nowej generacji kodu, który zawiera więcej kopii lepszych kodów.

Jednak następna generacja nie może być identyczną kopią pierwszej. Zamiast tego musi się w jakiś sposób zmienić. Zmiany te mogą obejmować zamianę dwóch terminów w kodzie — rodzaj mutacji punktowej. Lub mogą obejmować dwa kody, które są przecięte na pół, a połówki wymieniane – jak rekombinacja seksualna.

Każda z nowej generacji jest następnie testowana, aby zobaczyć, jak dobrze działa. Najlepsze fragmenty kodu są preferencyjnie reprodukowane w kolejnej generacji i tak dalej.

W ten sposób kod ewoluuje. Z biegiem czasu staje się lepszy, a po wielu pokoleniach, jeśli warunki są odpowiednie, może stać się lepszy niż jakikolwiek człowiek, który może zaprojektować koder.

Informatycy z powodzeniem zastosowali ewolucyjne podejścia do problemów, od projektowania robotów po budowę części samolotów.

Ale wypadło z łask z powodu ogromnego zainteresowania głębokim uczeniem. Dlatego ważnym pytaniem jest, czy może dorównać wydajności maszynom do głębokiego uczenia. Aby się tego dowiedzieć, Wilson i spółka zastosowali to podejście do opracowania kodu, który mógłby sterować arkadowymi grami komputerowymi z lat 80. i 90. XX wieku.

Gry te są dostępne w bazie danych zwanej Arcade Learning Environment, która jest coraz częściej wykorzystywana do testowania zachowań uczenia się różnego rodzaju algorytmów. Baza danych składa się z 61 gier Atari, takich jak Pong, Space Invaders, Breakout i Kung Fu Master.

Zadanie polega na stworzeniu algorytmu, który może grać w grę taką jak Pong, patrząc tylko na dane wyjściowe z ekranu, w taki sam sposób, w jaki grają ludzie. Tak więc algorytm musi przeanalizować każdą pozycję w grze, a następnie zdecydować, jak się poruszyć, aby zmaksymalizować swój wynik.

Sterowanie we wszystkich grach jest takie samo. Odpowiadają one ośmiu kierunkom, w które można poruszać kontrolerem (w górę, w dół, w lewo i w prawo oraz w czterech kierunkach po przekątnej), naciśnięciu przycisku, tym samym ośmiu ruchom połączonym z naciśnięciem przycisku i nie robieniu niczego. Nie wszystkie gry używają wszystkich 18 możliwych kombinacji, a niektóre używają tylko czterech.

Najpierw trzeba stworzyć kod. Podejście ewolucyjne wymaga słownika terminów, które można łączyć w kod komputerowy. Terminy wahają się od prostych działań, takich jak ADD (x+y)/2, do bardziej złożonych, takich jak zwrócenie 1-elementowego wektora x, jeśli x jest skalarem.

Wybór terminów składających się na to słownictwo jest ważny, a Wilson i wsp. używają zestawu już zdefiniowanego dla kartezjańskiego programowania genetycznego (jak nazywa się ich technikę).

Proces rozpoczyna się od losowego stworzenia kodu zawierającego 40 terminów. To jest genom programu. Genom ten jest następnie testowany, aby zobaczyć, jak dobrze gra, o czym świadczy wynik. W zależności od tego, jak dobrze działa, genom jest następnie reprodukowany z mutacjami i ponownie testowany, i tak dalej. W sumie zespół przetestował w ten sposób 10 000 genomów.

Wyniki stanowią ciekawą lekturę. Na początku genomy są kiepskie w grze. Ale z czasem stają się lepsze. I po wielu pokoleniach grają dobrze, czasem lepiej niż ludzie.

Wiele genomów grało w zupełnie nowe strategie gier, często te złożone. Ale czasami znajdowali proste, przeoczone przez ludzi.

Na przykład podczas gry w mistrza Kung Fu algorytm ewolucyjny odkrył, że najcenniejszym atakiem był cios przykucnięcia. Kucanie jest bezpieczniejsze, ponieważ pozwala uniknąć połowy pocisków wymierzonych w gracza, a także atakuje wszystko w pobliżu. Strategia algorytmu polegała na wielokrotnym użyciu tego manewru bez żadnych innych działań. Z perspektywy czasu używanie wyłącznie ciosu przykucniętego ma sens.

To zaskoczyło ludzkich graczy biorących udział w badaniu. Ręczne stosowanie tej strategii osiągnęło lepszy wynik niż normalne granie, a autor używa teraz ciosów przykucniętych wyłącznie podczas atakowania w tej grze, powiedzmy Wilson i spółka.

Ogólnie rzecz biorąc, rozwinięty kod działał dobrze w wielu grach, nawet przewyższając ludzi w grach takich jak Kung Fu Master. Co równie ważne, rozwinięty kod jest tak samo dobry, jak wiele podejść do głębokiego uczenia się i przewyższa je w grach takich jak Asteroids, Defender i Kung Fu Master.

Szybciej też daje wynik. Chociaż programy są stosunkowo niewielkie, wiele kontrolerów jest konkurencyjnych w stosunku do najnowocześniejszych metod dla zestawu wzorcowego Atari i wymaga mniej czasu na szkolenie, mówią Wilson i spółka.

Ewoluowany kod ma jeszcze jedną zaletę. Ponieważ jest mały, łatwo zobaczyć, jak działa. W przeciwieństwie do tego, dobrze znanym problemem związanym z technikami głębokiego uczenia się jest to, że czasami nie można dowiedzieć się, dlaczego podjęli określone decyzje, co może mieć konsekwencje praktyczne i prawne.

Ogólnie rzecz biorąc, jest to interesująca praca, która powinna sugerować informatykom, którzy skupiają się wyłącznie na głębokim uczeniu, że mogą przegapić pewną sztuczkę. Podejście ewolucyjne jest potężną alternatywą, którą można zastosować w wielu sytuacjach.

Rzeczywiście, niektórzy badacze zaczęli go używać do opracowywania lepszych maszyn do głębokiego uczenia się. Co może pójść nie tak?

Nr ref.: https://arxiv.org/abs/1806.05695 : Ewoluujące proste programy do grania w gry Atari

ukryć