Bot programmieren für OpenRA


Obwohl OpenRA standardmäßig nicht vorsieht, dass man dafür eigene AI Bots schreibt ist es notwendig darüber nachzudenken, wie denn der optimale Bot geschaffen sein müsste. Denn erstens, ist OpenRA derart flexibel, dass in naher Zukunft vielleicht eine Lua-Schnittstelle entwickelt wird, die derartige Plugins erlaubt und zweitens gibt es mit der AI Challange einen Wettbewerb (Ants, 2011) der genau dies vorsieht. Auch dort muss in einer Ameisenkolonie eine Siegstrategie entwickelt werden.

Aber wie geht man dazu am besten vor? Die gute Nachricht vorneweg: da OpenRA ein Computerspiel ist (und nicht etwa eines von diesen Roboter-Challanges die im richtigen Leben stattfinden) sind alle Spielinformationen im Computer bereits vorhanden. Es kann in Computerspielen keine Überraschungen geben, dass plötzlich irgendein Roboter ohne Strom dasteht oder derlei Ungemach mehr. Und das bedeutet, so für alle Computerspiele kann man auch für OpenRA eine Künstliche Intelligenz entwickeln die diesen Namen verdient. Erstaunlicherweise gibt es kein Computerspiel auf der Welt, für das bisher noch keine KI entwickelt werden konnte. D.h. in 100% aller Spiele sind Computer besser als Menschen: Computerschach, Lemmings, Mario AI usw. Die Liste ist endlos. Meist sind die Herausforderungen anderer Natur als in der KI an sich. Meist liegen die Probleme darin, dass die CPU Rechenzeit zu niedrig ist, um den Spielbaum vollständig zu durchlaufen. Und damit sind wir auch schon mittendrin im Abenteuer der Künstlichen Intelligenz von Computerspielen.

Man kann sich OpenRA ungefähr mit dem Endspiel beim Computerschach vergleichen. Und zwar selbst dann, wenn das OpenRA Spiel gerade erst seit 1 Sekunde läuft. Auch dann ist man bereits im Endspiel. Damit ist gemeint, von diesem Zeitpunkt aus betrachtet, ist die Anzahl möglicher Optionen streng limitiert. Man kann nicht mehr irgendwas bauen, sondern nur noch entsprechend der vorhandenen Tiberium-Vorräte sowie der Aktionen der Gegner. Anders gesagt, mit einem genügend schnellen Rechner kann man das Spiel komplett bis zu Ende durchrechnen und sagen wer gewinnt und welche Aktionen dafür erforderlich sind. Ähnlich wie beim Schach ist der dabei entstehende Spielbaum gigantisch. Das bedeutet, alle Möglichkeiten durchzuprobieren ist nur eine theoretische Option. Lediglich ein Quantencomputer könnte derartiges leisten.

In der Praxis benötigt man deshalb einen Algorithmus, der ebenfalls eine Sieg erringt, aber dafür weniger CPU Zeit benötigt. Ein guter Ansatz dafür ist eine evolutionäre Heuristik. Damit ist gemeint, dass man im Spiel ein Computerprogramm entwickelt. Ein sehr einfaches Computerprogramm lautet z.B.:
1. Verdiene möglichst viel Geld
2. Wenn die Basis angegriffen wird, hole alle Einheiten zur Basisverteidigung zurück
3. Baue möglichst viele Panzer

Das sind drei simple Regeln, die sich als Computercode umsetzen lassen und ein bestimmtes Spielverhalten ergeben. Da es sehr simple Regeln sind, wird eine KI damit zwar anfangs gut spielen können, im späteren Verlauf jedoch meist der unterlegene sein. Anders als eine Brute-Force-Suche im Spielbaum kommt diese Heuristik jedoch mit sehr wenig CPU-Leistung aus. Um die Regeln vollständig zu durchlaufen benötigt man nur wenig Computerpower. Das bedeutet, unabhängig von Sieg oder Niederlage weiß die Maschine zu jedem Zeitpunkt was gerade zu tun ist. Zumindest gegen eine Zufallsstrategie („Wähle per Zufallsgenerator den nächsten Zug aus“) ist diese Strategie im Vorteil.

Der Begriff „evolutionäre Heuristik“ beschreibt nun, dass sich die Spielstrategie ändert. Denn wir wissen ja nicht, was die optimale Strategie bei OpenRA ist (abgesehen von der Brute-Force-Methode). Das Ziel ist es, eine Heuristik zu finden, die unterhalb einer vorgegeben CPU-Verbrauchs-Schwelle bleibt und dabei die Siegwahrscheinlich maximiert. Um das zu erreichen, müssen verschiedene Heuristiken der Reihe nach durchprobiert werden. Dadurch spaltet sich das Gesamtproblem auf:
1. außerhalb des eigenen Spieles: finden der optimalen Heuristik
2. im Spiel: Anwenden der Heuristik

STAND DER OPENRA BOTS
Derzeit gibt es in OpenRA vier unterschiedliche KI-Bors: Normal AI, Rush AI, Naval AI und Turtle AI. Sie alle basieren auf Heuristiken, die manuell einkodiert wurden. D.h. Irgendwo im Programmtext ist hinterlegt, was die KI zu einem bestimmten Zeitpunkt tun muss. Anders als eine Brute-Force-Suche führen sie nicht direkt zum Sieg sondern sind meist ungeeignet für bestimmte Spielsituationen.

