Universität Bayreuth

Seminar: ,,Evolution von Kooperation und Altruismus"

Wintersemester 2007/2008

Seminararbeit:

Die Strategie Tit For Tat

im iterierten Prisoner′s Dilemma

Potentiale für bessere Performance und Robustheit nutzen

Abstract

Diese Arbeit hat zum Ziel, die Strategie Tit For Tat im iterierten

Prisoner′s Dilemma zu verbessern. Ausgehend von Axelrod und

seiner Schwächenanalyse werden dazu Maßnahmen diskutiert und

realisiert. Diese werden am Ende für verschiedene

Verwendungszwecke kombiniert, so dass TFTs Erfolg übertroffen

werden kann. Ein Ausblick widmet sich möglichen

Entwicklungen im IPD.

Autor: Christoph

Siemroth

---

Christoph Siemroth

"TFT im iterierten Prisoner′s Dilemma"

Inhaltsverzeichnis

Inhaltsverzeichnis

Vorwort 1

1. Robert Axelrods Computerturnier 1

1.1 Das Prisoner′s Dilemma 1

1.2 Regeln und Durchführung des Turniers 2

1.3 Ergebnisse und Schlüsse 3

1.4 Analyse der Schwächen von

TFT

4

2. Realisierung von Verbesserungen für TFT 6

2.1 Geringen Payoff gegen

Random

verbessern 6

2.1.1 Randomerkennung durch Muster 7

2.1.2 Erkennung durch Tracking von Gegnerzügen 8

2.2 Echo-Effekte erkennen und auflösen 9

2.2.1 Mustererkennung ohne Wissen 10

2.2.2 Mustererkennung durch Vergleich 10

2.2.3 Entdecken alternierender Züge durch Hochzählen 13

2.2.4 Bedingte Vergebung von Defektionen 15

2.3 Kooperationsangebote 15

2.4 Im Endgame-Effekt gut abschneiden 16

2.5 Eigene Noise-Fehler korrigieren 17

2.6 Die finale Version von

augmentedTFT

18

2.6.1 Maximale Robustheit 18

2.6.2 Auf IPD-Turniere optimiert 19

2.6.3 Für Umgebungen mit Noise 19

3. Ausblick 20

Anhang A ­ Unabhängigkeit in evolutionären Simulationen 21

Anhang B ­ Arten von Strategien 21

Literaturverzeichnis 23

Anlage

: Archiv mit zu dieser Arbeit gehöhrenden Dateien (Simulationsergebnisse und

Sourcecodes)

---

Christoph Siemroth

"TFT im iterierten Prisoner′s Dilemma"

Seite 1

Vorwort

Diese Arbeit hat es sich zum Ziel gemacht, eine erfolgreiche Strategie aus dem iterierten

Prisoner′s Dilemma weiter zu verbessern und Erweiterungen für verschiedene Einsatzgebiete,

z.B. für noiseverzerrte Simulationen, zu diskutieren. Diese Strategie ist

Tit For Tat

, vor allem

bekannt durch Robert Axelrods Buch "The Evolution of Cooperation" (1984), worauf hier

aufgebaut wird. Die vorgeschlagenen Maßnahmen wurden auch in der Praxis getestet, so dass

nicht nur die Theorie beleuchtet wird, sondern vor allem auch Probleme und Erkenntnisse aus

den Simulationen einfließen.

Dazu werden zunächst Grundlagen in Form des Prisoner′s Dilemmas erläutert und selektiv

die nützlichsten Ausführungen von Axelrod rekapituliert ­ in Bezug auf Turnier sowie der

Strategie

Tit For Tat

. Das zweite Kapitel ist der Hauptteil und befasst sich mit der Umsetzung

von Verbesserungen für Strategien, speziell für

TFT

, ausgehend von der Schwächenanalyse.

Das geschieht anhand von Sourcecode-Auszügen und experimenteller Ergebnisse sowie deren

Auswertung. Zum Abschluss gibt es einen Ausblick zur Zukunft von IPD-Turnieren.

Komplette Sourcecodes und ausführliche Simulationsergebnisse befinden sich aufgrund des

Umfangs nicht in diesem Dokument, sondern liegen bei.

1. Robert Axelrods Computerturnier
1.1 Das Prisoner′s Dilemma

Das Prisoner′s Dilemma, folgend PD, ist ein Spiel für üblicherweise zwei Spieler, welche

