Gegenseitiges geschachteltes Modellieren in der Interaktion mit einem künstlichen Agenten

INHALTSVERZEICHNIS

1 Einleitung
1.1 Entwurfsbeschreibung
1.2 Beteiligte Disziplinen, Begriffsklärung
1.3 Überblick

2 Stand der Forschung
2.1 Theorien und empirische Ergebnisse
2.1.1 Epistemische Logik
2.1.2 Spieltheorie
2.1.3 Psychologie und Verhaltensspieltheorie
2.1.4 Zusammenfassung
2.2 Künstliche Intelligenz
2.2.1 Allgemeine Diskussion
2.2.2 Spezielle Beispiele
2.2.3 Zusammenfassung

3 Konzipierung und Analyse
3.1 Wahl des einfachen Interaktionsszenarios
3.2 Spielstruktur und Berechnung des Nash-Gleichgewichtes .
3.3 Detektion der Verhaltensstrategien und MNM-Algorithmus
3.4 Wahl des zweiten Interaktionsszenarios
3.5 Erforderliche Programmkomponente

4 Programm
4.1 Programmstruktur
4.2 Hauptbenutzeroberfläche
4.2.1 Menü
4.2.2 ”Spieltisch”
4.3 MNM-Algorithmus
4.4 Spielbaumtraversierung
4.5 Einbindung der Java-Simplex-Implementation
4.6 Netzwerkspielverwaltung

5 Ausblick

6 Fazit

Abbildungsverzeichnis

Tabellenverzeichnis

Literaturverzeichnis

A

B

C

Kapitel 1 Einleitung

1.1 Entwurfsbeschreibung

In dieser Arbeit geht es darum, gegenseitiges Modellieren als ein menschli- ches Denkmuster maschinell ausführbar zu machen. Dieses Ziel gehört in das Forschungsfeld der Künstlichen Intelligenz, denn in dieser Disziplin wird die Intelligenz durch Nachbauen erforscht. Das Modellieren bezieht sich dabei allein auf das Abbilden der mentalen Vorgänge im Geist des anderen Indi- viduums, wie das folgende konstruierte, an die Krimi-Literatur erinnernde Beispiel zeigt:

. . N. wusste, dass er gestern von B. in der Stadt A. gesehen wurde, und B. fragte N. heute danach, was N. gestern gemacht hatte. Daraus schloss N., dass B. nicht wusste, dass

N. wusste, dass er gestern von B. in der Stadt

A. gesehen wurde. N. erzählte B., dass er in der Stadt D. war, was B. akzeptierte, weil er nicht wollte, dass N. erfahren würde, dass B. wusste, dass N. gestern in der Stadt A. war.

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

1.1. ENTWURFSBESCHREIBUNG

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

Abbildung in dieser Leseprobe nicht enthalten

N. und B. darstellen kann. Dabei können die mentalen Zustände der an- deren Agenten als ein Teil des Welt- bzw. Umgebungsmodells verstanden werden. Da zwei oder mehrere agentenmodellierende Agenten miteinander interagieren können, haben die Modelle unter Umständen einen geschachtel- ten Aufbau, so dass auch ”das eigene Modell im Geist des Anderen”-Modell bzw. verschachteltere Modelle repräsentiert werden können. Auch wenn die Agenten orthogonale Ziele verfolgen und miteinander nicht direkt interagie- ren, können sie allein durch Beobachtung der anderen zum Wissensgewinn gelangen, wie das folgende in der Literatur oft erwähnte Beispiel zeigt.

Muddy Children Puzzle [nach Fagin u. a., 1995]: Es gibt n Kinder (Abb. 1.2), die alle intelligent, ehrlich, hörend, sehend und aufmerksam sind. Dass sie die- se Eigenschaften haben, gehört 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 Wahr- scheinlichkeit 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 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 über Induktion beweisen lässt.

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

Abbildung in dieser Leseprobe nicht enthalten

Im Falle k = 1 sieht das Kind mit schmutzigem Gesicht, dass alle ande- ren 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 se- hen. Die sauberen Kinder sehen zwei schmutzige Kinder, die stehen geblieben sind, weil sie einander sehen können. Also treten bei der zweiten Aufforde- rung alle schmutzigen Kinder vor, und die sauberen Kinder bleiben stehen. Man kann für k = 3 genauso schlussfolgern, dass die Aufforderung dreimal wiederholt werden muss. Die Wiederholung der Aufforderung bringt die Kin- der 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ö- sung dieses Puzzles mit Hilfe eines Logikinterpreters [Bern, 2004] noch keine ausreichenden theoretischen Konzepte in sich, die auf die meisten Situatio- nen angewendet werden könnten. Man erkennt, dass bei einer beliebig ho- hen Schachtelungstiefe eine derartige Schlussfolgerung weder von Menschen noch von Maschinen umsetzbar ist, weil deren Kapazitäten begrenzt sind [Fagin u. a., 1995]. Was aber in dieser Arbeit beabsichtigt wird, ist das Mo- dellieren 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ät ausreichen würde, stellt sich dennoch die Frage nach der Rentabiltät. In Situationen wie bei kompitetiven Gesellschaftsspielen für zwei Spieler bringt das Modellieren des anderen Spielers bzw. Agenten keine Verbesserung mit sich, weil nach der Analyse dieser Spiele, die jeder Spieler für sich macht, für beide Spieler eine optimale Strategie angegeben werden kann [Holler und Illing, 2000, S. 62], von der keiner der Spieler, wäre er am Gewinnen interessiert, abweichen würde. Speziell bei Papier-Stein-Schere, wo die Vorhersage des gegnerischen Verhaltens sich anscheinend lohnt, ist es für jeden Spieler optimal, zufällig zwischen den Handgesten zu wählen, denn zufälliges Wählen erlaubt keine nutzbare Vorhersage über seine nächste Handgeste.

Das Interaktionszenario, bei dem agentenmodellierende künstliche Agenten demonstriert werden können, muss also diese Aspekte berücksichtigen. Das gegenseitige Modellieren erfordert gleichzeitig mehrere Individuen. Die ver- mutlich einzig bekannten intelligenten Wesen, die diese Art von Denkmus- tern entwickeln, sind wir Menschen. Das wirft die Frage auf, ob man beim Nachbauen allein künstliche Agenten interagieren lässt, oder Menschen mit einbezieht. Dazu gibt es in der KI zwei Ansichten bzw. Thesen darüber, 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ünscht ist. Setzt man den Schwerpunkt auf die Simulation des menschlichen Denkens und Verhaltens, so sind Menschen als evaluieren- de Interaktionspartner für 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ären, ob sich die ideale Intelligenz auch in der realen Welt, d. h. in der Interaktion mit ”nicht idea- len” echten Menschen, bewährt. Die Einbeziehung echter Menschen, worauf in dieser Arbeit der Schwerpunkt gesetzt wird, kann also aus der Sicht der beiden Thesen eine Wissenslücke fühlen. Fraglich ist aber, ob das gegenseitige Modellieren von Mensch und Maschine wegen verschiedener Funktionsweisen und Fähigkeiten in jeder Situation vorstellbar ist. Die Hauptaufgabe dieser Arbeit besteht daher im intelligenten Auswählen 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 simulta- nen Zügen, bei dem die optimale Strategie aufwändig berechnet werden muss.

Sie ist deshalb für Menschen schwer anwendbar. Die Spielregeln für das Spiel stammen aus dem kommerziellen Gesellschaftsspiel Pico 2 [Mathäus und Nestel, 1997]. Der Computergegner spielt dabei eine relativ gut abschneidende de- 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 übersteigt.

Das zweite Szenario verwendet ein vom Verfasser dieser Arbeit vorgeschlage- nes übertragbares Konzept für ein Spiel mit vier Spielern, das keine optimale Lösung garantiert und Anreiz für das gegenseitige Modellieren schafft. Die vier Spieler sind dabei in zwei Fraktionen à zwei Spieler unterteilt. Spieler in einer Fraktion können nur gemeinsam einen identischen Betrag gewinnen oder verlieren; jede Fraktion gewinnt nur so viel, wie die andere Fraktion verliert. Alle vier Spieler können nicht miteinander kommunizieren. Dabei haben die Spieler jeder Fraktion einen Anreiz dazu, miteinander zu kooperie- ren 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 übertragen werden. Das dadurch entstandene Pico 2 mit vier Spielern wurde als ein Netzwerkspiel implementiert und ist für empirische Studien verwend- bar.

1.2 Beteiligte Disziplinen, Begriffsklärung

Mit dem Thema, das in dieser Arbeit als gegenseitiges geschachteltes Model- lieren³ bezeichnet wird, beschäftigen sich Forscher aus Psychologie, Logik, Spieltheorie, Linguistik und Künstliche Intelligenz. In Bezug auf MNM wer- den verschiedene Fachbegriffe verwendet, die u. a. untereinander Korrespon- denzen aufweisen.

Für 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ünsche 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ö- herer Ordnung mit MNM.

