Mathis Lichtenberger | StudentenPACK.

Digitale Ameisen auf der Jagd.

AI (Artificial Intelligence) steht für künstliche Intelligenz. Dabei handelt es sich hier nicht unbedingt um Roboter, die es auf die Weltherrschaft abgesehen haben, eher um KI-Spieler, wie wir sie aus Computerspielen kennen.

Genau darum geht es bei der von Google gesposerten AI Challenge (http://aichallenge.org), einem internationalen Programmier-Wettbewerb, der vor 4 Jahren an der Universität Waterloo entstanden ist und mittlerweile unentgeltlich von Freiwilligen organisiert wird. Der Wettbewerb findet in unregelmäßigen Abständen statt. Jedes Mal wird ein anderes Spiel bereitgestellt und KI-begeisterte Programmierer aus der ganzen Welt können Computerspieler schreiben, die dann gegeneinander um den ersten Platz in der Rangliste kämpfen. Einen Preis gibt es dabei nicht zu gewinnen, der vorletzte Gewinner konnte sich jedoch so seinen Job bei Google sichern.

In dem aktuellen Spiel ging es darum, eine Ameisen-Kolonie zu kontrollieren. Jeder Spieler startet mit einem oder mehreren Ameisenhügeln in den labyrinthartigen Karten, auf denen sich zu Beginn je eine Ameise befindet. Die Aufgabe des Computerspielers besteht nun darin, in jedem Zug für jede eigene Ameise anzugeben, in welche Himmelsrichtung sie sich ein Feld weiter bewegen soll. Gelangt eine Ameise zu einem der während des Spiels zufällig verteilten Futterstückchen, so bekommt der Spieler eine weitere Ameise, die aus einem der eigenen Hügel kriecht. Im Laufe eines Spiels wächst die Größe der Kolonie meist auf mehrere hundert Ameisen an, je mehr desto besser. Interessant wird es nun, wenn sich feindliche Ameisen sehr nahe kommen, denn dann werden diese automatisch in einen Kampf verstrickt. In einer Eins-gegen-Eins-Situation sterben beide, bei Zwei-gegen-Eins stirbt nur die allein kämpfende. Für mehr Ameisen gibt es ein komplizierteres System, so dass es zu komplexen Kampfformationen im Spiel kommt. Ziel des Spiels ist es, die meisten Punkte zu sammeln. Dabei bekommt man zwei Punkte für jede Vernichtung eines gegnerischen Hügels (Vernichten bedeutet, mit einer eigenen Ameise auf das Feld zu treten), jeder Verlust eines Hügels verringert den Score um einen Punkt. Ein Spiel wird mit bis zu 10 Spielern gleichzeitig gespielt und es dauert maximal 1000 Züge bis der Gewinner fest steht. Die Computerspieler haben pro Zug nur eine halbe Sekunde Bedenkzeit.

Für mich (im 3. Semester Informatik) begann alles schon im Juli des letzten Jahres. Auf der Suche nach Ablenkung, um bloß nicht für die bevorstehenden Klausuren lernen zu müssen, bin ich auf die AI Challenge gestoßen. Zum damaligen Zeitpunkt befand sich der Wettbewerb noch in der Vorbereitungsphase, etwa 200 Beta-Tester hatten schon Computerspieler hochgeladen. Ich war von dem Spiel begeistert und habe es schon nach wenigen Versionen geschafft, recht weit oben in der Rangliste vertreten zu sein.

Mitte August, während ich an der Wakenitz saß und mit den kleinen Robotik-Segelbooten von Professor Schläfer beschäftigt war, schafften es meine Ameisen zum ersten Mal ganz nach oben und blieben auch mehrere Wochen an der Spitze der Rangliste. Erst im Oktober waren die Organisatoren endlich soweit, dass der Wettbewerb offiziell starten konnte. Zum Entsetzen der meisten Beta-Tester hatten die Organisatoren aber überraschenderweise eine gravierende Regeländerung ausgeheckt. Bis dahin gab es noch keine Hügel, jeder Spieler startete mit einer Ameise und neue Ameisen sind direkt beim Futter entsprungen. Und plötzlich waren die Hügel da, wenige Tage bevor es offiziell los ging! Im Nachhinein war diese Änderung sehr sinnvoll, das Spiel wurde dadurch deutlich interessanter, die Punktevergabe einfacher und außerdem hatten die Beta-Tester nicht mehr so einen großen Vorteil gegenüber Neueinsteigern.

Nur wenige Tage nach dem offiziellen Start hatten sich bereits mehrere tausend Programmierer angemeldet und der Wettbewerb war in vollem Gange. Und ich, immer noch geschockt von der Regeländerung, hatte meine KI noch nicht auf die Hügel angepasst. Eine Woche nach dem Start war meine erste Version dann endlich einsatzbereit. Beim Hochladen hätte ich niemals erwartet, dass sie über einen Monat lang alle anderen Spieler dominieren würde, aber so kam es. Mein Bot, unter dem Benutzernamen xathis (sehr kreativ, Mathis mit X statt M) verharrte auf Platz #1, jeden Tag unterhielten sich meine Konkurrenten im Chat über meine Spiele und urteilten über meine Strategien, im AI-Challenge-Forum wurden eigene Themen über meinen Spieler erstellt.

Ich könnte Ewigkeiten über die Implentierung meiner Strategie erzählen (habe ich auch, in meinem englischen AI Challenge Post Mortem auf http://xathis.com), aber hier werde ich mich kurz fassen, um nicht allzu technisch zu werden. Allgemein habe ich kaum eine globale Strategie. Stattdessen hängt die Bewegung der meisten Ameisen ausschließlich von der lokalen Umgebung ab, aus dem Zusammenspiel ergibt sich aber ein insgesamt komplexes Gesamtverhalten.

Für fast alle Aufgaben im Spiel, wie die Erforschung der Karte, das Futtersammeln und die Verteidigung, waren Algorithmen zur Pfadfindung wichtig. Die Algorithmen, die Professor Linnemann in der überaus spannenden Vorlesung Algorithmen und Datenstrukturen erklärt, wie zum Beispiel die Breitensuche oder die Suche mit dem gerichteten A*-Algorithmus, sind also tatsächlig zu etwas zu gebrauchen! Dabei kann man sich das karogitterähnliche Spielfeld als Graph vorstellen, bei dem jedes besuchbare Feld ein Knoten im Graph ist und je zwei benachbarte Felder mit einer Kante verbunden sind. Das Futtersammeln etwa lässt sich nun realisieren, indem wir eine Breitensuche von dem Feld jedes Futterteilchens aus starten, die gleichmäßig in alle Richtungen nach einer eigenen Ameise sucht und diese Richtung Futter schickt.

Die Kampftaktik erwies sich als die größte Herausforderung, hier gibt mehrere mögliche Herangehensweisen. Ich habe mich in Kampfsituationen dafür entschieden, die Ameisen in Gruppen einzuteilen und für diese Grüppchen einen Zug voraus zu berechnen. Da eigene und gegnerische Züge gleichzeitig stattfinden, reicht es nicht, nur zu überlegen, welche eigenen Züge am sinnvollsten sind, man muss auch bedenken, wie die gegnerischen Ameisen im nächsten Zug stehen könnten. Umgesetzt habe ich die Vorausberechnung mit dem Minimax bzw. Alphabeta Algorithmus, auf dem auch moderne Schachcomputer basieren. Dabei wird zur Laufzeit ein Baum der möglichen Züge erstellt und per Tiefensuche durchlaufen. Der Verzweigungsgrad dieses Baumes ist abhängig von der Anzahl an Ameisen für die wir vorausberechnen. So müssen schon bei 8 Ameisen, die jeweils 4 mögliche Züge haben, über 65000 Kombinationen betrachtet und ausgewertet werden.

Der Wettbewerb bietet eine große Palette an möglichen Programmiersprachen: von C++, C#, Java über Python und Ruby bis hin zu PHP, JavaScript und sogar Pascal sowie Visual Basic sind unterstützt. Ich habe für meinen Bot Java gewählt, da Java recht schnell ist und ich mit der Sprache und der Entwicklungsumgebung Eclipse schon länger gut vertraut bin. Mein Code ist nicht sehr schön, er widerspricht vermutlichen allen Maßstäben der sauberen Programmierung, die wir Informatiker im Softwaretechnik-Praktikum in unserem 4. Semester über uns ergehen lassen müssen. Die Hauptklasse Strategy.java hat 1800 Zeilen Code, was vergleichsweise wenig ist, wenn man bedenkt, dass das Softwaretechnik-Praktikum um die 12000 Zeilen beinhaltet. Wie die meisten anderen Top-Platzierten, habe auch ich meinen Code nach dem Wettbewerb veröffentlicht, ihr könnt ihn euch auf http://github.com/xathis ansehen.

Die Uni Lübeck war bei der AI Challenge gut vertreten, neben mir haben noch 20 weitere Studenten einen Computerspieler hochgeladen. Während des Wettbewerbs haben wir ein Treffen im Keller der Metameute organisiert, um unsere Spieler lokal gegeneinander antreten zu lassen und uns über Strategien auszutauschen. Einer der Kommilitonen ist Ruben Beyer, der es auch in die Top 50 geschafft hat. Er sicherte sich Platz #39 und ist damit drittbester Deutscher geworden.

Nach der anfangs starken Führung meiner ersten Version im offiziellen Wettbewerb und über einem Monat auf Platz #1, kam unweigerlich der Zeitpunkt, an dem mich einer nach dem anderen in der Rangliste überholte. Ich war natürlich eifrig dabei, meine Version 2 zu entwickeln, aber jeder Versuch einer Verbesserung führte in anderen Situationen zu einer Verschlechterung des Spielverhaltens. Auf meinem Computer konnte ich meine verschiedenen Versionen gegeneinander antreten lassen, es ist mir nicht gelungen, eine KI zu schreiben, die fast immer gegen meine erste Version gewann. Trotzdem war ich mir dann eine Woche vor Ende des Wettbewerbs sicher genug und traute mich, die zweite Version hochzuladen, die von meinen Konkurrenten mit hohen Erwartungen angenommen wurde. Und tatsächlich gelang es meinem Spieler die Erwartungen zu erfüllen, ich schoss wieder an die Spitze! In den letzten Tagen vor Ende des Wettbewerbs und Beginn des Finales herrschte viel Wirbel in der Rangliste, da viele der Teilnehmer neue Versionen bereit hatten.

Am 19. Dezember wurde dann das Einsenden neuer Versionen gesperrt und das 5-tägige Finale begann. Ab diesem Zeitpunkt hatte keiner der Teilnehmer mehr einen Einfluss, Daumen drücken und hoffen war alles, was ihnen blieb. Mittlerweile hatten knapp 8000 Leute ihre Computerspieler hochgeladen. Fairerweise muss man dazu sagen, dass nur zwei- bis dreitausend davon ernsthaft etwas programmiert hatten, die meisten restlichen hatten Starter-Pakete hochgeladen, die nur zufällige Züge machten. Ich hatte kurz vor Beginn des Finales noch eine dritte Version meines Spielers hochgeladen, die allerdings nur kleine Bugfixes enthielt, sodass kaum ein Unterschied zur 2. Version festzustellen war.

Im Finale wurden um die 170 Spiele mit jeder KI gespielt, die nach einigen Tagen innerhalb der ersten 500 Platzierungen lag, die Spiele konnten online angesehen werden und auch die Veränderungen in der Rangliste waren jederzeit abrufbar. Nach wenigen Spielen war ich auf meinem Stammplatz an der Spitze der Rangliste angekommen, doch es sollte noch sehr spannend werden.

Das Finale war zeitlich ausgerechnet so gelegt, dass es nach deutscher Zeit um 3 Uhr morgens am 24. Dezember (Heiligabend!) endete. Um 0:00 Uhr war noch alles in Ordnung, doch der Benutzer GreenTea aus Russland kam mit seinem Punktestand in der Rangliste immer dichter an mich heran. Ich lenkte mich ab, indem ich meinem Post Mortem (ein Artikel, in dem ich erkläre, was mein Code tut) den letzten Schliff verlieh, doch alle paar Minuten war die Spannung zu groß und ich aktualisierte die Rangliste. Gegen halb eins, 150 Minuten vor dem Ende, geschah es dann tatsächlich: GreenTea übernahm den ersten Platz und ich rutschte auf die #2. Shit, ich war so dicht dran! Innerlich hatte ich die Hoffnung schon fast aufgegeben, aber dann endlich ließ seine Glückssträhne nach und ich kam wieder dichter an ihn heran. Nervenaufreibender hätte es nicht sein können. Um 2:30 waren wir gleichauf, jedes einzelne Spiel war entscheidend.

Ich starrte auf den Countdown auf der Website. 00:00:03… 2… 1… Endlich stand der Stundenzeiger der Uhr waagerecht und der Countdown bliebt bei null stehen. 3 Uhr nachts und ich war immer noch über GreenTea an der Spitze der Rangliste.

Erleichtert, aber immer noch leicht zitternd, änderte ich den Anfang meines Post Mortems auf die obligatorischen zwei Sätze, die bereits von den Gewinnern der beiden vorigen Wettbewerbe genutzt worden waren:

„I can’t believe I won.

I can’t believe I won decisively at all.“

Jemand hat die Diskussion eröffnet, mach mit!