General Game Playing

Universelle Spieleprogramme


Seminararbeit, 2009

29 Seiten, Note: 1,3


Leseprobe


Inhaltsverzeichnis

Bilderverzeichnis

Tabellenverzeichnis Tabelle 1: Gewinner des GGP Wettbewerbs 2005 bis 2008 Seite 5, eigene Darstellung

Abkürzungs-und Akronymverzeichnis

1. Spiele als Forschungsobjekte der Künstlichen Intelligenz
1.1 Künstliche Spieler in der Vergangenheit
1.2 General Game Playing

2. Die General Game Playing Initiative
2.1 Die Weltmeisterschaft
2.2 Game Description Language (GDL)
2.2.1 Modellieruung eines Spiels in GDL
2.2.2 Die Syntax von GDL
2.2.3 Definierte Relationen in GDL
2.2.3.1 Die role Relation: (Spieler )
2.2.3.2 Die true Relation: (Spielzustand)
2.2.3.3 Die init Relation: (Initialzustand )
2.2.3.4 Die next Relation: (Spielaktualisierung )
2.2.3.5 Die legal Relation: (Erlaubte Spielzüge)
2.2.3.6 Die does Relation (Spielzüge)
2.2.3.7 Die goal Relation (Zielwert)
2.2.3.8 Die terminal Relation (Spielende )
2.3 Die Game Management Infrastruktur
2.3.1.1 Organisation des Spielablaufs

3. Strategien für das General Game Playing
3.1 Such-Verfahren
3.1.1 Minimax
3.1.2 Alpha-Beta-Suche
3.1.3 Iterative Vertiefung
3.1.4 Transpositionstabellen
3.2 Heuristische Bewertung
3.2.1 Identifikation syntaktischer Strukturen
3.2.1.1 Nachfolge-Relationen
3.2.1.2 Zähler
3.2.1.3 Spielbrett
3.2.1.4 Markierung/ Spielfigur
3.2.1.5 Zählbare Werte
3.2.2 Funktionsmerkmale als Bausteine der Bewertung
3.2.3.2 Zielerreichungsgrad
3.2.3.3 Stabilität von Funktionsmerkmalen

4. Fazit

Literaturverzeichnis

Bilderverzeichnis

Abbildung 1: Suchbaum für das Spiel Tic-Tac-Toe Seite 6, eigene Darstellung

Abbildung 2: Model eines Spiels Seite 6, Thielscher, Michael (2008): AAAI’08 Tutorial. TU Dresden

Abbildung 3: Minimax Algorithmus Seite 13, nach: http://de.wikipedia.org/w/index.php?title=Datei:Minimax.svg&filetimestamp=20070622002030

Abbildung 4: Alpha-Beta-Suche Seite 14, http://de.wikipedia.org/w/index.php?title=Datei:Alpha_beta.png&filetimestamp=20040827212544

Abbildung 5: Heuristische Funktion nach Kuhlmann Seite 20, Schiffel, Stephan; Thielscher, Michael (2007): Automatic Construction of a HeuristicSearch Function for General Game Playing. TU Dresden

Abbildung 6: Heuristische Funktion nach Schiffel und Thielscher Seite 22, Schiffel, Stephan; Thielscher, Michael (2007): Automatic Construction of a HeuristicSearch Function for General Game Playing. TU Dresden

Tabellenverzeichnis

Tabelle 1: Gewinner des GGP Wettbewerbs 2005 bis 2008 Seite 5, eigene Darstellung

Abkürzungs-und Akronymverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1. Spiele als Forschungsobjekte der Künstlichen Intelligenz

Seit Anbeginn der Zivilisation haben Brettspiele die intellektuellen Fähigkeiten der Menschen herausgefordert. Die Art von natürlicher Intelligenz, die in diesen Spielen gefordert wird, ist im Gegensatz zu physischen Spielen, wie Ballsportarten, einfach formal zu beschreiben. Sie stellt so ein attraktives Studienobjekt für das Forschungsgebiet der Künstlichen Intelligenz dar [Russel und Norvig 2004]. Im Folgenden wird die Entwicklung von den ersten „künstlichen Spielern“ (sog. Spielagenten) bis hin zum jungen Forschungszweig des General Game Playing (universelle Spielprogramme) aufgezeigt.

