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 ? 澳门葡京手机版app下载e eller svike hverandre, og hver spiller selv tjener mest p? ? svike hvis den andre 澳门葡京手机版app下载er, mens spillerne totalt tjener mest hvis begge 澳门葡京手机版app下载er. 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 ? 澳门葡京手机版app下载e (ikke si noe). Dersom begge 澳门葡京手机版app下载er 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 ? 澳门葡京手机版app下载e, vil den som tyster g? fri mens den som fors?ker ? 澳门葡京手机版app下载e 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 ? 澳门葡京手机版app下载e, mens det kan v?re veldig fristende ? fors?ke ? tyste hvis man mistenker at den andre vil 澳门葡京手机版app下载e.

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 (澳门葡京手机版app下载) 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 ? 澳门葡京手机版app下载e, og mest individuelt ved ? svike mens den andre 澳门葡京手机版app下载er.

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 澳门葡京手机版app下载e, 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 澳门葡京手机版app下载 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 澳门葡京手机版app下载 skal gi av score.

Kall funksjonen din med alle mulige kombinasjoner av “澳门葡京手机版app下载” 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(“澳门葡京手机版app下载”, “svik”) 
print(score)  # Skal gi [0, 5]
# Kall funksjonen med de 3 andre kombinasjonene av 澳门葡京手机版app下载 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 ? 澳门葡京手机版app下载e f?r kan det v?re mer sannsynlig at han/hun vil fortsette ? 澳门葡京手机版app下载e.

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 ? 澳门葡京手机版app下载e eller svike denne ene gangen, og basert p? valget returnere strengen “澳门葡京手机版app下载” eller “svik”. Regelen som skal brukes for ? avgj?re 澳门葡京手机版app下载 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 澳门葡京手机版app下载e.

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”, “澳门葡京手机版app下载”, “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 澳门葡京手机版app下载e 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 澳门葡京手机版app下载 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 澳门葡京手机版app下载e 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.