wiki:GameAITopics
Last modified 2 years ago

Themenliste:

aktuelle Methoden der künstlichen Intelligenz für Spiele (Michael Winkelmann)

Inhalt: Schon seit dem Beginn der Forschung an künstlicher Intelligenz waren Spiele ein beliebtes Forschungsobjekt. Spiele bieten eine einfache und anschauliche Möglichkeit neue Ansätze zu testen, da viele Menschen unterschiedlichste Spiele spielen. Seit dem nun auch das Internet vermehrt die Möglichkeit bietet Spiele online zu spielen, ist es auch immer einfacher an umfangreiche Daten für Spielstärkebestimmungen zu kommen.

Schon 1960 hat sich Prof. Arthur Samuel (Stanford) einen Überblick über den aktuellen Stand über künstliche Intelligenz in Spielen verschafft. 2000 wurde diese Arbeit von Prof. Jonathan Schaeffer (Alberta) aufgegriffen und hat dabei den damaligen Stand für die Spiele Backgammon, Bridge, Dame, Poker und Schach betrachtet. Nach nun mehr 9 Jahren hat sich wieder viel auf diesem Gebiet getan, so dass sich eine erneute Betrachtung des aktuellen Standes lohnt.

Das Ziel dieses Thema ist es einen Einstieg in die Thematik künstliche Intelligenz für Spiele zu ermöglichen und einen Gesamtüberblick über den aktuellen Forschungsstand zu ermöglichen. Dabei soll sowohl auf klassische Brettspiele als auch auf moderne PC-Spiele eingegangen werden.

Literatur:

Monte Carlo Tree Search (Andrej Finsterbusch und Mario Rothe)

Anwendungsgebiet: Go
Inhalt: Monte Carlo Algorithmen basieren auf Zufallsspielen, um daraus statistische Aussagen über Gewinnwahrscheinlichkeiten zu ermitteln. Lange Zeit spielten sie eher eine untergeordnete Rollen und konnten sich gegen andere Ansätze nicht durchsetzen. Der Durchbruch im Go, wovor sich ein Jahrzehnt im Go kaum etwas tat, gelang durch die Kombination von Monte Carlo Tree Search mit Upper Confidence bounds applied to Trees (kurz UCT). Innerhalb weniger Jahre wurde dadurch eine Spielstärkensteigerung erreicht, die zuvor nicht für möglich gehalten wurde. Seitdem wird an diesem Gebiet auch in anderen Anwendungsgebieten verstärkt geforscht.

Monte Carlo Algorithmen stammen aus dem Gebiet des Reinforcement Learnings. Eine der Grundprobleme des Reinforcement Learnings ist eine Strategie zu finden, den Spielbaum zu erforschen, so dass man sich auf der einen Seite auf schon vorhandenes Wissen stützt (starke Züge werden bevorzugt) und zum Anderen neue Wege erforscht werden. UCT kombiniert dies, in dem der Spielbaum asymmetrisch aufgebaut wird, wobei der Schwerpunkt auf starken Zügen liegt, und Informationen aus Zufallsspielen gezogen werden. Dadurch ist es möglich geworden auch komplexe Spiele ohne eine konkrete Bewertungsfunktion für nichtterminale Zustände, wie Go, anzugehen und erste große Erfolge zu erzielen.

Literatur:

Alpha-Beta-Suche (Nils Lomnitz und Sebastian Menski)

Anwendungsgebiet: Schach
Inhalt: Das Ziel eines jeden Spielers ist es in seinem Zug seine Punkte zu maximieren und der Gegner versucht dagegen die Punkte zu minimieren (vorausgesetzt es ist ein konkurrierendes Spiel). Mit diesem MiniMax-Ansatz lässt sich leicht der spieltheoretische Wert eines Zustandes bestimmen. Allerdings ist es dazu notwendig den ganzen Spielbaum zu erkunden, um überall die maximierenden bzw. minimierenden Züge zu bestimmen und die Informationen zurück zu propagieren. Da die meisten Spiele aber in Komplexität von NP oder PSPACE liegen, ist dies nicht praktikabel. Der Alpha-Beta-Algorithmus erlaubt es frühzeitig Teilbäume abzuschneiden und so die Berechnung des spieltheoretischen Werts eines Zustandes bedeutend zu beschleunigen.

