Obligatorisk innlevering uke 4
Frist for innlevering: tirsdag 21. september kl 23:59
Spørsmål eller kommentarer til oppgaveteksten sendes til ivargry@ifi.uio.no.
Læringsmål denne uken
- Kjenne til skrivemåte for while-løkker og for-løkker
- Kunne bruke løkker for å løse problemer
- Kunne bruke løkker sammen med samlinger
- Ha kjennskap til parametre i prosedyrer og parameteroverføring
- Kjenne til funksjoner og kunne bruke de for å få unngå redundans og få mer strukturerte programmer
Introduksjon
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. Om man ikke forstår spillet helt etter å ha lest introduksjonen, går det fint å begynnne på oppgavene, så vil ting kunne bli klarere etter hvert som 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å å forsøke å "lure" den andre til å samarbeide og selv svike.
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. Under avhør kan hver fange kan velge å tyste på den andre, eller å samarbeide (ikke si noe om hva de har gjort). 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 på hverandre 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 fordi man ender opp uten noen straff selv.
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 det lange løp få best utbytte 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 senere), og sitte igjen med en høyere total gevinst selv.
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:
- Begge samarbeider: 3 poeng til begge spillerne
- En spiller sviker og den andre samarbeider: 5 poeng til den som sviker og 0 poeng til den som samarbeider
- Begge sviker: 1 poeng til begge spillerne
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:
- Hvis motspilleren har sveket flere ganger enn han/hun har samarbeidet til nå: svik
- Hvis ikke: samarbeid
Bruk en for-løkke (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 skal 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:
- Samarbeid alltid de første 5 spillene
- Hvis det er mer enn 5 spill før, svik
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:
- Kalle de to funksjonene du skrev i oppgave 2 og 3 for å finne ut hvilket valg de to spillerne tar
- Legge inn de to valgene i de to listene som holder på tidligere valg
- Regne ut scoren de to spillerne får for de gitte valgene
- Legge til scoren for det gitte spillet på totalscoren for alle spill
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 20 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.
Tips (og ekstra utfordring):
- For å finne en god strategi, kan det være en god idé å teste strategien sin mot mange andre strategier i et turneringsoppsett (f. eks la alle spille parvis mot hverandre og se hvem som gjør det best sammenlagt). Dette krever litt koding, men skal være mulig å få til med det man har lært i uke 4.
Krav til innlevering
- Kun .py-filene skal leveres inn.
- Spørsmålene til innleveringen (nedenfor) skal besvares i kommentarfeltet.
- Koden skal inneholde gode kommentarer som forklarer hva programmet gjør.
- Programmet skal inneholde gode utskriftssetninger som gjør det enkelt for bruker å forstå.
Hvordan levere oppgaven
Kommenter på følgende spørsmål i kommentarfeltet i Devilry. Spørsmålene skal besvares.
- Hvordan synes du innleveringen var? Hva var enkelt og hva var vanskelig?
- Hvor lang tid (ca) brukte du på innleveringen?
- Var det noen oppgaver du ikke fikk til? Hvis ja: i. Hvilke(n) oppave(r) er det som ikke fungerer i innleveringen? ii. Hvorfor tror du at oppgaven ikke fungerer? iii. Hva ville du gjort for å få oppgaven til å fungere hvis du hadde mer tid?
For å levere:
- Logg inn på Devilry.
- Lever alle .py-filene , og husk å svare på spørsmålene i kommentarfeltet.
- 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.
- 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.