jeweils 2 Wahlmöglichkeiten haben: Kooperation (C) oder Nichtkooperation, auch Defektion

(D) genannt. Abhängig von der eigenen Entscheidung (1) und der des Gegners (2) ergibt sich

der Payoff für einen Zug, also der Gewinn oder die Ausbeute. Das lässt sich in einer 2x2-

Matrix veranschaulichen:

Cooperation2 Defection2

Cooperation1

R1 / R2

S1 / T2

Defection1

T1 / S2

P1 / P2

Unabhängig davon, welche Werte für die Payoffs vergeben werden, wird deutlich, dass das

Spiel symmetrisch ist. Jede Seite bekommt also für die gleiche Kombination aus eigener und

gegnerischer Entscheidung denselben Payoff. Allerdings gibt es zwei Bedingungen1, die bei

der Payoffverteilung gelten müssen, damit ein PD vorliegt:

(1) Ti > Ri > Pi > Si

für i = 1, 2

(2) (Ti + Si) / 2 < Ri

für i = 1, 2

Die erste Bedingung muss gelten, damit überhaupt von einem Dilemma gesprochen werden

kann. Dieses entsteht dadurch, dass es für jeden Spieler individuell rational ist, zu defektieren.

Denn egal, ob der andere Spieler kooperiert oder defektiert, bekommt man immer ein besseres

Resultat, indem man defektiert. Veranschaulicht in der Tabelle für Spieler 2:

Cooperation2 Defection2

Ergebnis für 2

Cooperation1

R1 /

R2

S1 /

T2

T2 > R2

D2 > C2

Defection1

T1 /

S2

P1 /

P2

P2 > S2

D2 > C2

Die Defektion ist somit die dominante Strategie, da sie besser ist unabhängig davon, was der

Gegner macht. Für diesen gilt das ebenfalls und so kann es bei rationalen Spielern im

1 Vgl. Hegselmann/Flache 2000: S. 76/77, demnach wird Bedingung (2) oft als optional betrachtet.

---

Christoph Siemroth

"TFT im iterierten Prisoner′s Dilemma"

Seite 2

spieltheoretischen Sinne nur ein Ergebnis geben: Beide defektieren und erhalten somit P als

Payoff. Da kein Akteur den Anreiz hat, sein Verhalten oder seine Wahl zu ändern, liegt ein

Gleichgewicht vor ­ genauer: ein

Nash-Gleichgewicht

.2 Das Dilemma besteht nun darin, dass

ein Ergebnis erreicht werden könnte, das beide besser stellt, also

pareto-superior

ist. Das

wäre dann der Fall, wenn beide kooperieren würden. Bei der eben vorausgesetzten

Rationalität wird das aber nicht geschehen, da dann wieder ein Anreiz zum Verhaltenswechsel

vorliegt, also die Wahl auf Defektion zurückfällt.

Das iterierte PD (kurz: IPD) besteht aus mehreren Runden des PDs, so dass dieselben

Akteure mehrere PDs hintereinander spielen. Hier wird die zweite Bedingung relevant. Diese

soll sicherstellen, dass Kooperieren in zwei Runden zwischen den Akteuren ertragreicher ist

als je einmal Defektieren und Kooperieren in entgegengesetzter Reihenfolge, also dass R·2 >

(T + S) gilt. Bei ausreichend wahrscheinlicher Fortsetzung des Spiels gibt es keine dominante

Strategie mehr. Während für (1) ordinaler Nutzen ausreichend ist, benötigt (2) einen

kardinalen Nutzenbegriff. Dieser ist auch für das Computerturnier notwendig, da die Payoffs,

also Nutzenwerte, zwischen verschiedenen Begegnungen verglichen und addiert werden, so

dass die Unterschiede/Intervalle und nicht nur die Ordnungen zählen.3

1.2 Regeln und Durchführung des Turniers

Die Frage, welche Strategie sich am besten in iterierten PDs schlägt, bewegte Robert Axelrod

dazu, ein Computerturnier zu veranstalten. ,,[Dabei] ist eine Strategie [...] eine Spezifikation

dessen, was in jeder Situation, die in einem Spiel überhaupt entstehen könnte, zu tun ist."4

Dazu wurden professionelle Spieltheoretiker aufgerufen, Strategien einzusenden und in einem

