Herausforderungen an die KI in Computerspielen

Cevat Yerli zeigte in seiner Keynote [1] eindrucksvoll den aktuellen hohen Stand von Grafikqualität in Computerspielen. Die Anforderung an Grafik ist hoch. Sowohl in den 3D-Modellen (die künstlerischen Aspekte) als auch in Game-Engines (die technischen Aspekte). Die Komplexität von Game-Engines zeigt David H. Eberly (3D Game Engine Design. Elsevier, 2006) [2]. Die synthetischen Welten kommen der grafischen Komplexität von der realen Welt stets näher. 1996 erschien Quake (1), das erste vollständige 3D-Spiel, in dem die Gegner und Gegenstände nicht durch 2D-Planes dargestellt wurden, sondern durch 3D-Geometrie. Fast 10 Jahre später erschien Quake 4 (2). Der grafische Unterschied wird in Abbildung 1 deutlich.

2007 kam die aktuelle Grafikreferenz namens Crysis (3) basierend auf der CryEngine 2 von Crytek auf den Markt. In [1] zeigte Cevat Yerli, dass die Qualität der CryEngine 2 (jetzt CryEngine 3) von realen Fotos auf den ersten Blick kaum zu unterscheiden ist, siehe Abbildung 2.

Aktuelles Beispiel für hohe Grafikqualität ist Modern Warfare 2 (4) aus dem Jahr 2009, siehe Abbildung 3.

Um ein realistisches Abbild in synthetische Welten zu erhalten, spielen neben der hohen Grafik­qualität weitere Faktoren eine wichtige Rolle. So zum Beispiel die physikalischen Gesetze. Moderne Physik-Engines (wie zum Beispiel PhysX von Nvidia oder die Havok-Engine) erlauben uns erst neue Ideen für Spiele zu erschaffen, wie zum Beispiel Portal (5). Reicht eine hohe Grafikqualität und Physik für eine lebendige synthetische Welt aus?

An dieser Stelle setzt der Artikel an. Eine lebendige synthetische Welt ist nur mittels moderner Methoden der Künstlichen Intelligenz (kurz KI) realisierbar. Somit kämen wir dem Wunsch einer realistischen Abbildung in einer synthetischen Welt näher. Es stellt sich lediglich die Frage, ob für Computerspiele eine realistische Abbildung erstrebenswert ist. Durch Arbeiten wie solche von Alexander Galloway (Gaming. University of Minnesota Press, 2006) [3] zeigt sich, dass der Computerspieler nicht an einer realistischen Abbildung unserer Welt interessiert ist, sondern viel mehr an einer realen Abbildung. Es ist legitim, dass in einer synthetischen Welt andere Naturgesetze oder Mechaniken existieren als in der realistischen Welt. Wichtig ist, dass diese glaubwürdig und konsistent sind. Oder in anderen Worten: Dass der Spieler der Welt glaubt und diese nicht hinterfragt. Eine reale Abbildung bedeutet auch, dass das Spiel sich einem einfachen und abstrakten Modell der realistischen Welt annimmt. Je realistischer ein Spiel wird, um so mehr verliert es den Spielcharakter und wandelt sich zu einer Simulation.

Für moderne und zukünftige Computerspiele besteht die Herausforderung in der Umsetzung von realen Welten, welche ein glaubwürdiges Modell der Physik und der KI realisieren.

Sichten auf die KI

Zuerst soll ein Blick auf die verschiedenen Sichten auf das Thema KI geworfen werden, siehe dazu Abbildung 4.

Publisher stellen den Wirtschaftsfaktor dar. Sie finanzieren Computerspiele, vermarkten und vertreiben diese. Entsprechend schauen Publisher beim Thema KI auf die Kosten der Umsetzung. Für Publisher ist es wichtig, dass die Produktion eines Computerspiels möglichst vorhersehbar und kalkulierbar sein sollte. Neue (in Computerspielen nicht verbreitete) KI Methoden bergen Risiken. So kann sich durch den Einsatz einer neuen und nicht in Computerspielen bewährten Technik ein potenzieller Zeitverzug in der Produktion ergeben. Dies wiederum führt zu höheren Kosten. Möchte man den potenziellen Zeitverzug minimieren, muss man ggf. auf existierende Software-Lösungen zurückgreifen, die ebenfalls die Kosten steigen lassen.

