INHALTSVERZEICHNIS

Inhaltsverzeichnis   

1  Einleitung  1

1.1  Entwurfsbeschreibung  1

1.2  Beteiligte Disziplinen, Begriffskl arung  5

1.3   

Uberblick   7

2  Stand der Forschung  8

2.1  Theorien und empirische Ergebnisse  8

2.1.1  Epistemische Logik  8

2.1.2  Spieltheorie  11

2.1.3  Psychologie und Verhaltensspieltheorie  16

2.1.4  Zusammenfassung  22

2.2  K unstliche Intelligenz  23

2.2.1  Allgemeine Diskussion  23

2.2.2  Spezielle Beispiele  26

2.2.3  Zusammenfassung  28

3  Konzipierung und Analyse  29

3.1  Wahl des einfachen Interaktionsszenarios  29

3.2  Spielstruktur und Berechnung des Nash-Gleichgewichtes  34

3.3  Detektion der Verhaltensstrategien und MN-MAlgorithmus  39

3.4  Wahl des zweiten Interaktionsszenarios  46

3.5  Erforderliche Programmkomponente  50

4  Programm  51

4.1  Programmstruktur  51

4.2  Hauptbenutzeroberfl ache  53

4.2.1  Men u  53

4.2.2  Spieltisch  55

4.3  MN-MAlgorithmus  56

4.4  Spielbaumtraversierung  57

4.5  Einbindung der Java-Simplex-Implementation  57

i

INHALTSVERZEICHNIS

4.6  Netzwerkspielverwaltung  59

5  Ausblick  62

6  Fazit  64

Abbildungsverzeichnis   65

Tabellenverzeichnis 67   

Literaturverzeichnis   68

A   73

B   74

C   78

ii

KAPITEL 1. EINLEITUNG

Kapitel 1

Einleitung

1.1 Entwurfsbeschreibung

In dieser Arbeit geht es darum, gegenseitiges Modellieren als ein menschliches Denkmuster maschinell ausf¨ uhrbar zu machen. Dieses Ziel geh¨ ort in das Forschungsfeld der K¨ unstlichen Intelligenz, denn in dieser Disziplin wird die Intelligenz durch Nachbauen erforscht. Das Modellieren bezieht sich dabei allein auf das Abbilden der mentalen Vorg¨ ange im Geist des anderen Individuums, wie das folgende konstruierte, an die Krimi-Literatur erinnernde Beispiel zeigt:

Als Einstieg kann man sich die in diesem Beispiel erw¨ ahnten N. und B. nicht nur als Menschen vorstellen. In der k¨ unstlichen Intelligenz verwendet man den Begriff Agent ¹ f¨ ur eine handelnde Einheit [Russell und Norvig, 1995, S. 4]. Diese beiden auch als k¨ unstliche Agenten vorstellbare Wesen handeln, verfolgen Ziele und entwickeln Modelle voneinander. Abbildung 1.1 zeigt den prinzipiellen Aufbau eines zielbasierten und modellbasierten Agenten, der

1

Abbildung 1.1: Modell- und zielbasierter Agent [Russell und Norvig, 1995, s.50]

N. und B. darstellen kann. Dabei k¨ onnen die mentalen Zust¨ ande der anderen Agenten als ein Teil des Welt- bzw. Umgebungsmodells verstanden werden. Da zwei oder mehrere agentenmodellierende Agenten miteinander interagieren k¨ onnen, haben die Modelle unter Umst¨ anden einen geschachtelten Aufbau, so dass auch ”das eigene Modell im Geist des Anderen”-Modell bzw. verschachteltere Modelle repr¨ asentiert werden k¨ onnen. Auch wenn die Agenten orthogonale Ziele verfolgen und miteinander nicht direkt interagieren, k¨ onnen sie allein durch Beobachtung der anderen zum Wissensgewinn gelangen, wie das folgende in der Literatur oft erw¨ ahnte Beispiel zeigt. Muddy Children Puzzle [nach Fagin u. a., 1995]: Es gibt n Kinder (Abb. 1.2), die alle intelligent, ehrlich, h¨ orend, sehend und aufmerksam sind. Dass sie diese Eigenschaften haben, geh¨ ort zum gemeinsamen Wissen ² der Kinder. D. h., es weiß jedes Kind und jedes Kind weiß, dass jedes Kind es weiß usw.. Jedes Kind bekommt nach dem gemeinsamen Spielen mit einer bestimmten Wahrscheinlichkeit ein schmutziges Gesicht, das es selbst nicht sehen kann und kein Kind sagt dem anderen, ob sein Gesicht schmutzig oder sauber ist. Einer der Eltern sagt, wenn mindestens eines der Kinder schmutzig geworden ist, dass

² Das Konzept des gemeinsamen Wissens wird im Abschnitt 2.1.1 genau formalisiert.

2

KAPITEL 1. EINLEITUNG

Abbildung 1.2: Muddy Children Puzzle [Meyer und Hoek, 1995]

mindestens ein Kind schmutzig geworden sei und vortreten solle. Die Kinder, die sicher sind, dass sie schmutzig sind, treten vor und alle anderen bleiben stehen. Der beaufsichtigende Erwachsene muss bei k schmutzigen Kindern die Aufforderung ϕ 1 = ”Mindestens einer von euch ist schmutzig. Schmutzige vortreten!” k-mal wiederholen, damit alle schmutzigen Kinder vortreten, was sich ¨ uber Induktion beweisen l¨ asst.

Im Falle k = 1 sieht das Kind mit schmutzigem Gesicht, dass alle anderen sauber sind und tritt vor. Die anderen Kinder bleiben stehen, weil sie schon ein schmutziges Kind sehen. Im Falle k = 2 bleiben zuerst alle stehen, weil jedes von ihnen mindestens ein schmutziges Kind sehen kann. Jedes der schmutzigen Kinder sieht dabei, dass das einzige schmutzige Kind, das es sieht, stehen bleibt, also muss dieses Kind ein anderes schmutziges Kind sehen. Die sauberen Kinder sehen zwei schmutzige Kinder, die stehen geblieben sind, weil sie einander sehen k¨ onnen. Also treten bei der zweiten Aufforderung alle schmutzigen Kinder vor, und die sauberen Kinder bleiben stehen. Man kann f¨ ur k = 3 genauso schlussfolgern, dass die Aufforderung dreimal wiederholt werden muss. Die Wiederholung der Aufforderung bringt die Kinder dazu, ihren aktuellen Wissenstand durch ihre Handlungen mitzuteilen. Diese Mitteilungen werden dann zum gemeinsamen Wissen der Kinder. Da die Voraussetzungen in diesem Puzzle sehr speziell sind, birgt eine L¨ osung dieses Puzzles mit Hilfe eines Logikinterpreters [Bern, 2004] noch keine ausreichenden theoretischen Konzepte in sich, die auf die meisten Situationen angewendet werden k¨ onnten. Man erkennt, dass bei einer beliebig hohen Schachtelungstiefe eine derartige Schlussfolgerung weder von Menschen

3

1.1. ENTWURFSBESCHREIBUNG

noch von Maschinen umsetzbar ist, weil deren Kapazit¨ aten begrenzt sind

[Fagin u. a., 1995]. Was aber in dieser Arbeit beabsichtigt wird, ist das Modellieren eines Agenten, der in eine Interaktion involviert ist. Es geht nicht um die Analyse einer Situation, in der perfekte Agenten interagieren. Auch wenn die Kapazit¨ at ausreichen w¨ urde, stellt sich dennoch die Frage nach der Rentabilt¨ at. In Situationen wie bei kompitetiven Gesellschaftsspielen f¨ ur zwei Spieler bringt das Modellieren des anderen Spielers bzw. Agenten keine Verbesserung mit sich, weil nach der Analyse dieser Spiele, die jeder Spieler f¨ ur sich macht, f¨ ur beide Spieler eine optimale Strategie angegeben werden

kann [Holler und Illing, 2000, S. 62], von der keiner der Spieler, w¨ are er am Gewinnen interessiert, abweichen w¨ urde. Speziell bei Papier-Stein-Schere, wo die Vorhersage des gegnerischen Verhaltens sich anscheinend lohnt, ist es f¨ ur jeden Spieler optimal, zuf¨ allig zwischen den Handgesten zu w¨ ahlen, denn zuf¨ alliges W¨ ahlen erlaubt keine nutzbare Vorhersage ¨ uber seine n¨ achste Handgeste.

Das Interaktionszenario, bei dem agentenmodellierende k¨ unstliche Agenten demonstriert werden k¨ onnen, muss also diese Aspekte ber¨ ucksichtigen. Das gegenseitige Modellieren erfordert gleichzeitig mehrere Individuen. Die vermutlich einzig bekannten intelligenten Wesen, die diese Art von Denkmustern entwickeln, sind wir Menschen. Das wirft die Frage auf, ob man beim Nachbauen allein k¨ unstliche Agenten interagieren l¨ asst, oder Menschen mit einbezieht. Dazu gibt es in der KI zwei Ansichten bzw. Thesen dar¨ uber, was die Forschung bezwecken sollte: das Nachbauen menschlicher Intelligenz und das Bauen ”idealer” Intelligenz [Russell und Norvig, 1995, S. 2]. Man kann auf Grund jeder dieser Thesen argumentieren, dass das Einbeziehen von Menschen erw¨ unscht ist. Setzt man den Schwerpunkt auf die Simulation des menschlichen Denkens und Verhaltens, so sind Menschen als evaluierende Interaktionspartner f¨ ur die Simulation dieser Art von Denkmustern - wie beim Turing-Test - unentbehrlich. Setzt man aber den Schwerpunkt auf die Entwicklung idealer Intelligenz, so ist es wichtig zu kl¨ aren, ob sich die ideale Intelligenz auch in der realen Welt, d. h. in der Interaktion mit ”nicht idealen” echten Menschen, bew¨ ahrt. Die Einbeziehung echter Menschen, worauf in dieser Arbeit der Schwerpunkt gesetzt wird, kann also aus der Sicht der beiden Thesen eine Wissensl¨ ucke f¨ uhlen. Fraglich ist aber, ob das gegenseitige Modellieren von Mensch und Maschine wegen verschiedener Funktionsweisen und F¨ ahigkeiten in jeder Situation vorstellbar ist. Die Hauptaufgabe dieser Arbeit besteht daher im intelligenten Ausw¨ ahlen und in der Implementation eines geeigneten Interaktionsszenarios. Diese Diskussion wird im Kapitel 3 direkt fortgesetzt, wo zwei Szenarien vorgeschlagen werden. Das erste Szenario verwendet ein kompetitives Gesellschaftsspiel mit simultanen Z¨ ugen, bei dem die optimale Strategie aufw¨ andig berechnet werden muss.

4

KAPITEL 1. EINLEITUNG

Sie ist deshalb f¨ ur Menschen schwer anwendbar. Die Spielregeln f¨ ur das Spiel

terministische Strategie, die durchschaut und ausgenutzt werden kann. Er ersetzt sie dann durch eine Gegenstrategie zur Gegenstrategie des Gegners, d. h. des Menschen, sobald die Sicherheit in der gegnerischen Antizipation der eigenen Strategie einen bestimmten Pegel ¨ ubersteigt.