späteren, zweiten Durchlauf wurden mit Kenntnisstand über den ersten Durchlauf abermals

Strategien eingeschickt ­ diesmal aber nicht nur von Professionellen und Spieltheoretikern.

Dabei galten folgende Regeln:

- jede Strategie trat gegen alle anderen eingesendeten Strategien an, sowie gegen sich

selbst und

Random

(spielt C mit 50% und D mit 50% Wahrscheinlichkeit)

- im ersten Turnier wurden 200 Züge gespielt, im zweiten gab es eine Abbruch-

wahrscheinlichkeit, so dass der erwartete Median der Länge 200 Runden entsprach

- Payoffs waren mit (T, R, P, S) = (5, 3, 1, 0) definiert

- fünfmaliges Durchführen der Begegnungen und Mitteln der Ergebnisse, um das

Endergebnis zu stabilisieren und Zufallsabweichungen zu minimieren

- kein Ausschließen rechenintensiver Strategien

- es gab keine Noise-Effekte (Verfälschungen von Kommunikation der Akteure)

Die verwendbaren Informationen für die Strategien bestehen aus den bisherigen eigenen

Zügen, die bisherigen Züge des Gegners sowie die Anzahl der Runden, wenn wie im ersten

Turnier festgelegt. Eine solche Festlegung der Rundenzahl führt üblicherweise zu einem

Endgame-Effekt (näheres in Sektion 2.4). Um diesen zu umgehen, greift man heute meistens

auf Abbruchwahrscheinlichkeiten zurück, so dass die letzte Runde nicht bekannt ist. Das hat

einen Nachteil in der Punktberechnung: Manche Duelle können wesentlich länger anhalten als

andere, was vor allem dann Auswirkungen hat, wenn bei Strategien ,,Fixkosten" anfallen, also

beispielsweise ein festes Muster am Anfang gespielt wird oder Defektionszüge zu

Identifikationszwecken nötig sind.5 Diese Kosten fallen bei mehr Runden weniger ins

Gewicht ­ analog zur Ökonomie, wo Fixkosten mit steigender Produktionsmenge sinkenden

Anteil an den Durchschnittskosten haben (Fixkostendegression). Mit mehrmaligem

2 Vgl. Ross (1997): Chapter 2.5 für spieltheoretische Lösungskonzepte.

3 Vgl. Ross (1997): Chapter 2.1 bezüglich kardinalen und ordinalen Nutzen bzw. Nutzenfunktionen.

4 Axelrod (1984): S. 12 ­ Bedingung: Die Zukunft hat hinreichend große Bedeutung.

5 Vgl. Li (2006): S. 94f. für ein Beispiel eines Identifikationsmusters.

---

Christoph Siemroth

"TFT im iterierten Prisoner′s Dilemma"

Seite 3

Wiederholen des Turniers und konsequenter Durchschnittsbildung im Ranking können diese

Differenzen durch Unterschiede der Rundenzahl weitgehend ausgeräumt werden.

1.3 Ergebnisse und Schlüsse

Die Strategie

Tit For Tat

(folgend

TFT

) gewann beide Turniere. Für bemerkenswert hält das

Axelrod vor allem, weil sie die einfachste Strategie war, denn alles was sie macht, ist in der

ersten Runde zu kooperieren und danach des Gegners vorherigen Zug zu spielen.6

(1) Einer Eigenschaft wird besonders zugeschrieben, diesen Erfolg begünstigt zu haben:

Axelrod nennt sie ,,Freundlichkeit" und besagt, kooperierend zu beginnen und nicht zuerst zu

defektieren. Im ersten Turnier waren die ersten acht Strategien freundlich und keine der

schlechter platzierten. Im zweiten Turnier betrug die Korrelation zwischen Freundlichkeit und

Punktzahl sogar 0,58. Hier sei aber angemerkt, dass Freundlichkeit eben gerade diesen Vorteil

brachte, weil mehrere Strategien freundlich waren. Ein Theorem Axelrods (angelehnt an das

Folk-Theorem, war schon vorher bekannt) besagt, dass es keine beste Strategie im IPD

unabhängig von den anderen Strategien geben kann.7 Das schlägt sich hier nieder, denn die

freundlichen Strategien haben ­ da es keine Noise-Effekte gab ­ durchgängig kooperiert (bis

auf die letzte Runde) und somit im Durchschnitt fast 3 Punkte pro Runde erhalten. Tatsächlich