In der mathematischen Logik und auch Philosophie bezeichnet man als epistemische Logik⁴ [Wooldridge, 2002] das Schlussfolgern über das Wissen, das zwischen mehreren Agenten verteilt ist. Es bedarf erweiterter Formalismen, um nicht nur Wissen sondern auch Wünsche und Intentionen in dieser Logik darstellen zu können [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ät. Ein rationaler Agent macht immer das, was ihn seines Wissens nach dem Erreichen seiner Ziele näher bringt [Russell und Norvig, 1995, s. 4] bzw. ihm den bestmöglichen Gewinn bringt. Situationen, in de- nen mehrere Agenten interagieren und deren Zielerreichung von den Hand- lungen anderer Agenten abhängt, werden als strategische Spiele bezeichnet [Holler und Illing, 2000]. Die Spieltheorie ist die Disziplin, die sich mit Ana- lyse der strategischen Spiele beschäftigt und zum Ziel hat, für jedes Spiel herauszufinden, wie sich rationale Spieler verhalten würden 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ür diese Arbeit sind em- pirische Arbeiten [z.B. Kareev, 1992; Hedden und Zhang, 2002; Stahl und Wilson, 1994], die das menschliche Verhalten in verschiedenen Spielen untersuchen. 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ür 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- schung, obwohl es auch andere Richtungen [Gmytrasiewicz und Durfee, 1992; Brazier und Treur, 1999] gibt, die auch eigene Begriffe wie rekursiv oder re- flektiv verwenden.

Bei der Begriffsfestlegung wird in dieser Arbeit die Tatsache berücksichtigt, dass ein künstlicher Agent die mentalen Vorgänge des Menschen nur annä- hernd 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.

1.3 Überblick

Kurzbeschreibung der folgenden Kapitel und Abschnitte:

- Kapitel 2 : Stand der Forschung.

- Abschnitt 2.1: Hier werden die relevantesten Arbeiten aus ver- schiedenen Disziplinen außer der Künstlichen Intelligenz darge- stellt und zusammengefasst. Die Darstellung der theoretischen Grundlagen in diesem Abschnitt ist aber sehr knapp, um nicht die Rahmen der Diplomarbeit zu sprengen.

- Abschnitt 2.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äftigt sich unter Verwendung der Erkenntnisse aus der interdisziplinär angelegten Recherche mit der Konzipierung des Programms

- Abschnitte 3.1, 3.2 und 3.3: Diese Abschnitte beschäftigen 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.

Kapitel 2 Stand der Forschung

2.1 Theorien und empirische Ergebnisse

2.1.1 Epistemische Logik

Die epistemische Logik ist eine Logik über 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öglich, 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ür möglich hält. 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ür die Agenten vorstellbaren Welten darstellt, und w ist die Welt, in der sich die Agenten tatsächlich befinden sollen. Jede Kante des Graphen gehört einem bestimmten Agenten und drückt aus, dass dieser Agent in jeder der beiden mit ihr verbundenen Welten die andere Welt für möglich hält. Am Beispiel des Muddy Children Puzzle aus der Einleitung kann man sich bei drei Kindern eine Kripke-Struktur (Tabelle 2.2) aus acht Welten vorstellen. Jede dieser Welten wird durch ein Tripple (p1, p2, p3) bezeichnet, wo pi = 1 gilt, wenn Kind i schmutzig ist und sonst 0.

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Kripke-Struktur von muddy children puzzle [Hoek und Verbrugge, 2002]

Mit Hilfe der epistemischen Logik lässt sich das Konzept des gemeinsamen Wissens CG formalisieren, dass sich vom Allgemeinwissen EG 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ünsche 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ätzen werden für jeden Agenten mehrere Modaloperatoren eingeführt. Bei dem bestverstandenen und weitverbreitetsten Ansatz BDI³ von Rao und Georgeff bedarf es pro Agent genau drei Operatoren: ”Bel” (überzeugt sein), ”Intend”(Absicht haben) und ”Des”(sich wünschen). Der BDI-Ansatz basiert auf den Arbeiten des Philosophen Michael Bratman und wurde erfolgreich implementiert. Die bekannteste Implementation der BDI- Logik ist PRS⁴.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Gemeinsames Wissen [Fagin u. a., 1995]

2.1.2 Spieltheorie

Die Spieltheorie ist, wie schon in der Einleitung erwähnt, eine Theorie über rationales Verhalten bei Interaktion mehrerer Subjekte. Sie wurde erst 1944 von John von Neumann und Oskar Morgenstern durch die Veröffentlichung des Buches ”The Theory of Games and Economic Behavior” [K.Berninghaus u. a., 2006] eingeführt. Seitdem steigt die Zahl der Disziplinen, in denen die Spiel- theorie Anwendungen gefunden hat: Wirtschaftswissenschaften, Soziologie, Psychologie, Künstliche Intelligenz und Biologie. Es wird zwischen koope- rativer 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önnen. In dieser Arbeit wird ausschließlich die nicht kooperative Spieltheorie betrachtet, wo- bei ”nicht kooperativ” nicht bedeutet, dass keine Kooperation zwischen den Spielern stattfindet.

Ein Spiel in der Spieltheorie ist der Aufbau einer strategischen Situation, dar- gestellt in Normalform oder in extensiver Form, wobei jedes Spiel in erstere Form überführt werden kann. Ein Spiel in Normalform mit z.B. zwei Spie- lern ist eine Bimatrix (sehe Tab. 2.1), wo jedes Element eine Auszahlung für jeden Spieler enthält. Nach der Konvention sind die Zeilen der Bimatrix den Handlungsalternativen, die später als Strategien bezeichnet werden, des ers- ten Spielers und die Spalten den Handlungsalternativen des zweiten Spielers zugeordnet. Die beiden Spieler wählen ihre Strategien s¹ i⁵ und s² j simultan und unabhängig voneinander aus und erhalten die Auszahlungen u1(s¹ i,sj)6 und u2(s¹ i,s2j).EineStrategiedominierteineandereStrategie,wennsiefür alle Strategien anderer Spieler eine höhere Auszahlung bringt. Ein rationaler Spieler würde nie eine dominierte Strategie spielen. Dadurch kann man die Ausgangsmatrix verkleinern, indem man die dominierten Spalten und Zei- len 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 gemisch- te Strategie verwenden. Diese stellt die eine Wahrscheinlichkeitsverteilung über die Strategien dar, nach der der Spieler mit Hilfe eines Zufallsgenera- tors eine der Strategien auswählt. Ein Standardlösungskonzept für Spiele ist das Nash-Gleichgewicht⁷. Das Nash-Gleichgewicht ist ein Tuple aus puren bzw. gemischten Strategien aller Spieler, wobei das einseitige Abweichen ei- nes Spielers von seiner Strategie für ihn keine Erhöhung seiner Auszahlung Spielernumme mit sich bringt. Nash-Gleichgewichte existieren für alle Spiele Γ(N, S, u), die folgende Bedingungen erfüllen:

1) der Strategieraum Si ⊂ ℜm ist kompakta und konvexb für alle Spieler i ∈ N;

2) für alle i ∈ N gilt: ui ist stetig und begrenzt in s ∈ S und quasi-konkav in si. [Holler und Illing, 2000, S. 62]

aabgeschlossen und begrenzt balle Mischungen aus Strategien sind erlaubt

Daraus lässt sich ableiten, dass es speziell in endlichen Spielen immer ein Nash-Gleichgewicht gibt, wenn nicht in puren, dann in gemischten Strategien. In dem hier erwähnten GD-Spiel (Tab. 2.1) ist (s¹²,s² ) das einzige NashGleichgewicht, obwohl es für beide Spieler besser gewesen wäre, (s¹¹,s¹ ) zu wählen. 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ünstlichen 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ügen darstellt, und enthält eine Auszahlung für jeden Spieler. Mit der Annahme des gemeinsamen Wissens der Rationalität aller Spieler CG(Rational(1) ∧ . . . ∧ Rational(n)) kann man mit Hilfe der Rückwärtsinduktion für jeden Spieler eine Verhaltensstrategie bestimmen, nach der er in jedem Knoten eine bestimmte Aktion wählt. Das Centipede-Spiel [Osborne und Rubinstein, 1994]⁸ ist ein gutes Beispiel (Abb. 2.4) für dieses Vorgehen. Der dort dargestellte Spielbaum ist von links nach rechts zu lesen. In jedem Knoten hat ein Spieler die Wahl zwischen zwei

Tabelle 2.1: Gefangenendilemma [Genesereth u. a., 1988]

Abbildung in dieser Leseprobe nicht enthalten

Zügen, ”r” und ”d” oder ”R” und ”D”. Die Knoten des Spielbaumes sind mit römischen Zahlen beschriftet, die die Nummern der Spieler darstellen, die sich in diesen Knoten entscheiden. Die Blätter sind mit Auszahlungen für beide Spieler versehen. Beginnend mit dem letzten Knoten werden die Auszahlungsvorhersagen (rote Schrift) sukzessive unter Annahme der Ratio- nalität des jeweiligen Spielers getroffen. Im vorvorletzten Knoten z.B. ent- scheidet sich Spieler II für ”D”, weil er weiß, dass der Spieler I rational ist ( IIRational(I) folgt aus CG(Rational(I)∧ Rational(II))), und sich deswegen für ”d” entscheiden wird, was aber eine kleinere Auszahlung für Spieler II bedeutet.

Abbildung in dieser Leseprobe nicht enthalten

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

Wenn die Züge eines der Spieler unsichtbar für den anderen sind, z.B. bei si- multanen Entscheidungen, spricht man von Spielen bei imperfekter Informa- tion [Osborne und Rubinstein, 1994]. Die Unsichtbarkeit früherer Züge führt dazu, dass man sich gleichzeitig in mehreren Knoten zu befinden glaubt. Diese Menge von Knoten wird in der Spieltheorie als Informationsmenge be- zeichnet. Dann gibt es noch die Spiele bei unvollständiger Information, d. h. Unkenntnis der Auszahlungsfunktion bzw. Strategiemenge des anderen Spie- lers. Spiele bei unvollständiger Information können aber in Spiele bei imper- fekter Information überführt werden, indem man am Anfang des Spiels einen verdeckten Zug der Natur⁹ einbaut, der den Typ des Spiels bzw. des Spielers festlegt. Die Lösung eines solchen Spieles liegt darin, den mutmaßlichen Typ des Spieles Ti gegeben die Spielbeobachtung D mit Hilfe des Bayes-theorems neu zu berechnen [F.Camerer, [2003]].

Abbildung in dieser Leseprobe nicht enthalten

Das schon erwähnte Muddy Children Puzzle lässt sich auch als ein Spiel in extensiver Form bei imperfekter Information darstellen [F.Camerer, [2003], S. ²³⁶ -²³⁹ ]. Dazu bedarf es einer Auszahlungsmatrix, die die Ehrlichkeit der

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

Die Spieltheorie gibt also nur vor, wie sich ein rationaler Spieler verhalten Kind\ schmutzig(1) sauber(0) stehen (rechter Zweig) 0 0 vortreten (linker Zweig) 1 − schwarz - Natur, grün - erstes Kind, blau - zweites Kind

Abbildung 2.5: ”Schmutzige Gesichter”

Abbildung in dieser Leseprobe nicht enthalten

soll, d. h. nach welchen Kriterien er eine Strategie auswählen soll. Das Aus- wählen einer Strategie ist aber mit einer aufwändigen Berechnung verbunden. In Spielen bei perfekter Information bedarf es dafür einfacher Spielbaum- durchsuchung, während in Spielen bei imperfekter Information, wo das Nash- Gleichgewicht unter Umständen in gemischten Strategien liegt, bedarf es der

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.2: Papier-Stein-Schere

Lösung von Ungleichungssystemen. Für Zwei-Personen-Nullsummenspiele oh- ne Nash-Gleichgewicht in puren Strategien, wie z.B. Papier-Stein-Schere (Tab. 2.2) sieht für den Zeilenspieler das zu lösende Problem so aus [entsprechend R.Singleton und F.Tyndall, 1974, S. 95]: argmaxp1,...,pm (min(∑i ai1 pi, . . . , ∑i ain pi)) ∑i pi = 1,∀i : pi ≥ 0 pi - Wahrscheinlichkeit für Aktionen des Zeilenspielers aij- Auszahlungen Es lässt sich als lineares Programm formulieren und mit Hilfe des SimplexAlgorithmus lösen [siehe dazu Owen, 1970].

Für die Berechnung optimaler Strategien in einem Spiel bedarf es grundsätzlich ausreichender Rechenkapazitäten, die bei größeren Spielen für alle bekannten Spieler einfach nicht verfügbar sind. Denn

”...bereits beim Schachspiel reichen die Fä- higkeiten selbst des besten Spieltheoretikers nicht aus, auch nur angeben zu können, ob der Spieler mit den weißen oder mit den schwarzen Figuren bei rationalem Verhalten gewinnen wird...”[K.Berninghaus u. a., 2006, S. 162]

Als Abhilfe wird in der künstlichen Intelligenz Approximation benutzt. Anstatt den ganzen Baum zu erforschen, wird [Russell und Norvig, 1995, S. 171f] ab einer bestimmten Tiefe die Güte eines Knotens geschätzt. Diese Schätzung weicht aber von der tatsächlichen Güte ab. Es macht dann auch für jeden Spieler Sinn, die gegnerische Schätzungsheuristik zu modellieren und deren Makel auszunutzen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: ToM von einem Roboter [Ono und Imai, 2000]

2.1.3 Psychologie und Verhaltensspieltheorie

In der Psychologie hat sich, wie schon im Abschnitt 1.2 erwähnt, der Begriff ToM als Bezeichnung für 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ünstlichen Wesen wie z.B. Roboter aufbauen können, wurde in Be- zug 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ät 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ählt, 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ülleimer fuhr und stehen blieb. Weitere zehn Menschen, die Ver- suchsgruppe, bekamen die Aussage direkt vom Roboter vorgespielt. In der Versuchsgruppe haben acht Personen die Aussage verstanden und entspre- chend 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önnen und dass wiederum diese Antizipation überhaupt möglich ist.

