IN1000 - H?st 2021

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 ? 中国竞猜网_中国足彩网-足球推荐e eller svike hverandre, og hver spiller selv tjener mest p? ? fors?ke ? "lure" den andre til ? 中国竞猜网_中国足彩网-足球推荐e 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 ? 中国竞猜网_中国足彩网-足球推荐e (ikke si noe om hva de har gjort). Dersom begge 中国竞猜网_中国足彩网-足球推荐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 ? 中国竞猜网_中国足彩网-足球推荐e, vil den som tyster g? fri mens den som fors?ker ? 中国竞猜网_中国足彩网-足球推荐e 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 ? 中国竞猜网_中国足彩网-足球推荐e, mens det kan v?re veldig fristende ? fors?ke ? tyste hvis man mistenker at den andre vil 中国竞猜网_中国足彩网-足球推荐e 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 (中国竞猜网_中国足彩网-足球推荐) 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 ? 中国竞猜网_中国足彩网-足球推荐e, og mest individuelt ved ? svike mens den andre 中国竞猜网_中国足彩网-足球推荐er.

I denne oppgaven vil vi bruke dette scoresystemet:

Begge 中国竞猜网_中国足彩网-足球推荐er: 3 poeng til begge spillerne
En spiller sviker og den andre 中国竞猜网_中国足彩网-足球推荐er: 5 poeng til den som sviker og 0 poeng til den som 中国竞猜网_中国足彩网-足球推荐er
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 中国竞猜网_中国足彩网-足球推荐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 中国竞猜网_中国足彩网-足球推荐 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 中国竞猜网_中国足彩网-足球推荐 skal gi av score.

Kall funksjonen din med alle mulige kombinasjoner av “中国竞猜网_中国足彩网-足球推荐” 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(“中国竞猜网_中国足彩网-足球推荐”, “svik”) 
print(score)  # Skal gi [0, 5]
# Kall funksjonen med de 3 andre kombinasjonene av 中国竞猜网_中国足彩网-足球推荐 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 ? 中国竞猜网_中国足彩网-足球推荐e f?r kan det v?re mer sannsynlig at han/hun vil fortsette ? 中国竞猜网_中国足彩网-足球推荐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 ? 中国竞猜网_中国足彩网-足球推荐e eller svike denne ene gangen, og basert p? valget returnere strengen “中国竞猜网_中国足彩网-足球推荐” eller “svik”. Regelen som skal brukes for ? avgj?re 中国竞猜网_中国足彩网-足球推荐 eller svik er:

Hvis motspilleren har sveket flere ganger enn han/hun har 中国竞猜网_中国足彩网-足球推荐et til n?: svik
Hvis ikke: 中国竞猜网_中国足彩网-足球推荐

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 中国竞猜网_中国足彩网-足球推荐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”, “中国竞猜网_中国足彩网-足球推荐”, “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 中国竞猜网_中国足彩网-足球推荐e 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 中国竞猜网_中国足彩网-足球推荐 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 中国竞猜网_中国足彩网-足球推荐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 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.