Tölvunarfræği 2

Aukaverkefni

2. hluti


Şá er komiğ ağ seinni hluta aukaverkefnisins fyrir şá sem eru í Tölvunarfræği 2. Í şessum seinni hluta eigiğ şiğ ağ skrifa forrit sem getur spilağ leikinn Refaveiğar viğ notandann. Forritiğ ykkar şarf ağeins ağ spila sem hundarnir, en notandinn leikur refnum.

Leiknum var lıst í fyrsta hluta aukaverkefnisins. Şağ gilda áfram sömu reglur, nema ağ einu leyti: Hundarnir vinna leikinn einungis ef şeir geta króağ refinn af. Í fyrri lısingunni var sagt ağ hundarnir vinna ef einhver şeirra nær refnum. Sú regla gerir leikinn of auğveldan fyrir hundana. Áfram gildir ağ hundarnir mega ekki fara á reit sem hefur annan hund eğa refinn.

Forritiğ ykkar á ağ velja sína leiki meğ şví ağ nota leikjatré og gildisfall (e. evaluation function). Forritiğ ykkar á ekki ağ smíğa leikjatréğ sjálft heldur ağeins ağ rekja sig í gegnum şağ til şess ağ finna hagstæğasta leikinn. Hér ağ neğan er sauğakódi fyrir şessa ağferğ (e. Minimax method):

     fall finnaBesta( stağa S, int dıpi, int tegund, int bestagildi, leikur bestileikur )
         ef dıpi = 0 şá
             bestagildi = gildisfall(S)
             hætta
         mögulegirleikir = búaTilAllaLeiki( S )
         ef fjöldi leikja = 0 şá
             bestagildi = gildisfall(S)
             hætta
         ef tegund er MAX şá
             næstategund = MIN
             bestagildi = -∞
         annars
             næstategund = MAX
             bestagildi = +∞
         endir
         fyrir alla leiki L í mögulegirleikir
             S' = stağa eftir leik L
             finnaBesta( S', dıpi-1, næstategund, nıttgildi, nırleikur ) 
             ef betra( nıttgildi, bestagildi, tegund) şá
                 bestagildi = nıttgildi
                 bestileikur = L
             endir
         endir
     endir
Falliğ betra skilar şví hvort nıttgildi sé betra en bestagildi, eftir şví hvort tegund er MAX eğa MIN. Şegar tegundin er MIN şá erum viğ ağ leita ağ lágildinu og şá eru lág gildi betri, en há gildi eru betri şegar tegundin er MAX. Şegar ákveğa şarf leik tölvunnar er kallağ á falliğ meğ núverandi stöğu, leitardıptina sem viğ viljum fara niğur á (t.d. 4) og tegundina MAX, şví viğ viljum hámarka okkar gildi. Falliğ skilar gildinu í viğfanginu bestagildi og besta leiknum í bestileikur.

Nokkar ábendingar:


Skiliğ skırslu um gerğ gildisfallsins, ásamt útprentun af forritinu og einum leik şess viğ notanda til dæmatímakennara ykkar fyrir kl. 12:00 mánudaginn 21. mars. Şeir munu ekki taka viğ verkefnum sem koma seinna.
annaing (hja) hi.is / hh (hja) hi.is, 7. mars, 2005.