Die Interaktionen zwischen Menschen, bei denen ToM gebraucht wird, ent- wickeln sich oft nicht entsprechend den Vorhersagen aus der Spieltheorie. Ein Centipede-Spiel ist z.B. trivial mit Rückwärtsinduktion zu lösen, wenn man von dem gemeinsamen Wissen der Rationalität der beiden Spieler ausgeht.

Ein Experiment mit einem 3-Stufen-Centipede-Spiel (Abb. 2.7) [Hedden und Zhang, 2002] zeigt, dass die Menschen von dieser Annahme generell nicht ausgehen.

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

Abbildung in dieser Leseprobe nicht enthalten

Dieses Spiel besteht aus vier Zellen. Die Spieler dürfen nacheinander begin- nend mit dem ersten Spieler in der Ausgangszelle bleiben oder in die nächste Zelle ziehen. Ein Spiel ist beendet, wenn einer der Spieler bleibt oder die vier- te Zelle erreicht wird. Bei dem ersten Teil des Experiments haben 35 weibliche plus 35 männliche 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 menschli- che Spieler spielen würden. Die Variablen Ai, Bi,Ci, Di sind Auszahlungen für Spieler i, einander ungleich und können mit natürlichen Zahlen von 1 bis 4 belegt werden. Es ergeben sich dadurch 144 verschiedene Möglichkeiten der Variablenbelegung bzw. Auszahlungsstrukturen. Bei dem ersten Zug des ers- ten Spielers ist für den ersten Spieler wichtig zu wissen, ob der zweite Spieler ziehen wird. Für den zweiten Spieler ist es wiederum wichtig zu wissen, ob der erste Spieler beim letzten Zug ziehen wird. Deshalb muss der erste Spieler für 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ässt sich die Vorgehensvorschrift angeben (Abb. 2.8), die abhängig 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 CII < BII 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 Aus- zahlungsstrukturen, bei denen der zweite Spieler, abgesehen davon, welche der beiden Strategien er benutzt, die gleiche Aktion ausführt. Diese Auszah- lungstrukturen werden für das Training der menschlichen Versuchspersonen eingesetzt, um sie mit dem Spiel vertraut zu machen. Danach mussten die

Abbildung 2.8: Zweite Ordnung [Hedden und Zhang, 2002]

Abbildung 2.9: Erste Ordnung [Hedden und Zhang, 2002]

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ückschlüsse darauf gemacht, gegen welche Strategie (myopic oder predictive =”ToM 1-order”) sie glaubten ge- spielt zu haben. Die 16 Partien wurden in 4 Sets zusammengefasst, über die ein Mittelwert berechnet wurde. Der Computer spielte eine feste kurzsich- tige oder vorausschauende Strategie. Der Graph 2.10 zeigt, dass einerseits die Menschen vorerst die Strategie des Computers mehrheitlich für myopic gehalten haben, aber dann mit jeder weiteren Partie langsam immer mehr zur korrekten Einschätzung des Gegners kamen. Ein weiterer Aspekt, der in diesem Experiment sichtbar geworden ist, zeigt, dass Menschen unabhängig von der Strategie des Gegners Fehler machten und eigene Vorhersage nicht optimal in eine Aktion umsetzten. Diese so genannten Rationalitätfehler la- gen im Durchschnitt bei 10,5%.

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

Abbildung 2.10: ToM-Drift [Hedden und Zhang, 2002]

Abbildung in dieser Leseprobe nicht enthalten

schen sich auf der Basis von Modellen anderer Menschen entscheiden, anstatt das Nash-Gleichgewicht zu wählen, das leicht zu bestimmen wäre. Bei einer Version dieses Spiels müssen mehrere teilnehmende Spieler simultan Zahlen zwischen 0 und 100 aufsagen. Es gewinnt derjenige Spieler einen festen Be- trag, dessen Zahl am nächsten zu 70% des Durchschnittes liegt. Gewinnen gleichzeitig mehrere Spieler, dann teilen sie sich den Gewinn. Wenn dann ein gemeinsames Wissen der Rationalität aller Spieler vorliegt, sollten al- le die 0 aufsagen. Stattdessen bekommt man beim wiederholten Spielen die auf Abbildung 2.11 dargestellte Graphik. Die Erklärung für 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ähr bei der gleichen Voraussage landen. Und diese Überlegung 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ür rationale Spieler vorhersagt. Un- tersuchungen in verschiedenen Spielen haben ergeben, dass Menschen beim Spielen eine Reihe von unterschiedlich begründeten Abweichungen demons- trieren. Colin F.Camerer, der Erfinder des Begriffs Verhaltensspieltheorie, drückt die Schlussfolgerung daraus folgendermaßen aus:

Abbildung 2.11: Beauty-Contest-Spiel [F.Camerer, 2003]

Abbildung in dieser Leseprobe nicht enthalten

”...If the data confirm game theory, you might say, the subjects must have under- stood; if the data disconfirm, the subjects must have not understood. Resist this con- clusion. The games are usualy simple, and most experimenters carefully control for un- derstanding Furthermore, by inferring subject understanding from data, there is no way to falsify the theory ” [F.Camerer, 2003, s. 22]

Eine weitere Abweichung menschlicher Spieler von idealen Spielern ist die Verwendung von gemischten Strategien, denn die Menschen können die ge- mischten Strategien in grösseren Spielen nicht exakt bestimmen. Den Untersuchungen [F.Camerer, 2003, S. 121ff] zufolge verfehlen die Men- schen die optimalen Wahrscheinlichkeiten bei übersichtlichen Spielen um ei- nige Prozentpunkte (Abb. 2.12 links). Bei sehr kleinen Wahrscheinlichkeiten ergeben sich dabei große prozentuale Abweichungen. Ausser der Einschätzung der Wahrscheinlichkeiten muss noch eine Zufallsfolge produziert werden, mit Hilfe derrer die Strategien beim wiederholten Spielen für andere Spieler un- vorhersagbar ausgewählt werden müssen. Die Produktion von Zufallsfolgen

Abbildung 2.12: Verwendung gemischter Strategien [F.Camerer, 2003; Kareev, 1992]

Abbildung in dieser Leseprobe nicht enthalten

ist aber nicht trivial. Die Experimente von [Kareev, 1992] zeigen, dass bei den von Menschen produzierten Zufallsfolgen die Wiederholungen seltener vor- kommen, als es bei einem echten Zufallsgenerator zu erwarten wäre. 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 vorstel- len, 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.

2.1.4 Zusammenfassung

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

1. Menschen können der Maschine durchaus Wünsche zuschreiben. Es ist aber nicht geklärt, wie sich ToM einer Maschine von ToM eines Menschen unterscheidet.

2. In Situationen, in denen das geschachtelte Modellieren intuitiv von Nut- zen ist, wie Muddy Children Puzzle, lässt sich das Wissen der anderen Agenten mit Hilfe epistemischer Logik herleiten, vorausgesetzt es gibt ein gemeinsames Wissen über die ”Intelligenz” aller beteiligten Agen- ten. Man kann aber den etwas schwer definierbaren Begriff der ”In- telligenz” durch eine Kombination aus Rationalität und ausreichender Verarbeitungskapazität ersetzen, wenn man diese Situation als ein Spiel in extensiver Form betrachtet.

3. Menschen machen mit einer bestimmten Wahrscheinlichkeit Rationa- litätsfehler. Interagiert ein Mensch mit anderen Subjekten, so kann er bzw. sie Annahmen in der Art wiei(¬Rational( j)) oderli(¬Rational( j)) oder generellkG(¬Rational(i))bilden.DasgemeinsameWissenderRa- tionalität kann also in der Interaktion mit Menschen nicht garantiert werden.

KAPITEL 2. STAND DER FORSCHUNG

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

2.2 Künstliche Intelligenz

2.2.1 Allgemeine Diskussion

Abbildung 2.13 (links) stellt graphisch dar, welche Art von Programmen nötig wären, um den Stand der bisherigen KI-Forschung in Bezug auf das Thema dieser Arbeit darzustellen. Auf diesem Bild sind ein Mensch und ein künstlicher Agent dargestellt, von denen jeder ein Modell (Denkblase) des anderen bildet und es dabei zum Aufbau geschachtelter Modelle kommt. Der tatsächliche Aufbau der Maschine kann dabei sehr primitiv sein - auch wenn man die Maschine als einen endlichen Automaten betrachten würde, könnte sie dann, um geschachtelt modellieren zu können, jedes vorstellbare geschachtelte Modell des menschlichen Gegenübers als einen Zustand in ih- rem Zustandsübergangsgraphen repräsentieren. Gleichzeitig muss aber auch der Mensch ein geschachteltes Modell der Maschine bilden können, weshalb die Maschine über eine Interaktionsmöglichkeit mit einem Menschen verfü- gen muss. Nach bisheriger Recherche konnte ein solches Setup nicht gefunden werden. Daher werden in diesem Kapitel nur prinzipiell ähnliche Arbeiten be- trachtet.

Eine Ähnlichkeit könnte man den unzähligen natursprachlichen Dialogsyste- men wie z.B. ELIZA unterstellen [Weizenbaum, 1966], denn sie alle täuschen eine Kommunikation mit einem Menschen vor (sogenannter Eliza-Effekt) und:

2.2. K ÜNSTLICHE INTELLIGENZ

”In der Kommunikation zwischen Menschen schreiben wir uns gegenseitig ein solches In- nenleben zu (intentionale Zustände). Wir ge- hen davon aus, dass der andere so wie wir Ab- sichten, Überzeugungen, Wünsche und Ziele hat ... ”[Wachsmuth, 2005].

Diese Vortäuschung verleitet den mit einem solchen System interagieren- den Menschen dazu, sich vorzustellen oder sich so zu verhalten, als würde er sich vorstellen, dass das System dem Gesprächspartner ein ”Innenleben” zuschreibt oder dass er glaubt, dass man ihm ein ”Innenleben” zuschreibt usw.. Nur leider funktionieren solche Systeme ohne innere Repräsentation geschachtelter Modelle. Dass ein Mensch ein geschachteltes Modell des Sys- tems 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örperte konversatio- nelle Agent¹² Max (Abbildung 2.13 ganz rechts, im blauen Overall) wur- de und wird im Laufe der Zeit mit vielen Features fortwährend aufgerüs- tet [z.B. Becker und Wachsmuth, 2006; Kopp und Wachsmuth, 2004], die eine Kommunikation ähnlich der zwischenmenschlichen¹³ mit ihm ermög- licht [Kopp u. a., 2005]. Max verfügt über eine reaktive und eine delibera- tive Komponente. Die reaktive Komponente legt die sofortigen Reaktionen fest, während die deliberative Komponente langfristiges Planen ermöglicht, für die bei Max die BDI-Architektur verwendet [Wachsmuth und Lessmann, 2002] wird. Max verfügt über eine Planbibliothek hierarchisch aufgebau- ter Pläne, die für die Auswahl der Intention (Intention) entsprechend des aktuellen Wissens (Beliefs) und Wünschens (Desires) verwendet wird. ”In- tentionale Zustände seines Dialogpartners repräsentiert 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übergangs- graph, dessen jeder Zustand einen Kompromiss zwischen Wünschen von Max und der mit ihm interagierenden Person bezüglich der Sprecherrolle darstellt. Ein anderes Beispiel sind die Passwortknacker, die strukturierte Buchstaben- folgen als erstes ausprobieren, weil die Menschen dazu neigen, sich struk-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ör- ter zu erfinden.