Eine weitere wichtige Aufgabe bei großen Publishern ist die Qualitätssicherung. Diese müssen sicherstellen, dass die KI keine Leistungsschwankungen oder unvorhersehbares Verhalten aufzeigen. Dieses potenzielle Risiko steckt in Black-Box-Ansätzen wie zum Beispiel bei Neuronalen Netzen [4].

Entwickler von Computerspielen haben häufig das Problem, keine Fachkräfte für die Entwicklung von modernen KI-Methoden zu haben. Das gesamte Wissen über Vor- und Nachteile, Risiken und Gewinne sowie deren Einsatzfähigkeiten ist häufig nicht vorhanden. Sollte dennoch das Wissen vorhanden sein, stellt sich die Frage, wann kann ein neuer KI-Ansatz entwickelt werden? Innerhalb der Produktion des Spiels ist es nicht mehr möglich, da schon alles für die Umsetzung geplant wurde. Bleibt nur noch die Vorproduktion oder außerhalb jeglicher Produktion. Innerhalb der Vorproduktion ist der Entwickler von der Zustimmung des Publishers abhängig und muss die Risiken, aber auch die möglichen Chancen aufzeigen sowie den Publisher vom Nutzen überzeugen. Außerhalb einer Produktion muss der Entwickler die Kosten komplett selbstständig tragen.

Unabhängig vom Wissen und den Kosten, stellt sich dem Entwickler die Frage, ob die KI performant genug entwickelt werden kann, damit sich die Systemvoraussetzungen für das Computerspiel in Grenzen halten und genug Leistung für die Grafikdarstellung vorhanden bleibt. Der Großteil der Systemleistung wird von den grafischen Prozessen und Algorithmen benötigt. Eine weitere Frage ist, ob die gewählte KI skalierbar ist in Bezug auf den Schwierigkeitsgrad. Es sollte einen einfachen Parameter geben, durch welche die »Intelligenz« der KI geregelt werden kann.

Zu guter Letzt sei noch auf einen letzten wichtigen Faktor auf Seiten der Entwickler hinzuweisen. Die KI muss zum Game Design passen! Es gibt Computerspiele die keine wirkliche KI zulassen, wie zum Beispiel bei Computerspielen des »Shoot’em up«-Genre (ein klassischer Vertreter sind die Spiele der »R-Type«-Reihe (6)).

Den wohl wichtigsten Faktor in Computerspielen stellt der Spieler selbst dar. Dieser wünscht sich eine faire KI. Ein Merkmal einer fairen KI ist, dass die KI nicht »cheaten« muss, um zu funktionieren. Strategiespiele wie Command & Conquer (7) sind typische Beispiele für KIs die »cheaten«. Dabei wird die KI über das gesamte Wissen der Karte beliefert. Nicht nur die topologischen Informationen werden geliefert, sondern auch alle Informationen zum Spieler selbst und seiner Lage sowie Situation. Ziel einer fairen KI sollte es sein, dieselben Kenntnisse über das Spiel und Spielmechaniken zu haben, wie der Spieler. Dies wird am ehesten erreicht, wenn der Zeitverzug durch die Bedingung über das Interface und die Interfacemöglichkeiten mit einberechnet werden. Somit sollte sich die KI genauso das Wissen aneignen wie der Spieler. Lediglich in Multiplayer-Spielen muss die KI das vollständige Wissen über die Gegebenheiten des Geländes haben, da in Multiplayer-Spielen immer wieder die gleichen Karten häufig gespielt werden und die KI einen »erfahrenen« Spieler abbilden soll.

Weiterhin wünscht sich der Spieler eine glaubwürdige KI, d. h. eine KI, welche dieselben Fehler macht wie ein menschlicher Spieler. Aber auch aus den Fehlern lernt (bis zu einem gewissen Grad). Zu einer glaubwürdigen KI gehört auch das Vermuten. Zum Beispiel könnte eine Shooter-KI auf Verdacht eine Granate in eine dunkle Ecke werfen oder in ein Haus, wo eine Stellung von anderen Spielern beschützt bzw. belagert wird, wie im Headquarter-Modus von Call of Duty: Modern Warfare (8). Häufig werden nicht alle sensorischen Möglichkeiten in die KI inte­griert. So zum Beispiel, wenn der Spieler Licht in einem Zimmer anmacht. Veränderung in der Lumineszenz oder auditive Wahrnehmung fehlen. Ab und zu wird die auditive Wahrnehmung vorgetäuscht, in dem ein Gegner »sagt«, er hätte was gehört, dabei ist der Spieler nur in die Nähe des Gegners gekommen und ein Ereignis wird ausgelöst.