Der Ausweg besteht darin, dass man die Brute-Force Methode nicht direkt für das Finden des optimalen nächsten Zuges einsetzt, sondern zum Finden der optimalen Heuristik. Aus spielerischen Aspekten ergibt das keinen Sinn, wird aber sinnvoll überall dort, wo es an Rechenpower mangelt. Zur Erinnerung: natürlich könnte man OpenRA quasi als Endspiel mittels Brute-Force optimal lösen. Ähnlich wie die Deep Blue Engine ist es möglich für einen Computer, jeden Zug probezuhandeln, die sich daraus ergebenden Folgezüge zu berücksichten. So hätte man eine Art von Gottesmaschine, die sowohl im Mikromanagement als auch im Makromanagement immer den richtigen Zug ausführt. Niemand könnte eine solche Engine noch besiegen. Sie würde immer gewinnen. Eine eigentliche Spielstrategie würde sie nicht verfolgen. Stattdessen wird von einem gegebenen Ausgangszustand einfach durchprobiert, was es für Möglichkeiten gibt, und für jede dieser Optionen bestimmt welche Folgen sie erzeugt.

Nur, OpenRa ist nicht irgendein theoretisches Spiel was auf einem unendlich schnellen Computer abläuft, sondern selbst ohne KI gibt es bereits time-lags. So dass für Rechenaufgaben der KI nur sehr wenig CPU-Zyklen bereitstehen. Da pro Sekunde mindestens 25 Bilder erzeugt werden müssen, darüberhinaus noch der Netzwerkstack verwaltet werden muss, ist es erforderlich an den CPU Zyklen zu sparen wo es nur geht. Deshalb bedarf es einer Art Standard-Strategie die immer ausgeführt werden kann und die fast nichts kostet. Und wenn dann noch CPU Zeit übrig ist, kann der Computer versuchen, diese Standardstrategie (die Heuristik) zu verbessern. In den meisten Fällen ohne Erfolg, aber manchmal vielleicht doch.

HEURISTIKEN
Wie findet man eine gute Heuristik? Natürlich mittels Wahrscheinlichkeitsrechnung. Dazu gilt es, in einer Sandbox zunächst möglichst viele Spiele von OpenRA zu erzeugen. Also tatsächliche Spielbäume mit konkreten Gewinn / Verlust-Szenarien. Um dann im zweiten Schritt Gemeinsamkeiten in den Gewinner-Spieler zu detektieren. Dieses wird als Datamining bezeichnet. Über eine Cluster-Analyse wird bestimmt welche Aktionen ausgeführt werden müssen, um einen Sieg zu erzielen.

Der Ansatz eine Heuristik zu finden wirkt anfangs ungewöhnlich. Ist doch die allgemeine Annahme, es würde nur darum gehen zu gewinnen. OpenRA spielt man meist deshalb um sich am Ende auf die Schulter zu klopfen und um den Geschwack des Erfolges zu schmecken. Und bis heute hält sich der populäre Mythos, dass Künstliche Intelligenz genau dies nicht könne: gewinnen. Weil, wenn eine Maschine in der Lage wäre ein Spiel zu gewinnen, womöglich noch gegen einen Menschen, dann ist die Maschine erfolgreicher als der Mensch. Und das würde bedeuten, es wäre tatsächlich eine Künstliche Intelligenz. Nur ist genau das wirklich nie ein Problem gewesen. Wie bereits in der Einleitung erwähnt, gibt es kein einziges Computerspiel bei dem Maschinen schlechter spielen als Menschen. Der einzige Fall, bei dem Maschinen gegen Menschen unterlegen sind, ist die wirkliche Welt. Also wo echte Roboter zum Beispiel einen Gegenstand greifen sollen oder soetwas. Aber dieses Versagen entsteht dadurch, dass die echte Welt nicht vollständig als Computerspiel implementiert wurde. Meist gibt es nur ein rudimentäres 3D Abbild der Wirklichkeit und das ist dann auch noch falsch. Das ist ungefähr so ähnlich, als wollte im Schach gewinnen ohne die Spielregeln zu kennen.

Bei Computerspielen ist das jedoch nicht der Fall. Sie haben gemeinsam, dass die Spiele funktionieren. Ein bugfreies OpenRA ist die Vorraussetzung über dafür überhaupt eine KI entwickeln zu können. Und unter dieser Bedingung ist genau das tatsächlich möglich. Die Entwicklung einer KI ist nun nicht mehr die eigentliche Herausforderung. Sondern die Schwierigkeit ist nur noch, wie man mit gegebener Rechenpower eine möglichst hohe Spielstärke realisiert.

Der hier vorgestellte Ansatz der evolutionären Heurstik löst das Problem in dem er Heuristiksuche vom eigentlichen Spiel abkoppelt. Man kann beispielsweise als Vorbereitung auf ein Turnier mehrere Zigtausend Spiele über Datamining-Techniken analysieren, daraus dann die optimale Heuristik distillieren und diese dann zu lächerlich geringen CPU-Zyklen in einem tatsächlichen Spiel einsetzen.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s