IN1000 - Høst 2021

Obligatorisk innlevering uke 10 (oblig nr. 8)

Frist for innlevering: 10. november kl 23:59

OBS: Denne innleveringen er obligatorisk og må være godkjent for at man skal kunne ta eksamen i faget.

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

Introduksjon

Denne innleveringen bygger litt videre på forrige innlevering, og målet nå er å prøve å lage inteligente sauer som spiser så mye gress som mulig og som unngår å bli spist av ulver. Det vil være en valgfri konkurranse som går ut på å lage den smarteste sauen (se detaljer til slutt i oppgave).

Å få en sau til å bevege seg noenlunde intelligent rundt på spillbrettet er krevende. Det er mange ting man må ta hensyn til, slik som:

Å ta hensyn til alle disse tingene er vanskelig, og å lage en kunstig intelligens som fører til optimale valg uansett bane vil være tilnærmet umulig. I problemer som dette er det derfor vanlig å gjøre en del forenklinger og lage en forenklet modell av problemet med en del antakelser. Dermed kan man løse enklere og mer isolerte problemer som sammen delvis løser det større problemet. Vi kommer til å gjøre disse forenklingene fra forrige oblig:

Prekode

Start med å laste ned disse filene. Du trenger ikke å sette deg inn i koden (den ligner mye på det man skrev i forrige innlevering), men det kan være greit å vite følgende:

PS: En endring fra forrige innlevering er at ulver nå heller ikke kan gå på steiner. Det gjør det litt vanskeligere for ulven.

Oppgave 1: Lese baner fra fil

Sjekk først at prekoden kjører uten å krasje og at du får opp et spillbrett på skjermen. Alt du skal trenge å gjøre er å kjøre:

python3 hovedprogram.py

(evt. kjøre hovedprogram.py på den måten du vanligvis kjører et Python-program)

Øverst i hovedprogram.py ser du at vi kaller spillbrett.legg_til_objekter_fra_fil("testbane1.txt"), men metoden legg_til_objekter_fra_fil i klassen Spillbrett gjør ikke det den skal. Implementer denne metoden (fjern først koden som er i metoden fra før):

Kjør hovedprogram.py og sjekk at du får opp dette på skjermen:

bilde

Oppgave 2: Sauehjerne

Hvis man har kode som skal utføre én konkret oppgave kan det være lurt å separere ut denne koden i en egen klasse. Det gjør ting mer ryddig og det er enklere å teste koden.

Koden som avgjør hvordan sauen beveger seg er et eksempel på slik kode. Tidligere har vi hatt denne koden i Sau-klassen, men Sau-klassen har også andre oppgaver. Koden som skal bestemme hvordan sauen beveger seg trenger kun å ha kjennskap til spillbrettet, og oppgaven til denne koden er å fortelle sauen hvilken retning den skal bevege seg.

Kjør hovedprogram.py og sjekk at sauen beveger seg mot venstre. Det betyr i så fall at sauen nå bruker hjernen sin og går den retningen hjernen sier at den skal gå.

Oppgave 3: Forbedre sauehjernen

Vi har nå en klasse Sauehjerne som har et konkret sett med informasjon (et spillbrett og en sau den hører til) og en konkret oppgave: Å bestemme en retning å gå.

Vi kan dermed steg for steg jobbe med denne klassen uten å bry oss om resten av koden. Vi kan også teste at hjernen fungerer som forventet uten å måtte kjøre hele programmet. Merk at vi også kan lage ulike klasser som følger samme oppsett som Sauehjerne (flere Sauehjerner) for å teste ut ulike implementasjoner. Det eneste vi krever er at alle disse klassene tar samme parametere i konstruktøren (dvs at de har samme signatur) og at de implementerer metoden velg_retning (altså at de har samme grensesnitt).

Sauehjernen kommer til å måtte ta en del avgjørelser basert på hvor andre ting befinner seg på spillbrettet. Vi kommer ofte til å måtte vurdere avstander og retninger på spillbrettet. Implementer disse metodene:

