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:

Í okkar tilfelli gæti verið gott að skilgreina tagið leikur sem tvennd reita, t.d. "(E1, D2)", því þá er enginn munur á leikjum hundanna og leikjum refsins.
Þið getið notað sýnislausnina á fyrri hlutanum sem grunn fyrir þennan hluta eða haldið áfram með ykkar eigin lausn.
Gildisfallið sem þið notið þarf ekki að vera mjög flókið, en það þarf þó að gefa mjög hátt gildi ef hundarnir eru búnir að króa refinn af og lágt gildi í upphafi leiksins. Gæði gildisfallsins munu ráða miklu um hversu vel forritið ykkar spilar leikinn.
Dýpið sem leitin fer niður á ræður miklu um hraða forritsins. Ef þið látið forritið leita djúpt í trénu þá getur það tekið langan tíma að ákveða hvern leik.
Það er hægt að auka hraðann á forritinu með því að nota Alpha-Beta útgáfuna af Minimax aðferðinni. Hún hendir út þeim greinum leitartrésins sem ekki geta haft áhrif á lokaniðurstöðu þess og þýðir að hægt er að fara dýpra í leikjatréð á þeim tíma sem til ráðstöfunar er.
Það er mjög áhugavert námskeið um leit í leikjatrjám við tölvunarfræðideild Alberta háskóla í Kanada.

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.