Cultaptation - Das Ergebnis und ein Beispiel

von Günther Rosenbaum

Lange hat es gedauert - doch mittlerweile ist die Gewinnerstrategie des Cultaptation Wettbewerbs ermittelt worden und die Autoren haben ihren Preis auf der EHBEA 2009 conference in St Andrews entgegengenommen. Die Strategie "Discountmachine" der Autoren Dan Cownden und Tim Lillicrap hat mit gutem Abstand gegenüber den Konkurrenten gewonnen.

Zitat[1]:
"There are a number of ways in which this strategy stands out and that may have contributed to its success. The first is that it attempts to characterise the environment in a highly comprehensive way, extracting a lot of information from its prior experiences, and is responsive to that information. The second is that this strategy explicitly makes decisions based on expected lifetime outcomes, rather than immediate payoff benefits. Finally, the strategy is noteworthy for the sophistication of the mathematics it uses to calculate expected payoffs."

Manche Dinge in diesem Wettbewerb scheinen auf der Hand zu liegen - denn jedem ist es irgendwie klar, dass das Kopieren einer "guten" Aktion (leider kopiert man aber nicht immer nur gute Aktionen) einfacher ist als das Finden einer guten Strategie durch wiederholte Trial & Error Versuche.

Dazu noch ein weiteres, etwas längeres Zitat aus den Wettbewerbsregeln[2], welches den Stand der aktuellen Forschungen wiedergibt; ich möchte jedem empfehlen, diesen Absatz vorab und in Ruhe durchzulesen:

"It is commonly assumed that social learning is inherently worthwhile. Individuals are deemed to benefit by copying because they take a short cut to acquiring adaptive information, saving themselves the costs of asocial (e.g. trial-and-error) learning. Copying, it is assumed, has the advantage that individuals do not need to re-invent technology, devise novel solutions, or evaluate environments for themselves. Intuitive though this argument may be, it is flawed (Boyd & Richerson 1985; Boyd & Richerson 1995; Rogers 1988; Giraldeau et al. 2003). Copying others per se is not a recipe for success. This is easy to understand if social learning is regarded as a form of parasitism on information (Giraldeau et al. 2003): asocial learners are information producers, while social learners are information scroungers. Game-theoretical models of producer-scrounger interactions reveal that scroungers do better than producers only when fellow scroungers are rare, while at equilibrium their payoffs are equal (Barnard & Sibly 1981). Similarly, theoretical analyses of the evolution of social learning in a changing environment (e.g. Boyd & Richerson 1985; Boyd & Richerson 1995; Rogers 1988; Feldman et al. 1996) reveal that social learners have higher fitness than asocial learners when copying is rare, because most 'demonstrators' are asocial learners who will have sampled accurate information about the environment at some cost. As the frequency of social learning increases, the value of copying declines, because the proportion of asocial learners producing reliable information appropriate to the observer is decreasing. An equilibrium is reached with a mixture of social and asocial learning (Enquist et al. 2007). These mathematical analyses, together with more conceptual theory (e.g. Galef 1995), imply that copying others indiscriminately is not adaptive; rather, individuals must use social learning selectively, and learn asocially some of the time. Natural selection in animals capable of social learning ought to have fashioned specific adaptive social learning strategies that dictate the circumstances under which individuals will exploit information provided by others (Boyd & Richerson 1985; Henrich & McElreath 2003; Laland 2004; Schlag 1998). At present, it is not clear which social learning strategy, if any, is best. The tournament has been set up to address this question."

Es galt also eine Strategie zu finden, die

Bevor ich aber die Ergebnisse noch etwas detaillierter betrachte, möchte ich meine eigene Strategie etwas erläutern; wer möchte, kann sich auch den Java und Mathlab Code im Detail anschauen[5].

In der paarweisen Simulation (nur die betrachte ich hier) treten jeweils 2 gegnerische Strategien über 10000 Runden gegeneinander an - die besser an die Umgebung angepasste Strategie wird sich dabei häufiger vermehren und den Gegner in seine Schranken verweisen! (Für den genauen Ablauf der Simulationen siehe [2])