1.1 Künstliche Spieler in der Vergangenheit

Seit in den 1950er Jahren die ersten programmierbaren Computer erfunden wurden, gehört das Spielen zu den wichtigsten Aufgaben der Künstlichen Intelligenz. Grund dafür ist die abstrakte Natur von Spielen im Gegensatz zur Realität. Die Zustände eines Spiels, sowie die durch Spielregeln eingegrenzten Einflüsse auf dessen Veränderung, sind einfach und vollständig formal zu beschreiben und in einem Modell abzubilden [Russel und Norvig 2004].

Für das beliebte Brettspiel Dame wurde bereits 1952 vom IBM Mitarbeiter Arthur Samuel ein Programm entwickelt, das gegen menschliche Amateur-Spieler gewinnen konnte. Es dauerte knapp 40 Jahre bis das von Jonathan Schaeffer entwickelte Dame -Programm Chinook auch gegen professionelle Dame -Spieler gewinnen konnte. 1990 konnte Chinook gegen den als besten Dame -Spieler aller Zeiten geltenden Dr. Marion Tinsley zwei Spiele gewinnen, verlor jedoch in der Gesamtwertung 18,5 -20,5. Chinook erlangte dann 1994 den Weltmeisterschaftstitel, weil Tinsley aus gesundheitlichen Gründen aufgeben musste. Die Weiterentwicklung führte dazu, dass Jonathan Schaeffer 2007 die vollständige Lösung des Dame -Spiels bekannt gab [Schaeffer 2007].

Ein Spiel gilt dann als „gelöst“, wenn ein Beweis für eine Spielstrategie gefunden wird, die mit Sicherheit zum Sieg bzw. Remis führt. Damit ist Dame das bisher komplexeste aller gelösten Spiele. Einige einfachere Spiele wie Mühle oder Vier Gewinnt wurden vorher bereits gelöst [Russel und Norvig 2004].

Im Schach konnte zwar 1997 schon der menschliche Weltmeister Gary Kasparow durch das von IBM entwickelte System Deep Blue geschlagen werden, jedoch ist die Wissenschaft noch weit davon entfernt, das Schach -Spiel zu lösen. Das hat einfache Gründe: für die Lösung des Dame -Spiels mussten 50 Computer 18 Jahre lang ununterbrochen rechnen, um die ca. 5*1020 Kombinationen in Dame durchzugehen [Schaeffer 2007]. Schach übertrifft die Komplexität von Dame bei weitem, mit geschätzten 10115 bis 10120 möglichen Spielverläufen [Bonsdorff et al. 1978].

Das asiatische Spiel Go birgt, auch aufgrund des größeren Spielfelds von 19x19, eine noch wesentlich höhere mathematische Komplexität. Die besten Go spielenden Programme sind gerade einmal auf dem Niveau eines menschlichen Anfängers [Russel und Norvig 2004].

Bei den bisher erwähnten Spielen handelt es sich ausnahmslos um Spiele mit vollständiger Information sowie fehlende Einwirkung von Zufall. Sowohl die Eigenschaft unvollständiger Information (z.B. unbekannte Kartenverteilung bei Kartenspielen) als auch die Unsicherheit bezüglich zufälliger Ereignisse (z.B. Würfel bei Backgammon) erschwert aufgrund der höheren Komplexität die Entwicklung eines Spielagenten.

1.2 General Game Playing

