Opdracht 2: strategieën vergelijken

Inleiding

Als het prisoner's dilemma meerdere keren wordt gespeeld, zijn veel strategieën denkbaar. Denk aan: altijd samenwerken, altijd verzaken, tit-for-tat, enz. We noemen een strategie succesvol als deze in vergelijking met andere strategieën een hoge opbrengst heeft. Bv. All-C is in de aanwezigheid van veel andere strategieën niet zo succesvol omdat All-C makkelijk van zich laat profiteren. Tit-for-tat is in de loop der jaren succesvol gebleken. Het presteert beter dan veel andere strategieën. Maar daarna zijn er toch ook serieuze concurrenten van TFT verschenen, denk aan Pavlov (a.k.a. “win stay, lose shift”). De vraag is nu: gegeven een aantal strategieën, bepaal welke de meest succesvolle is.

Mogelijke strategieën

Er zijn zeer veel strategieën denkbaar, varierend van eenvoudig (altijd samenwerken) tot complex (“speel C dan en slechts dan als mijn opponent in de afgelopen 10 ronden C speelde en ik in alle voorgaande ronden meer dan 70% C speelde, tenzij bla bla bla mits bla bla bla”). Strategieën worden besproken op bijvoorbeeld p. 227 van Kendall, Yao en Chong, pp. 293-305 van Flake en het artikel van Singer-Clark.

Score-tabel

Een voor de hand liggende manier om strategieën met elkaar te vergelijken is om een score-tabel aan te leggen. Hieronder zie je een een score-tabel voor zes strategieën, waarbij elk strategiekoppel 500x tegen elkaar uitkwam (bij strategieën met een random component heeft dit zin) waarbij dan telkens 100 ronden werd gespeeld:

Zes strategieën, 100 ronden, 0% ruis, 500 herstarts:

	always-cooperate	always-defect	play-randomly	unforgiving	tit-for-tat	Pavlov
always-cooperate	3	0	1.52	3	3	3	2.25
always-defect	5	1	2.99	1.04	1.04	3	2.35
play-randomly	4	0.5	2.25	0.57	2.27	2.26	1.98
unforgiving	3	0.99	2.99	3	3	3	2.66
tit-for-tat	3	0.99	2.25	3	3	3	2.54
Pavlov	3	0.5	2.24	3	3	3	2.46

Bij strategieën met een random component kunnen tabel-waarden variëren (rood). Aan het eind staan gemiddelden. Gegeven deze tabel lijkt unforgiving het best te presteren.

Spelers kunnen ook af en toe per ongeluk of expres een andere actie spelen dan hun strategie voorschrijft. Dit noemen we ruis (Eng.: noise).

Zes strategieën, 100 ronden, 5% ruis, 500 herstarts:

	always-cooperate	always-defect	play-randomly	unforgiving	tit-for-tat	Pavlov
always-cooperate	2.97	0.1	1.53	1.2	2.9	1.69	1.73
always-defect	4.85	1.07	2.96	1.12	1.2	2.97	2.36
play-randomly	3.91	0.59	2.25	0.65	2.27	2.26	1.99
unforgiving	4.18	1.06	2.92	1.51	1.58	2.94	2.36
tit-for-tat	3.02	1.04	2.25	1.44	2.42	2.36	2.09
Pavlov	3.79	0.59	2.23	1.09	2.37	2.88	2.16

Het probleem van een score-tabel is dat matige strategieën sterk lijken omdat ze profiteren van zwaktes in mindere strategieën. Bijvoorbeeld, All-D profiteert erg van naïeve strategieën zoals All-C. Als All-C er niet was dan zou All-D meteen een stuk minder presteren.

Replicator-dynamiek