avstand_til_objekt

Metoden skal ta et parameter objekt og returnere antall ruter sauen må gå for å komme til objektet. Husk at sauehjernen har tilgang til sauen gjennom self._sau. Husk også at vi nå ikke bryr oss om posisjonen i pixler til hvert objekt. Vi har forenklet ting ved å anta at hvert objekt finnes i en rute. Alle klasser implementere nå metodene rute_venstre() og rute_topp() som gir antall ruter objektet befinner seg fra hhv. venstre side og toppen av brettet.

Ettersom sauer og ulver bare kan bevege seg mot venstre/høyre og opp/ned ønsker vi at avstanden skal reflektere det. Dette kalles "Manhatten distance". Se for deg at du står på Manhatten hvor alle gater går opp/ned eller til siden og man ikke kan gå skrått. Avstanden fra et gatehjørne til et annet blir antall gater man må gå opp/ned pluss antall gater man må gå til venstre/høyre.

I vårt tilfelle vil for eksempel antall ruter man må gå til venstre/høyre mellom to objekter være abs(objekt1.rute_venstre() - objekt2.rute_venstre()). Bruk dette til å implementere avstanden mellom objektet som tas inn som parameter og sauen som hjernen har tilgang til.

retninger_mot_objekt

Lag også en metode retninger_mot_objekt som tar et objekt som parameter og som returnerer en liste over alle "retninger" sauen kan gå for å komme nærmere objektet. Hvis objektet er rett over sauen skal listen [opp] returneres. Hvis f. eks objektet er skrått over og til venstre for sauen skal listen ["opp", "venstre"] returneres (rekkefølgen i listen har ingen betydning), osv. Ignorer steiner og kanten på spillbrettet her, metoden skal kun tenke at det finnes en sau og et objekt.

retninger_fra_objekt

Lag tilsvarende en metode retninger_fra_objekt som returnerer en liste med alle retninger sauen kan gå for å øke avstanden fra objektet. Retningene her vil være de motsatte retningene av de som returneres i retninger_mot_objekt. Du kan altså enten implementere denne metoden fra scratch, eller kalle retninger_mot_objekt og gå gjennom retningene derifra og snu dem.

Oppgave 4: Test sauehjernen vi har laget så langt

Sauehjernen vår har nå noen metoder for å "tenke" (dvs beregne avstander og retninger) men ber fortsatt alltid sauen gå mot venstre. Før vi fortsetter ønsker vi å teste at hjernen tenker riktig.

Lag en fil test.py. Importer Sauehjerne, Sau og Spillbrett øverst i filen.

Test avstandsberegning

Lag en prosedyre test_avstand. I prosedyren gjør du følgende:

Gjenta det over med 3 andre gress-objekter som befinner seg andre steder på brettet. Regn ut avstanden for hånd først, gjerne ved å tegne på et ark, og sjekk at avstanden som Sauehjernen beregner stemmer med det du mener er riktig.

Bruk gjerne assert til å gjøre disse sjekkene, f. eks slik:

assert hjerne.avstand_til_objekt(gress) == 14, "Avstanden er feil"

Hvis du er ukomfortabel med å bruke assert, kan du bruke en if-test til å printe en feilmelding hvis resultatet er feil:

if hjerne.avstand_til_objekt(gress) != 14:
    print("Avstanden er feil, den skulle vært 14 men er ", hjerne.avstand_til_objekt(gress))

Test retningsberegning

Lag en prosedyre test_retning. I prosedyren gjør du følgende:

PS: Ettersom rekkefølgen ikke spiller noen rolle kan du gjøre om det som returneres til en mengde ("set") og sammenligne mot en annen mengde for å sjekke likhet (hvis du sammenligner lister vil Python si at listene er ulike om rekkefølgen er ulik):

retninger = sauehjerne.retninger_mot_objekt(gress)
assert set(retninger) == set(["opp", "venstre"])