Jede Strategie hat folgende 3 Aktionsmöglichkeiten in jeder Runde:

  1. EXPLOIT (benutzen)Dies ist die wichtigste und vermutlich häufigste aller Aktionen.
    Indem ich eine in einer früheren Runde gelernte Aktion meines Repertoires benutze, erhalte ich einen Ertrag und stärke damit meine Fitness (wenn der Ertrag genügend hoch ist) ... und bei höherer Fitness ist meine Fortpflanzungsrate höher.
  2. OBSERVE (nachahmen, kopieren, soziales Lernen)
    Bei Observe lerne ich eine der Aktionen, die ein zufällig ausgewählter Simulationsteilnehmer in der Vorrunde ausgeführt hatte. Wenn ich davon ausgehe, dass dessen Strategie eine ertragreiche Aktion gewählt hatte und ich diese Aktion noch nicht kannte, dann habe ich jetzt auch eine gute Aktion in meinem Repertoire.
    Leider (oder vielleicht glücklicherweise) ist das Abschauen auch fehlerbehaftet; der Ertrag ist etwas verfälscht und manchmal geht das Abkupfern völlig in die Hose - ich erhalte dann eine zufällige Aktion (ähnlich zu Innovate!).
    In der zweiten Stufe des Wettbewerbes war es auch möglich, dass ein OBSERVE nicht nur eine Aktion erlernt, sondern bis zu 6 Aktionen!
  3. INNOVATE (Trial&Error, asoziales Lernen)
    Hierbei erlerne ich zufällig eine der 100 Aktionen (inklusive des Ertrages) der Simulationsumgebung. Dies kann eine gute, schlechte oder sogar schon bekannte Aktion sein. Die Erträge einer gelernten Aktion ändern sich über die Zeit mit einer festen, aber unbekannten Wahrscheinlichkeit.

Dummerweise weiß ich auch nicht im voraus, welche Werte die Erträge annehmen können - ist 20 schon ein hoher Ertrag oder erst 150? Eine Aktion, die momentan 50 bringt, kann in wenigen Runden nur noch 0 wert sein - denn diese Erträge sind Zufallsvariablen.

Eine vermutlich gute Aktion werde ich häufig so lange benutzen (Exploit), bis sich plötzlich der Ertrag verändert: Man beachte, dass man in diesem Fall wieder so etwas wie ein Innovate ausführt - die Aktion erhält einen neuen, zufälligen Ertragswert!

Mehrere unabhängige Wahrscheinlichkeitsverteilungen beeinflussen die Umwelt während einer Simulationsreihe; diese Verteilungen werden vor einem Durchgang fixiert und ändern sich dann für eine ganze Testreihe nicht mehr (ein Individuum kann also während seiner Lebenszeit von durchschnittlich 50 Jahren diese Parameter zu schätzen versuchen). Dummerweise kannte man vor dem Wettbewerb nur einige grobe Eckwerte dieser Parameter - einige Dinge sind auch im Nachhinein noch nicht komplett offengelegt.

Jedes Individuum innerhalb der Simulation hat jede Runde (aber unabhängig vom Alter!) eine Sterbewahrscheinlichkeit von 2%. - stirbt jemand, so sofort wieder ein Kind geboren. Um die Strategie des Kindes festzulegen, wird ein "Vorfahre" aus allen 100 Individuen (eigene und gegnerische) zufällig gewählt - wobei die Auswahlwahrscheinlichkeit proportional zur Fitness (durchschnittlicher Ertrag pro Runde) gewählt wird. Zusätzlich tritt mit 2% Wahrscheinlichkeit noch eine Mutation auf, bei der der Nachfolger eine gegnerische Strategie nutzt.

Jedes Individuum hat nur die Informationen aller gelernten oder ausgeführten Aktionen seit seiner Geburt als Entscheidungskriterium für seinen nächsten Zug zur Verfügung: Wie würdet ihr jetzt eine gute Strategie formulieren, die möglichst fit ist, um sich gut fortzupflanzen und die sich gegen die Mutanten erfolgreich wehrt?

Aufgrund der vielen Unbekannten dreht man sich da immer wieder im Kreis...