Standardrichtung ist aber, die epistemische Logik als ein Modell für gegensei- tiges Modellieren mit ihren vielen Unterarten einzusetzen. Es gibt eine ganze Reihe von Logikinterpretern (LWB, Molog usw.), die zu Muddy Children Puzzle ähnliche logische Puzzles lösen können [Bern, 2004]. Die Lösung liegt darin, das Puzzle in logischen Formeln zu modellieren und den Wissensstand der Agenten nach jeder Iteration zu beweisen. Um solche Puzzles auf In- teraktion zwischen Menschen und Computer zu übertragen, bedarf es einer Modellierung der mentalen Auffassungsfähigkeit sowie der begrenzten Ver- arbeitungskapazität des Menschen. Die Modellierung der resourcebegrenzten Logik ist relativ schwierig und zur Zeit Gegenstand der Forschung. Mit men- taler Auffassungsfähigkeit sieht es noch schwieriger aus, denn Experimente zeigten, dass selbst ein Zwei-Personen-Puzzle nicht von der Mehrheit der Ver- suchspersonen gelöst werden konnte [F.Camerer, 2003, S. 236-239].

2.2. K ÜNSTLICHE INTELLIGENZ

2.2.2 Spezielle Beispiele

Rekursive Modellierungsmethode

Abbildung 2.14: RMM [Gmytrasiewicz und Durfee, 1992]

Abbildung in dieser Leseprobe nicht enthalten

In [Gmytrasiewicz, 1995] findet sich eine auf Interaktion zwischen Men- schen und Maschinen übertragbare Formalisierung der Spiele bei unvollstän- diger Information. Die dort vorgestellte RMM¹⁴ setzt begrenzte Resourcen voraus und besteht darin, dass ein Agent in einer Interaktion mit anderen Agenten einen Baum erstellt, der das Wissen über andere Agenten beinhaltet (Abb. 2.14, links). Ein Knoten in diesem Baum ist eine Sicht eines Agenten auf die aktuelle Situation und Kanten sind dem Ausdruck ”hält mit Wahr- scheinlichkeit p für möglich, dass” äquivalent. Die Knoten und die Kanten in diesem Baum korrespondieren mit Welten und Relationen der Kripke- Struktur. Der Unterschied dabei ist, dass es hier eine Wahrscheinlichkeitsver- teilung über die Möglichkeiten sowie eine Pfadlängenbegrenzung 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än- gig von den Aktionen der beiden Spieler dar. Der nächst 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 Blatt- knoten zu lösen. Die dort ermittelten optimalen Aktionen werden - gewichtet mit der Kantenwichtung - in den nächst höheren Knoten propagiert. Sind bei einem Knoten von allen seinen ausgehenden Kanten die optimalen Aktionen zurückpropagiert worden, so wird auch dieser Knoten gelöst und die optimalen Aktionen werden zurückpropagiert.

RMM hat u. a. in einem Algorithmus zur Lösung von Persuit Task Anwen- dung gefunden [Vidal und Durfee, 1995]. Persuit Task ist eine kooperative Aufgabe, bei der mehrere ”Raubtiere” ein sich zufällig bewegendes ”Beutetier” möglichst schnell umkreisen müssen und dabei nicht kommunizieren können. Der auf RMM basierte Algorithmus LR-RMM¹⁵ benutzt einen RMM-Baum und vergrößert ihn nur so lange, wie der Auszahlungszuwachs minus Rechen- kosten größ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ögliches Modell eines reflexiven Agenten vorgestellt, der über eigenes Wissen, den eigenen Schlussfolgerungs- prozess und den Schlussfolgerungsprozess anderer Agenten schlussfolgern kann. Das Modell besteht aus mehreren Komponenten, die verschiedene Aufgaben erledigen und miteinander kommunizieren können. Dieses Modell wurde für die Verbalisierung des Schlussfolgerungsprozesses beim Lösen 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:

”This puzzle is about two wise men, A and B, each of which is wearing a hat. Each hat is either black or white but at least one of the hats is white. Each wise man can only ob- serve the colour of the other wise man’s hat. Both wise men are able to reason logically and they know this from each other.”

Das implementierte Modell verbalisiert die Lösung des Puzzles aus der Sicht des weisen Mannes B gegeben die Aussage des weisen Mannes A darüber, ob er (Mann A) die Farbe seines Hutes schon kennt. Dabei werden Kompo- nenten 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ür die Arbeit zu entneh- men. Denn wenn ein System geschachtelte Modelle verbalisieren kann, dann muss es diese Modelle auch repräsentieren können. Ferner kann man sich vor- stellen, den Vergleich zwischen der sprachlichen Ausgabe des Systems und der Meinung der mit dem System interagierenden Person als Bewertungsgrund- lage zu benutzen.

2.2.3 Zusammenfassung

Wie die Recherche zeigte, wurde das in dieser Arbeit vorgeschlagene The- ma 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ünstlicher Agent anhand des beobachteten Verhalten des Menschen dyna- misch ein geschachteltes Modell des Gegenübers aufbaut. Als eine Erklärung dafür kann man erwähnen, dass dieses Vorhaben wegen der umfangreichen Theorie (sehe Abschnitt 2.1) relativ viel Einarbeitungszeit erfordert. Das Ziel dieser Arbeit ist genau diese Forschungslücke in der KI zu schliessen.

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 ge- schachtelt modellieren. Zu einer solchen Situation kann man sich im Grunde ein äquivalentes Spiel ausdenken und dann die optimale Strategie bestimmen. Trotzdem wird das Auswählen einer Strategie in einer solchen alltäglichen Situation bei Menschen oft ohne die Verwendung irgendwelcher mathemati- scher Konzepte z. B. aus der Spieltheorie gemacht. Auch die Spieltheoretiker können nicht jede reale Situation auf ein Spiel mit bekannter Lösungsstra- tegie zurückführen, denn sonst wäre die Spieltheorie eine Wissenschaft ohne jegliches Potential. Es wäre in zukünftigen Arbeiten interessant, herauszufin- den, ob das alltägliche, verhaltensbestimmende Denken eines Menschen im- mer mathematisch formalisierbar ist. Wenn aber ToM eines Menschen nicht immer mathematisch formalisierbar ist, dann könnte ein künstlicher Agent einen Menschen nie exakt modellieren, denn ein künstlicher Agent kann nur mathematisch formalisierbare Modelle aufbauen. Aber wenn ein Mensch ei- ne Vorstellung von den Vorgängen im Kopf des anderen hat, dann ist diese Vorstellung wahrscheinlich strukturiert, und wenn das so ist, dann ist ge- schachteltes Modellieren in der Interaktion zwischen Menschen und künst- lichen Agenten möglich. Wenn man also ein Interaktionsszenario auswählen will, bei dem ein künstlicher 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ürde sich ein Mensch wahrscheinlich anders vorstellen, als sie tatsächlich ist. Das würde die Modellierung dieses

Menschen komplizierter oder vielleicht sogar unmöglich machen. Das heißt, als MNM-Interaktionsszenario würde nur eine relativ leicht verständliche 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ählen. Denn so ist es sichergestellt, dass das Spiel menschlichen Spielern genügend Unterhaltung bietet. Der Unterhaltungsfaktor ist wichtig, damit sich die menschlichen Spieler mit der Struktur des Spiels intensiv beschäftigen. Als einfachstes MNMInteraktionsszenario kann man sich ein wiederholtes Spiel mit zwei Spielern, einem Menschen und einem künstlichen Agenten, vorstellen. Die Auswahlkriterien kann man folgendermaßen zusammenfassen:

1. Es muss einen Anreiz für das Modellieren des anderen geben.
2. Es darf keine Zufallszüge geben, denn man müsste dann die Risikoaffi- nität bzw. -aversion des Menschen berücksichtigen, was das Interakti- onsszenario unnötig verkomplizieren würde [Russell und Norvig, 1995, S. 592].
3. Es darf nicht zu kompliziert, wie Schach, und nicht zu einfach, wie Papier-Stein-Schere, sein. Das ist wichtig um Frustration und Langweile auszuschliessen.

Die Zwei-Personen-Gesellschaftsspiele teilen sich hauptsächlich in zwei Grup- pen: das gemeinsame Puzzle-Lösen und die Nullsummenspiele. Alle Zwei- Personen-Nullsummenspiele, unter Annahme des gemeinsamen Wissens über die Rationalität der beiden Spieler, haben ein Nash-Gleichgewicht und daher keinen Anreiz für das Modellieren des anderen. Beim gemeinsamen Puzzle- Lösen lässt sich das Nash-Gleichgewicht auch berechnen, obwohl die beiden Spieler es nicht sofort berechnen können 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 Men- schen nicht optimal. Dadurch kann man sich zwei Möglichkeiten vorstellen, bei denen die beiden Spieler ihr Verhalten in Abhängigkeit vom Verhalten des anderen ändern:

- Der künstliche Agent modelliert den Menschen und versucht seine Makel auszunutzen, worauf Mensch als Antwort sein Verhalten ändert. Das geänderte Verhalten würde aber neue Makel aufweisen, die von dem künstlichen Agenten ausgenutzt werden könnten.
- Der künstliche Agent weicht vom Nash-Gleichgewicht ab und wartet darauf, bis der Mensch es merkt und ausnutzt. Danach nutzt der künstliche Agent das geänderte menschliche Verhalten aus und wartet darauf, bis der Mensch es merkt und ausnutzt, usw..

Das erste Szenario scheidet aus, weil erstens das intuitive menschliche Spie- len schwer modellierbar ist und zweitens werden hier keine tief geschachtelten Modelle aufgebaut. Beim zweiten Szenario aber agiert der künstliche Agent nicht rational. Es bedarf einer Auszahlungsstruktur, die das Verhalten des künstlichen 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ünstliche Agent am Aufbau tief geschachtelter Modelle interessiert ist. Der künstliche Agent erfährt nicht während des Spielens, welche Strategie der Mensch tatsächlich spielt, sondern er muss sie anhand der Beobachtungen feststellen und kann daher seine Auszahlungen nur abschätzen. Die Auszah- lungen des menschlichen Spielers dagegen stellen die Bilanz zwischen Siegen und Niederlagen dar, die allen Spielern sichtbar ist. Wie man auf der Ma- trix 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öchste Auszahlung bekommt, wenn er den Gegner richtig modelliert und die niedrigste Auszahlung, wenn der Geg- ner ihn richtig modelliert. Als Beispiel nehmen wir an, dass der künstliche 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ächlich ein Modell der 1-Ordnung vom künstlichen Agenten, dann liegt der künstliche 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ügen. Ein sehr guter Kandidat für so ein Spiel, ist Pico 2 für zwei Spieler (Abb. 3.1). Die Regeln für dieses Spiel sind relativ einfach:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.1: Fiktives Spiel

”Basic Pico 2 is a game for two players.

... There are 11 cards with numbers 4,5,6,7,8,9,10,11,12,13,16 . Cards are shuffled and dealed, every player gets 5. One ex- tra card is out of the game, but known, it is shown face up between the two players hands. You secretly choose one of your cards ..., the [oponent] chooses one of his. Both cards are revealed, the higher card wins , unless it’s to high: The higher card looses, if it’s more than twice as high as the lower card. The winning card scores and is kept face up, the loosing card goes back to it’s players hand. Play continues until one player has only one card left. Then another round is played with reversed hands. The player with the most red dots after two rounds wins ” [Mathäus und Nestel, 1997]

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

Abbildung 3.1: Pico 2

Abbildung in dieser Leseprobe nicht enthalten

”... cause Pico (and Pico 2) is essentially based on bluff and the ability to anticipate the others action, this doesn’t quite be the thing against a computer :-) ...”[Mathäus und Nestel, 1997]

