Welche Algorithmen in Games eingesetzt werden

Der Begriff Heuristik ist sehr breit und in vielen verschiedenen Feldern zu finden, zum Beispiel in IT-Security. Der Grund dafür ist die Definition, welche wir hier mal vereinfacht, mit der Wikipedia-Definition in Klammern vorbereitet haben: Ich hab mein Bestes versucht (mit begrenztem Wissen und wenig Zeit), und es tut auch so ungefähr, was ich will (praktikable Lösung), aber garantieren kann ich nichts! (weichen oftmals von der optimalen Lösung ab). Deswegen wird die Heuristik in Anti-Viren-Programmen von Sicherheitsforschern auch als Schlangenöl bezeichnet, da unbekannte Schädlinge nie wirklich zuverlässig erkannt werden können.

Stellenmarkt
  1. Business Analyst (m/w/d)
    Engelbert Strauss GmbH & Co. KG, Freigericht
  2. (Medien-)Informatikerin / Kommunikationswissenschaftle- rin als IT-Verantwortliche (m/w/d) ... (m/w/d)
    Max-Planck-Gesellschaft zur Förderung der Wissenschaften e.V., München
Detailsuche

Im Prinzip ist alles eine Heuristik, das basierend auf dem aktuellen Spielzustand eine numerische Einschätzung für jede der möglichen Handlungen gibt. Jeder Algorithmus wird für jede mögliche Aktion, die folgen kann, eine numerische Einschätzung über deren Qualität geben. Also fürs Hochgehen zum Ziel belohnen (+1) und nicht belohnen, wenn es nicht in Richtung Ziel geht.

Heuristiken sind in der Regel domänenspezifisch und haben meistens Zugang zu Daten der Domäne, die andere Algorithmen nicht haben. Entsprechend kann keine allgemeine Aussage über die Laufzeit einer Heuristik gegeben werden, da die Komplexität der Einschätzung zu 100 Prozent implementationsabhängig ist.

Auch die anderen Algorithmen haben variable Laufzeiten, hier lässt sich jedoch ein Worst Case besser vorhersagen.

Die theoretisch perfekte Suche: Monte-Carlo-Tree-Search

Golem Karrierewelt
  1. Container Technologie: Docker und Kubernetes - Theorie und Praxis: virtueller Drei-Tage-Workshop
    04.-07.07.2022, virtuell
  2. Advanced Python – Fortgeschrittene Programmierthemen: virtueller Drei-Tage-Workshop
    23.-25.01.2023, Virtuell
Weitere IT-Trainings

Monte-Carlo-Tree-Search(MCTS) kann im Prinzip unendlich lange rechnen. Also wird ein Zeitlimit für jede Entscheidungsfindung festgelegt. Je länger dieser Zeitraum ist, desto wahrscheinlicher wird die optimale Aktion ausgewählt. Bevor das Optimum erreicht wird, ist die Qualität jedoch häufig schlecht.

Das Schöne an MCTS: Es braucht zwar einen Simulator des Spiels, aber nicht spezifisches Wissen über das gelöste Problem. Das funktioniert, da MCTS einfach durch zufälliges Wählen von Aktionen in die Zukunft schaut. Dies geschieht so lange, bis das Spiel zu Ende ist. Dadurch werden Teile des Spiel-Ablauf-Baumes vorhergesehen. Basierend auf diesem Halbwissen wird dann die Aktion gewählt, die am ehesten zu einem Sieg oder positiven Ergebnis in der Zukunft führen wird.

In Spielen mit großem Branching Factor ist durch die Zufälligkeit der Suche meistens jedoch die Qualität der gewählten Aktionen miserabel und genauso schlecht, als würde man direkt eine zufällige Aktion ohne Suche wählen. Die Forschung entwickelt halbwegs günstige Heuristiken, die die Suche durch den Baum gut leiten. Einziges Problem: Diese machen die sowieso schon teure Baum-Suche häufig noch teurer.

Neuronale Netze statt Zufallsprinzip

Abhilfe schaffen hier die neuronalen Netze. Alphazero hat seine Performance so gesteigert, weil nun nicht der Zufall, sondern ein neuronales Netz auswählt, wo entlang simuliert werden soll.

Hervor sticht hier Muzero. Dort ist nicht einmal mehr ein Simulator des Spieles notwendig, der die möglichen nächsten Aktionen und deren Ergebnisse (+/- 1) berechnet. Dies übernimmt ein weiteres neuronales Netz, das sich einfach die möglichen Aktionen und deren Werte ausdenkt.