Meine Strategie "StabilityObserver" habe ich dann folgendermaßen festgelegt:

Warum heißt die Strategie "StabilityObserver"? Nun, weil sie einerseits die Stabilität ihrer Umwelt "beobachtet" und andererseits fast ausschließlich durch "OBSERVE" lernt!

Einen Link auf die eingereichten Wettbewerbsunterlagen mit Java-Code sowie die Umsetzung auf Matlab-Code findet Ihr am Ende dieses Berichtes [5].

Nun, diese Strategie hat es nur (immerhin?) bis auf Platz 11 von 104 Einsendungen geschafft. Aber wie sah die Strategie des Siegers "Discountmachine" aus?

Hier eine grobe Beschreibung der Siegstrategie; Zitat[ 1]:

Our creature does three major things:

First it estimates/calculates, what we believe to be all the pertinent parameters of the simulation as well as a few other quantities that we believe to be useful. These are P_c, the mean of the payoff distribution, the mean of of the observed values, the correlation between observe and exploit values of the same action, N_observe, and where applicable the number of data points used to make these estimates.

Second it uses some of these parameters to estimate the expected payoff for performing each action in its repertoire. Once it has a best exploit chosen from its repertoire it compares the value of Exploiting to the value of Observing using a geometric discounting scheme based on our estimate of P_c and the given probability of death.

Lastly a machine learned function, takes into account N_observe and the estimates on the reliability of observing and P_c to adjust the value of Observing accordingly. Our creature then chooses whichever action has the higher perceived value, Observing or Exploiting. As a side note our creature only Innovates when it has an empty repertoire and observe doesn't work, which typically is only on the first turn of a simulation.

Worin liegt nun der Unterschied zu meiner Strategie?

So wie es aussieht, werden hier wohl die verschiedenen variablen Parameter der Umwelt recht genau geschätzt (ich habe nur einen einzigen Parameter grob geschätzt).

Anschließend versucht man, die erwarteten zukünftigen Erträge einer EXPLOIT und einer OBSERVE Aktion abzuschätzen.

Ein vereinfachtes Beispiel:

Gehen wir von einer recht variablen Umgebung aus, in welcher Aktionen im Mittel nur etwa 5 Runden stabil sind. Führe ich nun z.B. 5-mal eine Aktion mit dem Ertrag 100 aus, so habe ich hier also eine Fitness von 500/5 = 100.

Führe ich aber zuerst ein OBSERVE (hat immer Ertrag 0) durch und lerne tatsächlich eine bessere Aktion mit Ertrag 110, so erhalte ich eine Fitness von 0+110+110+110+110+110/6 = 550/6 = ca. 92. OBSERVE wäre hier also die schlechtere Alternative!

Hat man also gute Schätzwerte der Parameter, so kann man recht gute Entscheidungen treffen (wohl noch unterstützt durch entsprechende Abzinsung der zukünftigen Erträge).

Bei mir ist das ungenauer, mehr auf qualitativer denn auf quantitativer Weise geschehen. Zu guter Letzt habe ich die vermeintlich geringen Effekte der "Kopierfehler" einfach ignoriert.

Eine extrem vereinfachte Form des Wettbewerbes (kein OBSERVE, stabile Umgebung, Verteilungsfamilie der Aktionswerte bekannt, etc. ...) wurde in [3] nach dem Wettbewerb mathematisch analysiert: Als Kind lernen (INNOVATE), mit mathematischen Methoden den optimalen Stoppzeitpunkt für den Abbruch des Lernens bestimmen und dann bis zum Lebensende arbeiten (EXPLOIT) ... das ist dort die traurige Wahrheit für ein optimales Individuum!

Einen solchen optimalen "Smart Innovator" habe ich in der eigenen Simulationsumgebung bei stabiler Umgebung gegen den StabilityObserver antreten lassen: Es ist wohl klar, dass der Smart Innovator ohne "Observe" keine Chance gegen den StabilityObserver hatte!