Außerdem hat Pico 2 eine wissenschaftliche Vorgeschichte. Pico 2 wurde von einem in 1993-94 in Newsgroups angekündigten Programmierwettbewerb in- spiriert, bei dem eine Version des GD-Spiels, das INCA² Modell, möglichst optimal gelöst werde musste [Prechelt, 1994, 1996]. Die Regeln von INCA äh- neln aber stark den Regeln des Silverman-Spiels³, die von David Silverman in der Mitte der 70-er Jahre entwickelt wurden [A.Heuer und Leopold-Wildburger, 1995]. Pico 2 kann man auch als ein äußerst reduziertes Silverman-Spiel be- zeichnen.

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öhe- re Punktzahl erreicht. Die Runde besteht aus zwei Phasen⁵. Die beiden Pha- sen unterscheiden sich dadurch, dass die Spieler ihre Kartensätze vertauschen. Die Punkte werden in zwei Phasen gesammelt und dann summiert. Folglich ist das Ziel jedes Spielers x in jeder Phase die Differenz zwischen gegneri- schen (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ünf Karten. Da es insgesamt 11 Karten gibt, gibt es 2772 Möglichkei- ten, die Karten auf die Spieler zu verteilen. Diese Zahl berechnet sich aus dem Produkt der Zahl der Möglichkeiten, 5 Karten für den ersten Spieler aus den ursprünglichen 11 auszuwählen und der Zahl der Möglichkeiten, 5 Karten für [Abbildung in dieser Leseprobe nicht enthalten] den zweiten Spieler aus den restlichen 6 auszuwählen ( ∗ [Abbildung in dieser Leseprobe nicht enthalten] )⁶, wobei die

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

Die Karten werden simultan gezogen. Die Ablegeregel lässt 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ässt sich als ein Spielbaum mit imperfekter Information darstellen. Dieser Spielbaum

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.2: Kartenwichtung

Abbildung 3.2: Ablegeregel

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Kurzsichtige Auszahlungsmatrix

Abbildung in dieser Leseprobe nicht enthalten

ist gemeinsames Wissen der Spieler, weil die restliche Karte und die abgeleg- ten Karten offengelegt werden und dadurch jeder Spieler weiß, welche Karten der Gegner auf der Hand hält. Dadurch kann man vor jedem Zug eine Ma- trix kurzsichtiger Auszahlungen für 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 sofor- tigen 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 vorausschauen- de Auszahlungsmatrix. Der Erwartungswert eines Pfades selbst berechnet sich aus dem Erwartungswert der vorausschauenden Matrix des ersten Kno- tens, 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ärt 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 Unent- schieden zu erreichen, weil die beiden Phasen einander ausgleichen. Die Be- rechnung des Nash-Gleichgewicht besteht darin, in jeder vorausschauenden

Abbildung 3.4: Spielbaum einer Phase

Abbildung in dieser Leseprobe nicht enthalten

Matrix ein Nash-Gleichgewicht entweder in puren oder in gemischten Stra- tegien zu suchen. Das Suchen des Nash-Gleichgewichts in puren Strategien ist trivial. Man vergleicht einfach den maximalsten der minimalsten Einträ- ge jeder Zeile mit dem minimalsten der maximalsten Einträge 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ürlich haben die meisten Matrizen kein Nash-Gleichgewicht in puren Stra- tegien. Eine Evaluation aller Kartensätze, 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öglichen Kartensät- zen das Spielen optimaler Strategie ohne Verwendung gemischter Strategien möglich ist. Beim Kartensatz 〈4 · 5 · 6 · 7 · 8〉〈9 · 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ätze, die Spiele erzeugen, bei denen die Differenz zwischen Minimax und Maximin besonders groß ist. Solche Spiele ähneln vom Spiel- prinzip 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 zu minimieren, werden aus der ursprünglichen Matrix iteriert schwachdomi- nierte Spalten und Zeilen so lange entfernt, bis es keine mehr gibt. Die auf diese Weise verkleinerte Auszahlungsmatrix A (A des ersten Spielers ist −At des zweiten Spielers) wird danach in Form eines linearen Programms (Abb. 3.5) aufgeschrieben (µ-Erwartungswert, xi-Wahrscheinlichkeiten des ersten Spielers). Der Simplex-Algorithmus liefert wegen der Dualität⁷ [Owen, 1970, S. 41f] immer gleichzeitig die optimalen Wahrscheinlichkeiten für beide Spie- ler.

Die Verwendung gemischter Strategien auf Einphasenbäumen birgt aber in sich ein Problem in Bezug auf die spezielle Siegerbestimmung dieses Spiels. Die gemischte Strategie maximiert den Erwartungswert der Punktzahldiffe- renz, aber die Siegbedingung ist, dass diese Zahl einfach positiv ist. So kann z.B. ein niedrigerer immer noch positiver Erwartungswert mit kleinerer Streu- ung besser sein, als ein höherer Erwartungswert mit höherer Streuung. Exakte

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5: Lineares Programm zur Auszahlungsmatrix A

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.4: Beispiel zum Spielanfang

Lösung erhält man nur durch die Lösung eines aus beiden Phasen zusammen- gesetzten Spielbaumes, bei dem die Punkte vorwärts und die Siegwahrschein- lichkeiten rückwärts propagiert werden, was erheblich mehr Rechenaufwand als die Lösung eines Ein-Phasen-Baumes braucht. Dieser Algorithmus arbei- tet auch wie die Lösung einer Phase auf einem Baum mit Matrizen als Knoten für jeden simultanen Zug, aber die Einträge dieser Matrizen variieren zwi- schen −1 und 1 und geben die Siegwahrscheinlichkeit an. Die Einträge dieser Matrizen sind gleich den Erwartungswerten der entsprechenden Teilbäume. Der Wert eines Blattes ist eine Zahl aus der Menge {−1, 0, 1} und ist entspre- chend der dort erreichten Punktzahldifferenz gesetzt. Die Tabelle 3.4 stellt beispielsweise dar, mit welchen Wahrscheinlichkeiten für jede Karte zwei ra- tionale Spieler das Spiel zum Kartensatz 〈4 · 5 · 6 · 7 · 11〉〈8 · 10 · 12 · 13 · 16〉 anfangen sollen.

3.3 Detektion der Verhaltensstrategien und MNM-Algorithmus

Alle möglichen Verhaltensstrategien, die man in diesem Spiel verwenden könnte, 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 sofor- tige Auszahlung wahr, während die vorausschauenden den ganzen Spielbaum traversieren und die Erwartungswerte zum Wurzelknoten zurückpropagieren. 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ätzen im Schnitt nur um ≈ 16, 5%¹⁰, während das zufällige Spielen um ≈ 67% schlechter ist. Daraus kann man folgern, dass sogar das vollständige Vorausschauen in diesem Spiel nur wenig Vorteile bringt. Zu dieser Erkenntnis würden wahrscheinlich auch menschliche Pico-Spieler kommen und sich nur wenig auf das Vorausschauen wenig konzentrieren. Die Summenmaximierung, als eine gängige Verhaltens- strategie 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 irratio- nalen zufälligen Spieler verstanden. Diese Strategie hat aber einen entschei- denden Fehler - sie kann durchschaut und ausgenutzt werden. Tatsächlich erzielt die kurzsichtige Bestantwortstrategie (MBR¹¹ ) auf MSM bei Pico na- hezu hundertprozentige Gewinnwahrscheinlichkeit gegen MSM. Bestantwort- strategie auf Summenmaximierung wurde von 49% der Versuchspersonen an- gewendet und nur 27% nutzten Nash-Strategie.

Zusammengefasst eignet sich MSM gut dafür, einer deterministischen Ver- haltensstrategie zu Grunde gelegt zu werden, die der künstliche Agent im fiktiven Spiel (Abb. 3.1) spielen sollte. Die daraus entwickelte Verhaltens- strategie DMSM¹² lässt sich als folgender verbaler Algorithmus beschreiben:

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

1. Benenne die von DMSM ausgewählte Spalte in der kurzsichtigen Aus- zahlungsmatrix A als v.
2. Nimm alle Zeilen, die die beste Antwort auf v darstellen, und füge sie zur Strategiemenge F zusammen.
3. Spiele irgendeine Karte aus F.

Verhaltensstrategien höher grader Ordnung DMBR(MBR(·))¹⁴, die vom künst- lichen Agenten verwendet werden, müssen auch deterministisch sein, um ei- gene Durchschaubarkeit zu garantieren. Sie lassen sich folgendermaßen defi- nieren:

1. Nimm alle Spalten, die von MBR in der kurzsichtigen Auszahlungsma- trix A gespielt werden können und füge sie zur reduzierten Matrix R zusammen.
2. Benutze DMSM auf R. +Und die Verhaltensstrategien höher ungerader Ordnung MBR(DMBR(·)) sind entsprechend der 1-Ordnung-Strategie definiert.

Aus der Auszahlungmatrix des fiktiven Spiels (Abb. 3.1) lässt sich ein Zu- standsübergangsgraph (Abb. 3.6) für den künstlichen Agenten ableiten. Im initialen Zustand werden nur die Wahrscheinlichkeiten für drei Verhaltens- strategien des Gegners errechnet, die zusammen 100% ergeben: die zufällige, die MSM und die 1-Ordnung-Strategie. Jede nicht formalisierbare Verhaltens- strategie des Menschen im fiktiven Spiel wird als eine Linearkombination aus MSM und der zufälligen modelliert. Man kann sich auch vorstellen, dass der menschliche Spieler sich auf Grund besonderer Begabung entsprechend der exakten Nash-Strategie verhält und dadurch eine theoretisch höhere Auszah- lung erhalten kann, als ein DMSM-nutzender künstlicher Agent. Praktisch aber macht jeder Mensch mit einer bestimmten Wahrscheinlichkeit Fehler. Dadurch würde ein Mensch kaum eine höhere Gewinnwahrscheinlichkeit er- reichen. Außerdem ist die 1-Ordnung-Strategie viel profitabler und einfacher zu bestimmen.

Aus dem initialen Zustand geht der künstliche Agent in den nächsten, d. h. zweiten Zustand über, wenn die Wahrscheinlichkeit für die 1-Ordnung- Strategie P(1 − Ordnung) den Pegel p0 übersteigt. Im zweiten Zustand wird die 2-Ordnung-Strategie verwendet. Generell geht der künstliche Agent aus dem Zustand n bei P((1 + 2 ∗ n) − Ordnung) > p0 in den Zustand n + 1 über, für alle n von 0 bis unendlich. Da die Benutzung der Verhaltensstategien hö- her Ordnung für menschliche Spieler mit höherem Aufwand verbunden ist, werden sie irgendwann wieder eine intuitive Verhaltensstrategie verwenden. Daher muss der künstliche Agent vom Zustand n, n > 0, in den Zustand 0 übergehen, wenn die Summe der beiden, in diesem Zustand zu erwartenden Verhaltensstrategien unter den Pegel p1 rutscht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6: Zustandsübergangsgraph im fiktiven Spiel

Abbildung 3.7: Rekursives Modell des künstlichen Agenten im fiktiven Spiel

Abbildung in dieser Leseprobe nicht enthalten

Der künstliche Agent lässt sich auch mit Hilfe der RMM beschreiben (Abb. 3.7). Der Wurzelknoten des hier dargestellten rekursiven Modells, sowie je- der ungefühlte schwarzer Kreis, stellt DMBR-Strategie dar, wobei DMSM = DMBR(ZK) = DMBR(Nash) = DMBR(MSM) und MSM = MBR(ZK) gelten. Die ungefühlten roten Kreise symbolisieren dagegen die MBR-Strategie; der einzige gefühlte Knoten symbolisiert die Nash-Strategie. In jedem Zustand des Zustandsübergangsgraphen entspricht der künstliche Agent einem be- grenzten Ausschnitt aus dem allgemeinen rekursiven Modell.

Die Wahrscheinlichkeiten für einzelne zu erkennende Verhaltensstrategien werden nach dem Bayes-Theorem berechnet, bei der deren a-priori-Wahr- scheinlichkeiten gleich sind und die sich daher wegkürzen lassen: im Beispiel j von der Strategie a produziert zu sein.

Abbildung in dieser Leseprobe nicht enthalten

Jedes Verhaltensbeispiel ist eine kurzsichtige Auszahlungsmatrix, bei der der künstliche Agent die Beobachtung macht, dass der menschliche Spieler aus l möglichen Karten die Karte ci auswählt. Würde ein menschlicher Spieler z.B. zufällig entscheiden, dann wäre die Wahrscheinlichkeit für jede einzelne Karte¹ l. Entscheidet der menschliche Spieler aber nicht zufällig, sondern nach einer bestimmten Verhaltensstrategie, so gibt es m Karten, die er spielen würde, und n = l − m Karten, die er meiden würde. Hinzu kommt noch, dass der Mensch mit einer bestimmten Wahrscheinlichkeit Fehler macht, d. h. manchmal falsche Karten auswählt. Um die Fehlerwahrscheinlichkeiten für alle m und n Werte zu berechnen, wird hier QRE¹⁵ [F.Camerer, 2003, S. 33] verwendet:

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Nun setzt man für Auszahlung 0, wenn man einen Fehler macht, und 1, wenn die richtige Karte gespielt wird und erhählt die Wahrscheinlichkeit eines falschen Zuges:

Abbildung in dieser Leseprobe nicht enthalten

Nehmen wir jetzt an, der menschliche Spieler macht bei zwei auszuwählenden Aktionen mit 5%¹⁶ einen Fehler. Das würde ergeben:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.5: Wahrscheinlichkeiten für einen der richtigen Züge

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.6: Wahrscheinlichkeiten für einen der falschen Züge Durch Auflösung nach eλ erhält man:

Mit Hilfe dieses Wertes kann man die entgültigen Formeln für die Warscheinlichkeit der Auswahl eines Zuges angeben, gegeben die Menge der richtigen Züge R(Stra) in Anhängigkeit von der Strategie Stra:

(3.2)

Abbildung in dieser Leseprobe nicht enthalten

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ählt 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:

(3.3)

Abbildung in dieser Leseprobe nicht enthalten

si ist die imVerhaltensbeispiel j gewählte Karte

Das Hauptziel des künstlichen Agenten im fiktiven Spiel ist die Erkennung dessen, ob er vom menschlichen Spieler durchschaut wird. Dafür eignen sich aber nicht alle kurzsichtigen Matrizen; sie werden deswegen nicht in die Be- obachtungsliste aufgenommen. Hier sind die Ausschlusskriterien mit Begrün- dungen:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.7: Verteilung auswertbarer Fälle

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

2. Dominante Spalten : Das Wählen oder nicht Wählen dieser Spalten zeigt nur die allgemeine Rationalität und nicht die Antizipation der gegnerischen Handlung.

3. Kombination der Zeile und Spalte ist ein Nash-Gleichgewicht : Das Wählen dieser Spalte kann nicht nur als die Antizipation der gegneri- schen Handlung, sondern auch als gegnerische Antipazipation der eige- nen Handlung interpritiert werden.

Eine Evaluation¹⁷ hat ergeben, dass pro Runde im Schnitt ≈ 6.3 auswertbare Fälle vorkommen. Die Tabelle 3.7 gibt eine Verteilung dieser Fälle nach l und m an. Die Variable g, die die Gedächtnisgrösse festlegt, darf nicht zu groß sein, denn dann wäre der künstliche Agent wegen der Gleichgewichtung der Beobachtungen zu träge; und nicht zu klein, denn dann wäre er anfällig für Fehleinschätzungen. Nach Evaluation mit computersimulierten menschlichen Gegnern hat sich der Wert 9 für den initialen Zustand und der Wert 11 für andere Zustände als sinnvoll erwiesen. Genauso, mit Hilfe deiser Evaluation, sind auch die Werte für p0 und p1 auf 0, 96 und 0, 0005 gesetzt worden. Diese Werte könnten natürlich auch analytisch bestimmt werden, was aber relativ aufwändig.

Dem hier beschriebenen Aufbau des künstlichen Agenten im fiktiven Spiel (kann auch als MNM-Algorithmus bezeichnet werden) wird keine Optimalität unterstellt. Künftige Arbeiten werden eventuell basierend auf empirischen Studien einen besseren Aufbau vorschlagen.

3.4 Wahl des zweiten Interaktionsszenarios

Das erste Interaktionsszenario bedurfte eines fiktiven Spiels, um den Aufbau geschachtelter Modelle für den künstlichen Agenten zu rationalisieren. Deswegen sollte ein in diesem Abschnitt beschriebenes Spielkonzept eingeführt werden, das den Entwurf von Spielstrukturen möglich 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ür Kooperation (links) und Konkurrenz (rechts) ste- hen, bei denen das Nash-Gleichgewicht in gemischten Strategien liegt. In der Kooperationsituation müssen sich die beiden Spieler möglichst vorhersagbar und in der Konkurrenzssituation möglichst 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übers zu modellieren. Ist aber Konvention eingeführt, müssen 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 interes- siert, seinem Partner gegenüber vorhersagbar und seinem Gegner gegenüber unvorhersagbar zu verhalten. Voraussetzung dafür ist, dass der Partner und der Gegner sich voneinander in ihren Fähigkeiten irgendwie unterscheiden, sonst wäre das Verhalten des Spielers entweder den beiden gegenüber vorher- sagbar oder den beiden gegenüber unvorhersagbar. Um in solcher Situation ein optimales Verhalten zu wählen, 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äre mindestens einer der Spieler seines Partners Gegner. Die vier Spieler (1,2,3,4) sind in zwei Partnerpaa- re¹⁸ bzw. Fraktionen, I (1,3) und II (2,4), unterteilt (siehe Abb. 3.8). Spieler in einer Fraktion können 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 Auszah- lung 0. In sonstigen Fällen gewinnt jede Fraktion die Summe der Gewinne der beiden Spieler aus den jeweiligen Gegnerpaaren. Zusätzliche Bedingung ist, dass kein Spieler mit einem anderen kommunizieren darf. Sonst könnte jeder Spieler die mentalen Eigenschaften seines Partners verändern, indem er ihm seine Verhaltensstrategie mitteilt. Das Spiel wird wiederholt gespielt und es besteht das gemeinsame Wissen der Ungleichheit der Fähigkeiten aller Spieler. Die Abbildung 3.9 zeigt beispielsweise die Übertragung dieses Kon- zeptes auf Matching-Pennies und Papier-Stein-Schere. Wenn alle Spieler zwar unterschiedliche aber nicht begrenzte Fähigkeiten haben, dann haben solche Spiele kein garantiertes Nash-Gleichgewicht. Bei Matching-Pennies kann eine denkbare Strategie des Spielers sein, eine für den Gegner zufällig aussehende und für den Partner deterministische Bitfolge zu produzieren, denn das würde ihn besser stellen als rein zufälliges Spielen. Da die Fähigkeiten eines Spielers unbegrenzt sind, hat jeder Spieler eine unendliche Teilmenge aller möglichen Bitfolgenproduktionsregeln zur Verfügung. Hat man aber eine unendliche 18 Ähnlichwie bei den Spielen bridge und Doppelkopf

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.9: Übertragung auf Matching-Pennies und Papier-Stein-Schere

Strategiemenge zur Verfügung, so kann nach dem allgemeinen Existenzsatz kein Nash-Gleichgewicht garantiert werden (siehe Abschnitt 2.1.2). Um dieses Spielkonzept zum Aufbau eines Interaktionsszenarios zu verwen- den, bei dem Menschen mit Maschinen interagieren können, kann ein Gesell- schaftsspiel wie z.B. Pico 2 genommen werden, auf das es sich übertragen lässt. Die Annahme, dass die Spieler ein gemeinsames Wissen ihrer geistiger Verschiedenheit haben, würde unter Menschen ohne weiteres gelten. Durch Übertragung dieses Spielkonzeptes auf Pico 2 entsteht ein neues Ge- sellschaftsspiel, das als Pico 4 getauft werden kann. Die Regeln für Pico 4 lauten folgendermaßen:

- Es spielen insgesamt 4 Spieler in zwei Fraktionen à 2 Spieler.
- Die Spieler in einer Fraktion bekommen identische Kartensätze und nach Ablauf einer Phase, tauschen sie sie mit der anderen Fraktion aus.
- Das Spielziel besteht in der Maximierung der Punktzahl der eigenen Fraktion, die sich aus Summe der Punktzahl beider Spieler zusammen- setzt.
- Eine Phase wird beendet, wenn einer der vier Spieler nur noch eine Karte auf der Hand hat.
- Wenn beide Spieler in einer Fraktion die gleiche Karte werfen, so ge- winnen die Karten der anderen Fraktion und dürfen abgelegt werden, wenn sie auch nicht gleich sind, denn sonst kann kein Spieler seine Kar- te ablegen. Ansonsten gilt die Ablegeregel aus dem ursprünglichen Pico 2.

Für die Spielerplatzbelegungen (Spieler1, Spieler2, Spieler3, Spieler4) gilt fol- gende Äquivalenzregel: (a, b, c, d) =(b, a, d, c) =(c, d, a, b) =(d, c, b, a). Dadurch ergeben sich insgesamt fünf unterscheidbare Spielerplätzebelegungen, bei de- nen Menschen (M) und künstliche 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ültigkeit dieser Äquivalenz kann man sich leicht überzeugen, wenn man die Abbildung 3.8 dreht bzw. spiegelt.

Die Programmierung eines künstlichen Agenten, der in Pico 4 gegenüber Menschen gut abschneiden würde, ist nicht ohne empirische Studien mög- lich. 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ür Pico 4, das das Verhalten der Menschen in diesem Spiel protokolliert. Ferner ist außer der empirischen Studien mit bezahlten Versuchspersonen die Im- plementierung eines Online-Portals vorstellbar, bei dem an den Brettspielen interessierte Nutzer des Internets sich anmelden und gegeneinander spielen können. Diese Vorgehensweise ist kostengünstiger und würde eine vielgröße- re Datenmenge liefern. Nachteilig ist dabei die geringe Glaubwürdigkeit bzw. Qualität der Daten, denn die Online-Spieler könnten an etwas anderem als dem fairen Gewinnen interessiert sein.

3.5 Erforderliche Programmkomponente

Bevor man zur Beschreibung des entstandenen Programms übergeht, werden hier als eine Zusammenfassung dieses Kapitels die erforderlichen Programmkomponenten aufgelistet:

Benutzeroberfläche −→

Die Benutzeroberfläche ist notwendig, damit die menschlichen Spieler mit dem Programm interagieren können. Sie soll eine angemesse Darstellung des Spieles beinhalten.

Spielverwaltung mit Evaluationsmöglichkeit −→

Zudem ist eine Programmkomponente erforderlich, die für die Einhaltung der Spielregeln sorgt. Weiter muss es eine Möglichkeit geben, die Computerspieler gegeneinander zur Evaluationszwecken mehrere Runden spielen zu lassen.

Implementation des MNM-Algorithmus −→

Unter mehreren computerisierten Verhaltensstrategien sollte der MNMAlgorithmus implementiert werden. Dieser Algorithmus ist in dieser Arbeit die bedeutendste Komponente des Programms.

Netzwerkspiel −→

Die Möglichkeit zur Durchführung eines Netzwerkspiels ist aus zwei Gründen erforderlich: Erstens stellt sie eine einfache Möglichkeit zur Verbindung mit anderen Pragrammen dar, zweitens lassen sich so empirische Studien durchführen.

Kapitel 4 Programm

4.1 Programmstruktur

Für die Implementierung wurde die Programmiersprache Java verwendet. Die Plattformunabhängigkeit dieser Sprache sowie die Möglichkeit des Ausführens im Browser, macht diese Programmiersprache für die Durchführung empirischer Studien mit Internetnutzern sehr vorteilhaft.

Das entstandene Programm¹ beinhaltet die Implementierung beider Szenarien. Es ist in folgende Packetstruktur unterteilt:

>picocardgamepack

−→> helpful
−→> load
−→> payoff
−→−→> jcyw

Das UML-Diagramm im Anhang A zeigt die Beziehungen zwischen den Klas- sen im Packet picocardgamepack. Die Klasse GameAdmin wickelt die Spielver- waltung 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 reali- siert, die von den Klassen PlayerComputer oder PlayerHuman abstammen, die wiederum das Inferface Player vererben. Die Züge der Player-Klassen, die von PlayerHuman abstammen, werden entweder von der lokalen GUI oder vom Netzwerk gesetzt. Die Player-Klassen aber, die vom PlayerComputer ab- stammen, berechnen ihre Züge selbst unter Benutzung der Klassen aus dem Packet payoff.

160 Klassen und über 7000 Zeilen

Das Packet payoff (Abb. 4.1) beinhaltet Klassen, die für die Berechnung der Verhaltensstrategien zuständig sind. Alle Klassen, die von A abstammen, stellen Matrizen der simultanen Züge 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äge 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ür das Laden von Bildern und Kar- tensatzmengen zuständig sind. Das Packet helpful beinhaltet einige hilfreiche Klassen.

Abbildung 4.1: Packet payoff

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

4.2 Hauptbenutzeroberfläche

Die Hauptbenutzeroberfläche (Abb. 4.3) besteht aus einem Menü und einem ”Spieltisch”, der für zwei und vier Spieler benutztbar ist.

Abbildung 4.3: Hauptbenutzeroberfläche

Abbildung in dieser Leseprobe nicht enthalten

4.2.1 Menü

- Variant : Variante von Pico
- Two players : Pico 2
- Four players : Pico 4
- Game :
- New : Initialisiere ein neues Spiel.
- Next turn : Beende nächsten 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ätzen aus der ausge- wählten (- // -).
- Reset wins : Setze den Spielstand zurück und initialisiere ein neues Spiel.

4.2. HAUPTBENUTZEROBERFL ÄCHE

- MNM options : Setze die Parameter p0, p1 und Gedächtnisgrössen für den initialen Zustand und alle anderen Zustände.
- Exit : Beenden
- 1-4 : Die Zahlen 1 bis 4 stehen für die Spielerplätze. Bei jedem Wechsel wird eine neue Instanz eines bestimmten Spielertyps hergestellt und ein neues Spiel initialisiert.
- Local GUI : PlayerLocalGUI.
- Remote : PlayerServerClient.
- Random : PlayerRandom.
- Pure Strategie : PlayerPureSt, benutzt Maximin.
- Nash : PlayerNash, benutzt Nash-Gleichgewicht.
- Anti pure strategie : PlayerAntiPS, spielt optimal, wenn der Geg- ner Maximin spielt.
- Myopic sum maximalisation : PlayerMSM, kurzsichtige Summen- maximierung.
- noisy 1-order myopic : Playerorder1, verrauschte MBR(MSM).
- noisy 3-order myopic : Playerorder2, verrauschte MBR(DMBR(MBR(MSM))).
- MNM algorithm : PlayerMNM fm, MNM-Algorithmus.
- MNM algorithm (+Nash) : PlayerMNM fom, wie PlayerMNM fm, nur mit Erkennung optimaler Strategie.
- Cardssets : Art der Kartensätze (Anzahl)
- All possible (2772) : Alle.
- With sattle point (318) : Mit optimaler purer Strategie.
- Without sattle point (2454) : Ohne optimale pure Strategie.
- 10p (10) : Mit Minimax − Maximin = 10
- 10p eq (2) : Mit Minimax − Maximin = 10, aber mit ausgeglichenen Phasen.
- Network : Netzwerkmenü.
- Start & connect own server : Starte einen Server und verbinde diesen Client mit ihm.
- Disconnect & kill own server : Trenne diesen Client vom Server und beende ihn.
- 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ück.
- Withdraw the enrollment : Melde diesen Client aus einer Spielsit- zung 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).

Abbildung 4.4: Ausgabefenster

Abbildung in dieser Leseprobe nicht enthalten

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 ”Spielti- sches”. Die Spieler sind durchnummeriert mit Zahlen - 1, 2, 3, 4 - und befinden sich entsprechend ihrer Nummer: oben, unten, links, rechts. Auf dem ”Spiel- tisch” wird die Phase des Spiels durch die Zahlen 1 oder 2 angezeigt. Der Spielstand wird durch die Anzeige Score für Punkte und Wins für Anzahl der Siege (fällt bei vier Spielern weg) und gespielter Spiele (in Klammern). Die Karten werden bei lokalen menschlichen Spielern durch einen Mausklick ausgewählt. Ausgewählte Karten werden verschoben dargestellt.

4.3 MNM-Algorithmus

Der Computerspieler, der sich wie der im Abschnitt 3.3 beschriebene künstlicher Agent verhält, ist in der Klasse PlayerMNM fm implementiert. Die Klasse Data implementiert das Gedächtnis, auf dem die Wahrscheinlichkeiten für Verhaltensstrategien des menschlichen Spielers berechnet werden. Die genaue Implementierung des MNM-Algorithmus ist relativ trivial. Anhand der im Anhang B aufgeführten Ausgaben des MNM-Algorithmus kann man sich seine Funktionsweise veranschaulichen.

Die Ausgaben haben folgende Bedeutung:

- Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Beschreibung: Das Gedächtnis wird in Form einer Matrix ausgege- ben. Jede Zeile dieser Matrix entspricht im Zustand n einer bestimmten Verhaltenstrategie des menschlichen Gegenspielers in der Reihenfolge: zufällig, (n + 1)-Ordnung, MSM und (n − 1)-Ordnung (im Zustand 0 auf 0.0 gesetzt). Jede Spalte stellt ein Beobachtungsbeispiel dar (links =neu und rechts =alt).

- Beispiel:

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

Beschreibung: Ausgabe der Wahrscheinlichkeiten der gespielten Verhaltensstrategie des Gegners.

- Beispiel:

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übergang.

4.4 Spielbaumtraversierung

Die Traversierung des Spielbaumes kann sehr viel Rechenaufwand in An- spruch nehmen, wenn man keine intelligente Methoden anwendet, um ihn zu begrenzen. Aus jedem Knoten können n1 ∗ n2 Pfade befolgt werden, wo- bei n1 die Anzahl der Handkarten des ersten Spieler und n2 die Anzahl der Handkarten des zweiten Spielers angeben. Aus n1 ∗ n2 Pfaden können aber nur höchstens n1 + n2 Pfade unterschieden werden, von denen jeder Pfad ei- ner abgelegten Karte aus n1 + n2 Karten entspricht. Zweitens kann man den Rechenaufwand noch mehr begrenzen, wenn die wiederholten Zustände ge- speichert werden.

Die Spielbaumtraversierung wird statische durch Methoden in Klasse CalcTree aus dem Packet payoff implementiert.

4.5 Einbindung der Java-Simplex-Implementation

Die Implementierung des Simplex-Algorithmus ist nicht trivial und gute Im- plementationen sind kommerziell. Für Berechnung der gemischten Gleichge- wichte bei Pico reicht aber die im Netz frei verfügbare Java-Simlex-Implement- ation [Wisniewski und Wei, 2004]. Die Funktionsweise der Lösung einer Aus- zahlungsmatrix lässt sich am besten an einem Beispielproblem beschreiben. Die Matrix ist z. B. zu lösen. Dafür muss sie entsprechend der Abbildung 3.5 in ein lineares Programm umgewandelt und in die Benutzteroberfläche der Java- Simplex-Implementation eingegeben werden (Abb. 4.5, oben). Nach einigen Iterationen wird das Problem gelöst und es wird die auf Abbildung 4.5 (un- ten) dargestellte Ausgabe angezeigt. Daraus kann die Lösung für 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ösenden Matrix positiv sein muss. Das erreicht man, indem von der Matrix ihr kleinster negativer Betrag substrahiert und nach der Lösung dem Erwartungswert hinzuaddiert wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.5: Lösung einer Auszahlungsmatrix [Wisniewski und Wei, 2004]

Abbildung in dieser Leseprobe nicht enthalten

Die Klasse Simplex aus dem Packet payoff wandelt eine Auszahlungsmatrix in ein lineares Programm und gibt die Lösung 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 über ein Netzwerk wird mit Hilfe eines Servers ermöglicht. 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 Instan- zen der Klasse PicoTypeOnServer repräsentieren einzelne Spielsitzungen.

Der Server übernimmt nur die Verwaltung der Kommunikation und Zuord- nung zu Spielsitzungen. Die Spielverwaltung an sich wird aber von dem Client übernommen, der die Spielsitzung vorgeschlagen hat (Abb. 4.6 rechts). Die Clients, die die Spielverwaltung nicht übernehmen, werden ferngesteuert.

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

Abbildung 4.6: Netzwerkspielverwaltung

Abbildung in dieser Leseprobe nicht enthalten

Client in verschiedene Zustände übergehen. Der Zustandsübergangsgraph ei- nes Clients zeigt die Abbildung 4.6 links. Die Zustände haben folgende Be- deutung:

Disconnected : Nicht mit dem Server verbunden.

Connected : Verbunden mit dem Server. Dabei erhält 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ügend andere Clients angemeldet haben.

Started : Client hat die Verwaltung einer laufende Spielsitzung übernom- men (die Spielvewaltung wird nicht auf dem Server sondern auf einem Client abgewickelt, der die Spielsitzung vorgeschlagen hat).

Playing : Client nimmt an einer laufenden Spielsitzung teil.

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

Im Anhang C ist eine Liste der Befehle und Serverausgaben aufgeführt.

KAPITEL 4. PROGRAMM

Abbildung 4.7: Netzwerkdialog

Abbildung in dieser Leseprobe nicht enthalten

Die weiterführende Forschung kann man in folgende Kategorien unterteilen:

- Gestaltung emprischer Studien:

Im Abschitt 3.4 wurde schon erwähnt, dass für das zweite Interak- tionsszenario keine empirisch begründete Programmierung des künst- lichen Agenten angegeben werden kann. Daher ist es wünschenswert empirische Studien durchzuführen. Es wurde im genannten Abschnitt vorgeschlagen, die empirische Studien mit Internutzern durchzuführen. Die Implementierung solcher Möglichkeit ist aus technischer Sicht schon durch eine geringfügige Modifikation des in dieser Arbeit entstandenen Programms möglich. Die grosse Schwierigkeit solcher Studien ist aber die Verhinderung destruktiver und regelumgehender Verhaltensweisen der Onlinespieler. Solches Verhalten kann durch intelligenten Einsatz der zur Verfügung stehenden technischen Möglichkeiten in Grenzen ge- halten werden.

Außer des zweiten Interaktionsszenarios kann auch das erste Interakti- onsszenario mit menschlichen Spielern evaluiert werden. Das könnte wo- möglich zur Verbesserung des dort vorgeschlagenen MNM-Algorithmus führen.

- Kombination mit humanoiden Agenten:

Die zweite Richtung ist die Verwendung in Verbindung mit virtuellen Personen wie z. B. Max (siehe Abschnitt 2.2.1). In [Becker u. a., 2005] wurde die Auswirkung der computersimulierten emotionalen Verhal- tensweisen (nicht verbale Signale) von Max auf den emotionalen Zu- stand einer mit ihm interagierenden Personen untersucht. Die Aussage, die dabei bestätigt wurde, ist, dass die computersimulierten Emotionen des humanoiden Agenten für Menschen glaubwürdig waren. Man kann sich vorstellen, dass eine Ausgabe der computersimulierten Emotionen eines künstlichen Agenten, z.B. einer wahr gewordenen Aussage des Verhaltens der mit ihm interagierenden Person, sein Modell im Geist dieser Person signifikant verändern würde. Die emotionssimulierende Verhaltensweisen des humanoiden Agenten können auch als eine nicht verbale Ausgabemöglichkeit für das Modell des Menschen benutzt wer- den.

- Multimodale Konversation als Spiel:

Drittens kann man anstatt der Gesellschaftsspiele realistischere Inter- aktionsszenarien verwenden. Man kann z.B. eine multimodale Konver- sation, die in der AG ”Wissensbasierte Systeme” als ein Interaktionss- zenario verwendet wurde, als ein Spiel in extensiver Form modellieren. Diese Modellierungsmöglichkeit macht es möglich, ein Konversationss- zenario zu erfinden, bei dem die Modellierung des anderen bzw. ToM wichtig ist.

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ückt werden können, auf Computer in der Interaktion mit Menschen zu übertragen. 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” er- klärt. 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ür den Aufbau realitätsnaher Szenarien verwendet werden kann. Zusätzlich sind im Kapitel 5 drei vielversprechende Weiterentwicklungsmöglichkeiten aufgelistet worden.

Abbildungsverzeichnis

1.1 Modell- und zielbasierter Agent [Russell und Norvig, 1995] .

1.2 Muddy Children Puzzle [Meyer und Hoek, 1995]

2.1 Kripke-Struktur und Semantik d. epist. L. [Fagin u. a., 1995]

2.2 K.-Str. v. muddy child. p. [Hoek und Verbrugge, 2002]

2.3 Gemeinsames Wissen [Fagin u. a., 1995]

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

2.5 ”Schmutzige Gesichter”

2.6 ToM von einem Roboter [Ono und Imai, 2000]

2.7 Spielstruktur von [Hedden und Zhang, 2002]

2.8 Zweite Ordnung [Hedden und Zhang, 2002]

2.9 Erste Ordnung [Hedden und Zhang, 2002]

2.10 ToM-Drift [Hedden und Zhang, 2002]

2.11 Beauty-Contest-Spiel [F.Camerer, 2003]

2.12 Verwendung gem. Strategien [F.Camerer, 2003; Kareev, 1992]

2.13 ”Suchmuster” und Max [Wachsmuth und Lessmann, 2002] . . .

2.14 RMM [Gmytrasiewicz und Durfee, 1992]

3.1 Pico 2

3.2 Ablegeregel

3.3 Kurzsichtige Auszahlungsmatrix

3.4 Spielbaum einer Phase

3.5 Lineares Programm zur Auszahlungsmatrix A

3.6 Zustandsübergangsgraph im fiktiven Spiel

3.7 Rekursives Modell des künstlichen Agenten im fiktiven Spiel

3.8 Spielkonzept

4.1 Packet payoff

4.2 Beziehungen zwischen payoff-Klassen und Player-Klassen .

4.3 Hauptbenutzeroberfläche

4.4 Ausgabefenster

4.5 Lösung einer Auszahlungsmatrix [Wisniewski und Wei, 2004]

4.6 Netzwerkspielverwaltung

4.7 Netzwerkdialog

Tabellenverzeichnis

2.1 Gefangenendilemma [Genesereth u. a., 1988]

2.2 Papier-Stein-Schere

3.1 Fiktives Spiel

3.2 Kartenwichtung

3.3 Kartensätze

3.4 Beispiel zum Spielanfang

3.5 Wahrscheinlichkeiten für einen der richtigen Züge

3.6 Wahrscheinlichkeiten für einen der falschen Züge

3.7 Verteilung auswertbarer Fälle

3.8 Kooperation und Konkurrenz

3.9 Übertragung auf Matching-Pennies und Papier-Stein-Schere

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. <http://tcw2.ppsw.rug.nl/mas/LOK/lwb/>.

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ühlig, H. (2001). Ta- schenbuch 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 based speech act theory. In Proceedings of the 28th annual meeting on Association for Computational Linguistics, pages 79-88, Morristown, NJ, USA. Association for Computational Linguistics.

Fagin, R., Halpern, J., Moses, Y., und Vardi, M. (1995). Reasoning about Knowledge. The MIT Press, Cambridge, Massachusetts, London, England.

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

Genesereth, M. R., Ginsberg, M. L., und Rosenschein, J. S. (1988). Coope- ration 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). Reasoning about

