Das perfekte Snake-Spiel: Algorithmen, um den Klassiker zu meistern

Nur wenige YouTuber erklären Algorithmen und künstliche Intelligenz im Allgemeinen so gut wie Code Bullet. Seine Videos haben alles: Erfolge, Misserfolge, Beleidigungen, emotionale Krisen und einfache Herausforderungen, die zu gigantischen werden. Sein neuestes Video ist eine Fortsetzung des Projekts, das er vor Monaten veröffentlicht hat, in dem er darum kämpfte, dass eine künstliche Intelligenz lernt, Snake per Q-Learning zu spielen. Diesmal greift er erneut an und sucht Revanche, und obwohl die „Perfektion“ in den Videos von Code Bullet mit Vorsicht zu genießen ist, ist das Endergebnis dem vorherigen weit überlegen.

Es ist nicht das erste Mal, dass wir über künstliche Intelligenzen sprechen, die darauf trainiert wurden, Spiele zu meistern. Googles Deep-Q wurde mit Titeln für den Atari 2600 trainiert, insbesondere mit Albträumen auf dem Niveau von Montezuma's Revenge. Facebook nahm mit seinen Bots bereits an StarCraft-Turnieren teil, und OpenAI erzielte hochkarätige Siege bei DotA 2.

Die Verbindung zwischen Videospielen und künstlichen Intelligenzen wird nur noch stärker werden, aber unabhängig von der Qualität der Partien ist es keine schlechte Idee, ein wenig über den Prozess im Hintergrund zu lernen. Nehmen wir den Fall von Snake. Ein mehr als einfaches Spiel, wenn es von einem Menschen gespielt wird, aber was bräuchte eine künstliche Intelligenz, um es vollständig zu erobern?

Code Bullet auf YouTube entschied sich, diese Frage zu beantworten... und ich denke, er bereut es ein wenig. Nachdem er in seinem ersten Video Mitte Juli mit Q-Learning gelitten hatte, kehrte er zurück und warf seine gesamte bisherige Arbeit weg und begann von Null. Snake hat vier grundlegende Befehle: oben, unten, links und rechts. Es gibt eine Mauer am Rand der Karte, aber der eigene Körper der Schlange fungiert als innere Mauer, mit der zusätzlichen Schwierigkeit, dass er sich bewegt. Wenn man die Anzahl der Wege berechnet, beträgt die ungefähre Zahl 295 Trillionen Möglichkeiten... das heißt, es braucht etwas anderes.

Die erste Idee war, die Wege zu priorisieren, die es der Schlange ermöglichen, sich dem Futter zu nähern, anstatt sich mit Hilfe des A*-Algorithmus zu entfernen, einem der beliebtesten Algorithmen im Bereich Pathfinding... aber es funktionierte nicht. Als sie eingeklemmt wurde, hörte die Schlange einfach auf, sich zu bewegen. Die Lösung bestand darin, A* auf den Kopf zu stellen: Anstatt den kürzesten Weg zu suchen, nimmt die Schlange den längsten, was in gewisser Weise das ist, was alle Snake-Spieler tun sollten, wenn die Schlange sehr groß wird. Hinzu kam eine weitere Bedingung: Die Schlange muss immer in der Lage sein, auf 80 Prozent der leeren Blöcke zuzugreifen...

... und fast hätte es geklappt. Ein weiterer Neustart, und so erreichte er den sogenannten „Hamilton-Zyklus“, der die Snake-Karte als einen Kreislauf voller Knoten interpretiert, die er nur einmal besuchen und zum Anfang zurückkehren muss. Alles, was der neue Algorithmus tun musste, war, Hamilton-Zyklen zu erzeugen und jeden davon buchstabengetreu zu befolgen... aber das ist Code Bullet zu langweilig, also nahm er eine kleine Anpassung vor, damit die Schlange gelegentlich Abkürzungen nimmt. Ergebnisse? Der erste war ein Erfolg, mit einem perfekten Snake-Spiel. Der zweite scheiterte um nur zwei Blöcke... obwohl die Karte riesig war.