Idealna gra w Snake: Algorytmy, które opanowują klasyka

Mało który youtuber wyjaśnia algorytmy i sztuczną inteligencję tak jak Code Bullet. Jego filmy mają wszystko: sukcesy, porażki, obelgi, kryzysy emocjonalne i proste wyzwania, które stają się gigantyczne. Jego najnowszy film jest kontynuacją projektu opublikowanego miesiące temu, w którym walczył o to, aby sztuczna inteligencja nauczyła się grać w Snake'a za pomocą Q-learningu. Tym razem wraca do ataku, szukając rewanżu, i chociaż „perfekcji” w filmach Code Bulleta nie należy brać dosłownie, końcowy wynik jest znacznie lepszy od poprzedniego.

To nie pierwszy raz, gdy mówimy o sztucznych inteligencjach szkolonych do opanowywania gier. Deep-Q od Google był trenowany na grach Atari 2600, a zwłaszcza na koszmarach takich jak Montezuma's Revenge. Facebook wziął już udział z botami w turniejach StarCraft, a OpenAI odniosło głośne zwycięstwa w DotA 2.

Więź między grami wideo a sztuczną inteligencją będzie się tylko umacniać, ale niezależnie od jakości rozgrywek, warto dowiedzieć się czegoś o procesie w tle. Weźmy przypadek Snake'a. To gra więcej niż prosta dla człowieka, ale czego potrzebowałaby sztuczna inteligencja, aby ją całkowicie opanować?

Code Bullet na YouTubie postanowił odpowiedzieć na to pytanie... i chyba trochę tego żałuje. Po męce z Q-learningiem w swoim pierwszym filmie w połowie lipca, wrócił do ataku, wyrzucając całą swoją dotychczasową pracę do kosza i zaczynając od zera. Snake ma cztery podstawowe komendy: góra, dół, lewo i prawo. Na obwodzie mapy znajduje się ściana, ale ciało węża samo działa jak wewnętrzna ściana, z dodatkową trudnością, że się porusza. Obliczając liczbę ścieżek, przybliżona liczba to 295 trylionów możliwości... więc potrzebuje czegoś innego.

Pierwszym pomysłem było priorytetyzowanie ścieżek, które pozwalają wężowi zbliżyć się do jedzenia zamiast się oddalać, za pomocą algorytmu A*, jednego z najpopularniejszych w dziedzinie pathfindingu... ale nie zadziałało. Kiedy został uwięziony, wąż po prostu przestał się ruszać. Rozwiązaniem było odwrócenie A* do góry nogami: zamiast szukać najkrótszej trasy, wąż wybiera najdłuższą, co w pewnym sensie jest tym, co powinni robić wszyscy gracze w Snake'a, gdy wąż staje się bardzo duży. Do tego dodał kolejny warunek: wąż musi zawsze mieć dostęp do 80 procent pustych bloków...

... i prawie mu się udało. Kolejny restart, i tak doszedł do tak zwanego „Cykle Hamiltona”, który interpretuje mapę Snake'a jako obwód pełen węzłów, które należy odwiedzić tylko raz i wrócić na początek. To wszystko, co nowy algorytm powinien robić, to generować cykle Hamiltona i podążać za każdym co do joty... ale to jest nudne dla Code Bulleta, więc dokonał drobnej poprawki, aby wąż od czasu do czasu skracał drogę. Wyniki? Pierwszy był sukcesem – idealna gra w Snake'a. Drugi zakończył się porażką zaledwie o dwa bloki... chociaż mapa była ogromna.