Other Agents: Philosophy, Theory, and Implementation. <cite-

seer.ist.psu.edu/37797.html>.

Gmytrasiewicz, P. J. und Durfee, E. H. (1995). A rigorous, operational forma- lization 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ünchen. 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ührung 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üth, W. (2004,2006). Strategische Spiele. Springer, Berlin, Heidelberg.

Kopp, S., Gesellensetter, L., Krämer, N., und Wachsmuth, I. (2005). A conversational agent as museum guide - design and evaluation of a real-world application. In Panayiotopoulos und others (Eds.), editors, Intelligent Virtual Agents, LNAI 3661, pages 329-343, Berlin. Springer.

Kopp, S. und Wachsmuth, I. (2004). Synthesizing multimodal utterances for conversational agents. Computer Animation and Virtual Worlds, 15(1):39- 52.

Lesser, V. R. und Gasser, L., editors (1995). Proceedings of the First International Conference on Multiagent Systems, June 12-14, 1995, San Francisco, California, USA. The MIT Press.

Lessmann, N., Kranstedt, A., und Wachsmuth, I. (2004). Towards a cognitively motivated processing of turn-taking signals for the embodied conversational agent max. In AAMAS 2004 Workshop Proceedings: ”Embodied Conversational Agents: Balanced Perception and Action”.

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