Een betere manier om strategieën met elkaar te vergelijken is door aan te nemen dat deze evolueren. Dit werkt zo. We nemen aan dat er een populatie van strategieën is die zich op elk moment in een bepaalde verhouding bevindt. Dit noemen we de proportie. Een voorbeeld van een proportie is 20% All-C, 20% All-D, 10% random, 5% unforgiving, 5% TFT and 40% Pavlov. Dus hier \(p=(0.2, 0.2, 0.1, 0.05, 0.05, 0.4)\). Het idee is dat door evolutie het aandeel sterke strategieën geleidelijk aan groter, en het aandeel zwakke strategieën geleidelijk aan kleiner wordt. Dit kan worden bewerkstelligd met de discrete replicatorvergelijking. Dit werkt als volgt. Gegeven een score-tabel \(M\) en een proportie \(p=(p_1,\dots,p_n)\) met \(0\leq p_i\leq 1\) en \(\sum_i p_i=1\) wordt eerst de score (= verwachte opbrengst) van elk van de strategieën berekend: \[ s := Mp. \] Dus \(s := Mp\) is vector := matrix x vector. Bijvoorbeeld \(s_7\) is dan de score die strategie \(7\) behaalt als alle strategieën in de verhouding \(p\) aanwezig zijn. Vervolgens stipuleert de discrete replicatorvergelijking dat elk strategie-aandeel \(p_i\) in de populatie evenredig groeit met haar score: \[ q := p \circ s. \] waarbij “\(\circ\)” het Hadamard product is, dus \((q_1,\dots,q_n)=(p_1s_1,\dots,p_ns_n)\). De vector \(q\) representeert nu de juiste nieuwe verhoudingen, maar het is geen proportie, i.e., \(q\)'s elementen sommeren niet tot \(1\). De laatste stap is \(q\) te terug te brengen naar het \(n-1\)-simplex: \[ p := N(q) \quad [= \frac{1}{\sum_i q}q]. \] op deze manier geldt weer \(\sum_i p = 1\). Samengevat wordt de verhoudingsvector \(p\) elke tik als volgt ge-update: \[ p_{\text{nieuw}} := N(\;p_{\text{oud}} \circ (Mp_{\text{oud}})\;). \] Op deze manier evolueren de proporties. Dit heet de discrete replicator-dynamiek met geboorteparameter \(\beta=0\). Het werkcollegedictaat bevat een hoofdstuk met verdere uitleg.

Opbouw

Je bouwt je app in stappen op. Lees, voor je begint, ook de randvoorwaarden.

Stap 1: strategieën

1. Strategieën. Maak om te beginnen een paar makkelijke strategie-functies aan. Voorbeeld:

   to-report unforgiving [ my-history your-history ] ; ook wel bekend als
     if member? 1 your-history [ report 1 ]          ; Friedman of grim trigger
     report 0
   end
   

   Veel strategieën willen weten wie wat wanneer heeft gespeeld. Daarvoor zijn de geschiedenissen. Het cijfer 0 staat voor de eerste actie, te weten C, het cijfer 1 staat voor de tweede actie, te weten D.
2. Speel-functie. Het is handig strategie-functies aan te roepen met de zg. dispatch functionaliteit. De functie-aanroep wordt dan dynamisch met Netlogo's runresult aangemaakt.

   ; rapporteert de te spelen actie
   to-report play [ some-strategy my-history your-history ]
     report ifelse-value (random-float 1.0 < noise) [
       random 2 ; i.e., index van willekeurige actie
     ] [
       ; fabriceer de aanroepstring, en evalueer deze
       runresult (word some-strategy " my-history your-history")
     ]
   end
   

   Met play kunnen geprogrammeerde strategie-functies meteen getest worden, bijvoorbeeld: play "always-cooperate" [0 0 0 0 0] [1 0 0 1 0]. Verschijnen de laatst gespeelde acties nu vooraan of achteraan een history? Dat mag je zelf bepalen. Beide keuzes werken.

Eerste rij: score van always-cooperate tegen de rest in, zeg, 500 treffens van elk 100 ronden. Tweede rij: score van always-defect tegen de rest in, zeg, 500 treffens van elk 100 ronden. Lime is de gemiddelde score (die veranderd dus niet), oranje is gewogen score (\(Mp\)), cyaan is de startproportie, en roze is de huidige proportie.

Stap 2: de score-functie

Deze berekent voor elk gegeven strategie-koppel en voor een vast aantal herstarts, speelronden en ruispercentage (in te stellen via sliders), een empirisch gemiddelde score van het eerste element van dat koppel. De score-functie kan niet anders dan imperatief worden geprogrammeerd met een iteratie door rondes, omdat spelers een geschiedenis van zetten moeten bijhouden. (TFT wil bv. weten wat er de vorige ronde is gespeeld.)

Stap 3: de score-tabel

Als de score-tabel kan worden berekend en getoond, is het eerste gedeelte van je app af.