In [7] wird der Ansatz des Smart Innovators nochmal etwas modifiziert: Will man die Fortpflanzungswahrscheinlichkeit optimieren, so muss man manchmal schon als Kind EXPLOIT nutzen. Tja, kommt man etwas näher an die realen Wettbewerbsbedingungen, so wird es auch schon wieder etwas komplizierter... Des weiteren muss man beachten, dass "einfache" optimale Strategien/Nash-Gleichgewichte auch nur einen garantierten Ertrag gegen jeden Gegner garantieren - bei Wettbewerben muss man allerdings auch und gerade schwache Gegner möglichst hoch besiegen um eine hohe Gesamtpunktzahl zu erreichen.

Interessant und überraschend war die Strategie des Zweitplazierten "Intergeneration". Zitat[1]:

"My main idea is (although it seems not be as good as I expected) that an important information for the young is, how much is the "good" payoff (with how much I can be happy). If I have so much or more, I would just EXPLOIT until it changes, otherwise I would 8 times exploit and once observe.

The important trial is that the old could "say" something to the young, by "signaling" something to the young. The signal consists of doing an act whose number is divisible by 8. If the fraction is 1,2,3,4 this means that "payoff 8 is very good", 5,6,7,8 means "payoff 20 is very good" and 9,10,11,12 means "payoff 40 is very good".

If the old does not have this in his repertoire, he innovates. If he has more than one of these 4 possible "symbol" acts, he uses that with highest payoff -- because it is a higher chance that this will diffuse. Even the "opponent" can help spread out this signal, without knowing that. "

Huch! Das sieht ja so aus, als wollte da jemand schummeln, denn laut Regeln gibt es eigentlich keinen Kontakt und Informationsaustausch zwischen verschiedenen Individuen! Luke Rendell, einer der Organisatoren des Wettbewerbes sagt dazu:

"We thought about whether it was cheating or not but decided to let it go. I am investigating the properties of this strategy in more detail right now. I think that the 'signalling' part of the strategy made very little difference … "

Intergeneration war wohl aber auch der einzige Teilnehmer, der etwas grenzwertige Methoden benutzte - alle anderen haben sich nicht nur dem Worte sondern auch dem Sinne nach an die Regeln gehalten.

Es wird sicherlich auch noch eine wissenschaftliche Auswertung der besten Strategien geben - da bin ich schon drauf gespannt (z.B. [6]); auch die Organisatoren werden hierzu noch Informationen veröffentlichen (aber im Moment noch nicht verfügbar)!

Die besten Strategien in diesem Wettbewerb waren sicherlich nicht so elegant und allgemein verständlich wie damals die "Tit for Tat" Strategie im Wettbewerb von Axelrod; viele Teilnehmer haben zulässige mathematische Methoden benutzt - dies hat natürlich nichts mit Mogeln zu tun und ist auch bei vielen anderen Spielanalysen und Strategien notwendig!

Möglicherweise könnte es auch einen Folgewettbewerb geben... zumindest klang das so aus einem Nebensatz in einer Mail von Luke Rendell heraus.

Lassen wir uns überraschen!

Günther Rosenbaum

[1] Social Learning Strategies Tournament
Details of Stage II and Final Results
Luke Rendell and Kevin Laland, University of St Andrews
January 5, 2009

Details of Stage I Results
Luke Rendell and Kevin Laland, University of St Andrews
November 26, 2008

[2] Social Learning Strategies Tournament
Rules for entry
Kevin Laland and Luke Rendell, University of St Andrews
4th January 2008

[3]When Innovation Matters: An Analysis of Innovation in a Social Learning Game
Ryan Carr, Eric Raboin, Austin Parker, Dana Nau ICCCD 2008 Proceedings

[4]Evolution of social learning does not explain the origin of human cumulative culture
Magnus Enquist, Stefano Ghirlanda, 2006

[5] StabilityObserver (Java) - (Matlab)

[6] Within Epsilon of Optimal Play in the Cultaptation Social Learning Game
Ryan Carr, Eric Raboin, Austin Parker, and Dana Nau (Short Paper)
AAMAS 2009.

[7] Balancing Innovation and Exploitation in a Social Learning Game
Eric Raboin, Ryan Carr, Austin Parker, Dana Nau, 2008

Kommentare lesen/schreiben
 

©2009, Westpark Gamers