Mathäus, D. und Nestel, F. (1997). Doris and Frank’s game Pico/Pico2. <http://doris-frank.de/GamesPico 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 other people’s minds. In Hall, L. und Heylen, D., editors, Proceedings of the Joint Symposium on Virtual Social Agents, pages 191-198. The Society for the Study of Artificial Intelligence and the Simulation of Behaviour (AISB), Hatfield.

Noh, S. und Gmytrasiewicz, P. J. (1999). Towards flexible multi-agent decision-making under time pressure. In IJCAI ’99: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pages 492-499, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.

Noh, S. und Gmytrasiewicz, P. J. (2005). Flexible multi-agent decision making under time pressure. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 35(5):697-707.

Ono, T. und Imai, M. (2000). Reading a robot’s mind: A model of utterance understanding based on the theory of mind mechanism. In Proceedings of 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 ap- proach. 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.

Voorbraak, F. (1992). Generalized kripke models for epistemic logic. In TARK ’92: Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge, pages 214-228, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.

Wachsmuth, I. (2005). ”ich, Max”- Kommunikation mit künstlicher Intelligenz. In [Herrmann u. a., 2005], pages 329-354.

Wachsmuth, I. und Lessmann, N. (2002). Eine kognitiv motivierte Architektur für einen anthropomorphen Künstlichen Kommunikator. In Tagungsbeiträge ”Human Centered Robotic Systems 2002”, Karlsruhe, Dezember 2002, pages 141-148.