Oppgave 5: Gå mot gress

Vi er nå klare for å bruke det vi har laget av hjerne til å la sauen få gjøre noen smarte valg. Det første vi ønsker er å prøve å få sauen vår til å bevege seg mot gress.

Finne nærmeste gress

Lag først en metode naermeste_gress() i klassen Sauehjerne. Denne metoden skal gå gjennom alle "gress" som ikke er spist i spillbrettet og returnere det gresset som er nærmest sauen (her skal metoden avstand_til_objekt brukes). Hvis mer enn ett gress har samme avstand og er nærmest, har det ingenting å si hvilket av de som returneres.

Gress-klassen har en metode er_spist() som kan brukes for å sjekke om gresset er spist eller ikke fra før. Hvis det ikke finnes noe gress igjen som ikke er spist, skal metoden returnere None.

Gå mot nærmeste gress

Gjør følgende i metoden velg_retning i klassen Sauehjerne:

Kjør hovedprogram.py og sjekk at sauen ser ut til å bevege seg mot gress. At sauen blir spist på et punkt er helt greit, men hvis sauen beveger seg vekk fra gresset er noe galt. Sørg for at dette ser ut til å fungere før du fortsetter.

Oppgave 6: Unngå ulver

Vi har nå en sauehjerne som klarer å tenke seg frem til hvilken retning den skal gå for å spise gress (nærmeste gress), men vi ønsker gjerne at sauen også skal prøve å bevege seg vekk fra ulven.

Det er nå bare én ulv på brettet, og denne kan hentes ut ved å kalle ulv() på spillbrettet.

a

Utvid metoden velg_retning slik at hvis ulven har avstand til sauen mindre eller lik 6, så henter du ut retningene sauen må bevege seg for å komme seg vekk fra ulven. Slå disse sammen med listen over retninger sauen vil bevege seg for å komme til nærmeste gress, men gang listen med to først (slik at retningene vekk fra ulven kommer to ganger, du vil skjønne hvorfor snart). Koden din vil altså se litt slik ut (pseudokode):

retninger = []
# finn nærmeste gress
# hvis det er noe nærmeste gress, finn retningene mot nærmeste gress:
retninger_mot_gress = self.retninger_mot_objekt(gress)  # gress er her en variabel som peker på det nærmeste gresset
retninger.extend(retninger_mot_gress)

if [... ulv er nærmere enn 6 ruter ...]:
   retninger_vekk_fra_ulv = self.retninger_fra_objekt(self._spillbrett.ulv())
   # gang retningene med 2 (gir en liste der hvert element kommer to ganger)
   retninger_vekk_fra_ulv = retninger_vekk_fra_ulv * 2
   # legg til retningene i listen over alle retninger
   retninger.extend(retninger_vekk_fra_ulv)

Listen retninger vil da inneholde en haug av retninger, der retningene vekk fra ulven kommer to ganger. Vi vil se på denne listen som et sett med "stemmer" og ønsker å finne den retningen som har flest stemmer og følge den retningen. Vi lar ulve-stemmene telle dobbelt fordi vi anser det som viktigere å unngå ulven enn å spise gress.

b

Skriv en funksjon finn_vanligste_element_i_liste som tar en liste som parameter og returnerer det elementet som finnes flest ganger i listen. Denne funksjonen trenger ikke noe informasjonen fra klassen Sauehjerne så den kan bare lages som en enslig funksjon i filen sauehjerne.py utenfor klassen. Det gjør det enklere å teste den. Bruk for-løkker for å løse dette problemet.

Lag en prosedyre test_finn_vanligste_element_i_liste i filen test.py som tester denne funksjonen, f. eks slik:

from sauehjerne import finn_vanligste_element_i_liste
def test_finn_vanligste_element_i_liste():
    assert finn_vanligste_element_i_liste(["ned", "ned", "opp"]) == "ned"
    assert finn_vanligste_element_i_liste(["ned", "venstre", "opp", "venstre"]) == "venstre"
    ## Legg gjerne inn et par tester til