Die akademische Sicht auf das Thema KI in Computerspielen ist häufig, die beste und unschlagbarste KI für ein Computerspiel zu schreiben. Es werden Herausforderungen gesucht, um diese zu lösen. Dabei soll der Mensch geschlagen oder mindestens in seiner Leistung imitiert werden. Dies soll zu neuen Erkenntnissen führen. Im besten Fall soll es ermöglichen, Rückschlüsse auf das menschliche Denken und Entscheiden zu erhalten.

Software für KI in Spielen

In diesem Kapitel soll ein kurzer Überblick über aktuelle Produkte gegeben werden, welche KI in Spielen integrieren. Das Unternehmen »Xaitment« wurde 2004 als Spin-Off des »Deutschen Forschungszentrum für Künstliche Intelligenz« (German Researchcenter for artifical intelligence) gegründet. Die Produkte werden von Kunden, wie z. B. Gameforge, Gas powered Games, Factor 5 und vielen anderen verwendet. Mit xaitMap sollen Pfad-Daten und Navigations-Meshs (kurz NavMeshs) erzeugt werden. Damit soll der KI das Wissen über die Karte und die Bewegung auf der Karte gegeben werden. In Abbildung 5 sind die grünen Flächen die begehbaren Flächen. Die Kuben stellen die Wegpunkte dar.

xaitMove² ist für das Bewegungsverhalten zuständig. Innerhalb des Creators (die graphische Oberfläche) können Verhaltensmuster der KI bestimmt werden (siehe Abbildung 6), wie zum Beispiel verfolge jemanden, schneide jemandes Weg, flüchte vor jemanden, usw.

Zum Modellieren von endlichen Automaten gibt es xaitControl. Ebenfalls kann mittels des Creators auf graphischer Ebene ein endlicher Automat erstellt werden, siehe Abbildung 7. Der Endliche Automat wird dann in FSM-Engine xaitControl geladen und im Spiel verwendet. Den Transitionen können Wahrscheinlichkeiten vergeben werden.

Xaitment bietet zwei Produkte an, welche als »High-Level AI« bezeichnet werden. xaitKnow stellt dabei die Wissensrepräsentation der Welt dar, siehe Abbildung 8. Das Wissen wird in xaitThink aufgegriffen und in ein Expertensystem integriert und verwendet, siehe Abbildung 9.

In Abbildung 10 wird das Zusammenspiel aller einzelnen Anwendungen gezeigt

Eine Alternative zu Xaitment ist das Unternehmen Artificial Technology, welches 2007 gegründet wurde. Deren Produkt heißt »EKI One«. Es beinhaltet viele Elemente von Xaitment, aber in einem Werkzeug vereinigt und in einem Workflow. Es kann laut Hersteller mit Animationssystemen gekoppelt werden und enthält ein Perzeption-System für auditive, visuelle und olfaktorische Wahrnehmungen. Weiterhin enthält es eine Echtzeitvorschau der aktuell erstellten KI.

Ein bekannter Middleware-Hersteller ist Havok. Die bekannteste Middleware von Havok ist deren Physik-Engine. Neben der Physik-Engine ist eine KI-Engine in das Sortiment mit aufgenommen worden. Die KI-Engine von Havok beinhaltet insbesondere die Erstellung und das Streaming von NavMeshs als auch die Pfadfindung sowie Bewegung auf den NavMeshs. Ein großer Vorteil von Havok ist die Unterstützung aller wichtigen Plattformen.

Alle Produkte lassen sich auf zwei wesentliche Punkte zusammenfassen. Zum einen Bewegung von NPCs /Gegner und regelbasierte Ansätze für die KI.

Aktueller Stand