Es existieren viele ausgezeichnete Spielprogramme, die auf ihrer jeweiligen Domäne alle bzw. fast alle menschlichen Spieler besiegen können. Diese Spielagenten befinden sich auf einem hohen Intelligenzniveau in Bezug auf das Spiel, für das sie programmiert wurden. Wenn man bedenkt, dass diese Systeme ausschließlich nur auf dem jeweiligen Spezialgebiet einzusetzen sind, kann man dann nicht von einer eher beschränkten Intelligenz sprechen? Man stelle sich vor, ein Schach -Großmeister ist chancenlos gegen durchschnittlich intelligente Kindergartenkinder, wenn er gegen sie einfache Spiele wie Vier Gewinnt, Mühle und Tic - Tac-Toe spielt. Man würde seine intellektuellen Fähigkeiten wahrscheinlich in Frage stellen. Analog dazu kann man auch die Intelligenz der klassischen Spielagenten anzweifeln, die nur jeweils ein Spiel beherrschen. Bisher lag die Aufgabe der Analyse von komplexen Strategiespielen ausschließlich in Menschenhand. Der Mensch entwickelt spielspezifisches Wissen und Strategien zur Lösung des Spielproblems. Anhand der Ergebnisse dieser Denkprozesse wird nun ein Computer programmiert der lediglich dazu genutzt wird, anhand einer Schritt-für-Schritt Anleitung des Programmierers eine Lösung für die definierten Probleme zu finden [Genesereth und Love 2005]. Die eigentliche Intelligenz kam vom Menschen, die Rechenkraft vom Computer.

Wünschenswerter wäre ein Computersystem, das dem Menschen diese strategische Denkarbeit abnimmt und zu einer vom Menschen definierten Problemstellung automatisch eine Lösung findet, ohne genaue Instruktionen zur Lösungsfindung vorgegeben zu bekommen. Auf dieser Vision aufbauend hat sich ein neuer Forschungszweig entwickelt

– das General Game Playing (GGP). Hierbei geht es um die Entwicklung von Agenten, die ohne menschliche Intervention selbstständig viele verschiedene Arten von Spielen erlernen können. Ein GGP-Agent bekommt lediglich die Spielregeln eines Spiels überliefert und muss aus dieser Information das Spiel „erlernen“ und eine geeignete Strategie entwickeln, um es erfolgreich spielen zu können. Somit wird beim General Game Playing eine höhere Form von Intelligenz im Vergleich zu klassischen Spielagenten erreicht [Genesereth et al. 2008].