Der Alpha-Beta-Algorithmus ist zwar schon recht alt, aber hat auch heutzutage eine große Relevanz. Bspw. werden Alpha-Beta-Algorithmen weiterhin bei Schachprogrammen eingesetzt, welche bekannter Weise selbst menschliche Weltmeister im Schach schlagen können. Auch aus der Sicht der Forschung ist er nicht unbedeutend geworden, da der klassische Alpha-Beta-Algorithmus nur für zwei konkurrierende Spieler ausgelegt ist. In der Realität hat man es aber meist mit mehr als einen Gegner zu tun, so dass effiziente Erweiterungen des Alpha-Beta-Algorithmus benötigt werden.

Literatur:

Neuronale Netze (René Gutschmidt und Florian Brinkmeyer)

Anwendungsgebiet: Backgammon
Inhalt: Die künstlichen Neuronalen Netze wurden dem Neuronennetz des menschlichen Gehirns nachempfunden. Daher geht eine natürliche Faszination von diesem Thema aus.
Sie bestehen grundsätzlich aus verschiedenen Units(Knoten), die über Kanten miteinander Verbunden sein können. Inputunits empfangen Signale von der Außenwelt. Hiddenunits enthalten eine interne Repräsentation der Außenwelt und befinden sich zwischen den Inputunits und den Outputunits, die für das Weitergeben von Signalen an die Außenwelt zuständig sind. Ist das Netz konstruiert, folgt die Trainingsphase, in der das Netz durch

  • Entwicklung neuer Verbindungen, Löschen bestehender Verbindungen
  • Ändern der Gewichtungen zwischen den Neuronen
  • Anpassen der Schwellwerte der Neuronen
  • Hinzufügen oder Löschen von Neuronen

eine interne Repräsentation der Problemstellung aufbaut.
Die Lernverfahren eines künstlichen Neuronalen Netzes unterscheiden sich in

  • Überwachtes Lernen
  • Bestärkendes Lernen (Reinforcement Learning)
  • Unüberwachtes Lernen
  • Stochastisches Lernen.

Der Einsatz künstlicher Neuronaler Netze ist besonders dort geeignet, wo wenig explizites, systematisches Wissen über das zu lösende Problem vorliegt. Dies sind z.B. die Texterkennung, Bilderkennung und Gesichtserkennung, bei denen einige Hunderttausend bis Millionen Bildpunkte in eine im Vergleich dazu geringe Anzahl von erlaubten Ergebnissen überführt werden müssen. Im Bereich der Computerspiele haben Neuronale Netze beim Brettspiel Backgammon gute Erfolge erzielt.

Literatur:

Ant Colony Systems (Kristian Eckstein und Markus Lampe)

Inhalt: Ant Colony System sind genauso wie neuronale Netze aus der Natur inspiriert. Als Vorbild dienen Ameisen, die auf Futtersuche sind und dabei auf ihrem Weg Pheromone hinterlassen. Dadurch werden mehr Ameisen angelockt. Auf der anderen Seite werden natürlich erfolgreiche/kurze Wege zum Futter propagiert, wodurch diese Wege bevorzugt werden. Dieser Ansatz lässt sich auf Spiele übertragen und erstaunliche Ergebnisse bei komplexen Spielen konnten erreicht werden.

Literatur:

Path Finding (Matthias Dunkel und Jan Jantzen)

Anwendungsgebiet: moderne PC-Spiele (z.B. Bots in Shootern)
Inhalt: In den meisten modernen PC-Spielen ist es fast unverzichtbar einen Path Finding Algorithmus zu implementieren. Bots in Shootern müssen ihren Weg durch das Level finden (bzw. ihren Gegner), Einheiten in Strategiespielen müssen auf Befehl den Weg zwischen zwei Punkten finden und ggf. auch anderen Einheiten dabei ausweichen.