1. Bereken. Het idee is een lijst van lijsten (matrix) te maken, zodanig dat de eerste lijst de scores geeft van de eerste strategie t.o.v. elk van alle strategieën inclusief zichzelf. Om elke lijst te vullen kan dan de score-functie worden gebruikt. Het vullen van de matrix kan functioneel (korte code) of imperatief (makkelijker om dubbele berekeningen te vermijden).
2. Toon. Het is handig (maar niet verplicht) om de tabel in het 4e kwadrant van het canvas vullen, met de uitslag van het eerste strategie-paar op patch 0 0. Voorafgaand aan het vullen kan het canvas real time aangepast worden, bv. met

   resize-world -4 (length strategies + 2) (0 - (length strategies + 2)) 0
   

   Links worden dan vier kolommen vrijgehouden voor de strategie-namen (te plaatsen in kolom -1), rechts drie kolommen voor scores en marge, en onder drie rijen voor proporties en marge. Om het canvas op gelijke grootte te houden is het handig om de patch-grootte meteen aan te passen

   ; meer strategieen geeft kleinere patches
   set-patch-size round (192 / (length strategies))
   

Stap 4: initialiseren van een proportie

De replicator-vergelijking werkt op proporties. Er zijn verschillende manieren om een proportie te genereren: uniform, random, en biased te genereren.

1. Uniform. Als er \(n\) strategieën zijn dan is de initiële proportie \((\frac{1}{n},\dots,\frac{1}{n})\).
2. Random. Om \(n\) random getallen te genereren die sommeren tot \(1\) volstaat het niet om \(n\) random getallen te genereren en dan de verkregen \(n\)-vector terug te brengen naar het \(n-1\)-simplex (= de elementen weer te laten sommeren tot \(1\)). De gegenereerde \(n\)-vectoren zijn op deze manier dan namelijk niet uniform verdeeld over het \(n-1\)-simplex. Trek in plaats daarvan \(n\) keer een \(\text{Exp}(1)\) verdeelde variabele en breng de resulterende vector terug naar het \(n-1\)-simplex. De resulterende vector is \(\text{Dirichlet}(1,1,1)\) verdeeld en dat is uniform:

   to-report random-proportion [ n ]
     report project-on-simplex n-values n [ 0 - ln random-float 1 ]
   end
   
   ; Laat elementen tot 1 sommeren.  Alle elementen uit "list" moeten niet-
   ; negatief zijn en ten minste een element uit "list" moet positief zijn.
   to-report project-on-simplex [ list ]
     let s sum list
     report map [ x -> x / s ] list
   end
   

   Merk op dat met kans \(1\) de gegenereerde vector gekozen wordt uit het inwendige van het \(n-1\)-simplex. Dit is wenselijk omdat dat dan in elke proportie alle strategieën vertegenwoordigd zijn met kans \(1\).
3. Biased. Het is mogelijk een run van de replicator te starten met een proportie waarbij één vooraf opgegeven strategie met aandeel \(p\) aanwezig is, \(0\leq p\leq 1\), en de andere \(n-1\) strategieën uniform gekozen zijn uit het inwendige van het \(n-2\)-simplex.

Stap 5: het inbouwen van de replicator

Het programmeren van een routine die één stap van de replicator-vergelijking op een proportie uitvoert is extreem eenvoudig als functies gemaakt worden voor de volgende operaties: 1) het inwendig product van twee vectoren; 2) het Hadamard product van twee vectoren; 3) het product van een matrix en een vector (in die volgorde). Alle drie de functies zijn one-liners. Functie 3) kan gebruik maken van functie 1). (Eén stap wordt onleesbaar. Twee stappen is dan misschien sympathieker.)

Randvoorwaarden

Hier staat wat moet.* Bij afwijking van randvoorwaarden worden punten in mindering gebracht. Veel randvoorwaarden zijn opgesteld om later de beoordeling van je programma te vergemakkelijken.