Weizenbaum, J. (1966). Eliza - a computer program for the study of natu- ral language communication between man and machine. Commun. ACM, 9(1):36-45.

Wisniewski, T. J. und Wei, Y. (1996, 2004). The Simplex Java Applet. <http://www-fp.mcs.anl.gov/otc/GUIDE/Casestudies/simplex/applet /SimplexTool.html>.

Wooldridge, M., Müller, J. P., und Tambe, M., editors (1996). Intelligent Agents II, Agent Theories, Architectures, and Languages, IJCAI ’95, Workshop (ATAL), Montreal, Canada, August 19-20, 1995, Proceedings, volume 1037 of Lecture Notes in Computer Science. Springer.

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

Anhang A

Abbildung in dieser Leseprobe nicht enthalten

ANHANG B.

Abbildung in dieser Leseprobe nicht enthalten

Anhang C

Abbildung in dieser Leseprobe nicht enthalten

Danksagung

An dieser Stelle will ich Allen danken, die mir geholfen haben. Erstmal will ich allen Betreurern dafür danken, dass sie mich immer wieder mein Vorhaben gelobt haben. Das war sehr moti- vierend! Christian danke ich, dass er soviel Zeit für mich finden konnte und durch seine Anmerkungen die Qualität meiner Ar- beit erheblich verbessert hat. Dann will ich Nadine dafür danken, daß sie mit ihrem früheren 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ärt hat, mei- ne Arbeit Korrektur zu lesen. Aber am meisten danke ich meinen Eltern - ohne die Unterstützung zu Hause wäre ich nie soweit gekommen.

[...]

---

¹ von lat. agere handeln

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

³ Ab diesem Punkt wird dafür die englischsprachige Abkürzung MNM = ”Mutual Nested Modeling” verwendet.

⁴ epistemic logic

⁵ iterated analysis

⁶ behavioral game theory

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

² Statt wird auch K verwendet

³ belief-desire-intention

⁴ Procedural Reasoning System

⁵ sStrategienummer ⁶ uSpielernummer

⁷ John Nash 1951

⁸ Tausendfüsser

⁹ Zusätzlicher zufällig agierender Spieler

¹⁰ kurzsichtig

¹¹ nach Keynes’s ”General Theory of Employment, Interest, and Money” [F.Camerer, 2003, s. 210]

¹² Embodied conversational agent

¹³ kontextabhängige Gesten und Mimik

¹⁴ Recursive Modeling Method

¹⁵ Limited Rationality RMM

¹⁶ Das vorgestellte Modell wurde durch empirische Untersuchung an einer einzigen Person für ”weitgehend psychologisch plausibel” erklärt.

¹ Superspiel oder Metaspiel auch möglich

² iterated numerous choise action

³ Silverman’s Game

⁴ der Spielverlauf zwischen Spielstart und Siegerbestimmung

⁵ die ”Hinrunde” und die ”Rückrunde” aus der authentischen Spielbeschreibung

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

⁷ In dieser Arbeit wird nicht auf alle Einzelheiten der Lösung linearer Programme eingegan- gen, denn es würde deren Umfang sprengen. Interessierte Leser sollten dafür einschlägige Literatur nutzen.

⁸ 2*2772 Runden

⁹ myopic sum maximalisation

¹⁰ Di f f erenz der Siege Anzahl der Spiele ∗ 100%

¹¹ myopic best response

¹² deterministic MSM

¹³ risikoscheu

¹⁴ deteministic MBR

¹⁵ quantal response equilibrium

¹⁶ die menschliche Fehlerquote bewegt sich so zwischen 0% und 10%, wie es verschiedene Studien zeigen

¹ Klassen und uber 7000 Zeilen

² noch nicht implementiert