c

Fullfør metoden velg_retning ved å finne det vanligste element i listen retninger. Dette vil være retningen som sauehjernen har mest lyst til å bevege seg. Returner denne retningen.

Kjør hovedprogram.py og sjekk at Sauen beveger seg mot gress helt til den er i nærheten av ulven. Da bør den bevege seg bort fra Ulven.

Oppgave 7: Komme seg rundt ulven

Hvis du har fått til oppgave 5 riktig, vil du merke at sauen beveger seg fra ulven, men ender opp på enden av spillbrettet og blir stående og stange der. Dette skjer fordi den vil bort fra ulven, men ikke har noe annet som får den til å gå til siden når den har kommet til enden av brettet.

En enkel og naiv måte å unngå dette problemet på er få sauen til å forsøke å følge kanten av spillbrettet hvis den er ved kanten av spillbrettet.

Utvid velg_retning metoden slik:

OBS: Reglene over bør implementeres i den rekkefølgen de står for å fungere optimalt. Poenget er å først sjekke høyre side før man sjekker toppen slik at første regel vil slå inn om sauen er i øverste høyre hjørne (da ønsker vi at sauen skal gå nedover og ikke mot høyre for å unngå å stå fast).

Kjør hovedprogram.py igjen. Hvis reglene dine virker bør sauen bevege seg nedover når den kommer til enden av brettet og deretter komme seg forbi ulven (og ikke bli fanget på en stund på testbane1.txt).

Oppgave 8: Unngå hindre

Sauen vår blir nå trukket mot gress, beveger seg vekk fra ulven og den unngår å låse seg fast på kantene til brettet (ved at den følger kanten i retning med klokka). Men sauen vår er fortsatt dårlig på å unngå hindre.

Endre hovedprogram.py slik at testbane2.txt brukes i stedet for testbane1.txt og kjør programmet. Du vil trolig se at sauen etter hvert vil ønske å gå til venstre (mot nærmeste gress) men stange i en stein som står i veien:

bilde

a

Lag en metode stein_finnes_i_retning som tar et parameter retning og som returnerer True hvis det finnes en stein på neste rute i den gitte retningen fra sauen og False hvis ikke. I tilfellet vist på bildet over skal f. eks metoden returnere True hvis retningen som gis er "venstre" og False for alle andre retninger.

PS: Husk at du kan kalle metodene rute_venstre() og rute_topp() på et Stein-objekt.

b

Lag en metode hinder_finnes_i_retning som returnerer True hvis det enten er en stein på neste rute i den retningen eller hvis man er utenfor banen på neste rute i den retningen. Den første sjekken har du allerede gjort i metoden stein_finnes_i_retning, så unngå å kopiere kode fra den metoden og kall heller stein_finnes_i_retning fra hinder_finnes_i_retning.

c

Utvid velg_retning-metoden slik at det helt til slutt (etter at sjekken mot kanter er gjort) sjekkes om det finnes en stein i retningen som det er bestemt at sauen skal gå. Hvis det gjør det, velg en annen retning ved å velge en hvilken som helst retning hvor det ikke finnes et hinder (sjekk dette ved å kalle hinder_finnes_i_retning for de ulike mulige retningene som er igjen).

Hvis koden din fungerer som den skal nå, bør sauen fint klare å overleve på testbane2.txt og gjøre det ganske bra på testbane3.txt. Det er ikke noe krav at sauen din skal gjøre det bra på alle banene, men reglene over bør være implementert.

Prøv gjerne ut de andre testbanene og se hva som skjer.

Oppgave 9: Valgfri oppgave, lag din egen sauehjerne

Lag din egen sauehjerne:

Regler for konkurransen:

Noen tips:

Lykke til!

Krav til innleveringen

Hvordan levere oppgaven

Lever følgende filer:

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 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.