Entwicklung

Einführung in Spiele-KI

Dirk Primbs   //   Oktober 14, 2009   //   0 Kommentare

Künstliche Intelligenz ist ein wichtiger Baustein glaubwürdiger Spielwelten. Wir helfen Ihnen beim unkomplizierten Einstieg in eine Materie mit Tiefgang.

Wie schaffe ich es, dass sich mein Computergegner intelligent verhält? Und welche Technologien stehen dazu zur Verfügung? Kaum ein Thema ist potenziell so vielschichtig wie das der künstlichen Intelligenz. In diesem Artikel werfen wir einen Blick auf Verfahren, mit denen in Computerspielen die Illusion eines echten Gegners aufgebaut wird.

Am Anfang steht die Entscheidung

Was macht einen Gegner intelligent? Diese fast schon philosophische Frage lässt sich nicht so einfach beantworten, ist aber der zentrale Grund für KI in Spielen. Denn ein Gegner, der sich zu berechenbar und ungeschickt verhält, kann durchaus den Spielspaß trüben oder sogar völlig kosten. Um die Illusion von Intelligenz zu erreichen, gibt es verschiedenste Verfahren, aber allen ist eines gemeinsam: Es geht darum, Entscheidungen zu treffen, die plausibel erscheinen und so oder so ähnlich auch von einem Menschen getroffen werden könnten. KI im Kontext von Spielen ist die Fähigkeit des Computergegners, unter genau definierten Bedingungen bestimmte Aufgaben (eine Basis bauen, den Spieler verfolgen, etc.) so zu bewältigen, dass dem Verhalten scheinbar Intelligenz anhaftet.

Im KI-Übrungsspiel AntMe programmieren Sie die Verhaltensweise eines Ameisenstammes. Die fleißigen Insekten müssen in möglichst kurzer Zeit möglichst viel Nahrung einsammeln und dabei gefräßige Käfer bekämpfen.


Deterministische Algorithmen

Die einfachste Möglichkeit, intelligentes Verhalten in Spielen zu implementieren, ist auf der Basis fest implementierter Regelwerke Entscheidungen zu treffen. Im Vergleich mit menschlichem Verhalten könnte man von einfachen Reflexen und Instinkten sprechen, die wir unserem Spielgegner mitgeben. Im Code-Beispiel 1 aus dem Spiel AntMe kontrollieren wir Ameisen durch selbst geschriebene Programme.
Liest man den Code, ist sofort klar, was er bewirkt. Die Ameise, die einem Käfer begegnet, fällt eine Entscheidung basierend darauf, wie viele Kollegen in der Nähe sind. Je nachdem, ob genug Verstärkung da ist, greift die Ameise an oder läuft vor dem Käfer weg -- eine klassische deterministische Entscheidung, vergleichbar mit Reflexen oder Instinkten beim Menschen. Je nachdem wie geschickt die vorgegebenen Regelwerke gewählt sind, kann schnell ein glaubwürdiger Eindruck von intelligentem Verhalten entstehen.
Ein bekanntes Beispiel für diese Art der Vorgehensweise ist das Verfolgen (oder Meiden) von Gegnern. Im Code-Beispiel 2 erweitern wir unser erstes Programm so, dass die Ameise einen Käfer mit Sicherheitsabstand verfolgt bis sie genügend Kollegen für einen Angriff sieht. Man könnte von einer Art Selbsterhaltungstrieb sprechen, den die Ameise hier an den Tag zu legen scheint. Auch wenn die Intelligenz vom Programmierer stammt, kann der Effekt verblüffend wirken. Garniert man ihn noch mit einigen Zufällen, etwa bei der Fortbewegung, wirkt das Ergebnis noch realistischer.

Code-Beispiel 1

Stimmung im Computer - State Machines

