IN1000 - Høst 2020

Obligatorisk innlevering uke 4

Frist for innlevering: 15.09. kl 23:59

Spørsmål eller kommentarer til oppgaveteksten sendes til ivargry@ifi.uio.no.

Læringsmål denne uken

Introduksjon

Før du begynner på obligen kan det være lurt å ha fulgt undervisningsopplegget som gis i gruppen for det alternative oblig-løpet (torsdag kl 10:15-12:00 denne uken). Her blir det gitt litt introduksjon til spillteori, og vi løser et problem sammen som gjør det enklere å komme i gang med obligen. For de som vil gjøre denne obligen og ikke er på denne gruppen, vil det bli lagt ut en video i løpet av torsdagen som går gjennom det samme.

I denne oppgaven skal du lage et program som spiller spillet fangens dilemma. Det er også inkludert en valgfri konkurranser der de som ønsker kan levere et program som spiller mot alle andre program som blir levert (alle mot alle), og det kåres en vinner basert på hvem som får høyest sammenlagt score. Det er ikke noe krav for obligen å skrive et program som spiller bra. Det man blir vurdert på er hvorvidt man har fullføre deloppgavene (beskrevet under), hvor du blant annet må skrive funksjoner og bruke lister på riktig måte. Det er valgfritt hvor mye tid man vil bruke på å forbedre programmet slik at man kan vinne konkurransen.

Kort om Fangens dilemma

Dette er en introduksjon til spillet Fangens dilemma som er temaet for denne obligen. Det gjør ikke noe om man ikke forstår spillet fullstendig etter å ha lest dette, ettersom ting vil bli klarere når man gjør oppgavene.

Fangens dilemma er navnet på en type situasjon som oppstår når to parter (spillere) har muligheten til å samarbeide eller svike hverandre, og hver spiller selv tjener mest på å svike hvis den andre samarbeider, mens spillerne totalt tjener mest hvis begge samarbeider. Det finnes mange slike situasjoner i det virkelige liv, men situasjonen som ofte brukes som eksempel er tilfellet hvor to fanger er mistenkt for å ha gjort noe kriminelt. De sitter i hver sin celle, og kan ikke snakke sammen. Hver fange kan velge å tyste på den andre, eller å samarbeide (ikke si noe). Dersom begge samarbeider og ingen sier noe, vil de få en forholdsvis kort straff (si f. eks 1 år hver i fengsel). Hvis den ene derimot tyster på den andre, mens den andre forsøker å samarbeide, vil den som tyster gå fri mens den som forsøker å samarbeide vil få 10 år i fengsel. Hvis begge tyster vil de dele straffen og få 5 år hver. Poenget er at de sammenlagt får de kortest straff av å samarbeide, mens det kan være veldig fristende å forsøke å tyste hvis man mistenker at den andre vil samarbeide.

En lignende situasjon oppstår også i dyreriket hvor et dyr som har fått tak i mye mat kan velge å enten dele litt av maten med en venn eller beholde alt selv. To dyr vil i lengden tjene på om begge deler litt mat hver gang en av dem skaffer mye mat (samarbeid) fordi man gjerne skaffer mer enn man klarer å spise selv. Men en part kan velge å svike ved ta i mot mat fra en annen og ikke dele tilbake når han selv har skaffet mye mat), og sitte igjen med en høyere individuell gevinst.

Når man skal spille fangens dilemma, er det enklere å tenke på det man tjener som en score i stedet for antall år i fengsel eller mengde mat. Målet i spillet er å få høyest score.

Det har ingen stor betydning hva scoren er, så lenge man tjener mest sammenlagt ved å samarbeide, og mest individuelt ved å svike mens den andre samarbeider.

I denne oppgaven vil vi bruke dette scoresystemet:

Fangens dilemma blir interessant når man spiller spillet gjentatte ganger mot samme person, og det er et slikt program vi skal skrive her. Målet vil da være å samle så mange poeng som mulig totalt over alle spillene, og det er ikke opplagt hvilken strategi som fungerer best over tid. Hvis man for eksempel forsøker å være snill og alltid samarbeide, kan den andre spilleren utnytte det og svike.

Oppgave 1

Filnavn: fangens_dilemma.py

For å skrive det fulle programmet som spiller fangens dilemma trenger vi først noen hjelpe-funksjoner.

Skriv en funksjon beregn_score som tar de to parameterene valg_spiller1 og valg_spiller2.

De to parameterene representerer valget til hver spiller ved et gitt spill, og hver vil enten ha verdien samarbeid eller svik. Funksjonen skal bruk if-setninger til å finne scoren som hver spiller får fra dette spillet og returnere en liste med to elementer, der det første elementet er scoren som spiller 1 får og det andre elementet er scoren som spiller 2 får.

Se introduksjonen over for hva ulike kombinasjoner av svik og samarbeid skal gi av score.

Kall funksjonen din med alle mulige kombinasjoner av “samarbeid” og “svik” og sjekk at du får forventet output:

For eksempel skal du få [0, 5] hvis du kaller funksjonen slik:

score = beregn_score(“samarbeid”, “svik”) 
print(score)  # Skal gi [0, 5]
# Kall funksjonen med de 3 andre kombinasjonene av samarbeid og svik

Oppgave 2

Filnavn: fangens_dilemma.py (fortsett i samme fil som før)

Når man spiller fangens dilemma gjentatte ganger mot samme person vil det lønne seg å kjenne til tidligere spill. Hvis motspilleren for eksempel har pleid å samarbeide før kan det være mer sannsynlig at han/hun vil fortsette å samarbeide.

Skriv en funksjon spill_snilt som tar ett parameter, en liste som inneholder alle motspillerens valg til nå i spillet. Funksjonen din skal finne ut om du ønsker å samarbeide eller svike denne ene gangen, og basert på valget returnere strengen “samarbeid” eller “svik”. Regelen som skal brukes for å avgjøre samarbeid eller svik er:

Bruk en for-løkker (ikke count) for å telle antall ganger motspilleren har sveket.

Merk at hvis listen er tom (ingen tidligere spill har blitt utført), så vil det bety at du samarbeide.

Test funksjonen din noen ganger med noen lister som representerer tidligere spill. Hvis du for eksempel kaller funkjsjonen din slik, skal den returnere “svik”:

valg = spill_snilt([“svik”, “samarbeid”, “svik”])
print(valg)  # Skal gi svik

Oppgave 3

Filnavn: fangens_dilemma.py (fortsett i samme fil som før)

Lag tilsvarende som i oppgave 2 en funksjon spill_slemt. Funksjonen skal igjen avgjøre om du ønsker å svike eller samarbeide denne ene gangen basert på informasjon om tidligere spill.

Her skal du bruke denne regelen:

Oppgave 4

Filnavn: fangens_dilemma.py (fortsett i samme fil som før)

Lag en prosedyre utfor_spill som utfører 10 spill mellom den “snille” og den “slemme” spilleren som du har skrevet funksjoner for i oppgave 2 og 3.

I prosedyren må du definere to tomme lister som skal inneholde valgene spillerne tar, og to variable som holder på scoren til hver spiller (scoren er i utgangspunktet 0).

For hvert av de 10 spillene må du:

Print til slutt ut totalscoren til hver spiller (summen av scoren de får fra hvert spill). Hvem får høyest score totalt, den snille eller den slemme?

Oppgave 5

Filnavn: fangens_dilemma.py (fortsett i samme fil som før)

Lag en ny prosedyre utfor_spill_uendelig som gjør det samme som prosedyren du skrev i oppgave 4, men i stedet for å spille 10 spill skal prosedyren spørre brukeren om det skal utføres et nytt spill eller ikke (ved hjelp av input). Et nytt spill skal bli utført så lenge brukeren ønsker dette.

Oppgave 6 (valgfri oppgave, implementer din egen strategi)

Filnavn: fangens_dilemma.py (fortsett i samme fil som før)

Lag en funksjon min_strategi_BRUKERNAVN som på samme måte spill_snilt og spill_slemt tar en liste over tidligere spillrunder og returnerer samarbeid eller svik. Bytt ut "BRUKERNAVN" med ditt uio-brukernavn.

Denne gangen ønsker vi at funksjonen ikke bare skal ta en liste over motspillerens tidligere valg, men også en liste over tidligere valg man har gjort selv. Funksjonen må altså ta to parametere, der første parameter er motspillerens tidligere valg og neste parameter er ens egne tidliger valg (stort sett er det motspillerens tidligere valg som er interessante å se på, men det kan være nyttig å også ta valg basert på hva man selv har valgt tidligere).

I den funksjonen implementerer du selv din egen regel/strategi for å avgjøre om du skal samarbeide eller svike. Når du leverer denne innleveringen vil denne funksjonen plukkes ut og spille mot alle de andre som leverer.

Det vil alltid spilles 10 runder mot samme motspiller. Det blir kåret en vinner basert på sammenlagt score fra alle rundene man har spilt mot alle spillere (altså summen av scoren du oppnår i alle spillene, ikke antall spill/runder du har vunnet).

Du kan ta utgangspunkt i funksjonen du skrev i oppgave 4 for å spille min_strategi mot spill_snilt, spill_slemt eller andre strategier du implementerer. Det kan gjøre det enklere å finne frem til en god strategi som fungerer bra mot mange andre strategier.

Krav til innlevering

Hvordan levere oppgaven

Kommenter på følgende spørsmål i kommentarfeltet i Devilry. Spørsmålene skal besvares.

For å levere:

  1. Logg inn på Devilry.
  2. Lever alle .py-filene , og husk å svare på spørsmålene i kommentarfeltet.
  3. Husk å trykke lever/add delivery og sjekk deretter at innleveringen din er komplett. Du kan levere flere ganger, men alle filer må være med i hver innlevering.
  4. Den obligatoriske innleveringen er minimum av hva du bør ha programmert i løpet av en uke. Du finner flere oppgaver for denne uken på semestersiden.