Auch wenn dies wie eine recht triviale Aufgabe erscheint, so ist sie es jedoch nicht. Es darf nicht irgendein Pfad gefunden werden. Von einem intelligenten System erwartet man, dass es sowohl den kürzesten, als auch ggf. den ungefährlichsten Weg findet und dabei auf eine dynamische Umgebung reagiert. Da Spiele heutzutage auch nicht mehr rundenbasiert sind, sondern in Echtzeit ablaufen ist es des Weiteren unabdingbar, dass der beste Pfad zusätzlich in sehr kurzer Zeit gefunden wird. Dass dies alles noch immer nicht perfekt gelingt, merkt man als Spieler spätestens dann, wenn sich mal wieder alle Einheiten in großen Klumpen verhakt haben, was keines Wegs von Intelligenz zeugt.

Literatur:

Opponent Modelling (Oliver Matheis, Holger Jost und Alexandra Strekalova)

Anwendungsgebiet: Poker
Inhalt: Poker ist nicht nur durch die unvollständige Information über die Karten der Mitspieler eine Herausforderung für Computer. Die Möglichkeit für irrationales Verhalten, das Bluffen, macht eine Modellierung des Verhaltens der Mitspieler vonnöten um hohe Gewinnraten erreichen zu können.

Literatur:

Rational Learning (Bayesian Learning) (Franziska John, Stephan Juchatz und Florian Seele)

Anwendungsgebiet: Poker
Inhalt: Bayesian Learning kann grob als die Änderung des Wissen auf Basis von Erfahrung beschrieben werden. Neue Informationen(Erfahrungen) werden mit einem Vorwissen zu neuem Wissen kombiniert. Essentielle Grundlage Bayes'scher Methoden sind Wahrscheinlichkeiten zum Modellieren von Unsicherheiten. Bayesian Learning resultiert in einem Verhalten welches zum Nash Equilibrium konvergiert und wird auch zum Modellieren des gegnerischen Verhaltens verwendet.

Literatur:

Game Theory and Multiagent Systems (Thomas Popp, Alexander Blödorn und Richard Karuseit)

Anwendungsgebiet:

  • Was ist die optimale Strategie bei einem Spiel?
  • Wie verhält sich ein rationaler Gegner?
  • Wie optimiert man seine Strategie bei unvollständigem Wissen?

Mit solchen Fragen und mehr beschäftigt sich die Spieltheorie. Schon 1950 entwickelte John Nash das nach ihm benannte Nash Gleichgewicht, was einen Durchbruch in den Wirtschaftswissenschaften darstellte. Bei jeder Art von Spielen wäre es optimal die perfekte Strategie zu finden. Aber welche ist das? Und wie kann man sie berechnen?

Multiagent Systems haben mehrere Entitäten mit verschiedenem Wissensstand und verschiedenen Interessen. Da dies genau die Situation bei Spielen widerspiegelt, ist von Interesse sie zu betrachten. Daneben spielen Multiagent System u.A. auch eine Rolle im Rahmen der Informatik, bei der Wirtschaft, Logik, Parallelem Rechnen und der Linguistik. Hierbei soll sich allerdings auf den Zusammenhang mit der Spieltheorie (game theory) beschränkt werden.

(Thema für 2 Personen)

Literatur:

  • Multiagent Systems - Algorithmic, Game-Theoretic, and Logical Foundations von Yoav Shoham und Kevin Leyton-Brown (im Handapparat von Prof. Schaub)

Datenstrukturen (Tobias Moebert und Stefan Keil)


Inhalt: Alle Implementationen von Strategien benötigen effiziente Datenstrukturen, um bspw. den Zustand darzustellen. Nur durch effiziente Datenstrukturen sind schnelle und speicherschonende Berechnungen auf den Daten möglich. Für Spiele gibt es da verschiedene Anwendungsgebiete und Ansätze, z.B. Bitboards, Hash Tables, Zobrist Keys, Eröffnungsbücher

Literatur:

  • Meta Monte-Carlo Tree Search for Automatic Opening Book Generation - G. Chaslot et. al - GIGA'09 (im "Handapparat")

General Game Playing (Henning Pundrich?)

Inhalt: General Game Playing befasst sich mit der Herausforderung eine universelle Strategie für alle Spiele (mit vollständiger Information und deterministischen Zustandsübergängen) zu finden.

Literatur: