Auf der Suche nach General Game Playing


Vorneweg: auch hier wird keine Antwort darauf gegeben, wie man General Game Playing durchführen kann. Vielmehr sollen bisherige Ansätze als Übersicht dargestellt werden um zumindest den Status Quo beschreiben, was heute bereits möglich ist.

Beginnen wir doch einmal mit der Starcraft AI Challange, welche das prominenteste Beispiel für „computergenerated forces“ ist. Mit Starcraft AI gibt es eine Reihe von Problemen, wobei der augenfälligste wohl ist, dass sämtliche Teilnehmer des Wettbewerbes auf eine API zugreifen müssen, genannt BWAPI. Diese stellt die Verbindung zwischen den Bots und dem Computerspiel da. Wie man vielleicht schon ahnt, gibt es eine BWAPI nur für Starcraft und nicht für andere Spiele wie z.B. OpenRA, Lemmings oder Mario AI. Man kann deshalb sagen, dass BWAPI exakt das Gegenteil von General Game Playing darstellt.

Eine Alternative dazu wird im Aufsatz „GameScripter – A Vision Based Tool for Playing Games“ vorgestellt, dort erfolgt der Zugriff auf Computerspiele mit einem Konzept was ursprünglich für Aimbots entwickelt wurde und zwar über das Auslesen des Bildschirmspeichers. Bei 25 fps werden pro Sekunden 25x der aktuelle Bildschirminhalt als Screenshot erstellt und dieser dient dann als Input für „Gamescripter“. Gamescripter selber ist eine Art von API welche aus dem Bildschirminhalt eine Zustandsbeschreibung des Spiels erstellt, also eine Karte zurückgibt, wo gerade die eigenen Einheiten sind, wie der Punktestand ist und wo die Buttons angeordnet sind mit denen man Aktionen auslösen kann. Im Grunde ist GameScripter soetwas ähnliches wie die BWAPI nur kann es für unterschiedliche Spiele eingesetzt werden. Wirklich universell ist aber auch dieser Ansatz noch nicht, vor allem deshalb weil Gamescripter in C++ erstellt wurde, besser wäre es hingegen Java zu verwenden, weil diese Sprache auf allen Betriebssystemen stabil läuft.

Nachdem man eine Zwischenschicht hat, um jedes Spiel anzusteuern stellt sich die berechtigte Frage wie man denn konkret das Spiel bewältigen soll. Im berühmten Starcraft AI Wettbewerb ist das auch die eigentliche Herausforderung für die Teams. Meist wird zur Lösung eine action-orientierte Sprache wie ABL (A behavior Language) verwendet, man kann aber auch Lua-Scripte verwenden oder über Behavior-Trees das Programm erstellen. Im wesentlichen soll durch diese Scripte eine Aktionsreihenfolge beschrieben werden, zu welcher Zeit also welche Aktion durchgeführt wird. Hier stellt sich natürlich das Grundproblem, dass man vielleicht für ein Spiel wie Starcraft einen diesbezüglichen Planer erstellen kann, dieser dann aber nicht mehr andere Spiele verwendet werden kann. Woran das liegt, erkennt man wenn man sich konkrete Aktion-Planer einmal anschaut. Für Starcraft könnte in dem Bot-Script beispielsweise definiert sein:

1. Basis bauen
2. Basis verteidigen
3. Vorräte sammeln
4. gegnerische Basis angreifen

Derartige Oberbegriffe werden meist als Behavior Tree weiter ausgestaltet, so dass „Vorräte sammeln“ beispielsweise darin besteht „1. mit Sammler losfahren, 2. Vorräte einsammeln, 3. Mit Sammler zurückkehren“.

Wenn man das jeweilige Spiel richtig analysiert hat, kann man mit etwas Aufwand solche Hierarchichten Scripten sowohl für Starcraft als auch für andere Computerspiele erstellen. Und auch von der Spielebranche selber wird dieses Verfahren eingesetzt um sogenannte „Ingame AI“ zu generieren.

Auf formaler Ebene wird durch ein solches action-description-script eine Sprache definiert die man nicht nur linear auf dem Spielbrett ausführen kann, sondern auch in textueller Form auf dem Bildschirm ausgeben kann. Der Wettbewerbsbeitrag EISbot (Starcraft AI) verwendet beispielsweise eine grafische Darstellung, die in Echtzeit durch den Behavior Tree wandert und jeweils anzeigt in welchem Subtask die AI gerade agiert. Wenn man diese Einzelschritte linear als Text ausgibt, kann man eine Art von Geschichte erzählen. Und hier ist dann auch der Ansatz in Richtung General Game Playing.

Zuallerst geht es nicht darum, einen AI Bot zu entwickeln, der gut das jeweilige Spiel beherscht, sondern eine Stufe davor ist es, Menschen dabei zu beobachten wenn sie das jeweilige Spiel spielen. Und auch Menschen erzeugen durch ihre Aktionen auf dem Bildschirm einen Handlungsablauf der als Geschichte erzählt werden kann. Auf der Lowlevel Ebene besteht dieser handlungsablauf eines Starcraft Spielers nur aus Mausbewegungen:

1. Klicke auf (100,200)
2. Klicke auf (100,230)
3. Klicke auf (200,100)
usw.

Die Anzahl der Klicks wird statistisch als „Action per Minute“ (APM) bezeichnet. Jetzt benötigt man eine Art von Parser, genauer gesagt einen Annotator, der in der Lage ist, diese Lowlevel Geschichte mit Zusatzinformationen anzureichern. Beispielsweise ist bei vielen Spielen wie Lemmings oder OpenRA entweder rechts im Bild oder im unteren Bildschirmbereich die Aktionsleiste. Wenn also der Spieler dort draufklickt dann ist damit nicht nur der Punkt (100,200) gemeint, sondern der Klick bedeutet zusätzlich noch „Baue eine Einheit“. Und auf diese Weise kann man auch weitere Aktionen mit Zusatzinformationen anreichern um auf diese Weise die Sprache der Handlungen verständlicher zu machen.

Und ungefähr hier endet dann auch der aktuelle Kenntnisstand. Es gibt zwar einige Forschungen die sich mit der Annotation von Spielen beschäftigen und wieder andere Forschungen versuchen daraus dann Heuristiken abzuleiten, aber im Grunde ist das ganze weitestgehend noch unerforscht und fand bisher nur vereinzelt statt. Es ist jedoch erkennbar, dass mit diesem Ansatz man zumindest auf dem Weg zu „General Game Playing“ ist.

Fakt ist jedoch, dass das Erstellen eines Bots für ein konkretes Spiel im Grunde Benutzermodellierung bedeutet, dass also in Form von „A Behavior Language“ das ausgedrückt wird, wie der Programmierer normaleweise selbst das Spiel spielen würde. Ob man solche Botscripte vollautonom generieren kann sei mal dahingestellt. Fakt ist zuminddst, dass Botprogrammierung darin besteht, die Benutzerhandlungen eines guten Spielers zu verstehen und diese als Script zu formalisieren.

REALISIERUNG
Generell kann man davon ausgehen, dass es für jedes Spiel möglich ist, einen Bot zu programmieren der dieses Spiel zumindest auf niedrigem Level spielen kann. Die eigentliche Herausforderung besteht hauptsächlich darin, dafür konkreten Programmcode zu erstellen. Also erstens, eine Zwischenschicht zu programmieren die ähnlich wie Gamescripter oder BWAPI Zustandsinformationen des Spiels bereitstellt, zweitens das Spiel als solches zu verstehen und Heuristiken abzuleiten um drittens dann in einer Script-Sprache einen Bot zu entwickeln der dann letztlich autonom spielt. Auch Ansätze wie Case-Based-Reasoning oder Refinforcement-Learning stellen weniger eine Vorneweg: auch hier wird keine Antwort darauf gegeben, wie man General Game Playing durchführen kann. Vielmehr sollen bisherige Ansätze als Übersicht dargestellt werden um zumindest den Status Quo beschreiben, was heute bereits möglich ist.

Beginnen wir doch einmal mit der Starcraft AI Challange, welche das prominenteste Beispiel für „computergenerated forces“ ist. Mit Starcraft AI gibt es eine Reihe von Problemen, wobei der augenfälligste wohl ist, dass sämtliche Teilnehmer des Wettbewerbes auf eine API zugreifen müssen, genannt BWAPI. Diese stellt die Verbindung zwischen den Bots und dem Computerspiel da. Wie man vielleicht schon ahnt, gibt es eine BWAPI nur für Starcraft und nicht für andere Spiele wie z.B. OpenRA, Lemmings oder Mario AI. Man kann deshalb sagen, dass BWAPI exakt das Gegenteil von General Game Playing darstellt.

Eine Alternative dazu wird im Aufsatz „GameScripter – A Vision Based Tool for Playing Games“ vorgestellt, dort erfolgt der Zugriff auf Computerspiele mit einem Konzept was ursprünglich für Aimbots entwickelt wurde und zwar über das Auslesen des Bildschirmspeichers. Bei 25 fps werden pro Sekunden 25x der aktuelle Bildschirminhalt als Screenshot erstellt und dieser dient dann als Input für „Gamescripter“. Gamescripter selber ist eine Art von API welche aus dem Bildschirminhalt eine Zustandsbeschreibung des Spiels erstellt, also eine Karte zurückgibt, wo gerade die eigenen Einheiten sind, wie der Punktestand ist und wo die Buttons angeordnet sind mit denen man Aktionen auslösen kann. Im Grunde ist GameScripter soetwas ähnliches wie die BWAPI nur kann es für unterschiedliche Spiele eingesetzt werden. Wirklich universell ist aber auch dieser Ansatz noch nicht, vor allem deshalb weil Gamescripter in C++ erstellt wurde, besser wäre es hingegen Java zu verwenden, weil diese Sprache auf allen Betriebssystemen stabil läuft.

Nachdem man eine Zwischenschicht hat, um jedes Spiel anzusteuern stellt sich die berechtigte Frage wie man denn konkret das Spiel bewältigen soll. Im berühmten Starcraft AI Wettbewerb ist das auch die eigentliche Herausforderung für die Teams. Meist wird zur Lösung eine action-orientierte Sprache wie ABL (A behavior Language) verwendet, man kann aber auch Lua-Scripte verwenden oder über Behavior-Trees das Programm erstellen. Im wesentlichen soll durch diese Scripte eine Aktionsreihenfolge beschrieben werden, zu welcher Zeit also welche Aktion durchgeführt wird. Hier stellt sich natürlich das Grundproblem, dass man vielleicht für ein Spiel wie Starcraft einen diesbezüglichen Planer erstellen kann, dieser dann aber nicht mehr andere Spiele verwendet werden kann. Woran das liegt, erkennt man wenn man sich konkrete Aktion-Planer einmal anschaut. Für Starcraft könnte in dem Bot-Script beispielsweise definiert sein:

1. Basis bauen
2. Basis verteidigen
3. Vorräte sammeln
4. gegnerische Basis angreifen

Derartige Oberbegriffe werden meist als Behavior Tree weiter ausgestaltet, so dass „Vorräte sammeln“ beispielsweise darin besteht „1. mit Sammler losfahren, 2. Vorräte einsammeln, 3. Mit Sammler zurückkehren“.

Wenn man das jeweilige Spiel richtig analysiert hat, kann man mit etwas Aufwand solche Hierarchichten Scripten sowohl für Starcraft als auch für andere Computerspiele erstellen. Und auch von der Spielebranche selber wird dieses Verfahren eingesetzt um sogenannte „Ingame AI“ zu generieren.

Auf formaler Ebene wird durch ein solches action-description-script eine Sprache definiert die man nicht nur linear auf dem Spielbrett ausführen kann, sondern auch in textueller Form auf dem Bildschirm ausgeben kann. Der Wettbewerbsbeitrag EISbot (Starcraft AI) verwendet beispielsweise eine grafische Darstellung, die in Echtzeit durch den Behavior Tree wandert und jeweils anzeigt in welchem Subtask die AI gerade agiert. Wenn man diese Einzelschritte linear als Text ausgibt, kann man eine Art von Geschichte erzählen. Und hier ist dann auch der Ansatz in Richtung General Game Playing.