Ein erster Ansatz zu dieser Thematik kam 1993 von Barny Pell unter der damaligen Bezeichnung Meta-Gaming [Pell 1993]. Pells Programm Metagamer war jedoch beschränkt auf vereinfachte Variationen des Schachspiels. Erst die Einführung des General Game Playing Wettbewerbs 2005 durch die Stanford University (Fachbereich für Künstliche Intelligenz) erhöhte das allgemeine Interesse an diesem Forschungsgebiet und führte zur weltweiten Etablierung von aktiv partizipierenden Forschungsgruppen. Für die eigens hierfür entwickelte logische Programmiersprache Game Description Language (siehe Kapitel 2) gibt es sogar bereits ein Plugin für das populäre Framework eclipse [http://palamedes-ide.sourceforge.net/].

2. Die General Game Playing Initiative

In der Welt der Strategiespiele spielt der Wettbewerb zwischen menschlichen Spielern eine wichtige Rolle. Die Wettbewerber sind durch ihren Siegeswillen im Wettstreit darauf angewiesen, eine möglichst effektive Strategie zu entwickeln, um sich gegen den jeweiligen Kontrahenten durchsetzen zu können. Die beste Strategie ist hierbei der Schlüssel zum Erfolg, weshalb immer bessere Strategien entwickelt werden.

Für Computerprogramme kann man den gleichen positiven Effekt aus einem Wettbewerb erzielen. Beim General Game Playing (als Testplattform der Künstlichen Intelligenz) treten Programme gegeneinander an und messen sich in ihren Fähigkeiten. Je „intelligenter“ ein GGP-Agent ist, desto mehr Spiele wird er gewinnen. So kann man einen Wettbewerb hier als eine Evaluationstechnik für Intelligente Systeme betrachten [Genesereth und Love 2005].

Um auf diese Weise die wissenschaftliche Arbeit im Bereich General Game Playing anzutreiben, rief die AAAI (American Association for Artificial Intelligence) 2005 eine offene Weltmeisterschaft für universelle Spielprogramme ins Leben.

2.1 Die Weltmeisterschaft

Austragungsort für die General Game Playing Weltmeisterschaft ist die jeden Sommer stattfindende „National Conference“ der AAAI. Der Wettbewerb findet in zwei Runden statt, auf die Qualifikationsrunde folgt die Entscheidungsrunde. In der Qualifikationsrunde muss jeder Spielagent zunächst verschiedene Arten von Spielen durchspielen und wird dahingehend auf Konsistenz, Erkennen von Gewinnzuständen und insbesondere auf Performanz getestet. Die Agenten mit den besten Ergebnissen aus der Qualifikationsrunde erreichen die nächste Runde.

In der Entscheidungsrunde lässt man die Spielagenten jeweils gegen alle anderen Wettbewerbe in einer Serie von Spielen antreten, wobei die Komplexität von Spiel zu Spiel zunimmt. Der Teilnehmer mit den meisten Siegen in der Entscheidungsrunde gewinnt das Turnier und erhält ein Preisgeld von 10.000,-$.

Zu den verwendeten Spielen gehören Einzelspieler-Spiele (z.B. Labyrinthspiele), Mehrspieler-Spiele mit Kontrahenten (z.B. Tic-Tac-Toe) sowie mit Teambildung. Diese Spiele können sowohl vollständig berechenbar (Tic-Tac-Toe) sein als auch nicht (z.B. Schach). Weiterhin lässt sich noch zwischen Spielen mit vollständiger Information (z.B. Dame) und unvollständiger Information (z.B. Schiffe versenken) unterscheiden. [Genesereth und Love 2005].

Die folgende Tabelle listet die bisherigen Gewinner der Weltmeisterschaft auf.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1

Die Plattform zu diesem Wettbewerb bildet der Gamemaster. Die wichtigsten Bestandteile dieses, auf Web-Technologien aufbauenden Systems, sind der Game Master, die Game Description Language und die verwendeten Spiele an sich. Im Folgenden werden diese Bestandteile erklärt.

2.2 Game Description Language (GDL)

Um eine einheitliche formale Grundlage zur Beschreibung von Spielen für das General Game Playing zu schaffen, wurde die Game Description Language als Variante der logischen Programmiersprache Datalog entwickelt. Datalog ähnelt der Programmiersprache PROLOG.

In diesem Teilkapitel folgt zunächst eine kurze Erläuterung wie ein Spiel in GDL modelliert wird. Darauf aufbauend werden die GDL-Syntax sowie die vordefinierten Relationen aufgeführt, die zur formalen Beschreibung von Spielregeln und -zuständen benötigt werden. Als Referenz wird die offizielle Spezifikation der Game Description Language [Genesereth et al. 2008] verwendet.

2.2.1 Modellieruung eines Spiels in GDL

In der klassischen S Spieltheorie wird ein Spiel als Suchbaum m modelliert, wobei jeder Knoten die Aktion, allso den Spielzug, eines Spielers darstellt [Rus ssel und Norvig 2004]. Diese Methode zur a abstrakten Darstellung eines Spiels erzeugt e ein sehr umfangreiches Modell. Abbildung 11 e

[...]

Ende der Leseprobe aus 29 Seiten

Details

Titel
General Game Playing
Untertitel
Universelle Spieleprogramme
Hochschule
Universität Duisburg-Essen
Veranstaltung
Künstliche Intelligenz
Note
1,3
Autor
Jahr
2009
Seiten
29
Katalognummer
V132150
ISBN (eBook)
9783640383979
ISBN (Buch)
9783640384259
Dateigröße
620 KB
Sprache
Deutsch
Schlagworte
General, Game, Playing, Universelle, Spieleprogramme
Arbeit zitieren
Dennis Kater (Autor:in), 2009, General Game Playing, München, GRIN Verlag, https://www.grin.com/document/132150

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: General Game Playing



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden