![\"\"\/](\"https:\/\/www.westpark-gamers.de\/Ressourcen3\/cultaptation_t.jpg\")
<\/span><\/p>\nvon G\u00fcnther Rosenbaum<\/h4>\n
Lange hat es gedauert – doch mittlerweile ist die Gewinnerstrategie des Cultaptation Wettbewerbs
\nermittelt worden und die Autoren haben ihren Preis auf der EHBEA 2009 conference in St Andrews
\nentgegengenommen. Die Strategie “Discountmachine” der Autoren Dan Cownden und Tim
\nLillicrap hat mit gutem Abstand gegen\u00fcber den Konkurrenten gewonnen.<\/p>\n
Zitat[1]:
\n
\n“There are a number of ways in which this strategy stands out and that may have contributed
\nto its success. The first is that it attempts to characterise the environment in a highly
\ncomprehensive way, extracting a lot of information from its prior experiences, and is responsive to
\nthat information. The second is that this strategy explicitly makes decisions based on expected
\nlifetime outcomes, rather than immediate payoff benefits. Finally, the strategy is noteworthy for
\nthe sophistication of the mathematics it uses to calculate expected payoffs.<\/i>“<\/p>\n
Manche Dinge in diesem Wettbewerb scheinen auf der Hand zu liegen – denn jedem ist es irgendwie
\nklar, dass das Kopieren einer “guten” Aktion (leider kopiert man aber nicht immer nur
\ngute Aktionen) einfacher ist als das Finden einer guten Strategie durch wiederholte Trial &
\nError Versuche.<\/p>\n
Dazu noch ein weiteres, etwas l\u00e4ngeres Zitat aus den Wettbewerbsregeln[2], welches den Stand der
\naktuellen Forschungen wiedergibt; ich m\u00f6chte jedem empfehlen, diesen Absatz vorab und in Ruhe
\ndurchzulesen:<\/p>\n
“It is commonly assumed that social learning is inherently worthwhile. Individuals are
\ndeemed to benefit by copying because they take a short cut to acquiring adaptive information,
\nsaving themselves the costs of asocial (e.g. trial-and-error) learning. Copying, it is assumed, has
\nthe advantage that individuals do not need to re-invent technology, devise novel solutions, or
\nevaluate environments for themselves. Intuitive though this argument may be, it is flawed (Boyd
\n& Richerson 1985; Boyd & Richerson 1995; Rogers 1988; Giraldeau et al. 2003). Copying
\nothers per se is not a recipe for success. This is easy to understand if social learning is
\nregarded as a form of parasitism on information (Giraldeau et al. 2003): asocial learners are
\ninformation producers, while social learners are information scroungers. Game-theoretical models of
\nproducer-scrounger interactions reveal that scroungers do better than producers only when fellow
\nscroungers are rare, while at equilibrium their payoffs are equal (Barnard & Sibly 1981).
\nSimilarly, theoretical analyses of the evolution of social learning in a changing environment (e.g.
\nBoyd & Richerson 1985; Boyd & Richerson 1995; Rogers 1988; Feldman et al. 1996) reveal that
\nsocial learners have higher fitness than asocial learners when copying is rare, because most
\n‘demonstrators’ are asocial learners who will have sampled accurate information about the
\nenvironment at some cost. As the frequency of social learning increases, the value of copying
\ndeclines, because the proportion of asocial learners producing reliable information appropriate to
\nthe observer is decreasing. An equilibrium is reached with a mixture of social and asocial learning
\n(Enquist et al. 2007). These mathematical analyses, together with more conceptual theory (e.g.
\nGalef 1995), imply that copying others indiscriminately is not adaptive; rather, individuals must
\nuse social learning selectively, and learn asocially some of the time. Natural selection in animals
\ncapable of social learning ought to have fashioned specific adaptive social learning strategies
\nthat dictate the circumstances under which individuals will exploit information provided by others
\n(Boyd & Richerson 1985; Henrich & McElreath 2003; Laland 2004; Schlag 1998). At present, it
\nis not clear which social learning strategy, if any, is best. The tournament has been set up to
\naddress this question.<\/i>“<\/p>\n
Es galt also eine Strategie zu finden, die<\/p>\n
- \n
- den optimalen Zeitpunkt und die optimale H\u00e4ufigkeit von sozialem Lernen (Observe) nutzt,<\/li>\n
- die gelernten und ausgef\u00fchrten Aktionen der Vergangenheit analysiert und daraus
\nSchlussfolgerungen f\u00fcr die Zukunft zieht,<\/li>\n - bei Bedarf auch gelegentlich asoziales (Innovate) Lernen nutzt.<\/li>\n<\/ul>\n
Bevor ich aber die Ergebnisse noch etwas detaillierter betrachte, m\u00f6chte ich meine eigene
\nStrategie etwas erl\u00e4utern; wer m\u00f6chte, kann sich auch den Java und Mathlab Code im Detail
\nanschauen[5].<\/p>\nIn der paarweisen Simulation (nur die betrachte ich hier) treten jeweils 2 gegnerische
\nStrategien \u00fcber 10000 Runden gegeneinander an – die besser an die Umgebung angepasste Strategie
\nwird sich dabei h\u00e4ufiger vermehren und den Gegner in seine Schranken verweisen! (F\u00fcr den genauen
\nAblauf der Simulationen siehe [2])<\/p>\nJede Strategie hat folgende 3 Aktionsm\u00f6glichkeiten in jeder Runde:<\/p>\n
- \n
- EXPLOIT (benutzen)Dies ist die wichtigste und vermutlich h\u00e4ufigste aller Aktionen.
\n
\nIndem ich eine in einer fr\u00fcheren Runde gelernte Aktion meines Repertoires benutze, erhalte ich
\neinen Ertrag und st\u00e4rke damit meine Fitness (wenn der Ertrag gen\u00fcgend hoch ist) … und bei h\u00f6herer
\nFitness ist meine Fortpflanzungsrate h\u00f6her.<\/li>\n - OBSERVE (nachahmen, kopieren, soziales Lernen)
\n
\nBei Observe lerne ich eine der Aktionen, die ein zuf\u00e4llig ausgew\u00e4hlter Simulationsteilnehmer in der
\nVorrunde ausgef\u00fchrt hatte. Wenn ich davon ausgehe, dass dessen Strategie eine ertragreiche Aktion
\ngew\u00e4hlt hatte und ich diese Aktion noch nicht kannte, dann habe ich jetzt auch eine gute Aktion in
\nmeinem Repertoire.
\n
\nLeider (oder vielleicht gl\u00fccklicherweise) ist das Abschauen auch fehlerbehaftet; der Ertrag ist
\netwas verf\u00e4lscht und manchmal geht das Abkupfern v\u00f6llig in die Hose – ich erhalte dann eine
\nzuf\u00e4llige Aktion (\u00e4hnlich zu Innovate!).
\n
\nIn der zweiten Stufe des Wettbewerbes war es auch m\u00f6glich, dass ein OBSERVE nicht nur eine Aktion
\nerlernt, sondern bis zu 6 Aktionen!<\/li>\n - INNOVATE (Trial&Error, asoziales Lernen)
\n
\nHierbei erlerne ich zuf\u00e4llig eine der 100 Aktionen (inklusive des Ertrages) der
\nSimulationsumgebung. Dies kann eine gute, schlechte oder sogar schon bekannte Aktion sein. Die
\nErtr\u00e4ge einer gelernten Aktion \u00e4ndern sich \u00fcber die Zeit mit einer festen, aber unbekannten
\nWahrscheinlichkeit.<\/li>\n<\/ol>\nDummerweise wei\u00df ich auch nicht im voraus, welche Werte die Ertr\u00e4ge annehmen k\u00f6nnen – ist 20
\nschon ein hoher Ertrag oder erst 150? Eine Aktion, die momentan 50 bringt, kann in wenigen Runden
\nnur noch 0 wert sein – denn diese Ertr\u00e4ge sind Zufallsvariablen.<\/p>\nEine vermutlich gute Aktion werde ich h\u00e4ufig so lange benutzen (Exploit), bis sich pl\u00f6tzlich der
\nErtrag ver\u00e4ndert: Man beachte, dass man in diesem Fall wieder so etwas wie ein Innovate ausf\u00fchrt –
\ndie Aktion erh\u00e4lt einen neuen, zuf\u00e4lligen Ertragswert!<\/p>\nMehrere unabh\u00e4ngige Wahrscheinlichkeitsverteilungen beeinflussen die Umwelt w\u00e4hrend einer
\nSimulationsreihe; diese Verteilungen werden vor einem Durchgang fixiert und \u00e4ndern sich dann f\u00fcr
\neine ganze Testreihe nicht mehr (ein Individuum kann also w\u00e4hrend seiner Lebenszeit von
\ndurchschnittlich 50 Jahren diese Parameter zu sch\u00e4tzen versuchen). Dummerweise kannte man vor dem
\nWettbewerb nur einige grobe Eckwerte dieser Parameter – einige Dinge sind auch im Nachhinein noch
\nnicht komplett offengelegt.<\/p>\nJedes Individuum innerhalb der Simulation hat jede Runde (aber unabh\u00e4ngig vom Alter!) eine
\nSterbewahrscheinlichkeit von 2%. – stirbt jemand, so sofort wieder ein Kind geboren. Um die
\nStrategie des Kindes festzulegen, wird ein “Vorfahre” aus allen 100 Individuen (eigene
\nund gegnerische) zuf\u00e4llig gew\u00e4hlt – wobei die Auswahlwahrscheinlichkeit proportional zur Fitness
\n(durchschnittlicher Ertrag pro Runde) gew\u00e4hlt wird. Zus\u00e4tzlich tritt mit 2% Wahrscheinlichkeit noch
\neine Mutation auf, bei der der Nachfolger eine gegnerische Strategie nutzt.<\/p>\nJedes Individuum hat nur die Informationen aller gelernten oder ausgef\u00fchrten Aktionen seit
\nseiner Geburt als Entscheidungskriterium f\u00fcr seinen n\u00e4chsten Zug zur Verf\u00fcgung: Wie w\u00fcrdet ihr
\njetzt eine gute Strategie formulieren, die m\u00f6glichst fit ist, um sich gut fortzupflanzen und die
\nsich gegen die Mutanten erfolgreich wehrt?<\/p>\nAufgrund der vielen Unbekannten dreht man sich da immer wieder im Kreis…<\/p>\n
Meine Strategie “StabilityObserver” habe ich dann folgenderma\u00dfen festgelegt:<\/p>\n
- \n
- Um immer etwa 2% Innovationen (und damit “frisches Blut”) im eigenen Volk zu haben,
\nwurde in der ersten Runde eines jeden Individuums immer INNOVATE ausgef\u00fchrt.(Nat\u00fcrlich muss man
\nnicht selbst Innovate ausf\u00fchren – es gen\u00fcgt auch, dass gegnerische Individuen dies tun und man dies
\ndann kopiert). Die zweite und dritte Runde bestanden dann aus OBSERVE und EXPLOIT.<\/li>\n - Die Strategie sch\u00e4tzt die Stabilit\u00e4t ihrer Umgebung (payoff mutation rate), indem sie
\nberechnet, wie lange die ausgef\u00fchrten Aktionen in ihrer Vergangenheit ihren Ertrag nicht gewechselt
\nhaben. Der Mittelwert hiervon ist in etwa der Kehrwert der payoff mutation rate.<\/li>\n - Wenn die Stabilit\u00e4t der Umgebung gering ist (die Ertr\u00e4ge bleiben nur kurze Zeit stabil), dann
\nmacht es keinen Sinn Zeit zu verschwenden und immer wieder etwas Neues zu lernen. In diesem Fall
\nsollten die vorhandenen Aktionen einfach benutzt werden (und seltener gelernt werden).<\/li>\n - Ist die Stabilit\u00e4t der Umgebung sehr hoch, so wechseln die Ertr\u00e4ge der Aktionen nur sehr
\nselten. Um zu vermeiden, dass wir eine ung\u00fcnstige Aktion zu lange benutzen, wird jede 10te Runde
\nein OBSERVE eingeschoben – ansonsten wird die beste bekannte Aktion mit EXPLOIT benutzt.<\/li>\n - Bei mittlerer Stabilit\u00e4t wird immer dann ein OBSERVE eingeschoben, wenn der Ertrag der aktuell
\nausge\u00fcbten Aktion unterhalb des oberen Quartils aller bisher in der eigenen Lebensdauer gesehenen
\nErtr\u00e4ge rutscht. Nach einem OBSERVE kommt aber immer erst ein EXPLOIT.<\/li>\n - Die Umsetzung dieser Vorgaben ins Programm geschah eher qualitativ – die echten Zahlenwerte f\u00fcr
\ndie Begriffe\/Parameter in der obigen Beschreibung habe ich dann durch Testsimulationen heuristisch
\nbestimmt(wobei die Bereiche gleitend ineinander \u00fcbergehen).<\/li>\n<\/ul>\nWarum hei\u00dft die Strategie “StabilityObserver”? Nun, weil sie einerseits die Stabilit\u00e4t
\nihrer Umwelt “beobachtet” und andererseits fast ausschlie\u00dflich durch “OBSERVE”
\nlernt!<\/p>\nEinen Link auf die eingereichten Wettbewerbsunterlagen mit Java-Code sowie die Umsetzung auf
\nMatlab-Code findet Ihr am Ende dieses Berichtes [5].<\/p>\nNun, diese Strategie hat es nur (immerhin?) bis auf Platz 11 von 104 Einsendungen geschafft.
\nAber wie sah die Strategie des Siegers “Discountmachine” aus?<\/p>\nHier eine grobe Beschreibung der Siegstrategie; Zitat[ 1]:<\/p>\n
Our creature does three major things:<\/p>\n
First it estimates\/calculates, what we believe to be all the
\npertinent parameters of the simulation as well as a few other quantities that we believe to be
\nuseful. These are P_c, the mean of the payoff distribution, the mean of of the observed values, the
\ncorrelation between observe and exploit values of the same action, N_observe, and where applicable
\nthe number of data points used to make these estimates.<\/p>\nSecond it uses some of these parameters to estimate the expected
\npayoff for performing each action in its repertoire. Once it has a best exploit chosen from its
\nrepertoire it compares the value of Exploiting to the value of Observing using a geometric
\ndiscounting scheme based on our estimate of P_c and the given probability of death.<\/p>\nLastly a machine learned function, takes into account N_observe and
\nthe estimates on the reliability of observing and P_c to adjust the value of Observing accordingly.
\nOur creature then chooses whichever action has the higher perceived value, Observing or Exploiting.
\nAs a side note our creature only Innovates when it has an empty repertoire and observe doesn’t
\nwork, which typically is only on the first turn of a simulation.<\/p>\nWorin liegt nun der Unterschied zu meiner Strategie?<\/p>\n
So wie es aussieht, werden hier wohl die verschiedenen variablen Parameter der Umwelt recht
\ngenau gesch\u00e4tzt (ich habe nur einen einzigen Parameter grob gesch\u00e4tzt).<\/p>\nAnschlie\u00dfend versucht man, die erwarteten zuk\u00fcnftigen Ertr\u00e4ge einer EXPLOIT und einer OBSERVE
\nAktion abzusch\u00e4tzen.<\/p>\nEin vereinfachtes Beispiel:<\/p>\n
Gehen wir von einer recht variablen Umgebung aus, in welcher Aktionen im Mittel nur etwa 5
\nRunden stabil sind. F\u00fchre ich nun z.B. 5-mal eine Aktion mit dem Ertrag 100 aus, so habe ich hier
\nalso eine Fitness von 500\/5 = 100.<\/p>\nF\u00fchre ich aber zuerst ein OBSERVE (hat immer Ertrag 0) durch und lerne tats\u00e4chlich eine bessere
\nAktion mit Ertrag 110, so erhalte ich eine Fitness von 0+110+110+110+110+110\/6 = 550\/6 = ca. 92.
\nOBSERVE w\u00e4re hier also die schlechtere Alternative!<\/p>\nHat man also gute Sch\u00e4tzwerte der Parameter, so kann man recht gute Entscheidungen treffen (wohl
\nnoch unterst\u00fctzt durch entsprechende Abzinsung der zuk\u00fcnftigen Ertr\u00e4ge).<\/p>\nBei mir ist das ungenauer, mehr auf qualitativer denn auf quantitativer Weise geschehen. Zu
\nguter Letzt habe ich die vermeintlich geringen Effekte der “Kopierfehler” einfach
\nignoriert.<\/p>\nEine extrem vereinfachte Form des Wettbewerbes (kein OBSERVE, stabile Umgebung,
\nVerteilungsfamilie der Aktionswerte bekannt, etc. …) wurde in [3] nach dem Wettbewerb
\nmathematisch analysiert: Als Kind lernen (INNOVATE), mit mathematischen Methoden den optimalen
\nStoppzeitpunkt f\u00fcr den Abbruch des Lernens bestimmen und dann bis zum Lebensende arbeiten (EXPLOIT)
\n… das ist dort die traurige Wahrheit f\u00fcr ein optimales Individuum!<\/p>\nEinen solchen optimalen “Smart Innovator” habe ich in der eigenen Simulationsumgebung
\nbei stabiler Umgebung gegen den StabilityObserver antreten lassen: Es ist wohl klar, dass der Smart
\nInnovator ohne “Observe” keine Chance gegen den StabilityObserver hatte!<\/p>\nIn [7] wird der Ansatz des Smart Innovators nochmal etwas modifiziert: Will man die
\nFortpflanzungswahrscheinlichkeit optimieren, so muss man manchmal schon als Kind EXPLOIT nutzen.
\nTja, kommt man etwas n\u00e4her an die realen Wettbewerbsbedingungen, so wird es auch schon wieder etwas
\nkomplizierter… Des weiteren muss man beachten, dass “einfache” optimale
\nStrategien\/Nash-Gleichgewichte auch nur einen garantierten Ertrag gegen jeden Gegner garantieren –
\nbei Wettbewerben muss man allerdings auch und gerade schwache Gegner m\u00f6glichst hoch besiegen um
\neine hohe Gesamtpunktzahl zu erreichen.<\/p>\nInteressant und \u00fcberraschend war die Strategie des Zweitplazierten “Intergeneration”.
\nZitat[1]:<\/p>\n“My main idea is (although it seems not be as good as I expected) that an important
\ninformation for the young is, how much is the “good” payoff (with how much I can be
\nhappy). If I have so much or more, I would just EXPLOIT until it changes, otherwise I would 8 times
\nexploit and once observe.<\/i><\/p>\nThe important trial is that the old could “say” something
\nto the young, by “signaling” something to the young. The signal consists of doing an act
\nwhose number is divisible by 8. If the fraction is 1,2,3,4 this means that “payoff 8 is very
\ngood”, 5,6,7,8 means “payoff 20 is very good” and 9,10,11,12 means “payoff 40
\nis very good”.<\/p>\nIf the old does not have this in his repertoire, he innovates. If he has more than one of
\nthese 4 possible “symbol” acts, he uses that with highest payoff — because it is a
\nhigher chance that this will diffuse. Even the “opponent” can help spread out this
\nsignal, without knowing that.<\/i> “<\/p>\nHuch! Das sieht ja so aus, als wollte da jemand schummeln, denn laut Regeln gibt es eigentlich
\nkeinen Kontakt und Informationsaustausch zwischen verschiedenen Individuen! Luke Rendell, einer der
\nOrganisatoren des Wettbewerbes sagt dazu:<\/p>\n“We thought about whether it was cheating or not but decided to let it go. I am
\ninvestigating the properties of this strategy in more detail right now. I think that the
\n‘signalling’ part of the strategy made very little difference \u2026<\/i> “<\/p>\nIntergeneration war wohl aber auch der einzige Teilnehmer, der etwas grenzwertige Methoden
\nbenutzte – alle anderen haben sich nicht nur dem Worte sondern auch dem Sinne nach an die Regeln
\ngehalten.<\/p>\nEs wird sicherlich auch noch eine wissenschaftliche Auswertung der besten Strategien geben – da
\nbin ich schon drauf gespannt (z.B. [6]); auch die Organisatoren werden hierzu noch Informationen
\nver\u00f6ffentlichen (aber im Moment noch nicht verf\u00fcgbar)!<\/p>\nDie besten Strategien in diesem Wettbewerb waren sicherlich nicht so elegant und allgemein
\nverst\u00e4ndlich wie damals die “Tit for Tat” Strategie im Wettbewerb von Axelrod; viele
\nTeilnehmer haben zul\u00e4ssige mathematische Methoden benutzt – dies hat nat\u00fcrlich nichts mit Mogeln zu
\ntun und ist auch bei vielen anderen Spielanalysen und Strategien notwendig!<\/p>\nM\u00f6glicherweise k\u00f6nnte es auch einen Folgewettbewerb geben… zumindest klang das so aus einem
\nNebensatz in einer Mail von Luke Rendell heraus.<\/p>\nLassen wir uns \u00fcberraschen!<\/p>\n
G\u00fcnther Rosenbaum <\/i> <\/p>\n
[1] Social Learning Strategies Tournament
\n
\nDetails of Stage II and Final Results<\/a>
\n
\nLuke Rendell and Kevin Laland, University of St Andrews
\n
\nJanuary 5, 2009<\/p>\nDetails of Stage I Results<\/a>
\n
\nLuke Rendell and Kevin Laland, University of St Andrews
\n
\nNovember 26, 2008<\/p>\n[2] Social Learning Strategies Tournament
\n
\nRules for entry<\/a>
\n
\nKevin Laland and Luke Rendell, University of St Andrews
\n
\n4th January 2008<\/p>\n[3]When
\nInnovation Matters: An Analysis of Innovation in a Social Learning Game<\/a>
\n
\nRyan Carr, Eric Raboin, Austin Parker, Dana Nau ICCCD 2008 Proceedings<\/p>\n[4]Evolution of social learning does not explain the origin of human cumulative culture<\/a>
\n
\nMagnus Enquist, Stefano Ghirlanda, 2006<\/p>\n[5] StabilityObserver (Java<\/a>) – (Matlab<\/a>)<\/p>\n
[6] Within Epsilon of Optimal Play in the Cultaptation Social Learning Game<\/a>
\n
\nRyan Carr, Eric Raboin, Austin Parker, and Dana Nau (Short Paper)
\n
\nAAMAS 2009.<\/p>\n[7] Balancing
\nInnovation and Exploitation in a Social Learning Game<\/a>
\n
\nEric Raboin, Ryan Carr, Austin Parker, Dana Nau, 2008<\/p>\n","protected":false},"excerpt":{"rendered":"Cultaptation – Das Ergebnis und ein Beispiel von G\u00fcnther 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\u00fcber … Cultaptation – Das Ergebnis und ein Beispiel<\/span> weiterlesen
- Um immer etwa 2% Innovationen (und damit “frisches Blut”) im eigenen Volk zu haben,
- EXPLOIT (benutzen)Dies ist die wichtigste und vermutlich h\u00e4ufigste aller Aktionen.