Zuallerst geht es nicht darum, einen AI Bot zu entwickeln, der gut das jeweilige Spiel beherscht, sondern eine Stufe davor ist es, Menschen dabei zu beobachten wenn sie das jeweilige Spiel spielen. Und auch Menschen erzeugen durch ihre Aktionen auf dem Bildschirm einen Handlungsablauf der als Geschichte erzählt werden kann. Auf der Lowlevel Ebene besteht dieser handlungsablauf eines Starcraft Spielers nur aus Mausbewegungen:

1. Klicke auf (100,200)
2. Klicke auf (100,230)
3. Klicke auf (200,100)
usw.

Die Anzahl der Klicks wird statistisch als „Action per Minute“ (APM) bezeichnet. Jetzt benötigt man eine Art von Parser, genauer gesagt einen Annotator, der in der Lage ist, diese Lowlevel Geschichte mit Zusatzinformationen anzureichern. Beispielsweise ist bei vielen Spielen wie Lemmings oder OpenRA entweder rechts im Bild oder im unteren Bildschirmbereich die Aktionsleiste. Wenn also der Spieler dort draufklickt dann ist damit nicht nur der Punkt (100,200) gemeint, sondern der Klick bedeutet zusätzlich noch „Baue eine Einheit“. Und auf diese Weise kann man auch weitere Aktionen mit Zusatzinformationen anreichern um auf diese Weise die Sprache der Handlungen verständlicher zu machen.

Und ungefähr hier endet dann auch der aktuelle Kenntnisstand. Es gibt zwar einige Forschungen die sich mit der Annotation von Spielen beschäftigen und wieder andere Forschungen versuchen daraus dann Heuristiken abzuleiten, aber im Grunde ist das ganze weitestgehend noch unerforscht und fand bisher nur vereinzelt statt. Es ist jedoch erkennbar, dass mit diesem Ansatz man zumindest auf dem Weg zu „General Game Playing“ ist.

Fakt ist jedoch, dass das Erstellen eines Bots für ein konkretes Spiel im Grunde Benutzermodellierung bedeutet, dass also in Form von „A Behavior Language“ das ausgedrückt wird, wie der Programmierer normaleweise selbst das Spiel spielen würde. Ob man solche Botscripte vollautonom generieren kann sei mal dahingestellt. Fakt ist zuminddst, dass Botprogrammierung darin besteht, die Benutzerhandlungen eines guten Spielers zu verstehen und diese als Script zu formalisieren.

REALISIERUNG
Generell kann man davon ausgehen, dass es für jedes Spiel möglich ist, einen Bot zu programmieren der dieses Spiel zumindest auf niedrigem Level spielen kann. Die eigentliche Herausforderung besteht hauptsächlich darin, dafür konkreten Programmcode zu erstellen. Also erstens, eine Zwischenschicht zu programmieren die ähnlich wie Gamescripter oder BWAPI Zustandsinformationen des Spiels bereitstellt, zweitens das Spiel als solches zu verstehen und Heuristiken abzuleiten um drittens dann in einer Script-Sprache einen Bot zu entwickeln der dann letztlich autonom spielt. Auch Ansätze wie Case-Based-Reasoning oder Refinforcement-Learning stellen weniger eine Lösung für das Problem da, sondern dürfte als Feature-Requests im Jira-Ticket-System vermerkt werden zu dessen konkrete Realisierung in Programmcode Manpower benötigt wird.

Theoretisch fundierte Gründe warum es unmöglich wäre eine General Game Playing Software zu erstellen, scheint es keine zu geben. Vielmehr ist es so, dass es nicht unendlich viele Programmierer gibt, die sich erstens mit derlei Problemen beschäftigen und zweitens auch noch die Muße haben, sich im Rahmen eines konkreten Projektes damit näher auseinanderzusetzen.Lösung für das Problem da, sondern dürfte als Feature-Requests im Jira-Ticket-System vermerkt werden zu dessen konkrete Realisierung in Programmcode Manpower benötigt wird.

Theoretisch fundierte Gründe warum es unmöglich wäre eine General Game Playing Software zu erstellen, scheint es keine zu geben. Vielmehr ist es so, dass es nicht unendlich viele Programmierer gibt, die sich erstens mit derlei Problemen beschäftigen und zweitens auch noch die Muße haben, sich im Rahmen eines konkreten Projektes damit näher auseinanderzusetzen.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s