Ein gängiges Mittel um KI vorzutäuschen, sind Endliche Automaten, welche nicht viel mit KI zu tun haben. Endliche Automaten ermöglichen einen einfachen regelbasierten Ansatz und können mit verschiedenen Mitteln wie Wahrscheinlichkeiten, Hierarchien und Fuzzy Logic angereichert werden. Diese Anreicherungen beschränken sich häufig auf Wahrscheinlichkeiten. Der Ansatz der Endlichen Automaten kann bis zum Ansatz der Expertensysteme erweitert werden (wie auch bei den Produkten von Xaitment und Artificial Technology). Mit der steigenden Anzahl von Zuständen lässt sich ein »realistisches« Verhalten vortäuschen. Aber der Aufwand für die Wartung, Erweiterbarkeit und Anpassbarkeit steigt ebenfalls mit der Anzahl der Zustände. Es ist fraglich, ob der Kostenaufwand für diese Technik gerechtfertigt ist. Nichtsdestotrotz wird es in A³-Spielen wie Thief 3 (9) und Crysis (3) immer noch verwendet.

Einzelne Endliche Automaten bzw. Regelsätze lassen sich mittels Profile gruppieren. Solche Profile kennt man aus Brettspielen, wie zum Beispiel »Mensch ärger Dich nicht«. Diese Profile stellen immer eine dominierende Strategie dar, wie zum Beispiel »Schlag immer wenn möglich einen Spieler« oder »auf Sicherheit spielen«. Diese Profile findet man in Spielen, wie zum Beispiel Heroes of Might & Magic (10) wieder. In diesem Spiel finden sich unterschiedliche KI-Profile im Leveleditor wieder, wie zum Beispiel Kundschafter, Erbauer und viele andere.

Ein weiteres gängiges Mittel um KI vorzutäuschen, ist das Scripting von Verhalten, was wiederum das gleiche ist, wie das Modellieren eines Endlichen Automaten. Scripting schreibt genauso das Verhalten vor, wie bei Endlichen Automaten. Der Grad der Dynamik ist gleich. Einige Spiele bestehen in deren KI fast nur aus Scripting. Scripting ist zwingend ein wichtiger Teil für Computerspiele. Nur mit Scripting können effizient narrative Ereignisse zu einer bestimmten Zeit an einem bestimmten Ort ausgelöst werden.

Wegfindung wird in Computerspielen mit dem A*-Algorithmus umgesetzt und greift als einer der wenigen Teilbereiche auf die besten Lösungen der KI zurück. Teilweise wird der A*-Algorithmus angepasst, um die Bewegungen nicht zu starr wirken zu lassen, sondern organischer. Dabei greift der A*-Algorithmus auf ein NavMesh zurück, um seine Möglichkeiten zu identifizieren. Als Qualitätskriterium für NavMeshs gilt: Je weniger Navigationspunkte benötigt werden, um komplexe Wege zu realisieren, desto besser ist der Algorithmus für die Bewegung. Abbildung 11 zeigt links ein typisches Ergebnis für einen Raum in den ein NPC / Gegner eintreten kann und sich darin bewegen soll. Rechts wird das ideale Ergebnis gezeigt. Ein häufiges Problem bei der Bewegung sind immer noch nicht organische Bewegungen. In Computerspielen wie Risen (11) sind die Bewegungen der NPC / Gegner weiterhin kantig.

Wenn die aktuellen Ansätze zusammengefasst werden, könnte man überlegen von einer »Künstlichen Verdummung« anstelle von einer »Künstlichen Intelligenz« zu sprechen. Stattdessen könnte man auch sagen, dass es noch viel Spielraum gibt, um sich zu verwirklichen. Insgesamt wirken die Spielwelten immer noch größtenteils unnatürlich, leblos und dumm. Wenn Entwickler sagen, dass deren NPCs einen Tagesablauf nachgehen, ist die Frage, ob das auch nur wieder gescriptet wurde.

Einen ersten, besseren Ansatz finden wir im Computerspiel Black & White (12). Hier wird ein neuronales Netz verwendet. Neuronale Netze sind im Einsatz performant [4] und daher auch für Computerspiele geeignet. Lediglich zur Laufzeit kann das neuronale Netz nicht dazu lernen, da es zu viel Rechenaufwand darstellt. Für die Skalierbarkeit des Schwierigkeitsgrades kann folgende These aufgestellt werden: Je leichter der Schwierigkeitsgrad des neuronalen Netzes sein soll, desto mehr Trainingsdaten mit falschen Werten werden in die Trainingsphase eingestreut. Die kann aber zu Schwankungen in der KI oder zu unvorhersehbarem Verhalten führen. Weiterhin muss immer noch eine Testergruppe bei der Qualitätssicherung entscheiden, ob die KI sich nun in einem leichteren Schwierigkeitsgrad befindet oder nicht. Daher ist ein definitiver mathematischer Beweis nur schwer zu erbringen, da subjektives Empfinden eine Rolle spielt.