Angenommen, wir haben unsere KI mit einer Reihe deterministischer Algorithmen versorgt: Käfer angreifen, Zucker suchen oder Umgebung auskundschaften. Wie kombinieren wir nun diese Tätigkeiten -- vor allem dann, wenn sich einzelne Verhaltensweisen gegenseitig ausschließen? Die Antwort lautet State Machine. In unserem Beispiel verwenden die sogenannte Finite State Machine, wahrscheinlich die populärste Technik, KI in Spiele umzusetzen. Denn die Finite State Machine ist aufgrund ihrer einfachen Implementation in vielen Aufgabenfeldern extrem nützlich.
Im Kern geht es bei der darum, einen Computeralgorithmus in verschiedene Stati versetzen zu können, mit denen sich auch unterschiedliche Verhaltensweisen kombinieren lassen. Bleiben wir beim Beispiel unserer Ameisen und definieren einen Satz möglicher Zustände:

State 1: suchend
State 2: beschäftigt
State 3: angriffslustig

Mit jedem dieser Zustände verbinden wir unterschiedliche Verhaltensmuster:
State 1: Die Ameise läuft kreuz und quer über das Spielfeld bis Nahrung im Sichtfeld auftaucht. Taucht vorher ein Käfer auf, wechselt sie zu State 3. Findet sie Nahrung, wechselt die Ameise zu State 2, sammelt sie ein und trägt sie zum Bau.
State 2: Die Ameise läuft möglichst direkt zum Bau beziehungsweise zur Nahrung und weicht gegebenenfalls auftauchenden Käfern aus.
State 3: Die Ameise greift Käfer an oder verfolgt sie, bis genug andere Ameisen hinzustoßen. Sichtet sie unterwegs Nahrung, wechselt sie zu State 2. Verliert sie den Käfer aus der Sicht, wechselt sie zu State 1.
Es versteht sich von selbst, dass es sich hier nur um beispielhafte Vorgaben handelt. Nehmen wir an, wir haben die einzelnen Verhaltensmuster in einzelne Funktionen gepackt (etwa das Beispiel im vorigen Absatz), dann fehlt uns nur noch eine Variable, die den aktuellen Status hält und eine Stelle, an der wir diesen Status falls nötig ändern und entsprechende Aktionen einleiten. Natürlich kann es sein, dass eine Statusänderung nicht immer in alle Richtungen möglich ist. Um die Vorgehensweise zu demonstrieren, nehmen wir im Code-Beispiel 3 die Methode Sieht(Käfer) aus AntMe, da je nach State gerade in diesem Fall verschiedene Vorgehensweisen gefragt sind.

Code-Beispiel 2

Verhalten + Status = Verhaltensmuster

Kombiniert man State Machines und fest verdrahtete Verhaltensweisen, hat man Muster, die je nach Situation relativ komplex ausfallen können. Speziell in einem Implementationsstil wie dem eben gezeigten passiert es schnell, dass der Code unübersichtlich und damit schwerer verständlich und wartbar wird. Ein möglicher Ausweg ist, die verschiedenen in Methoden hinterlegten Verhaltensweisen zu benennen und in Listenstrukturen zu verwalten. Dann kann auf Verhalten fast schon konfiguratorisch zugegriffen werden, in dem in einer zentralen State Machine nur noch der Code hinterlegt wird, bei welchem Status welche Listeneinträge in welcher Reihenfolge auszuführen sind.

Erinnerung und erlerntes Verhalten