Mit genug verschwendetem Strom in riesigen Rechenzentren (PDF) kann man so dann eines Tages auch die Spielregeln von Shogi, Go oder Atari in einem neuronalen Netz lernen und zum Leiten der Baum-Suche verwenden.

Da Muzero keinen Simulator des angegangenen Problems braucht, ist es extrem anpassungsfähig. So kommt es, dass die ursprünglich für Spiele-KI entwickelte Methode auch Anwendung in der Kompression von Videos findet.

Es gibt auch einen Pionier unter den Videospielen: Total War Rome II. Hier wird MCTS in Kombination mit selbstgeschriebenen Heuristiken verwendet. Aber auch hier ist das Spiel an sich viel zu komplex und schwer, weswegen für die KI gewisse Spielaspekte vereinfacht werden. Dies stößt so manchem Hardcore-Fan eher negativ auf und fühlt sich nach Cheaten an.

Eine perfekte Symbiose lässt sich mit MCTS und Reinforcement Learning herstellen.

Bitte aktivieren Sie Javascript.
Oder nutzen Sie das Golem-pur-Angebot
und lesen Golem.de
  • ohne Werbung
  • mit ausgeschaltetem Javascript
  • mit RSS-Volltext-Feed
 Algorithmen: Warum ist die KI in Spielen so dumm?Was die KI von Forza Horizon so besonders macht 
  1.  
  2. 1
  3. 2
  4. 3
  5. 4
  6.  


Tom01 23. Mär 2022

CPU und GPU Rechenleistung macht gute Fortschritte. Da sehe ich kein Problem. Das die...

Tom01 23. Mär 2022

Ja, Schach z.B. ist vollkommen witzlos. Der Computer ledert selbst Schachmeister ruck...

Achranon 23. Mär 2022

Das ist völlig offensichtlich. Da ist der Gegner mal zu doof schnell genug in Deckung zu...

Zeiram 22. Mär 2022

ich war damals von FEAR fasziniert. Das Verhalten der Gegner hat mich mehr als...



Aktuell auf der Startseite von Golem.de
Prehistoric Planet
Danke, Apple, für so grandiose Dinosaurier!

Musik von Hans Zimmer, dazu David Attenborough als Sprecher: Apples Prehistoric Planet hat einen Kindheitstraum zum Leben erweckt.
Ein IMHO von Marc Sauter

Prehistoric Planet: Danke, Apple, für so grandiose Dinosaurier!
Artikel
  1. Star Wars: Cal Kestis kämpft in Jedi Survivor weiter
    Star Wars
    Cal Kestis kämpft in Jedi Survivor weiter

    EA hat offiziell den Nachfolger zu Star Wars Jedi Fallen Order angekündigt. Hauptfigur ist erneut Cal Kestis mit seinem Roboterkumpel BD-1.

  2. Fahrgastverband Pro Bahn: Wo das 9-Euro-Ticket sicher gilt
    Fahrgastverband Pro Bahn
    Wo das 9-Euro-Ticket sicher gilt

    Die Farbe der Züge ist entscheidend, was bei der Reiseplanung in der Deutsche-Bahn-App wenig nützt. Dafür laufen Fahrscheinkontrollen ins Leere.

  3. Retro Gaming: Wie man einen Emulator programmiert
    Retro Gaming
    Wie man einen Emulator programmiert

    Warum nicht mal selbst einen Emulator programmieren? Das ist lehrreich und macht Spaß - wenn er funktioniert. Wie es geht, zeigen wir am Gameboy.
    Von Johannes Hiltscher

Du willst dich mit Golem.de beruflich verändern oder weiterbilden?
Zum Stellenmarkt
Zur Akademie
Zum Coaching
  • Schnäppchen, Rabatte und Top-Angebote
    Die besten Deals des Tages
    Daily Deals • PS5 evtl. bestellbar • Prime Video: Filme leihen für 0,99€ • Gigabyte RTX 3080 12GB günstig wie nie: 1.024€ • MSI Gaming-Monitor 32" 4K günstig wie nie: 999€ • Mindstar (u. a. AMD Ryzen 5 5600 179€, Palit RTX 3070 GamingPro 669€) • Days of Play (u. a. PS5-Controller 49,99€) [Werbung]
    •  /