Das zweite Szenario verwendet ein vom Verfasser dieser Arbeit vorgeschlagenes ¨ ubertragbares Konzept f¨ ur ein Spiel mit vier Spielern, das keine optimale L¨ osung garantiert und Anreiz f¨ ur das gegenseitige Modellieren schafft. Die vier Spieler sind dabei in zwei Fraktionen ` a zwei Spieler unterteilt. Spieler

in einer Fraktion k¨ onnen nur gemeinsam einen identischen Betrag gewinnen oder verlieren; jede Fraktion gewinnt nur so viel, wie die andere Fraktion verliert. Alle vier Spieler k¨ onnen nicht miteinander kommunizieren. Dabei haben die Spieler jeder Fraktion einen Anreiz dazu, miteinander zu kooperieren und zwar so, dass die Art und Weise der Kooperation von den Spielern der anderen Fraktion nicht durchschaut wird. Dieses Konzept kann auf Pico 2 ubertragen werden. Das dadurch entstandene Pico 2 mit vier Spielern wurde ¨

als ein Netzwerkspiel implementiert und ist f¨ ur empirische Studien verwendbar.

1.2 Beteiligte Disziplinen, Begriffskl¨ arung

Mit dem Thema, das in dieser Arbeit als gegenseitiges geschachteltes Modellieren ³ bezeichnet wird, besch¨ aftigen sich Forscher aus Psychologie, Logik, Spieltheorie, Linguistik und K¨ unstliche Intelligenz. In Bezug auf MNM werden verschiedene Fachbegriffe verwendet, die u. a. untereinander Korrespondenzen aufweisen.

F¨ ur das Modell des anderen Agenten steht in der Psychologie der englisch-

sprachige Begriff Theory of Mind oder kurz ToM [Mol u. a., 2005]. ToM kann mit einer Ordnung versehen werden [Hedden und Zhang, 2002]. ToM erster Ordnung bedeutet, sich das Denken und die W¨ unsche einer anderen Person vorzustellen, ToM n-ter Ordnung bedeutet, sich das ToM (n − 1)-ter Ordnung aus der Sicht der anderen Person vorzustellen. Somit korrespondiert ToM h¨ oherer Ordnung mit MNM.

In der mathematischen Logik und auch Philosophie bezeichnet man als epis-

Modeling”verwendet.

5

temische Logik ⁴ [Wooldridge, 2002] das Schlussfolgern ¨ uber das Wissen, das

zwischen mehreren Agenten verteilt ist. Es bedarf erweiterter Formalismen, um nicht nur Wissen sondern auch W¨ unsche und Intentionen in dieser Logik darstellen zu k¨ onnen [Hoek und Wooldridge, 2003]. Ein wichtiger Begriff, den man nicht umgehen kann, wenn man das Handeln eines Agenten als Konsequenz aus seinem Wissen und seinen Zielen definiert, ist die Rationalit¨ at. Ein rationaler Agent macht immer das, was ihn seines

nen mehrere Agenten interagieren und deren Zielerreichung von den Handlungen anderer Agenten abh¨ angt, werden als strategische Spiele bezeichnet

[Holler und Illing, 2000]. Die Spieltheorie ist die Disziplin, die sich mit Analyse der strategischen Spiele besch¨ aftigt und zum Ziel hat, f¨ ur jedes Spiel herauszufinden, wie sich rationale Spieler verhalten w¨ urden bzw. sollten. Das wiederholte Betrachten des Spiels aus der Sicht verschiedener Spieler wird als iterierte Analyse ⁵ bezeichnet.

Es gibt aber auch Arbeiten, z. B. die Integration epistemischer Logik in die Spieltheorie (vgl. [Otterloo u. a., 2004; Bacharach, 1997]), die die einzelnen Disziplinen miteinander verbinden sollen. Relevant f¨ ur diese Arbeit sind em-

Die theoretische Auswertung der Daten dieser Experimente wird mit dem Begriff Verhaltensspieltheorie ⁶ [F.Camerer, 2003] gemeint, denn die Daten zeigen ein anderes Verhalten von Individuen, als die konventionelle Spiel-theorie es f¨ ur rationale Spieler vorhersagt. Von der Grundlagenforschung in Logik, Spieltheorie und Psychologie profitieren wiederum Linguistik und KI. In der KI stellen vor allem die Logikinterpreter das Hauptfeld der For-

flektiv verwenden.

Bei der Begriffsfestlegung wird in dieser Arbeit die Tatsache ber¨ ucksichtigt, dass ein k¨ unstlicher Agent die mentalen Vorg¨ ange des Menschen nur ann¨ ahernd simulieren bzw. modellieren kann. Deshalb wird anstatt Iteration oder Rekursion der Begriff Schachtelung verwendet, da er nicht die prinzipielle Gleichheit der unterschiedlich aufgebauten Interaktionspartner suggeriert.

⁴ epistemic logic

⁵ iterated analysis

⁶ behavioral game theory

6

KAPITEL 1. EINLEITUNG

1.3 ¨ Uberblick

Kurzbeschreibung der folgenden Kapitel und Abschnitte:

• Kapitel 2 : Stand der Forschung.

- Abschnitt 2.1: Hier werden die relevantesten Arbeiten aus ver-

- Abschnitt2.2: Dieser Abschnitt stellt den bisherigen Stand der Forschung in der KI in Bezug auf MNM dar.

• Kapitel 3: Das ist der Hauptteil der Arbeit. Er besch¨ aftigt sich unter Verwendung der Erkenntnisse aus der interdisziplin¨ ar angelegten Recherche mit der Konzipierung des Programms

- Abschnitte 3.1, 3.2 und 3.3: Diese Abschnitte besch¨ aftigen sich mit der Konzipierung und Analyse des ersten Interaktionsszenarios.

- Abschnitt 3.4: Hier wird das zweite Interaktionsszenario konzipiert und beschrieben.

- Abschnitt 3.5: Dieser Abschnitt fasst den Kapitel zusammen und listet Anforderungen an das Programm auf.

• Kapitel 4: Dieser Kapitel beschreibt das Programm.

• Kapitel 5: In diesem Kapitel werden weitere Meilensteine in der Realisierung von MNM mit Maschinen aufgelistet.

• Kapitel 6: Fazit.

7

Kapitel 2

Stand der Forschung

2.1 Theorien und empirische Ergebnisse

2.1.1 Epistemische Logik

Die epistemische Logik ist eine Logik ¨ uber das Wissen und wird auf der Basis

der Modallogik aufgebaut [Wooldridge, 2002, s. 267f]. Dieser Ansatz wurde 1962 von Jaakko Hintikka vorgeschlagen und ein Jahr darauf von Saul Kripke ausreichend formalisiert ¹ . Die Modallogik ist die Aussagenlogik, die um die Operatoren ” ” ² (es ist bekannt, dass) und ””(es ist m¨ oglich, dass) erweitert wurde. Formeln der Modallogik sind:

Epistemische Logik entsteht, wenn diese Operatoren indiziert werden, wobei die Indezies die Nummern der Agenten darstellen. Zum Beispiel bedeutet ” 2 1 φ”, dass Agent 2 weiß, dass Agent 1 ”φ” f¨ ur m¨ oglich h¨ alt. Die Semantik der epistemischen Logik ist eine Beziehung |= zwischen dem Tupple (M, w) (Abb. 2.1) und einer Formel. M ist dabei die Kripke-Struktur, die einen Graph aus den f¨ ur die Agenten vorstellbaren Welten darstellt, und w ist die Welt, in der sich die Agenten tats¨ achlich befinden sollen. Jede Kante des Graphen geh¨ ort einem bestimmten Agenten und dr¨ uckt aus, dass dieser Agent in jeder der beiden mit ihr verbundenen Welten die andere Welt f¨ ur m¨ oglich h¨ alt. Am Beispiel des Muddy Children Puzzle aus der Einleitung kann man sich bei

¹ Nach [Hoek und Verbrugge, 2002] schrieb als erster G.H von Wright 1953 ¨ uber epistemische Logik

² Statt wird auch K verwendet

8

KAPITEL 2. STAND DER FORSCHUNG

π : W × Φ → {true, f alse} Wahrheitsfunktion

K i : {W ×W } Bin¨ are Relationen zwischen den Welten w Referenzwelt bzw. aktueller Zustand (M, w) |= ϕ wenn und nur wenn π(w, ϕ) (M, w) |= ¬ϕ wenn und nur wenn ¬((M, w) |= ϕ)

V ψ wenn und nur wenn ((M, w) |= ϕ) V

(M, w) |= ϕ ((M, w) |= ψ)

W ψ wenn und nur wenn ((M, w) |= ϕ) W

(M, w) |= ϕ ((M, w) |= ψ)

(M, w) |= i ϕ wenn und nur wenn ∀w (((w, w ) ∈ K i ) → ((M, w ) |= ϕ))

V

(M, w) |= i ϕ wenn und nur wenn ∃w (((w, w ) ∈ K i ) ((M, w ) |= ϕ))

Abbildung 2.1: Definition von Kripke-Struktur und Semantik der epistemischen Logik [Fagin u. a., 1995]

Abbildung

[Hoek und Verbrugge, 2002]

drei Kindern eine Kripke-Struktur (Tabelle 2.2) aus acht Welten vorstellen. Jede dieser Welten wird durch ein Tripple (p 1 , p 2 , p 3 ) bezeichnet, wo p i = 1 gilt, wenn Kind i schmutzig ist und sonst 0.

Mit Hilfe der epistemischen Logik l¨ asst sich das Konzept des gemeinsamen Wissens C G formalisieren, dass sich vom Allgemeinwissen E G unterscheidet. Gemeinsames Wissen eines bestimmten Faktums bedeutet, dass alle dieses Faktum wissen, und alle wissen, dass alle dieses Faktum wissen und so weiter (Abb. 2.3).

Um die epistemische Logik um die Ziele bzw. W¨ unsche der Agenten zu erweitern, bedarf es erweiterter Formalismen. Die bestbekannten Formalis-

men in diesem Bereich sind [Hoek und Wooldridge, 2003]: Intentionslogik [Cohen und Levesque, 1990a,b], BDI-Logik und und KARO-Netzwerk. Bei allen diesen Ans¨ atzen werden f¨ ur jeden Agenten mehrere Modaloperatoren

9

eingef¨ uhrt. Bei dem bestverstandenen und weitverbreitetsten Ansatz BDI ³ von Rao und Georgeff bedarf es pro Agent genau drei Operatoren: ”Bel” (¨ uberzeugt sein), ”Intend”(Absicht haben) und ”Des”(sich w¨ unschen). Der BDI-Ansatz basiert auf den Arbeiten des Philosophen Michael Bratman und wurde erfolgreich implementiert. Die bekannteste Implementation der BDI-Logik ist PRS ⁴ .

³ belief-desire-intention

⁴ Procedural Reasoning System

10

KAPITEL 2. STAND DER FORSCHUNG

2.1.2 Spieltheorie

Die Spieltheorie ist, wie schon in der Einleitung erw¨ ahnt, eine Theorie ¨ uber

rationales Verhalten bei Interaktion mehrerer Subjekte. Sie wurde erst 1944 von John von Neumann und Oskar Morgenstern durch die Ver¨ offentlichung

theorie Anwendungen gefunden hat: Wirtschaftswissenschaften, Soziologie, Psychologie, K¨ unstliche Intelligenz und Biologie. Es wird zwischen kooperativer und nicht kooperativer Spieltheorie unterschieden. Die kooperative Spieltheorie befasst sich im Unterschied zu nicht kooperativer Spieltheorie mit Spielen, bei denen Spieler bindende Absprachen treffen k¨ onnen. In dieser Arbeit wird ausschließlich die nicht kooperative Spieltheorie betrachtet, wobei ”nicht kooperativ” nicht bedeutet, dass keine Kooperation zwischen den Spielern stattfindet.

Ein Spiel in der Spieltheorie ist der Aufbau einer strategischen Situation, dargestellt in Normalform oder in extensiver Form, wobei jedes Spiel in erstere Form ¨ uberf¨ uhrt werden kann. Ein Spiel in Normalform mit z.B. zwei Spielern ist eine Bimatrix (sehe Tab. 2.1), wo jedes Element eine Auszahlung f¨ ur jeden Spieler enth¨ alt. Nach der Konvention sind die Zeilen der Bimatrix den Handlungsalternativen, die sp¨ ater als Strategien bezeichnet werden, des ersten Spielers und die Spalten den Handlungsalternativen des zweiten Spielers

zugeordnet. Die beiden Spieler w¨ ahlen ihre Strategien s 1

und unabh¨ angig voneinander aus und erhalten die Auszahlungen u 1 (s ¹ und u 2 (s ¹ i , s ² j ). Eine Strategie dominiert eine andere Strategie, wenn sie f¨ ur alle Strategien anderer Spieler eine h¨ ohere Auszahlung bringt. Ein rationaler Spieler w¨ urde nie eine dominierte Strategie spielen. Dadurch kann man die Ausgangsmatrix verkleinern, indem man die dominierten Spalten und Zeilen eliminiert und in der so entstandenen Matrix dieses Vorgehen so lange wiederholt, bis sich keine weiteren Spalten oder Zeilen eliminieren lassen. Ein Spieler kann nicht nur eine pure Strategie, sondern auch eine gemischte Strategie verwenden. Diese stellt die eine Wahrscheinlichkeitsverteilung uber die Strategien dar, nach der der Spieler mit Hilfe eines Zufallsgenera¨

tors eine der Strategien ausw¨ ahlt. Ein Standardl¨ osungskonzept f¨ ur Spiele ist das Nash-Gleichgewicht ⁷ . Das Nash-Gleichgewicht ist ein Tuple aus puren bzw. gemischten Strategien aller Spieler, wobei das einseitige Abweichen eines Spielers von seiner Strategie f¨ ur ihn keine Erh¨ ohung seiner Auszahlung

11

mit sich bringt. Nash-Gleichgewichte existieren f¨ ur alle Spiele Γ(N, S, u), die folgende Bedingungen erf¨ ullen:

Daraus l¨ asst sich ableiten, dass es speziell in endlichen Spielen immer ein Nash-Gleichgewicht gibt, wenn nicht in puren, dann in gemischten Strategi-en. In dem hier erw¨ ahnten GD-Spiel (Tab. 2.1) ist (s 1 2 , s 2

Gleichgewicht, obwohl es f¨ ur beide Spieler besser gewesen w¨ are, (s 1

w¨ ahlen. Solches Nash-Gleichgewicht heißt nicht pareto-optimal. Ein Spiel in extensiver Form ist ein Spiel mit einer festgelegten Zugreihen-

folge, so dass ein in der K¨ unstlichen Intelligenz wohl bekannter Spielbaum entsteht [Russell und Norvig, 1995, S. 161f]. Jedes Blatt dieses Baumes liegt am Ende eines Pfades, der eine Folge von Z¨ ugen darstellt, und enth¨ alt eine Auszahlung f¨ ur jeden Spieler. Mit der Annahme des gemeinsamen Wissens der Rationalit¨ at aller Spieler C G (Rational(1) ∧ . . . ∧ Rational(n)) kann man mit Hilfe der R¨ uckw¨ artsinduktion f¨ ur jeden Spieler eine Verhaltensstrategie bestimmen, nach der er in jedem Knoten eine bestimmte Aktion w¨ ahlt. Das Centipede-Spiel [Osborne und Rubinstein, 1994] ⁸ ist ein gutes Beispiel (Abb. 2.4) f¨ ur dieses Vorgehen. Der dort dargestellte Spielbaum ist von links nach

rechts zu lesen. In jedem Knoten hat ein Spieler die Wahl zwischen zwei

⁸ Tausendf¨ usser

12

KAPITEL 2. STAND DER FORSCHUNG

Abbildung 2.4: 6-Stufen-Centipede-spiel [Hoek und Verbrugge, 2002]

Z¨ ugen, ”r” und ”d” oder ”R” und ”D”. Die Knoten des Spielbaumes sind mit r¨ omischen Zahlen beschriftet, die die Nummern der Spieler darstellen, die sich in diesen Knoten entscheiden. Die Bl¨ atter sind mit Auszahlungen f¨ ur beide Spieler versehen. Beginnend mit dem letzten Knoten werden die Auszahlungsvorhersagen (rote Schrift) sukzessive unter Annahme der Rationalit¨ at des jeweiligen Spielers getroffen. Im vorvorletzten Knoten z.B. entscheidet sich Spieler II f¨ ur ”D”, weil er weiß, dass der Spieler I rational ist ( II Rational(I) folgt aus C G (Rational(I) ∧ Rational(II))), und sich deswegen

f¨ ur ”d” entscheiden wird, was aber eine kleinere Auszahlung f¨ ur Spieler II bedeutet.

Wenn die Z¨ uge eines der Spieler unsichtbar f¨ ur den anderen sind, z.B. bei simultanen Entscheidungen, spricht man von Spielen bei imperfekter Information [Osborne und Rubinstein, 1994]. Die Unsichtbarkeit fr¨ uherer Z¨ uge f¨ uhrt dazu, dass man sich gleichzeitig in mehreren Knoten zu befinden glaubt. Diese Menge von Knoten wird in der Spieltheorie als Informationsmenge bezeichnet. Dann gibt es noch die Spiele bei unvollst¨ andiger Information, d. h. Unkenntnis der Auszahlungsfunktion bzw. Strategiemenge des anderen Spielers. Spiele bei unvollst¨ andiger Information k¨ onnen aber in Spiele bei imperfekter Information ¨ uberf¨ uhrt werden, indem man am Anfang des Spiels einen verdeckten Zug der Natur ⁹ einbaut, der den Typ des Spiels bzw. des Spielers festlegt. Die L¨ osung eines solchen Spieles liegt darin, den mutmaßlichen Typ des Spieles T i gegeben die Spielbeobachtung D mit Hilfe des Bayes-theorems

neu zu berechnen [F.Camerer, 2003].

Das schon erw¨ ahnte Muddy Children Puzzle l¨ asst sich auch als ein Spiel in extensiver Form bei imperfekter Information darstellen [F.Camerer, 2003, S. 236-239]. Dazu bedarf es einer Auszahlungsmatrix, die die Ehrlichkeit der

13

2.1. THEORIEN UND EMPIRISCHE ERGEBNISSE

Kinder rationalisiert und der Natur, die den Zustand der Kinder zuf¨ allig mit einer bestimmten Wahrscheinlichkeit festlegt (Abbildung 2.5). Hier wird aus Platzgr¨ unden nur der Fall f¨ ur zwei Kinder betrachtet. Die gestrichelten Linien auf dem Graph zeigen die Informationsmenge eines Kindes entsprechend ihrer Farbe. Wenn beide Kinder rational sind, so k¨ onnen sie sich nach der ersten Aufforderung nur in Knoten 2,8 oder 11 befinden. Wenn die Annahme des gemeinsamen Wissens der Rationalit¨ at gilt, wissen die Kinder von ihrer Rationalit¨ at und entscheiden sich bei der zweiten Aufforderung im Knoten 8 f¨ ur ”vortreten”.

Die Spieltheorie gibt also nur vor, wie sich ein rationaler Spieler verhalten

soll, d. h. nach welchen Kriterien er eine Strategie ausw¨ ahlen soll. Das Ausw¨ ahlen einer Strategie ist aber mit einer aufw¨ andigen Berechnung verbunden. In Spielen bei perfekter Information bedarf es daf¨ ur einfacher Spielbaumdurchsuchung, w¨ ahrend in Spielen bei imperfekter Information, wo das Nash-Gleichgewicht unter Umst¨ anden in gemischten Strategien liegt, bedarf es der

14

KAPITEL 2. STAND DER FORSCHUNG

L¨ osung von Ungleichungssystemen. F¨ ur Zwei-Personen-Nullsummenspiele ohne Nash-Gleichgewicht in puren Strategien, wie z.B. Papier-Stein-Schere (Tab. 2.2) sieht f¨ ur den Zeilenspieler das zu l¨ osende Problem so aus [entsprechend

Es l¨ asst sich als lineares Programm formulieren und mit Hilfe des Simplex-Algorithmus l¨ osen [siehe dazu Owen, 1970].

F¨ ur die Berechnung optimaler Strategien in einem Spiel bedarf es grunds¨ atzlich ausreichender Rechenkapazit¨ aten, die bei gr¨ oßeren Spielen f¨ ur alle bekannten Spieler einfach nicht verf¨ ugbar sind. Denn

Als Abhilfe wird in der k¨ unstlichen Intelligenz Approximation benutzt. Anstatt den ganzen Baum zu erforschen, wird [Russell und Norvig, 1995, S.

171f] ab einer bestimmten Tiefe die G¨ ute eines Knotens gesch¨ atzt. Diese Sch¨ atzung weicht aber von der tats¨ achlichen G¨ ute ab. Es macht dann auch f¨ ur jeden Spieler Sinn, die gegnerische Sch¨ atzungsheuristik zu modellieren und deren Makel auszunutzen.

15

2.1.3 Psychologie und Verhaltensspieltheorie

In der Psychologie hat sich, wie schon im Abschnitt 1.2 erw¨ ahnt, der Begriff ToM als Bezeichnung f¨ ur das mentale Modell des Geistes, z.B. eines anderen Menschen durchgesetzt. Um ToM wissenschaftlich zu untersuchen, bedarf es empirischer Studien. Dass Menschen ToM nicht nur von Menschen, sondern auch von k¨ unstlichen Wesen wie z.B. Roboter aufbauen k¨ onnen, wurde in Bezug auf Sprachverstehen in [Ono und Imai, 2000] untersucht. Bei dem auf der Abbildung 2.6 dargestellten Setup wurde ein Sprachgenerator verwendet, der

in seiner Wiedergabequalit¨ at soweit verschlechtert wurde, bis die vom ihm gemachten Aussagen von Menschen kaum verstanden wurden. Dann wurde die Aussage ”Move the trash can out of my way” ausgew¨ ahlt, die nur drei von sieben Menschen verstehen konnten. Diese Aussage wurde danach anderen zehn Menschen, der Kontrollgruppe, von einem Laptop vorgespielt, ohne dass deren Aufmerksamkeit auf den Roboter gelenkt wurde, der im gleichen Raum vor einen M¨ ulleimer fuhr und stehen blieb. Weitere zehn Menschen, die Versuchsgruppe, bekamen die Aussage direkt vom Roboter vorgespielt. In der Versuchsgruppe haben acht Personen die Aussage verstanden und entsprechend gehandelt, von der Kontrollgruppe aber haben nur drei sie verstanden und nur einer von denen hat entsprechend gehandelt. Dieses Experiment ist ein Argument zur Vorstellung, dass die Menschen erst durch die Antizipation der Ziele einer Maschine die Bedeutung ihrer Signale besser verstehen k¨ onnen und dass wiederum diese Antizipation ¨ uberhaupt m¨ oglich ist.

Die Interaktionen zwischen Menschen, bei denen ToM gebraucht wird, entwickeln sich oft nicht entsprechend den Vorhersagen aus der Spieltheorie. Ein Centipede-Spiel ist z.B. trivial mit R¨ uckw¨ artsinduktion zu l¨ osen, wenn man von dem gemeinsamen Wissen der Rationalit¨ at der beiden Spieler ausgeht.

16

KAPITEL 2. STAND DER FORSCHUNG

Abbildung 2.7: Spielstruktur von [Hedden und Zhang, 2002]

Dieses Spiel besteht aus vier Zellen. Die Spieler d¨ urfen nacheinander beginnend mit dem ersten Spieler in der Ausgangszelle bleiben oder in die n¨ achste Zelle ziehen. Ein Spiel ist beendet, wenn einer der Spieler bleibt oder die vierte Zelle erreicht wird. Bei dem ersten Teil des Experiments haben 35 weibliche plus 35 m¨ annliche Studenten teilgenommen, wobei in der Rolle von Spieler II immer ein computerisierter Gegner und in der von Spieler I ein Mensch auftraten. Den Versuchspersonen wurde mitgeteilt, dass sie gegen menschliche Spieler spielen w¨ urden. Die Variablen A i , B i ,C i , D i sind Auszahlungen f¨ ur Spieler i, einander ungleich und k¨ onnen mit nat¨ urlichen Zahlen von 1 bis 4 belegt werden. Es ergeben sich dadurch 144 verschiedene M¨ oglichkeiten der Variablenbelegung bzw. Auszahlungsstrukturen. Bei dem ersten Zug des ersten Spielers ist f¨ ur den ersten Spieler wichtig zu wissen, ob der zweite Spieler ziehen wird. F¨ ur den zweiten Spieler ist es wiederum wichtig zu wissen, ob der erste Spieler beim letzten Zug ziehen wird. Deshalb muss der erste Spieler f¨ ur seine Entscheidung aus der Sicht des zweiten Spielers denken, d. h. ToM zweiter Ordnung haben, falls der zweite Spieler ToM erster Ordnung hat. Aus ToM zweiter Ordnung l¨ asst sich die Vorgehensvorschrift angeben (Abb. 2.8), die abh¨ angig von der Variablenbelegung vorgibt, ob er ziehen sollte oder

nicht. Man kann sich aber auch vorstellen, dass der zweite Spieler sich nicht in die Sichtweise des ersten Spielers versetzt, sondern nur bei C II < B II zieht. Diese Strategie des zweiten Spielers wurde in diesem Paper myopic ¹⁰ benannt. Wenn der zweite Spieler die Strategie myopic benutzt, dann muss der erste Spieler die Strategie erster Ordnung (Abb. 2.9) benutzen. Es gibt aber Auszahlungsstrukturen, bei denen der zweite Spieler, abgesehen davon, welche der beiden Strategien er benutzt, die gleiche Aktion ausf¨ uhrt. Diese Auszahlungstrukturen werden f¨ ur das Training der menschlichen Versuchspersonen eingesetzt, um sie mit dem Spiel vertraut zu machen. Danach mussten die

17

Menschen 16 Partien gegen den als Computer spielen und dabei Vorhersagen treffen, ob der Gegner ziehen wird oder nicht. Anhand derer Vorhersagen und Aktionen in diesen Partien wurden R¨ uckschl¨ usse darauf gemacht, gegen

=”ToM 1-order”) sie glaubten ge-

spielt zu haben. Die 16 Partien wurden in 4 Sets zusammengefasst, ¨ ein Mittelwert berechnet wurde. Der Computer spielte eine feste kurzsichtige oder vorausschauende Strategie. Der Graph 2.10 zeigt, dass einerseits die Menschen vorerst die Strategie des Computers mehrheitlich f¨ ur myopic gehalten haben, aber dann mit jeder weiteren Partie langsam immer mehr zur korrekten Einsch¨ atzung des Gegners kamen. Ein weiterer Aspekt, der in diesem Experiment sichtbar geworden ist, zeigt, dass Menschen unabh¨ angig von der Strategie des Gegners Fehler machten und eigene Vorhersage nicht optimal in eine Aktion umsetzten. Diese so genannten Rationalit¨ atfehler lagen im Durchschnitt bei 10,5%.

Am Beispiel des Beauty-Kontest-Spiels ¹¹ kann man gut sehen, wie Men-

18

KAPITEL 2. STAND DER FORSCHUNG

schen sich auf der Basis von Modellen anderer Menschen entscheiden, anstatt das Nash-Gleichgewicht zu w¨ ahlen, das leicht zu bestimmen w¨ are. Bei einer Version dieses Spiels m¨ ussen mehrere teilnehmende Spieler simultan Zahlen zwischen 0 und 100 aufsagen. Es gewinnt derjenige Spieler einen festen Betrag, dessen Zahl am n¨ achsten zu 70% des Durchschnittes liegt. Gewinnen gleichzeitig mehrere Spieler, dann teilen sie sich den Gewinn. Wenn dann ein gemeinsames Wissen der Rationalit¨ at aller Spieler vorliegt, sollten alle die 0 aufsagen. Stattdessen bekommt man beim wiederholten Spielen die auf Abbildung 2.11 dargestellte Graphik. Die Erkl¨ arung f¨ ur solches Verhal-

ten ist, dass jeder Spieler versucht den Mittelwert voraussagen, bevor er die 70% dieses Mittelwerts als neuen Mittelwert festlegt, weil er denkt, dass alle anderen Spieler auch den Mittelwert vorauszusagen versuchen und ungef¨ ahr bei der gleichen Voraussage landen. Und diese ¨ Uberlegung kann jeder Spieler

so lange iterieren, bis er sicher ist, er ”schlau genug” und nicht ”zu schlau” denkt. Nach jedem Spiel sinkt aber der Mittelwert und landet irgendwann auf dem Nash-Gleichgewicht bei 0. Hier zeigt sich, dass Menschen sich nicht so verhalten, wie die Spieltheorie es f¨ ur rationale Spieler vorhersagt. Untersuchungen in verschiedenen Spielen haben ergeben, dass Menschen beim Spielen eine Reihe von unterschiedlich begr¨ undeten Abweichungen demonstrieren. Colin F.Camerer, der Erfinder des Begriffs Verhaltensspieltheorie, dr¨ uckt die Schlussfolgerung daraus folgendermaßen aus:

19

Eine weitere Abweichung menschlicher Spieler von idealen Spielern ist die Verwendung von gemischten Strategien, denn die Menschen k¨ onnen die gemischten Strategien in gr¨ osseren Spielen nicht exakt bestimmen.

Den Untersuchungen [F.Camerer, 2003, S. 121ff] zufolge verfehlen die Men-

schen die optimalen Wahrscheinlichkeiten bei ¨

nige Prozentpunkte (Abb. 2.12 links). Bei sehr kleinen Wahrscheinlichkeiten ergeben sich dabei große prozentuale Abweichungen. Ausser der Einsch¨ atzung der Wahrscheinlichkeiten muss noch eine Zufallsfolge produziert werden, mit Hilfe derrer die Strategien beim wiederholten Spielen f¨ ur andere Spieler un-vorhersagbar ausgew¨ ahlt werden m¨ ussen. Die Produktion von Zufallsfolgen

20

KAPITEL 2. STAND DER FORSCHUNG

ist aber nicht trivial. Die Experimente von [Kareev, 1992] zeigen, dass bei den von Menschen produzierten Zufallsfolgen die Wiederholungen seltener vorkommen, als es bei einem echten Zufallsgenerator zu erwarten w¨ are. Ferner ist der Graph der Wahrscheinlichkeitsdichte der menschlichen Zufallsfolgen viel ”spitzer” als die theoretisch zu erwartende Gauss-Verteilung (Abb. 2.12 rechts; gekennzeichnete Kurve ist Gauss-Verteilung). Man kann sich vorstellen, dass ein Computerprogramm, das auf einen Gegner eingestellt ist, der Wiederholungen meidet und kurzzeitig den Erwartungswert ausgleicht, bei einem Spiel wie ”Papier-Stein-Schere” gegen Menschen auf Dauer gewinnen wird.

21

2.1. THEORIEN UND EMPIRISCHE ERGEBNISSE

2.1.4 Zusammenfassung

Als Zusammenfassung der theoretischen und empirischen Literatur, die f¨ ur das Thema dieser Arbeit relevant sind, lassen sich folgende Aussagen treffen:

KAPITEL 2. STAND DER FORSCHUNG

Abbildung 2.13: ”Suchmuster” und Max [Wachsmuth und Lessmann, 2002]

2.2 K¨ unstliche Intelligenz

2.2.1 Allgemeine Diskussion

Abbildung 2.13 (links) stellt graphisch dar, welche Art von Programmen

n¨ otig w¨ aren, um den Stand der bisherigen KI-Forschung in Bezug auf das Thema dieser Arbeit darzustellen. Auf diesem Bild sind ein Mensch und ein k¨ unstlicher Agent dargestellt, von denen jeder ein Modell (Denkblase) des anderen bildet und es dabei zum Aufbau geschachtelter Modelle kommt. Der tats¨ achliche Aufbau der Maschine kann dabei sehr primitiv sein - auch wenn man die Maschine als einen endlichen Automaten betrachten w¨ urde, k¨ onnte sie dann, um geschachtelt modellieren zu k¨ onnen, jedes vorstellbare geschachtelte Modell des menschlichen Gegen¨ ubers als einen Zustand in ihrem Zustands¨ ubergangsgraphen repr¨ asentieren. Gleichzeitig muss aber auch der Mensch ein geschachteltes Modell der Maschine bilden k¨ onnen, weshalb die Maschine ¨ uber eine Interaktionsm¨ oglichkeit mit einem Menschen verf¨ ugen muss. Nach bisheriger Recherche konnte ein solches Setup nicht gefunden werden. Daher werden in diesem Kapitel nur prinzipiell ¨ ahnliche Arbeiten betrachtet. Eine ¨ Ahnlichkeit k¨ onnte man den unz¨ ahligen natursprachlichen Dialogsystemen wie z.B. ELIZA unterstellen [Weizenbaum, 1966], denn sie alle t¨ auschen eine Kommunikation mit einem Menschen vor (sogenannter Eliza-Effekt) und:

23

Diese Vort¨ auschung verleitet den mit einem solchen System interagierenden Menschen dazu, sich vorzustellen oder sich so zu verhalten, als w¨ urde er sich vorstellen, dass das System dem Gespr¨ achspartner ein ”Innenleben” zuschreibt oder dass er glaubt, dass man ihm ein ”Innenleben” zuschreibt usw.. Nur leider funktionieren solche Systeme ohne innere Repr¨ asentation geschachtelter Modelle. Dass ein Mensch ein geschachteltes Modell des Systems entwickelt, das System dagegen nicht, geschieht anscheinend, weil die Wissensdatenbank, die Reaktionen des Systems festlegt, von Konstrukteuren entwickelt wird, die ein Modell des mentalen Inneren eines durchschnittlichen Menschen in ihrer Vorstellung haben bzw. aus der Literatur oder sonstigen Quellen entnehmen und anhand dieses Modells das Verhalten des Systems festlegen.

Der in AG ”Wissensbasierte Systeme” entwickelte verk¨ orperte konversationelle Agent ¹² Max (Abbildung 2.13 ganz rechts, im blauen Overall) wurde und wird im Laufe der Zeit mit vielen Features fortw¨ ahrend aufger¨ us-

tet [z.B. Becker und Wachsmuth, 2006; Kopp und Wachsmuth, 2004], die eine Kommunikation ¨ ahnlich der zwischenmenschlichen ¹³ mit ihm erm¨ oglicht [Kopp u. a., 2005]. Max verf¨ ugt ¨

tive Komponente. Die reaktive Komponente legt die sofortigen Reaktionen fest, w¨ ahrend die deliberative Komponente langfristiges Planen erm¨ oglicht,

ter Pl¨ ane, die f¨ ur die Auswahl der Intention (Intention) entsprechend des aktuellen Wissens (Beliefs) und W¨ unschens (Desires) verwendet wird. ”Intentionale Zust¨ ande seines Dialogpartners repr¨ asentiert Max bislang nicht...

”[Wachsmuth, 2005], geschweige denn geschachtelte Modelle zu bilden, außer dass das Turn-Taking-Modell implementiert wurde [Lessmann u. a., 2004]. Das Turn-Taking-Modell ist in einfacher Betrachtung ein Zustands¨ ubergangsgraph, dessen jeder Zustand einen Kompromiss zwischen W¨ unschen von Max und der mit ihm interagierenden Person bez¨ uglich der Sprecherrolle darstellt. Ein anderes Beispiel sind die Passwortknacker, die strukturierte Buchstabenfolgen als erstes ausprobieren, weil die Menschen dazu neigen, sich struk- ¹² Embodiedconversational agent

¹³ kontextabh¨ angige Gesten und Mimik

24

KAPITEL 2. STAND DER FORSCHUNG

turierte Buchstabenfolgen besser zu merken. In einen Passwortknacker ist sozusagen ein festes Modell eines Menschen eingebaut. Mittlerweile wissen aber viele Menschen von der Funktionsweise der Passwortknacker, d. h. sie haben von denen ein Modell und versuchen, weniger ”menschliche” Passw¨ orter zu erfinden.

Standardrichtung ist aber, die epistemische Logik als ein Modell f¨ ur gegenseitiges Modellieren mit ihren vielen Unterarten einzusetzen. Es gibt eine ganze Reihe von Logikinterpretern (LWB, Molog usw.), die zu Muddy Children Puzzle ¨ ahnliche logische Puzzles l¨ osen k¨ onnen [Bern, 2004]. Die L¨ osung liegt darin, das Puzzle in logischen Formeln zu modellieren und den Wissensstand der Agenten nach jeder Iteration zu beweisen. Um solche Puzzles auf Interaktion zwischen Menschen und Computer zu ¨ ubertragen, bedarf es einer

Modellierung der mentalen Auffassungsf¨ ahigkeit sowie der begrenzten Verarbeitungskapazit¨ at des Menschen. Die Modellierung der resourcebegrenzten Logik ist relativ schwierig und zur Zeit Gegenstand der Forschung. Mit mentaler Auffassungsf¨ ahigkeit sieht es noch schwieriger aus, denn Experimente zeigten, dass selbst ein Zwei-Personen-Puzzle nicht von der Mehrheit der Versuchspersonen gel¨ ost werden konnte [F.Camerer, 2003, S. 236-239].

25

2.2.2 Spezielle Beispiele

Rekursive Modellierungsmethode

voraus und besteht darin, dass ein Agent in einer Interaktion mit anderen

Agenten einen Baum erstellt, der das Wissen ¨

(Abb. 2.14, links). Ein Knoten in diesem Baum ist eine Sicht eines Agenten auf die aktuelle Situation und Kanten sind dem Ausdruck ”h¨ alt mit Wahrscheinlichkeit p f¨ ur m¨ oglich, dass” ¨ aquivalent. Die Knoten und die Kanten in diesem Baum korrespondieren mit Welten und Relationen der Kripke-Struktur. Der Unterschied dabei ist, dass es hier eine Wahrscheinlichkeitsverteilung ¨ uber die M¨ oglichkeiten sowie eine Pfadl¨ angenbegrenzung gibt. In der

auf Abbildung 2.14 (rechts), dargestellten Situation erledigen zwei Roboter, R1 und R2, Aufgaben und bekommen Auszahlungen, die gleich der Summe aller erledigten Aufgaben minus Fahrtkosten sind. Der Wurzelknoten des hier dargestellten RMM-Baumes stellt die Auszahlungen des Roboters R1 abh¨ angig von den Aktionen der beiden Spieler dar. Der n¨ achst tiefere Knoten ist das von Roboter R1 vermutete Wurzelknoten des Roboters R2 usw.. Um die optimale Aktion aus so einem Modell zu berechnen, sind zuerst die Blattknoten zu l¨ osen. Die dort ermittelten optimalen Aktionen werden - gewichtet mit der Kantenwichtung - in den n¨ achst h¨ oheren Knoten propagiert. Sind bei einem Knoten von allen seinen ausgehenden Kanten die optimalen Aktionen

¹⁴ Recursive Modeling Method

26

KAPITEL 2. STAND DER FORSCHUNG

zur¨ uckpropagiert worden, so wird auch dieser Knoten gel¨ ost und die optimalen Aktionen werden zur¨ uckpropagiert.

RMM hat u. a. in einem Algorithmus zur L¨ osung von Persuit Task Anwendung gefunden [Vidal und Durfee, 1995]. Persuit Task ist eine kooperative Aufgabe, bei der mehrere ”Raubtiere” ein sich zuf¨ allig bewegendes ”Beutetier” m¨ oglichst schnell umkreisen m¨ ussen und dabei nicht kommunizieren k¨ onnen. Der auf RMM basierte Algorithmus LR-RMM ¹⁵ benutzt einen RMM-Baum und vergr¨ oßert ihn nur so lange, wie der Auszahlungszuwachs minus Rechenkosten gr¨ oßer als ein bestimmter Wert ist. Der Evaluation zurfolge schneidet LR-RMM besser als andere im Vergleich evaluierte Heuristiken ab.

Verbalisierung des geschachtelten Modellierens

In [Brazier und Treur, 1999] wurde ein m¨ ogliches Modell eines reflexiven Agenten vorgestellt, der ¨ uber eigenes Wissen, den eigenen Schlussfolgerungsprozess und den Schlussfolgerungsprozess anderer Agenten schlussfolgern kann. Das Modell besteht aus mehreren Komponenten, die verschiedene Aufgaben erledigen und miteinander kommunizieren k¨ onnen. Dieses Modell wurde f¨ ur die Verbalisierung des Schlussfolgerungsprozesses beim L¨ osen einer simplen Variante von Wise Men’s Puzzle verwendet. Dieses Puzzle ist im Grunde eine Abwandlung vom Muddy Children Puzzle und wird im Paper folgendermaßen beschrieben:

Das implementierte Modell verbalisiert die L¨ osung des Puzzles aus der Sicht des weisen Mannes B gegeben die Aussage des weisen Mannes A dar¨ uber, ob er (Mann A) die Farbe seines Hutes schon kennt. Dabei werden Komponenten des Systems so eingestellt, dass sie durch ihre Kommunikation eine interne Schleife bilden, die Hypothesen nacheinander beweist bzw. widerlegt. Diesem Ansatz ist nur ¹⁶ die Idee der Verbalisierung f¨ ur die Arbeit zu entnehmen. Denn wenn ein System geschachtelte Modelle verbalisieren kann, dann

f¨ ur ”weitgehend psychologisch plausibel” erkl¨ art.

27

muss es diese Modelle auch repr¨ asentieren k¨ onnen. Ferner kann man sich vorstellen, den Vergleich zwischen der sprachlichen Ausgabe des Systems und der Meinung der mit dem System interagierenden Person als Bewertungsgrundlage zu benutzen.

2.2.3 Zusammenfassung

Wie die Recherche zeigte, wurde das in dieser Arbeit vorgeschlagene Thema in der KI noch nie direkt in Angriff genommen. Noch nicht Stand der Forschung ist ein Setup, bei dem ein mit einem Menschen interagierender k¨ unstlicher Agent anhand des beobachteten Verhalten des Menschen dynamisch ein geschachteltes Modell des Gegen¨ ubers aufbaut. Als eine Erkl¨ arung daf¨ ur kann man erw¨ ahnen, dass dieses Vorhaben wegen der umfangreichen Theorie (sehe Abschnitt 2.1) relativ viel Einarbeitungszeit erfordert. Das Ziel dieser Arbeit ist genau diese Forschungsl¨ ucke in der KI zu schliessen.

28

KAPITEL 3. KONZIPIERUNG UND ANALYSE

Kapitel 3

Konzipierung und Analyse

3.1 Wahl des einfachen Interaktionsszenarios

In der Entwurfsbeschreibung (Abschnitt 1.1) wurde gleich am Anfang ein Beispiel einer plausiblen realen Situation gezeigt, wo Individuen einander geschachtelt modellieren. Zu einer solchen Situation kann man sich im Grunde ein ¨ aquivalentes Spiel ausdenken und dann die optimale Strategie bestimmen. Trotzdem wird das Ausw¨ ahlen einer Strategie in einer solchen allt¨ aglichen Situation bei Menschen oft ohne die Verwendung irgendwelcher mathematischer Konzepte z. B. aus der Spieltheorie gemacht. Auch die Spieltheoretiker k¨ onnen nicht jede reale Situation auf ein Spiel mit bekannter L¨ osungsstrategie zur¨ uckf¨ uhren, denn sonst w¨ are die Spieltheorie eine Wissenschaft ohne jegliches Potential. Es w¨ are in zuk¨ unftigen Arbeiten interessant, herauszufinden, ob das allt¨ agliche, verhaltensbestimmende Denken eines Menschen immer mathematisch formalisierbar ist. Wenn aber ToM eines Menschen nicht immer mathematisch formalisierbar ist, dann k¨ onnte ein k¨ unstlicher Agent einen Menschen nie exakt modellieren, denn ein k¨ unstlicher Agent kann nur mathematisch formalisierbare Modelle aufbauen. Aber wenn ein Mensch eine Vorstellung von den Vorg¨ angen im Kopf des anderen hat, dann ist diese Vorstellung wahrscheinlich strukturiert, und wenn das so ist, dann ist geschachteltes Modellieren in der Interaktion zwischen Menschen und k¨ unstlichen Agenten m¨ oglich. Wenn man also ein Interaktionsszenario ausw¨ ahlen will, bei dem ein k¨ unstlicher Agent einen Menschen modellieren soll, dann muss dieses Szenario den Menschen zur Wahl einer formalisierbaren Strategie verleiten. Anders gesagt: Der interagierende Mensch sollte daran interessiert sein, eine strukturierte Denk- und Verhaltensweise zu entwickeln. Die Struktur einer realen Situation w¨ urde sich ein Mensch wahrscheinlich anders vorstellen, als sie tats¨ achlich ist. Das w¨ urde die Modellierung dieses

29

3.1. WAHL DES EINFACHEN INTERAKTIONSSZENARIOS

Menschen komplizierter oder vielleicht sogar unm¨ oglich machen. Das heißt, als MNM-Interaktionsszenario w¨ urde nur eine relativ leicht verst¨ andliche Situation in Frage kommen. Gewinnorientierte Gesellschaftsspiele passen relativ gut in dieses Muster.

Anstatt ein Spiel zu konstruieren, ist es besser, eines aus den schon lange bekannten bzw. erfolgreich vermarkteten Spielen auszuw¨ ahlen. Denn so ist es sichergestellt, dass das Spiel menschlichen Spielern gen¨ ugend Unterhaltung bietet. Der Unterhaltungsfaktor ist wichtig, damit sich die menschlichen Spieler mit der Struktur des Spiels intensiv besch¨ aftigen. Als einfachstes MNM-Interaktionsszenario kann man sich ein wiederholtes Spiel mit zwei Spielern, einem Menschen und einem k¨ unstlichen Agenten, vorstellen. Die Auswahlkriterien kann man folgendermaßen zusammenfassen:

Die Zwei-Personen-Gesellschaftsspiele teilen sich haupts¨ achlich in zwei Gruppen: das gemeinsame Puzzle-L¨ osen und die Nullsummenspiele. Alle Zwei-Personen-Nullsummenspiele, unter Annahme des gemeinsamen Wissens ¨ uber

die Rationalit¨ at der beiden Spieler, haben ein Nash-Gleichgewicht und daher keinen Anreiz f¨ ur das Modellieren des anderen. Beim gemeinsamen Puzzle-L¨ osen l¨ asst sich das Nash-Gleichgewicht auch berechnen, obwohl die beiden Spieler es nicht sofort berechnen k¨ onnen und daher von ”Puzzle” sprechen. Dadurch scheinen die Auswahlkriterien vorerst inkonsistent zu sein. Aber wie der Abschnitt 2.1.4 gezeigt hat, weichen Menschen vom Nash-Gleichgewicht ab. Speziell in Zwei-Personen-Nullsummenspielen spielen Menschen nicht optimal. Dadurch kann man sich zwei M¨ oglichkeiten vorstellen, bei denen die beiden Spieler ihr Verhalten in Abh¨ angigkeit vom Verhalten des anderen ¨ andern:

KAPITEL 3. KONZIPIERUNG UND ANALYSE

• Der k¨ unstliche Agent weicht vom Nash-Gleichgewicht ab und wartet darauf, bis der Mensch es merkt und ausnutzt. Danach nutzt der k¨ unstliche Agent das ge¨ anderte menschliche Verhalten aus und wartet darauf, bis der Mensch es merkt und ausnutzt, usw..

Das erste Szenario scheidet aus, weil erstens das intuitive menschliche Spielen schwer modellierbar ist und zweitens werden hier keine tief geschachtelten Modelle aufgebaut. Beim zweiten Szenario aber agiert der k¨ unstliche Agent nicht rational. Es bedarf einer Auszahlungsstruktur, die das Verhalten des k¨ unstlichen Agenten rationalisiert, wie sie auf Tabelle 3.1 dargestellt ist. Eine solche Auszahlungsstruktur wird als fiktives Spiel ¹ bezeichnet [Owen, 1970, S. 32f]. Die Matrix des fiktiven Spiels stellt ein wiederholtes Zwei-Personen-Nullsummenspiel dar, bei dem der menschlicher Spieler gewinnen will und der k¨ unstliche Agent am Aufbau tief geschachtelter Modelle interessiert ist. Der k¨ unstliche Agent erf¨ ahrt nicht w¨ ahrend des Spielens, welche Strategie der Mensch tats¨ achlich spielt, sondern er muss sie anhand der Beobachtungen feststellen und kann daher seine Auszahlungen nur absch¨ atzen. Die Auszahlungen des menschlichen Spielers dagegen stellen die Bilanz zwischen Siegen und Niederlagen dar, die allen Spielern sichtbar ist. Wie man auf der Matrix sehen kann, besitzt jeder Spieler eine unendliche Anzahl von Strategien und jede Strategie entspricht einem Modell des Gegners. Man sieht, dass der menschliche Spieler immer dann die h¨ ochste Auszahlung bekommt, wenn er den Gegner richtig modelliert und die niedrigste Auszahlung, wenn der Gegner ihn richtig modelliert. Als Beispiel nehmen wir an, dass der k¨ unstliche Agent ein Modell der 2-Ordnung hat, d. h., dass er weiß, das der Mensch ein Modell der 1-Ordnung von ihm hat. Hat der Mensch tats¨ achlich ein Modell der 1-Ordnung vom k¨ unstlichen Agenten, dann liegt der k¨ unstliche Agent richtig und ”durchschaut” den Menschen.

Spiele bei denen sich das Durchschauen einer deterministischen bzw. puren Strategie lohnt, sind Spiele bei imperfekter Information, d. h. mit simultanen bzw. verdeckten Z¨ ugen. Ein sehr guter Kandidat f¨ ur so ein Spiel, ist Pico 2 f¨ ur zwei Spieler (Abb. 3.1). Die Regeln f¨ ur dieses Spiel sind relativ einfach:

31

Hinzu kommt, dass die Beschreibung des Spielkonzepts durch den Autor thematisch sehr nah am Konzept dieser Arbeit ist:

32

KAPITEL 3. KONZIPIERUNG UND ANALYSE

Außerdem hat Pico 2 eine wissenschaftliche Vorgeschichte. Pico 2 wurde von einem in 1993-94 in Newsgroups angek¨ undigten Programmierwettbewerb in-

zeichnen.

33

3.2 Spielstruktur und Berechnung des Nash-

Gleichgewichtes

In diesem Abschnitt wird die Struktur des Spiels formalisiert. Es handelt sich um ein Zwei-Personen-Nullsummenspiel bei imperfekter Information in ex-

tensiver Form. In einer Runde ⁴ dieses Spiels gewinnt derjenige, der eine h¨ ohere Punktzahl erreicht. Die Runde besteht aus zwei Phasen ⁵ . Die beiden Phasen unterscheiden sich dadurch, dass die Spieler ihre Kartens¨ atze vertauschen. Die Punkte werden in zwei Phasen gesammelt und dann summiert. Folglich ist das Ziel jedes Spielers x in jeder Phase die Differenz zwischen gegnerischen (des Spieler x) und eigenen Punkten di f f (x) = (Punkte(x) − Punkte(y)) zu maximieren, wobei di f f (x) = −di f f (y) gilt. In jeder Phase bekommt jeder Spieler f¨ unf Karten. Da es insgesamt 11 Karten gibt, gibt es 2772 M¨ oglichkeiten, die Karten auf die Spieler zu verteilen. Diese Zahl berechnet sich aus dem Produkt der Zahl der M¨ oglichkeiten, 5 Karten f¨ ur den ersten Spieler aus den urspr¨ unglichen 11 auszuw¨ ahlen und der Zahl der M¨ oglichkeiten, 5 Karten f¨ ur

11 6

) ⁶ , wobei die den zweiten Spieler aus den restlichen 6 auszuw¨ ahlen ( ∗

5 5

H¨ alfte der 2772 Kartens¨ atze spiegelverkehrt ist. Zwei spiegelverkehrte Kartens¨ atze unterscheiden sich nur dadurch, dass die beiden Phasen vertauscht sind. Zwei spiegelverkehrte Kartens¨ atze ergeben Spiele, deren optimale L¨ osung identisch ist. Die spiegelverkehrten Kartens¨ atze werden aber trotzdem unterschieden, weil es w¨ ahrend des Spiels zu unterschiedlichen Lerneffekten kommen kann, die die L¨ osung des Spiels aus der Sicht jedes einzelnen Spielers ver¨ andern. Von den Handkarten kann jede Karte jeder Zeit benutzt werden, soweit sie nicht abgelegt ist. Falls eine Karte c x abgelegt wird, bekommt ihr Besitzer x eine Punktzahl Wichtung(c x ) entsprechend der Wichtung der Karte (Tabelle 3.2).

Die Karten werden simultan gezogen. Die Ablegeregel l¨ asst sich am besten

in Pseudo-Code definieren (Abb. 3.2). Eine Phase wird abgeschlossen, wenn einer der Spieler nur noch eine Karte auf der Hand hat. Eine Phase l¨ asst sich als ein Spielbaum mit imperfekter Information darstellen. Dieser Spielbaum

⁴ der Spielverlauf zwischen Spielstart und Siegerbestimmung

⁵ die ”Hinrunde” und die ”R¨ uckrunde” aus der authentischen Spielbeschreibung

⁶ Kombination ohne Wiederholung [Bronstein u. a., 2001, S. 767]

34

KAPITEL 3. KONZIPIERUNG UND ANALYSE

ist gemeinsames Wissen der Spieler, weil die restliche Karte und die abgelegten Karten offengelegt werden und dadurch jeder Spieler weiß, welche Karten der Gegner auf der Hand h¨ alt. Dadurch kann man vor jedem Zug eine Matrix kurzsichtiger Auszahlungen f¨ ur jede Kartenkombination aufstellen (Abb. 3.3). Die Auszahlungen in dieser Matrix sind entsprechend der Konvention in

der Spieltheorie aus der Sicht des Zeilenspielers dargestellt und geben die so-fortige Auswirkung auf die Differenz des ersten Spielers di f f (x) an, die er zu maximieren und der Spaltenspieler zu minimieren versucht. Außer der sofortigen Auszahlung bewirkt eine Kartenkombination gleichzeitig die Auswahl eines Pfades im Spielbaum. Jeder Pfad besitzt einen Erwartungswert. Der Erwartungswert eines Pfades wird zum jeweiligen Eintrag der kurzsichtigen Auszahlungsmatrix aufaddiert und ergibt sich dadurch die vorausschauende Auszahlungsmatrix. Der Erwartungswert eines Pfades selbst berechnet sich aus dem Erwartungswert der vorausschauenden Matrix des ersten Knotens, das heißt, der Auszahlung im Nash-Gleichgewicht. Die Blattknoten des Spielbaumes sind Situationen, in denen einer der Spieler nur noch eine Karte besitzt; sie werden mit Erwartungswert 0 belegt. Nachdem die Struktur des Spieles gekl¨ art worden ist, wenden wir uns der Berechnung des Nash-Gleichgewichts zu. In diesem Spiel existiert ein Nash-Gleichgewicht und das Spielen der vom Nash-Gleichgewicht vorgeschlagenen Strategien garantiert jedem Spieler, im Durchschnitt mindestens ein Unentschieden zu erreichen, weil die beiden Phasen einander ausgleichen. Die Berechnung des Nash-Gleichgewicht besteht darin, in jeder vorausschauenden

35

Matrix ein Nash-Gleichgewicht entweder in puren oder in gemischten Strategien zu suchen. Das Suchen des Nash-Gleichgewichts in puren Strategien ist trivial. Man vergleicht einfach den maximalsten der minimalsten Eintr¨ age jeder Zeile mit dem minimalsten der maximalsten Eintr¨ age jeder Spalte der Auszahlungsmatrix. Wenn die beiden gleich sind, hat man ein Nash-Gleichgewicht in puren Strategien gefunden [R.Singleton und F.Tyndall, 1974]. Nat¨ urlich haben die meisten Matrizen kein Nash-Gleichgewicht in puren Strategien. Eine Evaluation aller Kartens¨ atze, bei der die Erwartungswerte der Pfade durchgehend mit Maximin(bzw. Minimax)-Regel berechnet wurden, hat ergeben, dass nur bei 318 aus 2772 (Tabelle 3.3) m¨ oglichen Kartens¨ at-

zen das Spielen optimaler Strategie ohne Verwendung gemischter Strategien m¨ oglich ist. Beim Kartensatz 4 · 5 · 6 · 7 · 89 · 10 · 11 · 12 · 13 z.B. legt der erste Spieler zuerst die Karte 4 ab, dann legt der zweite Spieler die Karten 9 und 10 ab, wonach der erste Spieler die Karte 5 ablegt und anschließend legt der zweite Spieler die Karten 11 und 13 ab und beendet mit 12 : 3. Aber es gibt auch Kartens¨ atze, die Spiele erzeugen, bei denen die Differenz zwischen Minimax und Maximin besonders groß ist. Solche Spiele ¨ ahneln vom Spielprinzip her ”Papier-Stein-Schere”.

Die Berechnung der gemischten Strategien erfolgt mit Hilfe des Simplex-Algorithmus [Owen, 1970, S. 39f]. Um den Aufwand beim Simplex-Verfahren

36

KAPITEL 3. KONZIPIERUNG UND ANALYSE

Minimax − Maximin 0 1 2 3 4 6 5 7 8 9 10

Abbildung 3.5: Lineares Programm zur Auszahlungsmatrix A

zu minimieren, werden aus der urspr¨ unglichen Matrix iteriert schwachdominierte Spalten und Zeilen so lange entfernt, bis es keine mehr gibt. Die auf

diese Weise verkleinerte Auszahlungsmatrix A (A des ersten Spielers ist −A t

des zweiten Spielers) wird danach in Form eines linearen Programms (Abb. 3.5) aufgeschrieben (µ-Erwartungswert, x i -Wahrscheinlichkeiten des ersten Spielers). Der Simplex-Algorithmus liefert wegen der Dualit¨ at ⁷ [Owen, 1970, S. 41f] immer gleichzeitig die optimalen Wahrscheinlichkeiten f¨ ur beide Spieler.

Die Verwendung gemischter Strategien auf Einphasenb¨ aumen birgt aber in sich ein Problem in Bezug auf die spezielle Siegerbestimmung dieses Spiels. Die gemischte Strategie maximiert den Erwartungswert der Punktzahldifferenz, aber die Siegbedingung ist, dass diese Zahl einfach positiv ist. So kann z.B. ein niedrigerer immer noch positiver Erwartungswert mit kleinerer Streuung besser sein, als ein h¨ oherer Erwartungswert mit h¨ oherer Streuung. Exakte

gen, denn es w¨ urde deren Umfang sprengen. Interessierte Leser sollten daf¨ ur einschl¨ agige Literatur nutzen.

37

L¨ osung erh¨ alt man nur durch die L¨ osung eines aus beiden Phasen zusammengesetzten Spielbaumes, bei dem die Punkte vorw¨ arts und die Siegwahrscheinlichkeiten r¨ uckw¨ arts propagiert werden, was erheblich mehr Rechenaufwand als die L¨ osung eines Ein-Phasen-Baumes braucht. Dieser Algorithmus arbeitet auch wie die L¨ osung einer Phase auf einem Baum mit Matrizen als Knoten f¨ ur jeden simultanen Zug, aber die Eintr¨ age dieser Matrizen variieren zwischen −1 und 1 und geben die Siegwahrscheinlichkeit an. Die Eintr¨ age dieser Matrizen sind gleich den Erwartungswerten der entsprechenden Teilb¨ aume. Der Wert eines Blattes ist eine Zahl aus der Menge {−1, 0, 1} und ist entsprechend der dort erreichten Punktzahldifferenz gesetzt. Die Tabelle 3.4 stellt beispielsweise dar, mit welchen Wahrscheinlichkeiten f¨ ur jede Karte zwei rationale Spieler das Spiel zum Kartensatz 4 · 5 · 6 · 7 · 118 · 10 · 12 · 13 · 16 anfangen sollen.

38

KAPITEL 3. KONZIPIERUNG UND ANALYSE

3.3 Detektion der Verhaltensstrategien und

MNM-Algorithmus

Alle m¨ oglichen Verhaltensstrategien, die man in diesem Spiel verwenden k¨ onnte, wenn man den großen Aufwand der exakten Berechnung des Nash-Gleichgewichtes umgehen will, teilen sich in zwei Gruppen: die kurzsichtigen und die vorausschauenden. Die kurzsichtigen Strategien nehmen nur die sofortige Auszahlung wahr, w¨ ahrend die vorausschauenden den ganzen Spielbaum traversieren und die Erwartungswerte zum Wurzelknoten zur¨ uckpropagieren. Man kann sich auch eine Mischung aus diesen beiden Gruppen vorstellen, bei der der Spielbaum begrenzt bzw. gewichtet traversiert wird. Messungen ⁸ haben ergeben, dass kurzsichtige Summenmaximierung (MSM ⁹ ) in Vergleich zur Nash-Strategie auf allen Kartens¨ atzen im Schnitt nur um

≈ 16, 5% ¹⁰ , w¨ ahrend das zuf¨ allige Spielen um ≈ 67% schlechter ist. Daraus kann man folgern, dass sogar das vollst¨ andige Vorausschauen in diesem Spiel nur wenig Vorteile bringt. Zu dieser Erkenntnis w¨ urden wahrscheinlich auch menschliche Pico-Spieler kommen und sich nur wenig auf das Vorausschauen wenig konzentrieren. Die Summenmaximierung, als eine g¨ angige Verhaltensstrategie menschlicher Spieler, ist empirisch selbst bei den relativ kleinen 3 × 3-Matrizen mit 24% nachgewiesen worden [Stahl und Wilson, 1994]. Die Summenmaximierung wird auch als eine Antwortstrategie auf einen irrationalen zuf¨ alligen Spieler verstanden. Diese Strategie hat aber einen entscheidenden Fehler - sie kann durchschaut und ausgenutzt werden. Tats¨ achlich erzielt die kurzsichtige Bestantwortstrategie (MBR ¹¹ ) auf MSM bei Pico nahezu hundertprozentige Gewinnwahrscheinlichkeit gegen MSM. Bestantwortstrategie auf Summenmaximierung wurde von 49% der Versuchspersonen angewendet und nur 27% nutzten Nash-Strategie.

Zusammengefasst eignet sich MSM gut daf¨ ur, einer deterministischen Verhaltensstrategie zu Grunde gelegt zu werden, die der k¨ unstliche Agent im fiktiven Spiel (Abb. 3.1) spielen sollte. Die daraus entwickelte Verhaltens-

strategie DMSM ¹² l¨ asst sich als folgender verbaler Algorithmus beschreiben:

1. Nimm alle Zeilen mit maximaler Summe aus der kurzsichtigen Auszahlungsmatrix A und f¨ uge sie zur Strategiemenge F zusammen.

39

Wenn DMSM die vom k¨ unstlichen Agenten verwendete 0-Ordnung-Strategie im fiktiven Spiel ist, dann ist die sie durchschauende, vom Menschen zu benutzende 1-Ordnung-Strategie die kurzsichtige Bestanwortstrategie MBR(·), weil die Motivation f¨ ur die Benutzung einer vorausschauenden Bestanwortstrategie wegen sehr geringer Verbesserung fehlt. Nun zur Definition von MBR(DMSM):

Verhaltensstrategien h¨ oher grader Ordnung DMBR(MBR(·)) ¹⁴ , die vom k¨ unstlichen Agenten verwendet werden, m¨ ussen auch deterministisch sein, um eigene Durchschaubarkeit zu garantieren. Sie lassen sich folgendermaßen definieren:

Und die Verhaltensstrategien h¨ oher ungerader Ordnung MBR(DMBR(·)) sind entsprechend der 1-Ordnung-Strategie definiert.

Aus der Auszahlungmatrix des fiktiven Spiels (Abb. 3.1) l¨ asst sich ein Zu-stands¨ ubergangsgraph (Abb. 3.6) f¨ ur den k¨ unstlichen Agenten ableiten. Im initialen Zustand werden nur die Wahrscheinlichkeiten f¨ ur drei Verhaltensstrategien des Gegners errechnet, die zusammen 100% ergeben: die zuf¨ allige,

¹³ risikoscheu ¹⁴ deteministic MBR

40

KAPITEL 3. KONZIPIERUNG UND ANALYSE

Abbildung 3.6: Zustands¨ ubergangsgraph im fiktiven Spiel

die MSM und die 1-Ordnung-Strategie. Jede nicht formalisierbare Verhaltensstrategie des Menschen im fiktiven Spiel wird als eine Linearkombination aus MSM und der zuf¨ alligen modelliert. Man kann sich auch vorstellen, dass der menschliche Spieler sich auf Grund besonderer Begabung entsprechend der exakten Nash-Strategie verh¨ alt und dadurch eine theoretisch h¨ ohere Auszahlung erhalten kann, als ein DMSM-nutzender k¨ unstlicher Agent. Praktisch aber macht jeder Mensch mit einer bestimmten Wahrscheinlichkeit Fehler. Dadurch w¨ urde ein Mensch kaum eine h¨ ohere Gewinnwahrscheinlichkeit erreichen. Außerdem ist die 1-Ordnung-Strategie viel profitabler und einfacher zu bestimmen.

Aus dem initialen Zustand geht der k¨ unstliche Agent in den n¨ achsten, d. h. zweiten Zustand ¨ uber, wenn die Wahrscheinlichkeit f¨ ur die 1-Ordnung-

Strategie P(1 − Ordnung) den Pegel p 0 ¨

die 2-Ordnung-Strategie verwendet. Generell geht der k¨ unstliche Agent aus dem Zustand n bei P((1 + 2 ∗ n) − Ordnung) > p 0 in den Zustand n + 1 ¨ uber,

f¨ ur alle n von 0 bis unendlich. Da die Benutzung der Verhaltensstategien h¨ oher Ordnung f¨ ur menschliche Spieler mit h¨ oherem Aufwand verbunden ist, werden sie irgendwann wieder eine intuitive Verhaltensstrategie verwenden. Daher muss der k¨ unstliche Agent vom Zustand n, n > 0, in den Zustand 0 ubergehen, wenn die Summe der beiden, in diesem Zustand zu erwartenden ¨

Verhaltensstrategien unter den Pegel p 1 rutscht.

41

Abbildung 3.7: Rekursives Modell des k¨ unstlichen Agenten im fiktiven Spiel

Der k¨ unstliche Agent l¨ asst sich auch mit Hilfe der RMM beschreiben (Abb. 3.7). Der Wurzelknoten des hier dargestellten rekursiven Modells, sowie je-

der ungef¨ uhlte schwarzer Kreis, stellt DMBR-Strategie dar, wobei DMSM = DMBR(ZK) = DMBR(Nash) = DMBR(MSM) und MSM = MBR(ZK) gelten. Die ungef¨ uhlten roten Kreise symbolisieren dagegen die MBR-Strategie; der einzige gef¨ uhlte Knoten symbolisiert die Nash-Strategie. In jedem Zustand des Zustands¨ ubergangsgraphen entspricht der k¨ unstliche Agent einem begrenzten Ausschnitt aus dem allgemeinen rekursiven Modell. Die Wahrscheinlichkeiten f¨ ur einzelne zu erkennende Verhaltensstrategien werden nach dem Bayes-Theorem berechnet, bei der deren a-priori-Wahrscheinlichkeiten gleich sind und die sich daher wegk¨ urzen lassen:

Die Wahrscheinlichkeiten P(Data | Str a ) werden auf einer endlichen Liste von zuletzt beobachteten Verhaltensbeispielen berechnet:

g

KAPITEL 3. KONZIPIERUNG UND ANALYSE

im Beispiel j von der Strategie a produziert zu sein.

Jedes Verhaltensbeispiel ist eine kurzsichtige Auszahlungsmatrix, bei der der k¨ unstliche Agent die Beobachtung macht, dass der menschliche Spieler aus l m¨ oglichen Karten die Karte c i ausw¨ ahlt. W¨ urde ein menschlicher Spieler z.B. zuf¨ allig entscheiden, dann w¨ are die Wahrscheinlichkeit f¨ ur jede einzelne

Karte ¹ l . Entscheidet der menschliche Spieler aber nicht zuf¨ allig, sondern nach einer bestimmten Verhaltensstrategie, so gibt es m Karten, die er spielen w¨ urde, und n = l − m Karten, die er meiden w¨ urde. Hinzu kommt noch, dass der Mensch mit einer bestimmten Wahrscheinlichkeit Fehler macht, d. h. manchmal falsche Karten ausw¨ ahlt. Um die Fehlerwahrscheinlichkeiten f¨ ur alle m und n Werte zu berechnen, wird hier QRE ¹⁵ [F.Camerer, 2003, S. 33] verwendet:

Da der k¨ unstliche Agent deterministisch ist und keine Fehler macht, gibt es nur eine Strategie s −i mit 100%-prozentiger Wahrscheinlichkeit. Das f¨ uhrt zur Vereinfachung:

Nun setzt man f¨ ur Auszahlung 0, wenn man einen Fehler macht, und 1, wenn die richtige Karte gespielt wird und erh¨ ahlt die Wahrscheinlichkeit eines falschen Zuges:

und die Wahrscheinlichkeit eines richtigen Zuges:

Nehmen wir jetzt an, der menschliche Spieler macht bei zwei auszuw¨ ahlenden Aktionen mit 5% ¹⁶ einen Fehler. Das w¨ urde ergeben:

Studien zeigen

43

Durch Aufl¨ osung nach e ^λ erh¨ alt man:

e ^λ = 0.95 0.05 = 19

Mit Hilfe dieses Wertes kann man die entg¨ ultigen Formeln f¨ ur die Warscheinlichkeit der Auswahl eines Zuges angeben, gegeben die Menge der richtigen Z¨ uge R(Str a ) in Anh¨ angigkeit von der Strategie Str a :

Mit Hilfe von Gleichungen 3.2 lassen sich die Tabellen 3.5 und 3.6 aufstellen, die die Wahrscheinlichkeiten modellieren, mit denen eine Karte von einem Menschen gew¨ ahlt wird, falls sie seiner gespielten Strategie entspricht oder seiner gespielten Strategie nicht entspricht. Die Gleichungen 3.1 und 3.2 kann man folgendermaßen in Beziehung setzen:

Das Hauptziel des k¨ unstlichen Agenten im fiktiven Spiel ist die Erkennung dessen, ob er vom menschlichen Spieler durchschaut wird. Daf¨ ur eignen sich

44

KAPITEL 3. KONZIPIERUNG UND ANALYSE

aber nicht alle kurzsichtigen Matrizen; sie werden deswegen nicht in die Beobachtungsliste aufgenommen. Hier sind die Ausschlusskriterien mit Begr¨ undungen:

1. m = l : Die von DMBR ausgew¨ ahlte Zeile ist gleich in allen Spalten.

2. Dominante Spalten : Das W¨ ahlen oder nicht W¨ ahlen dieser Spalten zeigt nur die allgemeine Rationalit¨ at und nicht die Antizipation der gegnerischen Handlung.

3. Kombination der Zeile und Spalte ist ein Nash-Gleichgewicht : Das W¨ ahlen dieser Spalte kann nicht nur als die Antizipation der gegnerischen Handlung, sondern auch als gegnerische Antipazipation der eigenen Handlung interpritiert werden.

Eine Evaluation ¹⁷ hat ergeben, dass pro Runde im Schnitt ≈ 6.3 auswertbare F¨ alle vorkommen. Die Tabelle 3.7 gibt eine Verteilung dieser F¨ alle nach l und m an. Die Variable g, die die Ged¨ achtnisgr¨ osse festlegt, darf nicht zu groß sein, denn dann w¨ are der k¨ unstliche Agent wegen der Gleichgewichtung der Beobachtungen zu tr¨ age; und nicht zu klein, denn dann w¨ are er anf¨ allig f¨ ur Fehleinsch¨ atzungen. Nach Evaluation mit computersimulierten menschlichen Gegnern hat sich der Wert 9 f¨ ur den initialen Zustand und der Wert 11 f¨ ur andere Zust¨ ande als sinnvoll erwiesen. Genauso, mit Hilfe deiser Evaluation, sind auch die Werte f¨ ur p0 und p1 auf 0, 96 und 0, 0005 gesetzt worden. Diese Werte k¨ onnten nat¨ urlich auch analytisch bestimmt werden, was aber relativ aufw¨ andig.

Dem hier beschriebenen Aufbau des k¨ unstlichen Agenten im fiktiven Spiel (kann auch als MNM-Algorithmus bezeichnet werden) wird keine Optimalit¨ at unterstellt. K¨ unftige Arbeiten werden eventuell basierend auf empirischen Studien einen besseren Aufbau vorschlagen.

¹⁷ 10 ∗ 2772 Runden, zuf¨ allig gegen DMSM

45

3.4. WAHL DES ZWEITEN INTERAKTIONSSZENARIOS

3.4 Wahl des zweiten Interaktionsszenarios

Das erste Interaktionsszenario bedurfte eines fiktiven Spiels, um den Aufbau geschachtelter Modelle f¨ ur den k¨ unstlichen Agenten zu rationalisieren. Deswegen sollte ein in diesem Abschnitt beschriebenes Spielkonzept eingef¨ uhrt werden, das den Entwurf von Spielstrukturen m¨ oglich macht, bei denen der Aufbau geschachtelter Modelle rational ist.

Es gibt zwei Verhaltensmuster, Kooperation und Konkurrenz, die bei der Interaktion mehrerer Individuen betrachtet werden. Die Abbildung 3.8 zeigt zwei einfache Spiele, die f¨ ur Kooperation (links) und Konkurrenz (rechts) stehen, bei denen das Nash-Gleichgewicht in gemischten Strategien liegt. In der Kooperationsituation m¨ ussen sich die beiden Spieler m¨ oglichst vorhersagbar und in der Konkurrenzssituation m¨ oglichst unvorhersagbar verhalten. Das vorhersagbare Verhalten baut sich am besten auf Grund einer bestimmten Konvention auf. Bevor aber eine solche Konvention erfunden wird, haben die beiden Spieler Interesse daran, das Verhalten des Gegen¨ ubers zu modellieren. Ist aber Konvention eingef¨ uhrt, m¨ ussen sie es nicht mehr machen. Nehmen wir aber an, dass mehrere Spieler interagieren, und jeder Spieler einen festen Partner und einen festen Gegner hat. Dadurch ist jeder Spieler daran interessiert, seinem Partner gegen¨ uber vorhersagbar und seinem Gegner gegen¨ uber unvorhersagbar zu verhalten. Voraussetzung daf¨ ur ist, dass der Partner und der Gegner sich voneinander in ihren F¨ ahigkeiten irgendwie unterscheiden, sonst w¨ are das Verhalten des Spielers entweder den beiden gegen¨ uber vorhersagbar oder den beiden gegen¨ uber unvorhersagbar. Um in solcher Situation ein optimales Verhalten zu w¨ ahlen, muss jeder Spieler seinen Partner und seinen Gegner modellieren. Da aber alle Spieler das tun wollen, wird es zum Aufbau geschachtelter Modelle kommen.

Die kleinste Zahl der Spieler in einem Spiel, wo jeder Spieler einen Gegner

und einen Partner hat, ist 4, denn bei 3 w¨ are mindestens einer der Spieler

46

KAPITEL 3. KONZIPIERUNG UND ANALYSE

seines Partners Gegner. Die vier Spieler (1,2,3,4) sind in zwei Partnerpaare ¹⁸ bzw. Fraktionen, I (1,3) und II (2,4), unterteilt (siehe Abb. 3.8). Spieler in einer Fraktion k¨ onnen nur gemeinsam einen identischen Betrag gewinnen oder verlieren und jede Fraktion gewinnt nur so viel, wie die andere Fraktion verliert. Außer den Fraktionen sind die Spieler in zwei Gegnerpaare, α (1,2) und β (3,4), unterteilt. Jedes Gegnerpaar spielt ein Nullsummenspiel ohne Nash-Gleichgewicht in puren Strategien, wie z.B. Matching-Pennies (Abb. 3.8 rechts). Wenn beide Spieler in einer Fraktion die gleichen Strategien spielen, so verlieren sie einen Betrag b, außer wenn die Spieler anderer Fraktion auch die gleichen Strategien spielen, denn dann bekommt jeder Spieler als Auszahlung 0. In sonstigen F¨ allen gewinnt jede Fraktion die Summe der Gewinne der beiden Spieler aus den jeweiligen Gegnerpaaren. Zus¨ atzliche Bedingung

ist, dass kein Spieler mit einem anderen kommunizieren darf. Sonst k¨ onnte jeder Spieler die mentalen Eigenschaften seines Partners ver¨ andern, indem er ihm seine Verhaltensstrategie mitteilt. Das Spiel wird wiederholt gespielt und es besteht das gemeinsame Wissen der Ungleichheit der F¨ ahigkeiten aller Spieler. Die Abbildung 3.9 zeigt beispielsweise die ¨ Ubertragung dieses Konzeptes auf Matching-Pennies und Papier-Stein-Schere. Wenn alle Spieler zwar unterschiedliche aber nicht begrenzte F¨ ahigkeiten haben, dann haben solche Spiele kein garantiertes Nash-Gleichgewicht. Bei Matching-Pennies kann eine denkbare Strategie des Spielers sein, eine f¨ ur den Gegner zuf¨ allig aussehende und f¨ ur den Partner deterministische Bitfolge zu produzieren, denn das w¨ urde ihn besser stellen als rein zuf¨ alliges Spielen. Da die F¨ ahigkeiten eines Spielers unbegrenzt sind, hat jeder Spieler eine unendliche Teilmenge aller m¨ oglichen Bitfolgenproduktionsregeln zur Verf¨ ugung. Hat man aber eine unendliche

¹⁸ ¨ Ahnlich wie bei den Spielen bridge und Doppelkopf

47

Tabelle 3.9: ¨ Ubertragung auf Matching-Pennies und Papier-Stein-Schere

Strategiemenge zur Verf¨ ugung, so kann nach dem allgemeinen Existenzsatz kein Nash-Gleichgewicht garantiert werden (siehe Abschnitt 2.1.2). Um dieses Spielkonzept zum Aufbau eines Interaktionsszenarios zu verwenden, bei dem Menschen mit Maschinen interagieren k¨ onnen, kann ein Gesellschaftsspiel wie z.B. Pico 2 genommen werden, auf das es sich ¨ ubertragen

l¨ asst. Die Annahme, dass die Spieler ein gemeinsames Wissen ihrer geistiger Verschiedenheit haben, w¨ urde unter Menschen ohne weiteres gelten. Durch ¨ Ubertragung dieses Spielkonzeptes auf Pico 2 entsteht ein neues Gesellschaftsspiel, das als Pico 4 getauft werden kann. Die Regeln f¨ ur Pico 4 lauten folgendermaßen:

KAPITEL 3. KONZIPIERUNG UND ANALYSE

• Wenn beide Spieler in einer Fraktion die gleiche Karte werfen, so gewinnen die Karten der anderen Fraktion und d¨ urfen abgelegt werden, wenn sie auch nicht gleich sind, denn sonst kann kein Spieler seine Karte ablegen. Ansonsten gilt die Ablegeregel aus dem urspr¨ unglichen Pico 2.

F¨ ur die Spielerplatzbelegungen (Spieler1, Spieler2, Spieler3, Spieler4) gilt folgende ¨ Aquivalenzregel: (a, b, c, d) =(d, c, b, a). Dadurch =(c, d, a, b)

ergeben sich insgesamt f¨ unf unterscheidbare Spielerpl¨ atzebelegungen, bei denen Menschen (M) und k¨ unstliche Agenten (K) beteiligt sind: (M, M, M, K), (M, M, K, K), (M, K, M, K), (M, K, K, M) und (M, K, K, K). Von der G¨ ultigkeit

Die Programmierung eines k¨ unstlichen Agenten, der in Pico 4 gegen¨ uber Menschen gut abschneiden w¨ urde, ist nicht ohne empirische Studien m¨ oglich. Es liegen aber keine empirische Studien in diesem Bereich vor, weil dieses Spielkonzept erst in dieser Arbeit vorgeschlagen wurde. Deshalb ist die hier vorgeschlagene Vorgehensweise die Implementierung eines Netzwerkspiels f¨ ur Pico 4, das das Verhalten der Menschen in diesem Spiel protokolliert. Ferner ist außer der empirischen Studien mit bezahlten Versuchspersonen die Implementierung eines Online-Portals vorstellbar, bei dem an den Brettspielen interessierte Nutzer des Internets sich anmelden und gegeneinander spielen k¨ onnen. Diese Vorgehensweise ist kosteng¨ unstiger und w¨ urde eine vielgr¨ oßere Datenmenge liefern. Nachteilig ist dabei die geringe Glaubw¨ urdigkeit bzw. Qualit¨ at der Daten, denn die Online-Spieler k¨ onnten an etwas anderem als dem fairen Gewinnen interessiert sein.

49

3.5. ERFORDERLICHE PROGRAMMKOMPONENTE

3.5 Erforderliche Programmkomponente

Bevor man zur Beschreibung des entstandenen Programms ¨ ubergeht, werden

hier als eine Zusammenfassung dieses Kapitels die erforderlichen Programmkomponenten aufgelistet:

Benutzeroberfl¨ ache −→

Spielverwaltung mit Evaluationsm¨ oglichkeit −→

Implementation des MNM-Algorithmus −→

Netzwerkspiel −→

KAPITEL 4. PROGRAMM

Kapitel 4

Programm

4.1 Programmstruktur

F¨ ur die Implementierung wurde die Programmiersprache Java verwendet. Die Plattformunabh¨ angigkeit dieser Sprache sowie die M¨ oglichkeit des Ausf¨ uhrens im Browser, macht diese Programmiersprache f¨ ur die Durchf¨ uhrung empirischer Studien mit Internetnutzern sehr vorteilhaft. Das entstandene Programm ¹ beinhaltet die Implementierung beider Szenarien. Es ist in folgende Packetstruktur unterteilt:

Das UML-Diagramm im Anhang A zeigt die Beziehungen zwischen den Klassen im Packet picocardgamepack. Die Klasse GameAdmin wickelt die Spielverwaltung ab und ist mit der Klasse GameMainGUI wechselseitig referenziert. Die Klasse GameAdmin beinhaltet außerdem die Instanzen der Klassen mit dem gemeinsamen Interface Player. Alle Spieler werden durch Klassen realisiert, die von den Klassen PlayerComputer oder PlayerHuman abstammen, die wiederum das Inferface Player vererben. Die Z¨ uge der Player-Klassen, die von PlayerHuman abstammen, werden entweder von der lokalen GUI oder vom Netzwerk gesetzt. Die Player-Klassen aber, die vom PlayerComputer abstammen, berechnen ihre Z¨ uge selbst unter Benutzung der Klassen aus dem Packet payoff.

¹ 60 Klassen und ¨ uber 7000 Zeilen

51

4.1. PROGRAMMSTRUKTUR

Das Packet payoff (Abb. 4.1) beinhaltet Klassen, die f¨ ur die Berechnung der

Verhaltensstrategien zust¨ andig sind. Alle Klassen, die von A abstammen, stellen Matrizen der simultanen Z¨ uge dar. Die Klasse A beinhaltet außerdem viele statische Methoden, die von verschiedenen Klassen benutzt werden. Der Unterschied zwischen AInt und ADouble ist, dass die Eintr¨ age der Matrizen in diesen Klassen entsprechend int oder double sind. Das UML-Diagramm 4.2 stellt dar, welche Computerspieler welche Klassen aus dem Packet payoff

instanzieren. Das Packet load beinhaltet Klassen, die f¨ ur das Laden von Bildern und Kartensatzmengen zust¨ andig sind. Das Packet helpful beinhaltet einige hilfreiche Klassen.

Abbildung 4.2: Beziehungen zwischen payoff-Klassen und Player-Klassen

52

KAPITEL 4. PROGRAMM

4.2 Hauptbenutzerober߬ ache

Die Hauptbenutzeroberfl¨ ache (Abb. 4.3) besteht aus einem Men¨ u und einem ”Spieltisch”, der f¨ ur zwei und vier Spieler benutztbar ist.

4.2.1 Men¨ u

• Variant : Variante von Pico

- Two players : Pico 2

- Four players : Pico 4

• Game :

- New : Initialisiere ein neues Spiel.

- Next turn : Beende n¨ achsten Zug (wenn kein menschlicher Spieler vorhanden ist).

- Eval a round : Spiele eine Runde zu Ende (- // -).

- Eval 100 rounds : Spiele 100 Runden(- // -).

- Eval all sets : Spiele alle Spiele zu Kartens¨ atzen aus der ausgew¨ ahlten (- // -).

- Reset wins : Setze den Spielstand zur¨ uck und initialisiere ein neues Spiel.

53

KAPITEL 4. PROGRAMM

- Connect a server : Verbinde diese Client mit einem Server.

- Disconnect : Beende die Verbindung.

- Monitor : Zeige den Serverzustand

- Propose a thread of games : Schlage eine Spielsitzung vor.

- Take back the proposal : Nimm den Vorschlag zur¨ uck.

- Withdraw the enrollment : Melde diesen Client aus einer Spielsitzung ab.

- Start the thread : Starte die Spielsitzung.

- Retreat from the thread : Beende die Spielsitzung.

• ? :

- Game tree 1/2 : Zeige die Auszahlungsmatrix ”1 vs 2”.

- Game tree 3/4 : Zeige die Auszahlungsmatrix ”1 vs 2”.

- Output : Zeige das Ausgabefenster (Abb. 4.4).

4.2.2 ”Spieltisch”

Der ”Spieltisch” besteht aus Karten der Spieler und dem Spielstand. Jeder Spieler hat eine Reihe Handkarten und einen Stapel abgelegter Karten rechts davon. Die nicht teilnehmende Karte befindet sich in der Mitte des ”Spieltisches”. Die Spieler sind durchnummeriert mit Zahlen - 1, 2, 3, 4 - und befinden sich entsprechend ihrer Nummer: oben, unten, links, rechts. Auf dem ”Spieltisch” wird die Phase des Spiels durch die Zahlen 1 oder 2 angezeigt. Der Spielstand wird durch die Anzeige Score f¨ ur Punkte und Wins f¨ ur Anzahl

55

4.3. MNM-ALGORITHMUS

der Siege (f¨ allt bei vier Spielern weg) und gespielter Spiele (in Klammern). Die Karten werden bei lokalen menschlichen Spielern durch einen Mausklick ausgew¨ ahlt. Ausgew¨ ahlte Karten werden verschoben dargestellt.

4.3 MNM-Algorithmus

Der Computerspieler, der sich wie der im Abschnitt 3.3 beschriebene k¨ unstlicher Agent verh¨ alt, ist in der Klasse PlayerMNM fm implementiert. Die Klasse Data implementiert das Ged¨ achtnis, auf dem die Wahrscheinlichkeiten f¨ ur Verhaltensstrategien des menschlichen Spielers berechnet werden. Die genaue Implementierung des MNM-Algorithmus ist relativ trivial. Anhand der im Anhang B aufgef¨ uhrten Ausgaben des MNM-Algorithmus kann man sich seine Funktionsweise veranschaulichen. Die Ausgaben haben folgende Bedeutung:

KAPITEL 4. PROGRAMM

Player2> The card proposed by DMSM is: 13.

Player2> Your responds: 5 Player2> My respond: 10 Player2> Your responds: 12 Player2> My respond: 13 Player2> So, I prefer card 13.

Beschreibung: Berechnung der Strategie. In diesem Beispiel ist es DMBR(MBR(DMBR(MBR(DMSM)))).

• Beispiel:

Player2> So I decide to switch to 2-order.

Beschreibung: Zustands¨ ubergang.

4.4 Spielbaumtraversierung

Die Traversierung des Spielbaumes kann sehr viel Rechenaufwand in Anspruch nehmen, wenn man keine intelligente Methoden anwendet, um ihn zu begrenzen. Aus jedem Knoten k¨ onnen n1 ∗ n2 Pfade befolgt werden, wobei n1 die Anzahl der Handkarten des ersten Spieler und n2 die Anzahl der Handkarten des zweiten Spielers angeben. Aus n1 ∗ n2 Pfaden k¨ onnen aber nur h¨ ochstens n1 + n2 Pfade unterschieden werden, von denen jeder Pfad einer abgelegten Karte aus n1 + n2 Karten entspricht. Zweitens kann man den Rechenaufwand noch mehr begrenzen, wenn die wiederholten Zust¨ ande gespeichert werden.

Die Spielbaumtraversierung wird statische durch Methoden in Klasse Calc-Tree aus dem Packet payoff implementiert.

4.5 Einbindung der Java-Simplex-Implementation

Die Implementierung des Simplex-Algorithmus ist nicht trivial und gute Implementationen sind kommerziell. F¨ ur Berechnung der gemischten Gleichgewichte bei Pico reicht aber die im Netz frei verf¨ ugbare Java-Simlex-Implementation [Wisniewski und Wei, 2004]. Die Funktionsweise der L¨ osung einer Auszahlungsmatrix l¨ asst sich am besten an einem Beispielproblem beschreiben. Die Matrix

8 2

3 10

57

Abbildung 4.5: L¨ osung einer Auszahlungsmatrix [Wisniewski und Wei, 2004]

ist z. B. zu l¨ osen. Daf¨ ur muss sie entsprechend der Abbildung 3.5 in ein lineares Programm umgewandelt und in die Benutzteroberfl¨ ache der Java-Simplex-Implementation eingegeben werden (Abb. 4.5, oben). Nach einigen Iterationen wird das Problem gel¨ ost und es wird die auf Abbildung 4.5 (unten) dargestellte Ausgabe angezeigt. Daraus kann die L¨ osung f¨ ur beide Spieler entlesen werden:

mit dem Erwartungswert 5.692. Man muss aber wegen der Spezifikation der Java-Simplex-Implementation darauf achten, dass der voraussichtliche Erwartungswert der zu l¨ osenden Matrix positiv sein muss. Das erreicht man, indem von der Matrix ihr kleinster negativer Betrag substrahiert und nach der L¨ osung dem Erwartungswert hinzuaddiert wird.

58

KAPITEL 4. PROGRAMM

Die Klasse Simplex aus dem Packet payoff wandelt eine Auszahlungsmatrix in ein lineares Programm und gibt die L¨ osung in geeigneter Form aus. Dazu ist aber das Packet jcyw notwendig, das aus zwei Klassen, RevisitedSimplex und Matrix, besteht. Diese beide Klassen wurden der Java-Simplex-Implementation entnommen.

4.6 Netzwerkspielverwaltung

Das Spielen ¨ uber ein Netzwerk wird mit Hilfe eines Servers erm¨ oglicht. Der Server wird mit Hilfe der Klassen PicoServer, ServerThread und PicoTypeOn-Server implementiert. PicoServer ist dabei die Hauptklasse, die nach Angabe einer Portnummer startbar ist. PicoServer besitzt eine Liste von Instanzen der Klasse ServerThread, die paralelle Threads darstellen. Jede Instanz der der Klasse ServerThread verwaltet einen Dialog mit einem Client. Die Instanzen der Klasse PicoTypeOnServer repr¨ asentieren einzelne Spielsitzungen. Der Server ¨ ubernimmt nur die Verwaltung der Kommunikation und Zuordnung zu Spielsitzungen. Die Spielverwaltung an sich wird aber von dem Client ubernommen, der die Spielsitzung vorgeschlagen hat (Abb. 4.6 rechts). Die

¨ Clients, die die Spielverwaltung nicht ¨ ubernehmen, werden ferngesteuert.

Als Client kann ein aufgerufenes Pico-Programm auftreten. Dabei kann ein

Client in verschiedene Zust¨ ande ¨

nes Clients zeigt die Abbildung 4.6 links. Die Zust¨ ande haben folgende Bedeutung:

59

4.6. NETZWERKSPIELVERWALTUNG

Disconnected : Nicht mit dem Server verbunden.

Connected : Verbunden mit dem Server. Dabei erh¨ alt der Client einen Loginnamen.

Proposed : Client hat eine Spielsitzung auf dem Server vorgeschlagen und erwartet Anmeldungen weiterer Clients.

Enrolled : Client ist in einer vorgeschlagenen Spielsitzung angemeldet.

Can start : Client hat eine Spielsitzung auf dem Server vorgeschlagen und kann es starten, weil es gen¨ ugend andere Clients angemeldet haben.

Started : Client hat die Verwaltung einer laufende Spielsitzung ¨ ubernom-

Playing: Client nimmt an einer laufenden Spielsitzung teil.

Die Abbildung 4.7 zeigt den Netzwerkdialog, der aus dem Men¨ u ”Network” aufgerufen werden kann, wenn eine Verbindung zum Server besteht. Im rechten Bereich des Netzwerkdialogs sieht man die Liste der an den Server angeschlossenen Clients. Im linken Bereich gibt es eine Liste vorgeschlagener bzw. laufender Spielsitzungen. Der untere Bereich ist f¨ ur das Chatten ² vorgesehen. Jeder Eintrag in der Liste der Spielsitzungen enth¨ alt den Loginnamen des vorschlagenden Clients (oben), die Bezeichnung der Kartensatzmenge und die besetzbaren bzw. schon besetzten Pl¨ atze. Ein nicht besetzter Platz ist durch einen Knopf mit Aufschrift ”enroll” gekennzeichnet. Beim Dr¨ ucken eines ”Enroll”-Knopfs wird der Client f¨ ur das jeweilige Spiel angemeldet. Ein anmeldender Client kann nur in einer Spielsitzung einen Spieler bereitstellen. Ein vorschlagender Client dagegen kann keine (bei Beobachtung) oder beliebig viele (wenn Computerspieler erforderlich sind) Spieler in einer Spielsitzung bereitstellen.

Im Anhang C ist eine Liste der Befehle und Serverausgaben aufgef¨ uhrt.

² noch nicht implementiert

60

KAPITEL  4. PROGRAMM  

Abbildung  4.7: Netzwerkdialog  

61

Kapitel 5

Ausblick

Die weiterf¨ uhrende Forschung kann man in folgende Kategorien unterteilen:

KAPITEL 5. AUSBLICK

eines k¨ unstlichen Agenten, z.B. einer wahr gewordenen Aussage des Verhaltens der mit ihm interagierenden Person, sein Modell im Geist dieser Person signifikant ver¨ andern w¨ urde. Die emotionssimulierende Verhaltensweisen des humanoiden Agenten k¨ onnen auch als eine nicht verbale Ausgabem¨ oglichkeit f¨ ur das Modell des Menschen benutzt werden.

• Multimodale Konversation als Spiel:

Drittens kann man anstatt der Gesellschaftsspiele realistischere Interaktionsszenarien verwenden. Man kann z.B. eine multimodale Konversation, die in der AG ”Wissensbasierte Systeme” als ein Interaktionsszenario verwendet wurde, als ein Spiel in extensiver Form modellieren. Diese Modellierungsm¨ oglichkeit macht es m¨ oglich, ein Konversationsszenario zu erfinden, bei dem die Modellierung des anderen bzw. ToM wichtig ist.

63

Kapitel 6

Fazit

Das Ziel dieser Arbeit war menschliche Denkmuster, wie sie durch Satzfragmente wie ”... Ich (will|weiß), dass er (will|weiß), dass ich ...” ausgedr¨ uckt werden k¨ onnen, auf Computer in der Interaktion mit Menschen zu ¨ ubertragen. Dieses Ziel wurde im Abschnitt 1.1 aus einer intuitiven Vorstellung zu einem klaren Forschungsziel herausgearbeitet.

Wie im Abschnitt 1.2 angedeutet und im Abschnitt 2.1 dargestellt wurde, musste ein grosser Umfang an theoretischen und empirischen Erkenntnissen aus mehreren Disziplinen - epistemische Logik, Spieltheorie und Psychologie - analysiert werden, um dieses Forschungsziel in Angriff zu nehmen. Dabei wurden Begriffe wie ”Gemeinsames Wissen” und ”Nash-Gleichgewicht” erkl¨ art. Aus empirischen Untersuchungen mehrerer Quellen wurde deutlich, dass Menschen sich nicht wie rationale Agenten verhalten. Im Abschnitt 2.2 wurde gezeigt, dass es in KI noch kein solches Forschungsziel gestellt wurde. Dennoch wurde in Kapitel 3 und 4 ein konkretes Interaktionsszenario auf der Basis eines Gesellschaftsspieles konzipiert und implementiert werden. Und es wurde ein weitergehendes Konzept eines Spieles entwickelt, das f¨ ur den Aufbau realit¨ atsnaher Szenarien verwendet werden kann. Zus¨ atzlich sind im Kapitel 5 drei vielversprechende Weiterentwicklungsm¨ oglichkeiten aufgelistet worden.

64

ABBILDUNGSVERZEICHNIS

Abbildungsverzeichnis

1.1 Modell- und zielbasierter Agent [Russell und Norvig, 1995] . . 2 1.2 Muddy Children Puzzle [Meyer und Hoek, 1995] . . . . . . . . 3

65

ABBILDUNGSVERZEICHNIS   

4.5  L osung einer Auszahlungsmatrix Wisniewski und Wei, 2004  58

4.6  Netzwerkspielverwaltung  59

4.7  Netzwerkdialog  61

66

TABELLENVERZEICHNIS

Tabellenverzeichnis

2.1 Gefangenendilemma [Genesereth u. a., 1988] . . . . . . . . . . 12 2.2 Papier-Stein-Schere . . . . . . . . . . . . . . . . . . . . . . . . 15

67

LITERATURVERZEICHNIS

Literaturverzeichnis

A.Heuer, G. und Leopold-Wildburger, U. (1995). Silverman’s Game. Springer-Verlag, Berlin, Heidelberg, New York.

Bacharach, M. O. L. (1997). The Epistemic Structure of a Theory of a Game. Kluwer Academic Publishers.

Becker, C., Prendinger, H., Ishizuka, M., und Wachsmuth, I. (2005). Evaluating affective feedback of the 3d agent max in a competitive cards game. In [Tao u. a., 2005], pages 466-473.

Becker, C. und Wachsmuth, I. (2006). Modeling primary and secondary emotions for a believable communication agent. unpublished.

Bern, U. (2004). Multi-agent modelling in the Logics Workbench. .

Brazier, F. M. T. und Treur, J. (1999). Compositional modelling of reflective agents. Int. J. Hum.-Comput. Stud., 50(5):407-431.

Bronstein, I., Semendijajew, K., Musiol, G., und M¨ uhlig, H. (2001). Taschenbuch der Mathematik. Verlag Harri Deutsch, Thun und Frankurt am Main.

Cohen, P. R. und Levesque, H. J. (1990a). Intention is choice with commitment. Artif. Intell., 42(2-3):213-261.

Cohen, P. R. und Levesque, H. J. (1990b). Performatives in a rationally

Fagin, R., Halpern, J., Moses, Y., und Vardi, M. (1995). Reasoning about

LITERATURVERZEICHNIS

F.Camerer, C. (2003). Behavioral Game Theory. Princeton University Press, New Jersey.

Genesereth, M. R., Ginsberg, M. L., und Rosenschein, J. S. (1988). Cooperation without communication. Distributed Artificial Intelligence, pages 220-226.

Gmytrasiewicz, P. J. (1995). On reasoning about other agents. In [Wooldridge u. a., 1996], pages 143-155.

Gmytrasiewicz, P. J. und Durfee, E. H. (1992). A logic of knowledge and belief for recursive modeling: A preliminary report. In AAAI, pages 628-634.

Gmytrasiewicz, P. J. und Durfee, E. H. (1993).

Other Agents: Philosophy, Theory, and Implementation. seer.ist.psu.edu/37797.html>.

Gmytrasiewicz, P. J. und Durfee, E. H. (1995). A rigorous, operational formalization of recursive modeling. In [Lesser und Gasser, 1995], pages 125-132.

Hedden, T. und Zhang, J. (2002). What do you think I think you think?: Strategic reasoning in matrix games. Cognition, 85(1):1-36.

Herrmann, C., Pauen, M., Rieger, J., und Schicktanz, S., editors (2005). Bewusstsein: Philosophie, Neurowissenschaften, Ethik, M¨ unchen. Wilhelm Fink Verlag (UTB).

Hoek, W. v. d. und Verbrugge, R. (2002). Epistemic logic: A survey. In [Petrosjan und Mazalov, 2002], pages 53-94.

Hoek, W. v. d. und Wooldridge, M. (2003). Towards a logic of rational agency. Logic Journal of the IGPL, 11(2):135-159.

Holler, M. J. und Illing, G. (1996,2000). Einf¨ uhrung in die Spieltheorie. Springer.

Kareev, Y. (1992). Not that bad after all: Generation of random sequences. Journal of Experimental Psychology: Human Percetion and Performance, 18(4):1189-1194.

K.Berninghaus, S., Ehrhart, K.-M., und G¨ uth, W. (2004,2006). Strategische Spiele. Springer, Berlin, Heidelberg.

69

LITERATURVERZEICHNIS

Kopp, S., Gesellensetter, L., Kr¨ amer, N., und Wachsmuth, I. (2005). A con-

Kopp, S. und Wachsmuth, I. (2004). Synthesizing multimodal utterances for

Lesser, V. R. und Gasser, L., editors (1995). Proceedings of the First Inter-

Lessmann,N., Kranstedt, A., und Wachsmuth, I. (2004). Towards a cogni-

Levesque, H. J. (2000). The Logic of Knowledge Bases. The MIT Press, Cambridge, Massachusetts, London, England.

Math¨ aus, D. und Nestel, F. (1997). Doris and Frank’s game Pico/Pico2. de.html>.

Meyer, J.-J. C. und Hoek, W. v. d. (1995). Epistemic Logic for AI and Computer Science. Cambridge University Press.

Mol, L., Verbrugge, R., und Hendriks, P. (2005). Learning to reason about

Noh, S. und Gmytrasiewicz, P. J. (1999). Towards flexible multi-agent

Noh, S. und Gmytrasiewicz, P. J. (2005). Flexible multi-agent decision ma-

Ono, T. und Imai, M. (2000). Reading a robot’s mind: A model of utterance

LITERATURVERZEICHNIS

the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, pages 142-148. AAAI Press / The MIT Press.

Osborne, M. und Rubinstein, A. (1994). A Course in Game Theory. MIT Press.

Otterloo, S. v., Hoek, W. v. d., und Wooldridge, M. (2004). Preferences in game logics. In AAMAS ’04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, pages 152-159, Washington, DC, USA. IEEE Computer Society.

Owen, G. (1970). Spieltheorie. Springer-Verlag, Berlin.

Petrosjan, L. und Mazalov, V., editors (2002). Nova Science Publishers, New York.

Prechelt, L. (1994). A motivating example problem for teaching adaptive systems design. SIGCSE Bull., 26(4):25-34.

Prechelt, L. (1996). Inca: A multi-choice model of cooperation under restricted communication. BioSystems, 37(1-2):127-134.

R.Singleton, R. und F.Tyndall, W. (1974). Games and Programs. W. H. Freeman and Company, San Francisco.

Russell, S. und Norvig, P. (2003,1995). Artificial Intelligence: a modern approach. Pearson Education, Inc., Upper Saddle River, New Jersey, USA.

Stahl, D. O. und Wilson, P. W. (1994). Experimental evidence on players’ models of other players. Journal of Economic Behavior and Organisation, 25:309-327. Department of Economics, University of Texas, Austin, TX 78712, USA.

Stulp, F. und Verbrugge, R. (2002). A knowledge-based algorithm for the internet transmission control protocol (tcp) (extended version). Bulletin of Economic Research, 54(1):69-94. Blackwell Publishers Ltd, Oxford, UK and Boston, USA.

Tao, J., Tan, T., und Picard, R., editors (2005). The First International Conference on Affective Computing and Intelligent Interaction, LNCS 3784, Beijing, China. Springer.

Vidal, J. M. und Durfee, E. H. (1995). Recursive agent modeling using limited rationality. In [Lesser und Gasser, 1995], pages 376-383.

71

LITERATURVERZEICHNIS

Voorbraak, F. (1992). Generalized kripke models for epistemic logic. In

Wachsmuth, I. (2005). ”ich, Max”- Kommunikation mit k¨ unstlicher Intelli-

Wachsmuth, I. und Lessmann, N. (2002). Eine kognitiv motivierte Architek-

Weizenbaum, J. (1966). Eliza - a computer program for the study of natu-

Wisniewski, T. J. und Wei, Y. (1996, 2004). The Simplex Java Applet.

Wooldridge, M., M¨ uller, J. P., und Tambe, M., editors (1996). Intelli-

Wooldridge,M. J. (2002). Multi-agent systems : an introduction. Wiley,

ANHANG A.

Anhang A

73

Anhang B

Beispielausgaben des MNM-Algorithmus

Beispielausgabe 1.

Beschreibung: Die initiale Ausgabe in der Spielsitzung ”Random vs MNM-Algorithmus”. Das Ged¨ achtnis ist noch leer.

Player2> My strategy in initial state is DMSM.

Player2> Ready to recognize Random, MSM and (2*n+1)-order (n from N). Player2> Memory size in initial state is 9. Player2> Memory size in other states is 11. Player1> I use pseudorandom generator. Player1> So, I prefer card 10. Player2> My actual memory is not full yet: [] [] [] []

Player2> The card proposed by DMSM is: 6. Player2> So, I prefer card 6.

Beispielausgabe 2

Beschreibung: Eine der Ausgaben am Anfang der Spielsitzung ”Random vs MNM-Algorithmus”. Das Ged¨ achtnis ist noch nicht voll.

Player1> I use pseudorandom generator.

Player1> So, I prefer card 8. Player2> My actual memory is not full yet:

[0.25 [0.045 0.045 [0.045 0.864 [0.0

74

ANHANG B.

Player2> The card proposed by DMSM is: 11.

Player2> So, I prefer card 11.

Beispielausgabe 3

Beschreibung: Eine der Ausgaben im Laufe der Spielsitzung ”Random vs MNM-Algorithmus”. Das Ged¨ achtnis ist jetzt voll und es k¨ onnen Wahrscheinlichkeiten f¨ ur Verhaltensstrategien des Gegners angegeben werden.

Player1> I use pseudorandom generator.

Player1> So, I prefer card 9. Player2> My actual memory is now full:

[0.333 0.333 [0.905 0.048 [0.905 0.048 [0.0 0.0

Player2> You play with probality 99.15 % Random Player2> You play with probality 0.43 % 1-order. Player2> You play with probality 0.42 % MSM Player2> The card proposed by DMSM is: 11. Player2> So, I prefer card 11.

Beispielausgabe 4

Beschreibung: Die Ausgabe im Laufe der Spielsitzung ”Noisy 1-order vs MNM-Algorithmus” im Augenblick des Zustandswechsels des k¨ unstlichen Agenten.

Player1> I have calculated a myopic payoff matrix.

Player1> So, I prefer card 11. Player2> My actual memory is now full: [0.25 0.2 0.333 0.25 0.25 0.2 0.333 0.25 0.2 ]

[0.864 0.463 0.905 0.045 0.045 0.463 0.905 0.864 0.826 ] [0.025 0.024 0.048 0.864 0.045 0.826 0.026 0.864 0.043 ] [0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 ]

Player2> You play with probality 1.53 % Random Player2> You play with probality 98.47 % 1-order. Player2> You play with probality 0.0 % MSM Player2> So I decide to switch to 2-order. Player2> The card proposed by DMSM is: 16. Player2> Your responds: 8 11 12 Player2> My respond: 16 Player2> So, I prefer card 16.

Beispielausgabe 5

Beschreibung: Die Ausgabe im Laufe der Spielsitzung ”Noisy 1-order vs MNM-Algorithmus” direkt nach dem Zustandswechsel des k¨ unstlichen Agen-

75

ten. Nach jedem Zustandswechsel muss das Ged¨ achtnis neu aufgebaut werden.

Player1> I have calculated a myopic payoff matrix.

Player1> So, I prefer card 8. Player2> My actual memory is not full yet: [] [] [] []

Player2> The card proposed by DMSM is: 4. Player2> Your responds: 8 Player2> My respond: 9 Player2> So, I prefer card 9.

Beispielausgabe 6

Beschreibung: Eine der Ausgaben im Laufe der Spielsitzung ”Noisy 1-order vs MNM-Algorithmus” nach dem Zustandswechsel des k¨ unstlichen Agenten. Das Ged¨ achtnis ist jetzt voll und es k¨ onnen Wahrscheinlichkeiten f¨ ur Verhaltensstrategien des Gegners angegeben werden.

Player1> I have calculated a myopic payoff matrix.

Player1> So, I prefer card 16. Player2> My actual memory is now full: [0.2 0.2 0.25 0.25 0.2 0.2 0.25 0.2 0.2 0.333 0.333 ]

[0.017 0.024 0.045 0.025 0.463 0.017 0.025 0.024 0.024 0.026 0.026 ] [0.826 0.826 0.864 0.864 0.826 0.043 0.864 0.826 0.826 0.026 0.026 ] [0.826 0.826 0.864 0.864 0.024 0.463 0.864 0.826 0.826 0.905 0.905 ] Player2> You play with probality 0.0 % Random Player2> You play with probality 0.0 % 3-order. Player2> You play with probality 0.25 % MSM Player2> You play with probality 99.74 % 1-order Player2> The card proposed by DMSM is: 12. Player2> Your responds: 16 Player2> My respond: 9 Player2> So, I prefer card 9.

Beispielausgabe 7

Beschreibung: Die Ausgabe im Laufe der Spielsitzung ”Random vs MNM-Algorithmus” nach der Spielsitzung ”Noisy 1-order vs MNM-Algorithmus” im Augenblick des Zustandswechsels des k¨ unstlichen Agenten.

Player1> I use pseudorandom generator.

Player1> So, I prefer card 16. Player2> My actual memory is now full:

76

ANHANG B.

[0.333 0.25 0.2 0.2 0.333 0.25 0.2 0.2 0.2 0.2 0.2 ]

[0.487 0.045 0.043 0.043 0.905 0.475 0.322 0.017 0.043 0.013 0.013 ] [0.048 0.045 0.043 0.043 0.048 0.045 0.043 0.043 0.826 0.826 0.826 ] [0.048 0.025 0.024 0.463 0.048 0.045 0.043 0.043 0.826 0.826 0.826 ] Player2> You play with probality 99.95 % Random. Player2> You play with probality 0.0 % 3-order. Player2> You play with probality 0.01 % MSM. Player2> You play with probality 0.03 % 1-order. Player2> So I decide to switch to 0-order. Player2> The card proposed by DMSM is: 5. Player2> So, I prefer card 5.

Beispielausgabe 8

Beschreibung: Die Ausgabe im Laufe der Spielsitzung ”Noisy 3-order vs MNM-Algorithmus” nach der Spielsitzung ”Noisy 1-order vs MNM-Algorithmus” im Augenblick des Zustandswechsels des k¨ unstlichen Agenten.

Player1> I have calculated a myopic payoff matrix.

Player1> So, I prefer card 12. Player2> My actual memory is now full: [0.2 0.5 0.333 0.25 0.2 0.2 0.5 0.333 0.25 0.25 0.2 ]

[0.463 0.95 0.905 0.864 0.463 0.024 0.95 0.905 0.475 0.025 0.463 ] [0.463 0.95 0.048 0.864 0.043 0.043 0.05 0.905 0.045 0.864 0.463 ] [0.043 0.05 0.048 0.045 0.043 0.043 0.05 0.048 0.045 0.864 0.024 ] Player2> You play with probality 3.63 % Random. Player2> You play with probality 96.22 % 3-order. Player2> You play with probality 0.15 % MSM. Player2> You play with probality 0.0 % 1-order. Player2> So I decide to switch to 4-order. Player2> The card proposed by DMSM is: 13. Player2> Your responds: 5 Player2> My respond: 10 Player2> Your responds: 12 Player2> My respond: 13 Player2> So, I prefer card 13.

77

Anhang C

Syntax der Netzwerkbefehle in EBNF

< L >::= < B >::= < P >::= < PT >::= < Ph >::= < D >::= < DN >::= < Cd >::= < I >::= < 5xI >::= < C >::= < S >::= < Str >::= < lCd0 >::= < lCd1

>::= . . .

< llCd0 >::= .1. < lCd0 > . < llCd1 >::= .2. < lCd1 > .

. . .

< llCdn >::=

< llCdnHS >::= < llCdn >< L >< llCdn > < llCdn2 >::=

< llCdn24 >::= < llCdn2 > | < llCdn2 >< L >< llCdn2 > < llB2 >::=

< llB4 >::= < llS2 >::= < llS4 >::= < g >::= < gc >::=

78

ANHANG C.

Befehlsliste ’Von Client zu Server’:

ANHANG C.

Ausgabeliste ’Von Server zu Client’:

Danksagung

An dieser Stelle will ich Allen danken, die mir geholfen haben.

Erstmal will ich allen Betreurern daf¨ ur danken, dass sie mich

immer wieder mein Vorhaben gelobt haben. Das war sehr moti-

vierend! Christian danke ich, dass er soviel Zeit f¨ ur mich finden

konnte und durch seine Anmerkungen die Qualit¨ at meiner Ar-

beit erheblich verbessert hat. Dann will ich Nadine daf¨ ur danken,

daß sie mit ihrem fr¨ uheren Vorschlag voll ist Schwarze getroffen

hat. Ipke und Gerhard sei gedankt, dass sie mir soviele fachspe-

zifische Tips gegeben haben.

Ich finde es ganz toll, dass Dorothea sich bereit erkl¨ art hat, mei-

ne Arbeit Korrektur zu lesen. Aber am meisten danke ich meinen

Eltern - ohne die Unterst¨ utzung zu Hause w¨ are ich nie soweit

gekommen.