IN1000 - H?st 2020

Obligatorisk innlevering uke 10 (oblig nr. 8)

Frist for innlevering: 03.11. kl 23:59

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

Det er mulig ? levere innleveringen f?r fristen og f? den rettet tidligere ved ? skrive "Klar til retting" i kommentarfeltet i Devilry. Man vil da ikke kunne f? ny retting senere.

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 krevende, 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:

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.

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.beregn_avstand(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.beregn_avstand(gress) != 14:
    print("Avstanden er feil, den skulle v?rt 14 men er ", hjerne.beregn_avstand(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 beregn_avstand 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.

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"]) == "opp"
    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 6: 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 7: 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 8: 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.