| BSc KI — Cursus Natuur & Berekening | 2025-26 |
In deze opdracht laat je individuen het prisoner's dilemma spelen.
Als het prisoner's dilemma eenmalig wordt uitgevoerd, hebben beide spelers de neiging om te verzaken, terwijl ze beter af zouden zijn door samen te werken. Samenwerking (en dus een hogere opbrengst) kan ontstaan als partijen opereren in een sociale omgeving, en handelen op basis van eerdere interacties, en na interacties strategieën overnemen van meer succesvolle spelers uit hun omgeving.
|
en neem aan dat de episode-lengte gelijk is aan 100. In de eerste ronde zal de middelste speler (met strategie TFT) C spelen tegen alle buren en 4x3=12 eenheden verdienen. (Ga na!) In elke volgende ronde zal de middelste speler C spelen tegen “altijd C” en “TFT”, en D spelen tegen alle permantente verzakers en dus elke ronde 4x3 + 4x1=16 eenheden verdienen. Na 100 ronden is er een gemiddelde opbrengst. Voor de middelste speler is dat
C D C (3,3) (0,5) D (5,0) (1,1)
(1 ronde x 12 + 99 ronden x 16) / (8 buren x 100 ronden) = 1596/800 = 1,995.
Na elke episode vergelijkt elke speler zijn gemiddelde opbrengst met die van zijn buren, en adopteert de strategie van degene met de hoogste opbrengst. Als er meerdere spelers zijn met een hoogste opbrengst dan wordt de strategie willekeurig uit die spelers gekozen. Het is mogelijk dat de speler zelf de hoogste opbrengst genereert en daardoor niet van strategie veranderd. Ook is het mogelijk dat de speler zelf bij de groep met hoogste opbrengst hoort, dat de groep met hoogste opbrengst uit meer dan twee cellen bestaat, en dat de centrale speler de strategie van een andere cel adopteert. Dus een speler kan van strateige veranderen, zelfs als deze een hoogste opbrengst scoort.
De uitdaging is om te zien of spelers, die elk hun eigen plan volgen, desondanks evolueren naar samenwerking.
Hier staat wat moet. Bij afwijking van randvoorwaarden worden punten in mindering gebracht.
Er wordt een acht gescoord als volledig aan alle randvoorwaarden is voldaan.
always-cooperate, always-defect,
play-randomly, unforgiving, tit-for-tat en Pavlov incorporeren en de dynamiek moet vergelijkbaar zijn met de convergentie-tabellen.4949 always-cooperate 3525 eatherly 3304 Pavlov 996 forgiving-tit-for-tat 611 unforgiving 315 always-defect 275 tit-for-tat 271 tit-for-two-tats 47 Joss-5% 13 pessimistic-tit-for-tatDe frequentie van verdwenen strategieën wordt niet afgedrukt. Links-padden met spaties (zoals hier) zou netjes zijn maar het hoeft niet.
|
|
Een perzisch tapijt met uitbetalingen reward, temptation, sucker en punishment resp. 1, 1.8, 0, en 0, en één patch op always-defect in een zee van always-cooperate. |
|
Extra punten kunnen worden verdiend door het aanbrengen van extra features. Het aantal extra punten hangt af van het gewicht van een feature en de implementatie-kwaliteit. Voorbeelden:
strategiewisselingen = 0.95×strategiewisselingen + 0.05×δstrategie, vorige strategiewaarbij δi,j de zg. Kronecker deltafunctie is. Kleur vervolgens de patch met
scale-color. Makkelijk te implementeren.
Tot zover de opdrachtbeschrijving. Hierna volgen wat tips, een samenvatting van nakijkmodel, wat referenties, een overzicht van wijzigingen, en helemaal onderaan snippets.
|
| Killer-strategie |
Zes strategieën, 20 ronden, 0% ruis, 1000 herstarts:
| always-cooperate | always-defect | play-randomly | unforgiving | tit-for-tat | Pavlov | |
|---|---|---|---|---|---|---|
| always-cooperate | 3 | 0 | 1.52 | 3 | 3 | 3 |
| always-defect | 5 | 1 | 2.99 | 1.2 | 1.2 | 3 |
| play-randomly | 4 | 0.5 | 2.25 | 0.85 | 2.33 | 2.35 |
| unforgiving | 3 | 0.95 | 2.84 | 3 | 3 | 3 |
| tit-for-tat | 3 | 0.95 | 2.22 | 3 | 3 | 3 |
| Pavlov | 3 | 0.5 | 2.22 | 3 | 3 | 3 |
Zes strategieën, 20 ronden, 5% ruis, 1000 herstarts:
| always-cooperate | always-defect | play-randomly | unforgiving | tit-for-tat | Pavlov | |
|---|---|---|---|---|---|---|
| always-cooperate | 2.98 | 0.1 | 1.55 | 2.37 | 2.9 | 2.2 |
| always-defect | 4.84 | 1.07 | 2.98 | 1.27 | 1.34 | 3.01 |
| play-randomly | 3.91 | 0.6 | 2.25 | 0.94 | 2.33 | 2.34 |
| unforgiving | 3.35 | 1.02 | 2.82 | 2.33 | 2.41 | 2.9 |
| tit-for-tat | 3.02 | 1 | 2.21 | 2.31 | 2.74 | 2.64 |
| Pavlov | 3.48 | 0.58 | 2.23 | 2.2 | 2.67 | 2.88 |
Bij strategieën met een random component of bij runs met ruis kunnen tabel-waarden afwijken (rood). Door het relatief hoge aantal herstarts is de spreiding klein.
Het volgende nakijkmodel zal worden gebruikt.
-----------------------------------
1. nette en intuitieve GUI
2. kleuren en veldgrootte kloppen
3. documentatie (in code, in tab, *.png)
4. code-organisatie
5. efficiente code / snelle executie
6. dynamiek is symmetrisch (i.e., patch-update dynamiek klopt) (*)
7. juist gedrag always-C, always-D, random, unforgiving, TFT en Pavlov (**)
8. grafiek en ranglijst van proporties
(*) Controleer met eenvoudig Perzisch tapijt.
(**) Dit vergt wat tijd om na te kijken. Het werkt denk ik 't best als je, met het convergentiegedrag van deze zes strategieën in het achterhoofd, enkele steekproeven neemt met deelverzamelingen van { always-cooperate, always-defect, play-randomly, unforgiving, tit-for-tat en Pavlov }. Als combinaties niet kloppen dan zie je dat snel genoeg.
(***) Het ontbreken van een basis-feature kan niet worden gecompenseerd met een extra feature. Een evt. 3e punt van extra feature 8 wordt naar het oordeel van de beoordelaar meegewogen in het totaalcijfer.
----- cijfer acht -----------------
9. extra feature 1
10. extra feature 2
----- cijfer tien -----------------
to normalize-strategy-ratios aangepast zodat deze ook werkt in NL6.
Specifiek is run (word "set start-" ?1 " precision (start-" ?1 " / sum-of-strategies ) 2") veranderd naar run (word "set start-" ?1 " precision (start-" ?1 " / " sum-of-strategies " ) 2"). Dus sum-of-strategies evalueert in dit stukje nu mee.
c terug veranderd in normalize-strategy-ratios.
Hieronder volgen code snippets (codefragmenten). De snippets zijn facultatief. Het is niet verplicht ze te gebruiken, we hebben misschien zelfs liever dat je je eigen code schrijft. De snippets behoren niet tot de opdracht, en zijn zeker niet bedoeld als stappenplan. De snippets zijn meer bedoeld om je op weg te helpen mocht je vastlopen. De werking van de snippets is niet gegaranderd, en de practicumleiding is niet verplicht om er uitleg over te geven.
payoff-matrix, een lijst van lijsten strategy-colors om een koppeling te maken tussen strategieën en kleuren, een lijst van strings strategies om strategie-namen in op te slaan, een lijst van kleurnamen colors om strategie-kleuren in op te slaan, een lijst van oplopende getallen indices 0, 1, 2, .. (die even lang is als de lijst van strategieën) om strategieën te kunnen indexeren, een lijst van lijsten (“matrix”) score-table om voor elk strategie-koppel gemiddelde payoffs in op te slaan.
Verder is het handig de volgende patch variabelen te hebben:
de patch set neighborhood om bij te houden welke patches de omgeving definiëren, een integer-variabele strategy om (een index van) de huidige strategie vast te houden, een numerieke variabele mean-total-payoff om de gemiddelde payoff over acht buren per episode bij te houden.
set payoff-matrix (list (list CC-payoff-reward CD-payoff-sucker )
(list DC-payoff-temptation DD-payoff-punishment))
waarbij CC-payoff-reward etc. slider-variabelen zijn. Als acties (C of D) worden gerepresenteerd door bits (0 en 1, resp.), kan de uitbetaling van, bijvoorbeeld, CD worden gevonden door item 1 (item 0 payoff-matrix). Immers, C=0 en D=1.
set strategy-colors [
["always-cooperate" green ]
["always-defect" red ]
...
]
Koppelen kan ook met een Netlogo tabel (ook wel: hash, of: associative array), maar dat zou overkill zijn. De strategieën en kleuren heb je namelijk apart nodig:
set strategies map [ [x] -> item 0 x ] strategy-colors ; strip strategies from strategy-colors set colors map [ [x] -> item 1 x ] strategy-colors ; strip colors from strategy-colorsHet is handig strategieën rond te laten gaan als indices, omdat ze regelmatig gebruikt worden als indexen voor lijsten of tabellen:
set indices n-values length strategies [ [x] -> x ] ; 0, 1, .., n-1 where n is number of strategiesDus "always-cooperate" en "always-defect" zouden dan indices respectievelijk 0 en 1 hebben. Verder moeten patches 'weten' wat hun omgeving is, i.e., met welke andere patches ze hun score mogen vergelijken:
ask patches [ set neighborhood (patch-set self neighbors) ] ; 8 neighbors and myself ask patches [ set neighborhood patches in-radius 1.5 ] ; same effect!Initialisatie kan eindigen door twee hoofdroutines aan te roepen: één om een run te initialiseren, en één om de score-tabel te berekenen:
initialise-run calculate-score-table
clear-output,
clear-all-plots, reset-ticks. Doe dit niet met clear-all, omdat dan de inhoud van kostbare globale variabelen (zoals de score-tabel) ook gewist worden.start-always-cooperate, start-always-defect, etc. Voordat je het veld vult met strategieën is het netjes om te controleren of de startproporties wel sommeren tot 1. Als de start-proporties niet sommeren tot 1 is het nodig de start-proporties te normaliseren:
; this routine ensures that start-ratio's sum to one
; it requires start- sliders for all strategies, otherwise this routine won't work
to normalize-strategy-ratios
let sum-of-strategies sum map [ [s] -> run-result (word "start-" s) ] strategies
if abs(sum-of-strategies - 1) <= 0.01 [ stop ] ; already normalized
foreach strategies [ [?1] ->
run (word "set start-" ?1 " precision (start-" ?1 " / " sum-of-strategies " ) 2")
]
end
[0, 0, 0, 0, 1, 1, 2, 2, 2, 2].Een poelgrootte van 10 is voldoende om proporties met een nauwkeurigheid van (ongeveer!) 1/10 te representeren. Maar 10 is wel een beetje krap. Netlogo heeft genoeg geheugen om tijdelijk grote strategie-poelen aan te maken
to-report rijtje [ x n ] ; e.g., rijtje 7 5 yields [7 7 7 7 7] report n-values n [ x ] end ; strategy pool is a list of strategies where the multiplicity of every strategy is in accordance ; with its start ratio; this makes for a cheap and well-known way to pick elements proportionally let strategy-bag map [ [i] -> rijtje i (1000 * run-result (word "start-" item i strategies)) ] indices ; strategy-bag now looks like [[0 0 0 ...] [1 1 ...] [2 2 2 2 2 ...] ...] ; the length of each sub-list corresponds to the start-proportion of that strategy let strategy-pool reduce [ [x y] -> sentence x y ] strategy-bag ; strategy-pool now looks like [0 0 0 ... 1 1 ... 2 2 2 2 2 ... ...] ; and contains about 1000 indices ask patches [ set strategy one-of strategy-pool ; "strategy" is a natural number; "one-of" is a Netlogo primitive set pcolor item strategy colors ; give patch the color of the strategy it it assigned to ]
foreach indices [ [i] ->
create-temporary-plot-pen item i strategies
set-plot-pen-color item i colors
]
set score-table map [ [s] -> score-row-for s ] strategiesEen score-rij voor strategie s bestaat uit “score entries”.
to-report score-row-for [ s1 ] report map [ [s2] -> score-entry-for s1 s2 ] strategies end
restarts:
to-report score-entry-for [ s1 s2 ] report mean n-values restarts [ score-for s1 s2 ] end
to-report score-for [ s1 s2 ]
let my-history []
let your-history []
let my-total-payoff 0
repeat rounds [
let my-action play s1 my-history your-history
let your-action play s2 your-history my-history
let my-payoff item your-action (item my-action payoff-matrix)
set my-total-payoff my-total-payoff + my-payoff
set my-history fput my-action my-history ; most recent actions go first
set your-history fput your-action your-history
]
report my-total-payoff
end
Soms wordt er “per vergissing” een willekeurige actie gespeeld:
to-report play [ some-strategy my-history your-history ]
report ifelse-value (random-float 1.0 < ruis) [
random-action ] [ runresult (word some-strategy " my-history your-history") ]
end
Als some-strategy = "always-cooperate" dan zal (word some-strategy " my-history your-history") evalueren naar de string "always-cooperate my-history your-history". Als deze string vervolgens wordt ge-evalueerd met run-result, levert deze een actie (0 of 1) op, mits de functie always-cooperate is gedefinieerd:
to-report always-cooperate [ my-history your-history ] report 0 endIn dit geval is de te nemen actie altijd 0 (= cooperate) en wordt de inhoud van de geschiedenissen duidelijk niet gebruikt om de te nemen actie te bepalen.
to go
ask patches [
; determine mean payoff over eight neighbors by asking them to look up in the global
; score-table to see what YOU (proponent patch) would earn by playing against them
set mean-total-payoff ; a patch variable
mean [
item strategy item ([ strategy ] of myself) score-table
] of neighbors
]
ask patches [
; let winner be one of patches in neighborhood with highest mean total payoff
; set strategy to strategy of winner; color with new strategy
; ...
]
tick
do-plots ; it is customary to plot /after/ ticks
end
to do-plots let frequencies map [ [i] -> count patches with [ strategy = i ] ] indices set proportions map [ [i] -> i / count patches ] frequencies ; that's ok: count patches is an inexpensive operation let filtered-indices filter [ [i] -> item i frequencies > 0 ] indices ; filter dissapeared strategies let indices-sorted-by-proportion sort-by [ [f1 f2] -> item f1 frequencies > item f2 frequencies ] filtered-indices ; clear output widget and print new ranking ; plot strategy proportions end
Toelichting:setupdoet de initialisatie en roeptinitialise-runencalculate-score-tableaan (om resp. een run te initialiseren, en om de score-tabel te berekenen). Met de knoppenresetresp.recalcis het mogelijk deze twee routines afzonderlijk aan te roepen. (Dus metresetwordt het veld opnieuw gevuld volgens de start-proporties, zonder dat de score-tabel wordt herberekend.) Het herberekenen van de score-tabel is uiteraard wel nodig als één van de waarden vanrestarts,rounds, ofruiswijzigt.
Alspitaan staat, dan worden bij elke initialisatie van een run de start-proporties van N willekeurige strategieën op 1/N gezet, en de rest op 0, waarbij N =strategies-to-pit.
Het canvas toont de kleuren van de strategieën. In de bovenstaande uitwerking is het ook mogelijk om, meteen of gedurende een run, gradaties van samenwerking per patch of de payoffs per patch te visualiseren. Daarvoor dienen de onderste drie knoppen. De gradatie van samenwerking is een getal tussen de 0 en 1 dat aangeeft hoe vaak een strategie tijdens een episode gemiddeld genomen heeft samengewerkt t.o.v. de acht opponenten (0 = nooit; 1 = altijd). Het visualiseren van de payoffs is makkelijk te implementeren, immers deze waarden zijn al beschikbaar. Het visualiseren van de graden van samenwerking is moeilijker te implementeren. Zg. samenwerkings-ratio's (graad van samenwerking gedurende één episode t.o.v. één opponent) moeten tijdens het berekenen van de score-tabel immers al worden opgeslagen. Entries in de score-tabel bestaan dan niet meer uit enkelvoudige scores, maar uit data-structuren (bv. lijsten) met daarin de score en de samenwerkings-ratio over een x-aantal ronden. Een gevolg is dat de functie score-entry-for ingewikkelder wordt.
Strategieën, gemiddelde samenwerking (wit is hoog), en gemiddelde uitbetalingen (wit is hoog) in tik 57 van een run met 6743 unforgiving, 5511always-cooperate, 2496always-defect, en 2411forgiving-tit-for-tat.
| Laatst gewijzigd op woensdag 13 november 2024, om 15:02 uur | Auteur(s): Gerard Vreeswijk | Translate to en, ru, or tr |