Herausforderungen für die Zukunft

Welche Möglichkeiten aus der KI stehen uns zur Verfügung, um die aktuelle Situation zu verbessern?

Eine Möglichkeit sind Agenten-Systeme. Jeder NPC stellt einen Agenten dar, mit eigenen Bedürfnissen und geht diesen nach. Agenten kommunizieren untereinander und tauschen Informationen aus oder versuchen deren Wünsche und Bedürfnisse zu erfüllen. Dadurch könnten lebendigere und dynamischere Welten entstehen. Lediglich muss gesichert werden, dass in diesem Agenten-System keine Deadlock-Situationen auftauchen oder wenn doch, diese gelöst werden können. Rollenspiele wären ideal für solche Agenten-Systeme. Insbesondere um das Leben in einer mittelalterlichen Stadt lebendig zu transportieren. Anstelle von Agenten-Systemen wären auch die Erkenntnisse aus dem Bereich des Artifical Life sehr interessant, um zum Beispiel soziale Netze zu modellieren und die Agenten darin agieren zu lassen.

Wie schon im letzten Kapitel angeschnitten sind die Methoden aus dem Soft Computing eine mögliche Lösung für effizientere KI Ansätze. Neben neuronalen Netzen, ist der Einsatz von Fuzzy Logic sehr gut denkbar, welches in gewissem Maße auch schon in Kombination mit Endlichen Automaten angesprochen und verwendet worden ist. Damit lässt sich starres Verhalten durch ein graduelleres Verhalten ablösen. Interessant wären insbesondere die Möglichkeiten von Neuro-Fuzzy-Systemen.

Eine andere Möglichkeit um adaptives Verhalten zu erhalten, wäre der Einsatz von Case Based Reasoning. Die KI speichert Schlüsselsituationen ab und holt diese bei ähnlichen Situationen aus dem Archiv raus. Der Erfolg bzw. Misserfolg aus den vorherigen Schlüsselsituationen fließt in die aktuelle Entscheidung mit ein. Entsprechend lässt sich das gesamte Feld des maschin­ellen Lernens mit integrieren für adaptives Verhalten.

Ein klassischer Punkt in der KI ist die Optimierung von Parametern. Ein typischer Parameter in Computerspielen ist das Balancing von Einheiten. Typischerweise in Strategiespielen. Das automatische optimieren von Balancing ist eine weitere Herausforderung. Dabei sollen die unterschiedlichen Stärken und Schwächen erhalten bleiben und aufeinander optimiert werden. Solch ein automatisches Balancing könnte über mathematische Modelle gelöst werden oder über Evolutionäre Algorithmen.

Ein gerade immer stärker werdendes Thema in Computerspielen, insbesondere in Videospielen, sind alternative Steuerungsmöglichkeiten. Dies wurde insbesondere durch Nintendo und deren neue Konsole Wii initiiert. Mit neueren Ansätzen wie dem Project Natal von Microsoft ist vielleicht bald eine direktere und interaktivere Kommunikation möglich. Bei Project Natal soll Gesichtserkennung enthalten sein. Dies könnte zum Beispiel auch verwendet werden, um Emotionen des Spielers in das Spiel zu übertragen. Damit wären wir beim Thema maschinelles Sehen. Ein weiterer Punkt bei dem maschinelles Sehen wichtig werden könnte ist, wenn sich Augmented Reality als neue Plattform für Computerspiele etabliert. Dann muss per maschinelles Sehen eine unbekannte Umgebung erkannt und in das Spiel integriert werden. Erste Augmented Reality Ansätze in Videospielen findet man bei der Playstation 3 von Sony mittels dem EyeToy in Eye of Judgement (13) und demnächst in EyePet (14).