1. Buttons. De app wordt geïnitialiseerd en de score-tabel wordt berekend middels een knop en routine “setup” (shortcut X). De replicator-vergelijking wordt geïnitialiseerd en uitgevoerd middels knoppen en routines “reset” (shortcut R), “step” (shortcut S) en “go” (shortcut G). De setup routine zal automatisch een reset uitvoeren.
2. Beschikbare strategieën. De lijst van beschikbare strategieën moet ten minste 10 lang zijn, te beginnen met respectievelijk All-C, All-D, random, unforgiving, TFT, en Pavlov. De rest is vrij te kiezen.
3. Speelbare strategieën. Via een slider kan worden opgegeven hoeveel strategieën meedoen. Zeg dat k gekozen is. Via een chooser kan vervolgens worden aangegeven hoe uit de lijst van 10 wordt geselecteerd. Op volgorde: de eerste k van 10, danwel a-select: een willekeurige greep van k uit 10 op voorwaarde dat All-C er altijd bij zit.
4. Canvas. Het canvas wordt bij initialisatie automatisch aangepast aan de omvang van de score-tabel (die weer afhangt van het aantal speelbare strategieën). De kleuren van de strategienamen, gemiddelde score, de door proporties gewogen score, de start-proportie en de huidige proportie zijn respectievelijk geel, lime, orange, cyan en pink. Het schaakbordpatroon (zie boven) hoeft niet te worden overgenomen, dit was om de patches te tonen.
5. Plot. Er is één plot. Behalve voor All-C worden plot-pennen dynamisch gecreëerd. Kleuren voor de eerste zes strategieën zijn respectievelijk green, red, gray, blue, violet, brown. Er wordt geplot vóór elke iteratie.
6. Tekstveld. Na initialisatie komt in het tekstveld te staan hoeveel strategieën meedoen en welke dat zijn. Vervolgens wordt een legenda van de score-tabel afgedrukt. Na een run wordt een rangorde van strategieën afgedrukt.
7. Run. Het is mogelijk om aan te geven om de hoeveel ronden een run van de replicator tijdelijk stopt. De “go” knop komt dan omhoog. Om de run voort te zetten moet deze dan opnieuw worden ingedrukt. Het is mogelijk aan te geven dat een run kan worden gestopt bij convergentie. (Er is sprake van convergentie als de proporties nauwelijks meer veranderen.)
8. Proporties. Alle drie hierboven beschreven methoden om een proportie te genereren (uniform, random, biased).
9. Scenarios. De volgende twaalf scenarios moeten met het instellen van een chooser gevolgd door één druk op een knop kunnen worden geïnitialiseerd en meteen gerund: zes proporties waarbij telkens één basis-strategie begint met 50% aandeel en de rest met 10% aandeel, met 1000 herstarts, 100 ronden, 0% ruis. De volgende zes hetzelfde maar dan met 5% ruis.

Met de standaard-implementatie kunnen maximaal acht punten worden verdient.

Extra

Extra punten kunnen worden gescoord door het aanbrengen van één van de volgende features, tot een maximum van tien punten. Als er meerdere features zijn geïmplementeerd telt het best uitgevoerde feature. Het ontbreken van een onderdeel uit de basis-implementatie kan niet worden gecompenseerd met een extra feature.

1. Statistieken (2 pt). I.h.a. hangt de limiet van de replicator, naast de score-tabel, af van de begin-proportie. Genereer voor een vaste score-tabel een groot aantal keer een willekeurige proportie en maak een overzicht (bv. een histogram) van het gewicht van strategieën na convergentie.
2. Nash evenwicht (I) (2 pt). Er is een stelling die zegt dat, als de begin-proportie zich in het inwendige van het n−1-simplex bevindt, en de replicator-dynamiek convergeert, het limietpunt dan een Nash-evenwicht is. Het vinden van Nash-evenwichten is notoir moeilijk. Het controleren of een proportie een Nash-evenwicht is, is echter makkelijk. Schrijf een functie die op een naïeve manier controleert of een limiet van de replicator Nash is.
3. Nash evenwicht (II) (2 pt). Download de command line tool gambit-enummixed van Gambit en zet 'm in de Netlogo dir. Download de shell extensie van Netlogo en zet 'm in Netlogo's extensions dir. Met deze twee hulpmiddelen is het mogelijk Nash-evenwichten in Netlogo uit te rekenen, en deze te vergelijken met de limietputen van de replicator. Snippets:

   let matrix-row-player [[3 0] [5 1]] ; prisoner's dilemma, dimension is 2
   let matrix-col-player [[3.2 0.2] [5.2 1.2]] ; bijna prisoner's dilemma
   

   Bouw invoer string op:

   let gambit-input fabricate-gambit-input matrix-row-player matrix-col-player
   

   Gambit input is nu NFG 1 R "" { "1" "2" } { 2 2 } 3 3.2 5 0.2 0 5.2 1 1.2. Zet deze in een shell variabele:

   shell:setenv "GAMBIT_INPUT" gambit-input
   

   Roep Gambit aan en vang de uitvoer op:

   let gambit-output (shell:exec "cmd" "/c" "echo" ; windows shell command
                                 "%GAMBIT_INPUT%" "|" "gambit-enummixed" "-q")
   

Tips

1. Score-tabel. Het berekenen van de score-tabel is een tijdrovende operatie. Om te voorkomen dat de score-tabel onnodig wordt herberekend kun je bijhouden of relevante sliders tussentijds zijn veranderd. Zo niet, dan hoeft de score-tabel ook niet opnieuw te worden berekend.
2. Onderscheid. Het berekenen en tonen van de score-tabel staat bijna volledig los van de replicator-vergelijking. De parameters restarts, rounds en noise, bijvoorbeeld, zijn alleen nodig voor het berekenen van de score-tabel, en niet voor de replicator-dynamiek. Aan de andere kant heeft de notie proportie alleen maar betekenis in de replicator-dynamiek. Dus de oranje kolom en de cyaan en roze rij kunnen pas getoond worden als een proportie bekend is, bijvoorbeeld aan het begin van een run van de replicator.
3. Voorbeeld-interface