begünstigt das Design des Turniers, was Strategien gegen sich selbst antreten lässt,

freundliche Strategien, da diese dort 3 Punkte einfahren gegenüber nur 1 Punkt, den

bestimmte unfreundliche Strategien zumindest zeitweise gegen sich selbst erhalten. Dieser

Unterschied fällt aber bei komplexeren unfreundlichen Strategien immer weniger ins Gewicht

(z.B. Fingerprint-Strategien, die sich selbst erkennen und daher gut abschneiden).

In der evolutionären Spieltheorie gibt es dazu folgende Gedanken: Nehmen wir an, es gäbe

eine Population von Individuen, die nur

Hawk

spielen, also immer defektieren. Kommt nun

ein einzelnes Individuum mit freundlicher Strategie dazu, so wird es in diese Population nicht

eindringen können, denn es verliert gegen jedes andere Individuum in der Interaktion durch

IPD. Bei einem

TFT

Spieler würde immer die erste Runde verloren gehen, aber das ist

ausreichend, dass dieser ausstirbt.

Hawk

ist also eine kollektiv stabile Strategie.8 Im Turnier

kann dieser Fall aber nicht auftreten, da die freundliche Strategie zumindest mit sich selbst

kooperiert. Und sie bekommt dort in jeder Runde den dreifachen Payoff von

Hawk

, die hier

als Repräsentant von früh defektierenden Strategien aufgeführt wird. Das heißt also, dass

schon wenige freundliche Strategien gegenüber vielen

Hawk

-ähnlichen besser abschneiden

können. Bemerkenswert ist darüber hinaus, dass freundliche Strategien auch Vorteile haben,

je größer die Rundenzahl ist, denn dann schwindet der Nachteil aus der ersten Runde9 gegen

Hawk

und es gibt mehr Runden, in denen der höhere Payoff aus gegenseitiger Kooperation

mit anderen freundlichen Strategien oder sich selbst erspielt werden kann.

(2) Eine weitere vorteilhafte Eigenschaft wird in ,,Vergebung" gefunden, also der Neigung,

nach Defektion auch wieder Kooperation einzugehen.

TFT

besitzt diese Eigenschaft, aber in

recht schwacher Form, da Kooperation nur wieder zustande kommt, wenn ein

Kooperationsangebot vom Gegner vorliegt. In einer leicht abgeänderten Form nenne ich die

Eigenschaft ,,Nachsicht", wenn auf eine fällige Defektion aufgrund von Defektion des

Gegners verzichtet wird. Nachsicht ist dabei nur relativ ein Vorteil, denn in einer Population

aus nur ausbeutenden Strategien ist diese Eigenschaft ein Nachteil. Freundliche Strategien

können keine ausbeutenden Strategien sein, da diese an einem gewissen Punkt defektieren, so

dass man durchaus eine positive Korrelation vom Erfolg von Freundlichkeit und Nachsicht

einräumen kann: Beide sind vorteilhaft, wenn es viele freundliche Strategien gibt. Beide sind

nachteilig, wenn es viele ausbeutende gibt.

6 Vgl. Axelrod (1984): Kapitel 2 für ausführliche Analyse, hier wird nur das Relevante aufgearbeitet.

7 Vgl. Axelrod (1984): S. 14.

8 V(

Hawk

,

Hawk

) V(x,

Hawk

) [= Payoff x gegen

Hawk

] für alle möglichen Strategien x.

9 Natürlich nur, wenn auf die Defektion der ersten Runde folgend reagiert wird (siehe Provozierbarkeit).

---

Christoph Siemroth

"TFT im iterierten Prisoner′s Dilemma"

Seite 4

(3) Eine andere Eigenschaft wurde nach dem zweiten Turnier als wichtig identifiziert: Die

,,Provozierbarkeit", also die Neigung, eine Defektion des Gegners durch eigenes Defektieren

zu bestrafen. Sie wurde erst hier wichtig, weil durch die Erkenntnisse des ersten Turniers

vermehrt ausbeutende Strategien aufkamen. Man bemerke, dass Provozierbarkeit das

Gegenteil von Nachsicht ist ­ zumindest solange man nicht unterscheiden kann zwischen

unnötiger Defektion (z.B. ausgelöst durch leichte Noise oder vernachlässigbare Ausbeutungs-

versuche) und Defektion mit schlechten Folgen, wenn nicht bestraft. Diese Unterscheidung

