Algorithmen: Warum ist die KI in Spielen so dumm?

Superschlaue Fahrzeuge in Forza Horizon, aber Autos auf Schienen in Cyberpunk 2077: KI in Games könnte toll sein, ist es aber oft nicht. Warum?

Artikel von Matthias Müller-Brockhausen veröffentlicht am 14. März 2022, 9:04 Uhr

Tolle KI in Forza Horizon und Autos auf Schienen in Cyberpunk 2022 - warum? (Bild: Xbox Game Studios/CD Project Red/Montage: Golem.de)

Überall wird geworben: Für smarte Assistenten, die dir jeden Wunsch von den Lippen ablesen und unschlagbare Bots, gegen die auch Weltmeister keine Chance haben - sei es in Brettspielen wie Go oder in Echtzeit-Strategiespielen wie Starcraft 2. Die Technik, um exzellente und unschlagbare Computergegner zu programmieren, ist weitgehend verfügbar, gut verstanden und häufig sogar quelloffen zum Selbstverwenden (zum Beispiel Alphastar für Starcraft 2 oder Alphazero für Go).

Wie kommt es, dass dennoch in aktuellen AAA-Spielen wie Cyberpunk 2077 Autos auf einer festen Schiene fahren, während sich in Forza Horizon die Fahrzeuge fast schon menschlich verhalten? Oder dass in Doom auf Nightmare die Gegner als sehr schwierig empfunden werden, während in Cyberpunk 2077 die AI der Nichtspielercharakter (NPC) überall zu wünschen lässt?

Gute KI geht auf Kosten der Bildrate

Hierbei ist vor allem Laufzeit ein großes Problem. Spieler wollen mindestens eine Bildrate von 30, idealerweise aber 60 oder 120 fps. Das heißt aber auch, dass jeder Tick der Spielweltsimulation maximal 33, 16 oder 8 Millisekunden dauern darf. Sonst tritt der Graus eines jeden Gamers auf: Lag.

Daher ist nicht jede KI-Methode für Echtzeit-Games auch geeignet. Die populärsten Methoden sind - sorry an jeden Wissenschaftler, dessen Unterfeld gerade ignoriert wird! - Heuristiken, Monte-Carlo-Tree-Search (MCTS), Reinforcement Learning (RL) und evolutionäre Algorithmen, die später noch einzeln erklärt werden.

In Games kommen meist Heuristiken zum Einsatz, die eine schnelle Bildrate ermöglichen, deren KI-Qualität aber nicht wirklich vorhersehbar ist. Weltmeister schlägt man mit einer solchen KI allerdings nicht. Dafür werden eher Baumsuch- oder Lern-Algorithmen verwendet, die sich aber aufgrund ihrer Geschwindigkeit nicht für Echtzeit-Spiele eignen und sehr teuer sind.

Eine Lösung ist der Einsatz neuronaler Netze. Sie machen es möglich, langsame Berechnungen enorm zu beschleunigen. Forza setzt beispielsweise neuronale Bots ein, was die tolle KI der Fahrzeuge erklärt. Alphastar schafft damit Echtzeitberechnung in Starcraft.

Während das Training dieser Netze teuer ist, ist die Ausführung eines fertig trainierten Netzes unproblematisch in Spiele zu integrieren. Die Anpassungsfähigkeit/Generalisierung von Gelerntem ist aktuell jedoch noch der blockierende Faktor für weite Verbreitung und der Grund dafür, dass bis jetzt kaum neuronal-basierte KI in Spielen zu finden ist.

Wie denkt KI?

Um die Funktionsweise der Algorithmen zu verstehen, muss man wie eine KI sehen und denken. Dies geschieht meistens in Bäumen. Der aktuelle Zustand ist dabei die Wurzel/der Ast und jede mögliche Aktion stellt eine neue Verzweigung dar.

• 

Ein Beispiel für eine simple Raster-Welt (Bild: Matthias Müller-Brockhausen)

Die Anzahl der möglichen Aktionen entscheidet hier auch über die Komplexität oder den sogenannten Branching Factor des Baumes. Je höher dieser ist, desto länger dauern Berechnungen auf dem Baum und desto schwieriger wird es, schlaue KI zu kreieren. Für Raster-Welten ist dieser Baum vorhersehbar klein (Branching Factor von 4), aber Spiele, die wir Menschen spielen, sind viel komplexer.

Schach hat einen Branching Factor von ungefähr 35 und Go ca. 250. Da lässt sich auch ein Schritt in die Zukunft kaum noch in der vorher gezeigten Visualisierung unterbringen. Der Branching Factor ist auch der Grund dafür, dass Rennspiele es einfacher mit KI haben (4 bis 5 Aktionen, wenn man die Handbremse dazu nimmt) als zum Beispiel ein NPC in einer Welt, in der noch die 360°-Blickrichtung und Interaktionsknöpfe (etwa press F to pay respect) parallel zum Gehen hinzukommen.

Schauen wir uns die oben genannten vier KI-Methoden genauer an - Heuristiken, Monte-Carlo-Tree-Search (MCTS), Reinforcement Learning und evolutionäre Algorithmen - und klären, wodurch genau die KI in Forza Horizon so gut ist.