Bisher haben wir mit mehr oder weniger fixierten Entscheidungsprozessen gearbeitet. Was aber, wenn wir unserer KI erlauben wollen, sich in einem gewissen Rahmen selbst zu entwickeln? So schwammig wie sich der Begriff »Lernen« anfühlt, so einfach ist er zu implementieren. Beginnen wir mit der Erinnerung: Das Konzept des Speichers ist alles, was wir dazu brauchen. Eine Ameise, die über das Spielfeld läuft, kann sich beispielsweise merken, wo sie zuletzt Nahrung gesehen hat oder wo sich der Bau befindet. Als erinnerungswürdige Information gelten dabei alle, die uns im Spiel weiterbringen oder benutzt werden können, um im nächsten Schritt einen Lernerfolg zu identifizieren. Dazu brauchen wir zusätzlich zur Erinnerung eine Vorstellung davon, was denn gute oder schlechte Ergebnisse im Sinne unserer Spielelogik wären. Im Falle von AntMe kann man verschiedene Dinge als gut definieren: einen Käfer besiegen, Nahrung zum Bau tragen, Nahrung finden. Schlecht hingegen wäre: unterwegs an Erschöpfung sterben oder vom Käfer besiegt werden.
Um in unseren bisherigen Funktionen Raum für Lernen zu lassen, könnten wir beispielsweise ein paar Variablen von der Ameise selbst festlegen lassen. Wie wäre es zum Beispiel mit der Fluchtdistanz in unserem Käfer-Angriffs-Algorithmus? Wird die zu kurz gewählt, sterben mehr Ameisen - ist sie zu groß, entkommen die Käfer häufig. Wie implementiert man so etwas? Die Antwort in unserem Fall ist einfach: Zufallsgenerator gepaart mit Statistik. Die Ameise »spielt« mit den Zahlenwerten und sieht an der Spielestatistik, ob sich das Ergebnis zum schlechteren oder besseren hin verändert hat. Man kann diese Art zu lernen relativ weit treiben. Beispielsweise wäre es denkbar, komplette Verhaltensmuster auf diese Weise zu definieren und zu bewerten. Damit die Ergebnisse nicht zu chaotisch werden, sollte die Variation nicht unkontrolliert erfolgen, sondern immer als Abweichung vom bisherigen Modell definiert sein.

Code-Beispiel 3

Wie geht’s weiter? -- Genetische Algorithmen

Auch wenn die meisten Spiele-KIs mit Finite State Machines, Verhaltensmustern und einigen Zufallswerten arbeiten, so ist der nächste Schritt gar nicht weit entfernt: die Evolution. Genetische Algorithmen sind ein schönes Beispiel dafür, wie Prozesse aus der Natur in Software übertragen werden können. Hier wird nach Problemlösungen gesucht, indem man mit den Gesetzen der Vererbung arbeitet. Dazu werden Eigenschaften (im Spiel etwa Aggressivität, Geschwindigkeit, Kraft, usw.) als Gene dargestellt (häufig in Form von Binärketten), die bei jeder Generation des KI-Gegners mit ein wenig Zufall nach einem bestimmten Algorithmus variiert werden. Anschließend erfolgt die Bewertung, ob das resultierende »Gen« näher an der erwünschten Lösung liegt und sich eventuell eine weitere Mutation lohnt.

Fazit

KI in Spielen kann eine echte Herausforderung sein. Die grundlegenden Konzepte sind im Prinzip aber gar nicht so kompliziert. Insbesondere deshalb, weil aufwändigere Technologien wie neuronale Netze oder spezialisierte Agenten eher selten Anwendung finden. Trotzdem ist es wichtig, geschickt mit dem Instrumentarium zu arbeiten. Ein blühender Komponentenmarkt hilft dabei zusätzlich. So kann man etwa State Machine Implementierungen in Form von Regel-Engines erwerben oder gleich mit kompletten KI-SDKs auf Probleme wie Pathfinding oder ähnliches losgehen. Empfehlenswerte Versuchsfelder sind die programmierbaren Bots verschiedener Spiele oder Programmierspiele wie AntMe, Projekt Hoshimi & Co. Mit dem so erprobten Repertoire steht dann auch größeren Spiele-KI-Projekten sicherlich nichts mehr im Weg.

Dirk Primbs

zum Autoren: Dirk Primbs ist Technical Evangelist bei Microsoft Deutschland. Er befasst sich mit den Technologien in .Net, hegt aber spezielle Vorlieben für Themen im Grafik-, Smart-Clinet- und Security-Umfeld. Er spricht regelmäßig auf Konferenzen, schreibt Fachartikel und ist Referent beim Microsoft TechTalk.
dirk.primbs@microsoft.com

Kommentare

Einen Kommentar hinterlassen

Um einen Kommentar hinterlassen zu können, müssen Sie sich zuerst anmelden oder registrieren.

» zur Anmeldung
» zur Registrierung