erfordert aber eine sehr ,,schlaue" Strategie, also hohe Komplexität, oder ist gar nicht

möglich.10 Ob es vorteilhaft ist, bei einer Defektion des Gegners nachsichtig zu sein (z.B. bei

Joss

, was kooperativ startet, dann mit p=0,1 defektiert und sonst

TFT

spielt) oder nicht (z.B.

Hawk

,

Random

) lässt sich nur sagen, wenn man die Strategie kennt (also ihre

Handlungsvorschriften kennt) oder wenn man genügend Informationen im Spiel sammeln

kann. Nach einer gegnerischen Defektion liegen diese aber oft noch nicht vor und sind daher

meistens nur mit viel Aufwand oder gar nicht in Erfahrung zu bringen. Der Versuch kann im

Turnier zudem viele Punkte kosten. Ob Nachsicht oder Provozierbarkeit besser ist, lässt sich

daher oft nur nach dem Turnier mit Kenntnis der gegnerischen Strategien sagen. Vorher ist

eine Vermutung über die Zusammensetzung des Strategiepools im Turnier hilfreich, um zu

entscheiden, ob die Strategie eher nachsichtig oder provozierbar sein soll.

(4) Das führt zur Eigenschaft der ,,Verständlichkeit", die Axelrod ebenfalls als vorteilhaft

bezeichnet. Strategien, die sie nicht haben, können den Gegner zu falschen Entscheidungen

führen, was beiden Punkte kosten kann, wenn z.B. Kooperation nicht zustande kommt bzw.

Echo-Effekte auftreten. Das Problem aus dem vorherigen Absatz tritt also oft wegen

mangelnder Verständlichkeit der anderen Strategie auf.

(5) Im evolutionären Kontext ist es von Vorteil, gut gegen sich selbst abzuschneiden, da

erfolgreiche Strategien einen höheren Anteil in der Gesamtpopulation annehmen und öfter auf

sich selbst treffen. Außerdem ist Unabhängigkeit wichtig, was bei ausbeutenden Strategien

deutlich wird, die bei Vorhandensein von ausbeutbaren Strategien erfolgreich sind, während

ihre Opfer aussterben. Zeitlich versetzt sterben dann aber auch die Ausbeuter aus, weil sie die

Quelle ihres Erfolges ausgerottet haben.11

1.4 Analyse der Schwächen von TFT

(1)

TFT

ist zwar verständlich, selbst aber zu simpel, um den Gegner zu verstehen ­ es werden

nur mechanisch die Züge des Gegners wiederholt. Dabei nutzt die Strategie das Potential der

bisherigen Interaktionsgeschichte nur minimal aus, denn es wird nur auf den letzten Zug des

Gegners zurückgegriffen. Eine Hauptschwäche (nach Axelrod; weil mit großem

Verbesserungspotential) von

TFT

hat hier ihre Ursache: Das schlechte Abschneiden gegen

Random

, denn mit Kenntnis von nur einem Zug kann

Random

nicht erkannt werden. Gleiches

ist der Fall in Spielumgebungen mit starken Noise-Effekten, die gegnerische Strategien

ebenfalls wie

Random

erscheinen lassen, auch wenn sie es nicht sind.

(2) Als zweite Hauptschwäche ist die Unfähigkeit bekannt, Echo-Effekten wie gegen

Joss

zu begegnen. Nachsichtiges Verhalten wäre in dem Fall besser als auf die Provokation

einzugehen, doch

TFT

ist zu simpel, um das zu erkennen. Nicht nur gegen

Joss

kann es diese

Effekte geben, genauso wenig wie sie auch nur so geartet sein müssen. Folgende Tabelle zeigt

zwei verschiedene Echo-Effekte anhand der ersten Züge in einem IPD von

TFT

gegen

Joss

und

Pavlov

12 (C=1 und D=0):

10 Vgl. Li (2006): S. 89.

11 Siehe Anhang A für veranschaulichende Grafiken aus evolutionären Simulationen.

12 Vgl. S. Y. Chong et al. (2006a): S. 30 für Beschreibung der Strategie; sie startet mit Defektion und ändert das

Verhalten aus vorherigem Zug immer, wenn Payoff 0 oder 1 war, ansonsten bleibt sie dabei.

---