Für den Edutainment-Bereich würde sich das automatische Beweisen anbieten. So könnte für Mathe-Lernspiele auch Schritt für Schritt das resultierende Ergebnis nachverfolgt werden, ohne das explizit vom Entwickler jeder Schritt vorher mitgeliefert werden muss. Dies könnte dann auch auf Puzzle- und Knobel-Spiele ausgeweitet werden, wie zum Beispiel bei Professor Layton (15).

Zum Abschluss dieses Artikels sollen zehn wesentliche Punkte zusammengefasst werden für die KI in Computerspielen. Ziel dieser Punkte soll es sein, nachhaltig die KI in Computerspielen zu verbessern, indem in diesem Bereichen geforscht wird. Erst durch die Verzahnung von Forschung und den Entwicklern von Computerspielen kann der nächste große Schritt in der Evolution von Computerspielen stattfinden.

1. Sind moderne KI Methoden performant zu realisieren, damit diese in Spielen eingesetzt werden können?
2. Finden wir einen Weg für adaptive Schwierigkeitsgrade in modernen KI Methoden für Spiele bzw. ein Parameter zur Skalierung der Schwierigkeitsgrade?
3. Können wir moderne KI Methoden in einfache Werkzeuge kapseln?
4. Ist es möglich natürlichere / lebendigere synthetische Welten zu erschaffen?
5. Können wir durch moderne KI Methoden, die Kosten und den Aufwand in der Entwicklung von Computerspielen reduzieren?
6. Schaffen wir es, durch die Verwendung von modernen KI Methoden Rückschlüsse auf das menschliche Denken / Entscheiden zu ziehen?
7. Ist eine lebendigere Kommunikation wie im neuen Projekt Milo and Kate von den Lionhead Studios möglich?
8. Wie kann eine KI für Augmented Reality aussehen, die auf die realen Teile der Anwendung reagieren oder kommunizieren kann?
9. Eine intelligente Squad-KI / Team-KI die hilft, aber nicht zu viel macht.
10. Kann zugesichert werden, dass beim Einsatz von modernen KI Methoden möglichst wenig unvorhersehbares Verhalten oder Leistungsschwankungen realisierbar sind?

Die Herausforderung für die Zukunft der Computerspiele besteht darin, lebendige reale Welten zu erschaffen. Diese zukünftigen realen Welten lassen sich nur realisieren mit modernen KI-Methoden!

Referenzen

[1] Cevat Yerli. The Future of Gaming Graphics. Keynote, 1st Game Developers Conference Europe, Cologne, Germany, 2009.
[2] David H. Eberly. 3D Game Engine Design. Elsevier, 2006.
[3] Alexander Galloway. Gaming. University of Minnesota Press, 2006.
[4] Raul Rojas. Theorie der neuronalen Netze. Springer, 1993.

Ludografie

(1) id Software (1996), Quake (PC). Lyon, Frankreich: GT Interactive.
(2) Raven Software, id Software (2005), Quake 4 (PC). Santa Monica, USA: Acti vision.
(3) Crytek (2007), Crysis (PC). Redwood City, USA: Electronic Arts.
(4) Infinity Ward (2009), Call of Duty: Modern Warfare 2 (PC). Santa Monica, USA Activision.
(5) Valve (2007), Portal (PC). Redwood City, USA: Electronic Arts.
(6) Irem (1988), R-Type (Amiga). Southampton, England: Electric Dreams.
(7) Westwood Studios (1995), Command & Conquer (PC). London, England: Vir gin Interactive.
(8) Infinity Ward (2007), Call of Duty: Modern Warfare (PC). Santa Monica, USA: Activision.
(9) Ion Storm (2004), Thief: Deadly Shadows (PC). Redwood City, USA: Eidos.
(10) Nival Interactive (2006), Heroes of Might & Magic 5 (PC). Paris, Frankreich: Ubisoft.
(11) Piranha Bytes (2009), Risen (PC). München, Deutschland: Deep Silver.
(12) Lionhead Studios (2001), Black & White (PC). Redwood City, USA: Electronic Arts.
(13) Sony (2007), Eye of Judgement (Playstation 3). Tokio, Japan: Sony.
(14) Sony (2009), EyePet (Playstation 3). Tokio, Japan: Sony.
(15) Level-5 (2008), Professor Layton und das geheimnisvolle Dorf (Nintendo DS). Kyoto, Japan: Nintendo.

#im fokus #berlin #digital film design #game design