Toelichting: setup zet alles klaar en berekent de score-tabel. reset genereert een initiële proportie voor de replicator. step voert één stap van de replicator uit, go meerdere. strategy-to-bias en bias worden alleen gebruikt bij de “biased” initialisatie. Het rode vierkant geeft aan dat er gestopt is vanwege convergentie. (Tijdens een run is het vierkant zwart en bij een stop anders dan convergentie is het vierkant oranje.) Voor het selecteren van scenarios is er voor gekozen om geen namen te gebruiken (“scenario 1, scenario 2, ...”) maar een directe lijst van parameterwaarden, waarvan eigenlijk alleen de ruispercentages en startproporties variëren.

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt.

   ------------------------------------------------------

    1. GUI (compleet, net, logisch georganiseerd)
    2. code-organisatie
    3. correcte code
    4. implementatie initialisatie-methoden, waaronder score-tabel
    5. implementatie replicatorvergelijking
    6. correcte werking mechanismen setup, reset, step, go, scenario draaien
    7. correcte dynamiek, correcte plots scenarios 1-12
    8. documentatie (in code, in tab, *.png)

   ----- cijfer acht ------------------------------------

    9. best of extra feature
   10. "

   ----- cijfer tien ------------------------------------

Reflectie

Tot slot doen we even een stapje terug. Wat zijn we aan het testen en waarop testen we? Wel, we testen verschillende zogenaamde reactieve strategieën

S = { All-C, All-D, TFT, Unforgiving, Pavlov, Eatherly, ... }

G = { prisoner's dilemma }.

In het mastervak multi-agent learning werd in het academisch jaar 2019-20 een opdracht uitgeschreven waarin de experimentele opzet er zo uitzag:

S = { Random, No-regret learning, Fictitious Play, Satisficing Play, ε-Greedy learning, Bully, UCB, ... }

G = { constant sum games, cooperation games, tragedy of the commons games, ... }.

Het verschil tussen reactieve en lerende is overigens minder duidelijk dan hierboven misschien werd gesuggereerd. Neem Eatherly. Deze strategie werkt samen met een kans die gelijk is aan het samenwerkingspercentage van de opponent. Met wat goede wil zou je kunnen zeggen dat Eatherly dus leert van het gedrag van z'n opponent. Omgekeerd is Bully geen lerende, maar een koppige strategie die, nadat hij zijn tegenstander heeft bestudeerd, één actie kiest en die alle ronden speelt. Het is meer zo dat de strategieën uit de masterfase bedoeld zijn om goed te werken op alle speltypen, en niet alleen maar op het prisoner's dilemma.

Zie ook

• Morality Metrics On Iterated Prisoner’s Dilemma Players Tyler Singer-Clark, 2014 (lokale kopie).
• Blz. 227 van The Iterated Prisoners' Dilemma: 20 Years on, Graham Kendall, Xin Yao, Siang Yew Chong, 2007
• Complex strategies in the iterated prisoner’s dilemma door Jean-Paul Delahaye en Philippe Mathieu. In: Chaos and society 29 (1995), pp. 283-292.
• Blz. 293-301 van The Computational Beaty of Nature, Gary Flake, 1998.
• Generate uniformly distributed weights that sum to unity (stack exchange).
• Oude practicumopdracht met als onderwerp het ruimtelijk geïtereerde gevangenen-dilemma. Deze opdracht heeft veel gemeen met de huidige opdracht en bevat veel code-voorbeelden. Het is aan te raden daar even naar te kijken.
• Stelling 11.5.3, blz. 239 uit: Dynamical systems, Shlomo Sternberg, Courier Corporation (2010).

Wijzigingen

08 maart 2018

“De simplex” → “het simplex”. (Nederlandstalige Wikipedia vermeldt overigens “de”.)

10 maart 2018

N.a.v. vragen op vrijdag 09 maart nog een stukje uitleg toegevoegd (kopje “Onderscheid”). Enkele aanvullingen in de uitleg, enkele wijzigingen in de layout. (Geen inhoudelijke aanvullingen of wijzigingen van de opdracht.)

12 maart 2018

Nog even met twee woorden in de inleiding duidelijk gemaakt dat het om het PD gaat. (De tekst is hierdoor feitelijk een handvol woorden korter geworden.)