Lösen allgemeiner Spiele durch heuristische Suche

  • View
    213

  • Download
    0

Embed Size (px)

Transcript

  • Johannes Aldinger

    Matr.Nr. 1321288Lehrstuhl Grundlagen der KI

    Prof. Dr. Bernhard Nebel

    Freiburg, 29. April 2009

    Lsen allgemeiner Spiele durch heuristische Suche

  • Erklrung

    Hiermit erklre ich, dass ich diese Abschlussarbeit selbststndig verfasst habe, keine anderen

    als die angegebenen Quellen und Hilfsmittel verwendet habe und alle Stellen, die aus verf-

    fentlichten Schriften entnommen wurden, als solche kenntlich gemacht habe. Darber hinaus

    erklre ich, dass diese Abschlussarbeit nicht bereits fr eine andere Prfung angefertigt wur-

    de.

    Freiburg, den 29. April 2009

    Johannes Aldinger

  • Inhaltsverzeichnis

    1 Einfhrung 5

    2 Grundlagen 6

    2.1 Wettbewerb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

    2.2 Spielmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

    2.3 Datalog und GDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

    2.3.1 Die Syntax von GDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

    2.3.2 Die Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

    2.3.3 KIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

    2.3.4 Vordenierte Relationen in GDL . . . . . . . . . . . . . . . . . . . . . 14

    2.3.5 Restriktionen der GDL-Relationen . . . . . . . . . . . . . . . . . . . . 17

    3 Bestandteile eines GGP-Systems 19

    3.1 Anforderungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

    3.2 Planungsmodul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    3.2.1 Bestensuche fr Einpersonenspiele . . . . . . . . . . . . . . . . . . . . . 21

    3.2.2 Minimax fr Zweipersonenspiele . . . . . . . . . . . . . . . . . . . . . . 22

    3.2.3 GGP-Anpassung von Minimax . . . . . . . . . . . . . . . . . . . . . . . 24

    3.3 Heuristikmodul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

    3.3.1 Evaluierungsfunktionen fr Spiele . . . . . . . . . . . . . . . . . . . . . 25

    3.3.2 Heuristiken fr Planungsprobleme . . . . . . . . . . . . . . . . . . . . . 27

    3.3.3 Parallele Plne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

    3.3.4 FF-Heuristik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

    3.4 Die Evaluierungsfunktion fJO . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

    3.5 bersetzung von GDL nach FF . . . . . . . . . . . . . . . . . . . . . . . . . . 31

    3.5.1 Zustandsvariablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    3.5.2 Initialzustand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    3.5.3 Operatoren und Axiome . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    3.5.4 Zielformel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

    4 Implementierung 37

    4.1 Vorgehen und berblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    4.2 Erstellen der Zustandsvariablen . . . . . . . . . . . . . . . . . . . . . . . . . . 38

    4.3 Syntax-basierte Erreichbarkeitsanalyse . . . . . . . . . . . . . . . . . . . . . . 39

    4.4 Initial- und Terminalzustand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

    4.5 Operatoren und Axiome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

    4.6 Der Planer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

  • 5 Experimente 41

    5.1 Maze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    5.2 Blocksworld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

    5.3 Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    5.4 Minichess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

    5.5 Ergebnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

    6 Fazit 45

    4

  • 1 Einfhrung

    Spiele stehen seit jeher im Fokus der knstlichen Intelligenz. Dem Schachspiel kam dabei ein

    besonders groes Interesse zu. Computerschach sollte zur Unterhaltung und zur Analyse von

    Schachpartien dienen, und auerdem einen Einblick in das menschliche Denken und Handeln

    bringen. Mit der Zeit wurden die Programme immer strker, und heute sind Schachprogramme

    fr Heimcomputer1 besser als die menschlichen Gromeister. Dennoch sind die Einblicke in

    die menschliche Denkweise drftig. Zwar spielen Schachcomputer sehr gut Schach, aber eben

    nur Schach. Andere Spiele, selbst einfache wie Tic-Tac-Toe, knnen von ihnen nicht gelst

    werden. Ein Spezialgebiet konnte mit Hilfe von Expertenwissen soweit perfektioniert werden,

    dass der Computer seine schnellere Rechenzeit gegenber dem Menschen ausspielen kann,

    ein tieferer Einblick bleibt aber versagt. Ein Schritt in Richtung eines allgemeineren Denkens

    sind Computerprogramme, welche nicht nur ein Spiel spielen knnen, sondern jedes Spiel.

    Dem Computer werden dazu lediglich die Spielregeln eines Spiels vermittelt. Die Forschung in

    diesem Gebiet nennt sich General Game Playing (GGP).

    Ein erfolgversprechender Ansatz um allgemeine Spiele zu lsen wird hier vorgestellt. Planungs-

    probleme knnen, nicht zuletzt auch auf Grund uerst erfolgreicher Forschung der Universi-

    tt Freiburg [HN01][Hel06][RW08], sehr fortschrittlich gelst werden. Einspieler-Knobelspiele

    sind im Grunde genommen nichts anderes als Planungsprobleme. Lediglich die Eingabesprache

    (Game Description Language (GDL) statt Planning Domain Description Language (PDDL))

    unterscheidet sich ein wenig. Mehrpersonenspiele erweitern die Problemstellung um die Un-

    gewissheit der Aktionen der Mitspieler, aber dennoch gibt es Mglichkeiten, diese Teilgebiete

    miteinander zu verbinden.

    In Kapitel 2 wird der Rahmen beschrieben, in welchem die GGP-Forschung stattndet. In

    Kapitel 3 werden theoretische Vorberlegungen zum allgemeinen Lsen von Spielen vermittelt

    und Anpassungsmglichkeiten auf die GGP-Problemstellung aufgezeigt. Kapitel 4 beschreibt

    schlielich die praktische Realisierung dieses Ansatzes in Java. Die hieraus gewonnenen Er-

    gebnisse werden schlielich im Kapitel 5 beschrieben.

    1 Deep Fritz - Kramnik 4:2 (2006)

    5

  • 2 Grundlagen

    GGP [GL05] ist ein aktueller Forschungsbereich, der insbesondere durch seine allgemeine Aus-

    richtung interessant ist. Entgegen den bisherigen Experten-Spielprogrammen knnen allge-

    meine Spielprogramme viele verschiedene Spiele spielen. Aber auch andere Aufgaben wie z.B.

    Geschftsmodellmanagement, Automatisierungsprozesse im elektronischen Handel sowie Veri-

    kationsprobleme lassen sich als Spiel modellieren [GL05]. Um verschiedene Anstze mitein-

    ander vergleichen zu knnen, ist ein Rahmen ntig, welcher einen gemeinsamen Standard als

    Grundlage schat. Dieser wird durch den GGP-Wettbewerb der Stanford University gegeben,

    welcher ein Teil der AAAI-Konferenz ist. Im Folgenden wird der so denierte Rahmen be-

    schrieben. Dies sind einerseits der Wettbewerb selbst, andererseits die Spielmodellierung und

    die Spielregelbeschreibungssprache GDL.

    2.1 Wettbewerb

    Von der Association for the Advancement of Articial Intelligence (AAAI) wird regelmig ein

    oener Wettbewerb im Bereich GGP veranstaltet, bei dem die Teilnehmer ihre allgemeinen

    Spielprogramme in einem Turnier gegeneinander antreten lassen. Das beste Programm wird

    mit einer Siegprmie von 10.000 US$ belohnt.

    Sowohl Normierungen wie die Sprache GDL als auch die Kommunikations- und Kontroll-

    Plattform Game Master (GM) werden zur Verfgung gestellt. Die Kommunikation mit GM

    erfolgt ber das Internet mit dem Hyper Text Transfer Protocol (HTTP). Der GM regelt

    die Kommunikation der Spieler, misst die Zeit und fungiert als Schiedsrichter. So whlt er

    beispielsweise zufllige Zge aus, falls die zur Verfgung stehende Zeit abgelaufen ist oder ein

    illegaler Zug bermittelt wurde. Zudem verfgt er ber ein grasches Interface, so dass die

    Spiele des Wettbewerbs anschaulich mitverfolgt werden knnen.

    2.2 Spielmodell

    Die Spiele, welche im Rahmen von GGP betrachtet werden, sind endliche, synchrone Spiele.

    Endlich bedeutet, dass sowohl die Anzahl der Spieler, die Anzahl der mglichen Zge und der

    Zustnde endlich ist. Synchron bedeutet, dass in jeder Runde alle Spieler gleichzeitig einen Zug

    auswhlen. Das ist keine Einschrnkung, da in vielen sequentiellen Spielen der einzig legale

    Zug eines Spielers noop (also die mache-nichts-Aktion) ist, wenn er nicht an der Reihe ist.

    Im Gegensatz zu spezialisierten Spielprogrammen mssen GGP-Spieler sowohl einfache (Tic-

    6

  • Tac-Toe) wie auch komplexe Spiele (Schach) spielen knnen. Die Welt kann sowohl statisch als

    auch dynamisch formuliert werden. Spiele mit partieller Information werden bisher noch nicht

    untersttzt, eine Erweiterung der Spielbeschreibungssprache GDL ist aber mglich [LHH+08].

    Ein Spiel besteht formal aus den folgenden Komponenten:

    eine Menge von Zustnden S

    n Spieler, sogenannten Rollen r1, . . . , rn

    n Aktionsmengen, eine fr jeden Spieler I1, . . . , In

    legale Zge fr jeden Spieler in einem Zustand l1, . . . , ln, li Ii S

    eine partielle Zustandbergangsfunktion, die aus den Aktio-

    nen der Spieler und dem aktuellen Zustand den Nachfolgezu-

    stand berechnet.

    u : I1 InS S

    einem Initialzustand s0 S

    eine Menge von Terminalzustnden T S

    eine Funktion pro Spieler, die den Ge