Iti0120lab6lisa

Karujahi hästi mängimine eeldab, et saadakse jagu järgmisest probleemist - võiduseisud on otsingupuus sügaval ning vahepeal midagi eriti ei juhtu, näiteks ei ole "löömist". Peenemalt öeldes on igasugused seisueelised dünaamilised ning võivad nii tekkida kui kaduda.

Alpha-beta efektiivsemaks muutmine

Kõige olulisemad allpool olevatest tehnikatest on korduvate seisude elimineerimine, hinnangufunktsioon ja peavariandi arvestamine. Käikude järjestamine ja transpositsioonitabel lisavad otsingule võimsust.

Korduvate seisude elimineerimine

Alpha-beta on sügavutiotsing ning tsüklid mängupuus genereerivad sinna lõputus koguses tippe. Karujahi puhul teame ka, et ükskõik milline kordus on alati karu jaoks kasulik. Seda võib minimax hinnangut arvutades isegi karu võiduks lugeda, kuna see on parim võimalik tulemus karu jaoks - kahe korduva seisu vahel pole jahimehed mitte midagi saavutanud.

• jäta meelde kõik mängus reaalselt esinenud seisud ja seisude jada otsingupuu juurest käesoleva tipuni (s.t. kuidas otsing hetkel arvab, et mäng edasi läheks)
• katkesta otsing (s.t. tagasta seisu väärtus, mis on karu jaoks positiivne ja jahimeeste jaoks negatiivne), kohe, kui otsingu käigus esinev seis kordab mingit eelnevat seisu
• pane tähele, et sama nuppude konfiguratsioon on sama seis ainult siis, kui käigul on ka sama pool

Käikude järjestamine

Alpha-beta algoritm eeldab, et paremad käigud tehakse enne, kui halvemad. Üks lihtsamaid viise seda teha oleks otsida enne käike, mis viivad mänguvälja keskele. Karu eelistaks jääda keskele ning jahimehed peavad ka sinna liikuma, et karu äärele tõrjuda. Seega võime väga umbkaudu hinnata, et käigud keskmistele väljadele on paremad.

Transpositsioonitabel

Eelnevad muudatused teevad meie otsingu teoreetilisest seisukohast väga palju efektiivsemaks. Praktikas peab ta aga ikkagi palju tühja tööd tegema, kuna meie karujahi mängus, nagu ka paljudes teistes mängudes, viivad sageli erinevad käikude järjestused samade seisudeni, seda nii samal kui ka teistel otsingusügavustel.

Väga lihtsustatult on transpositsioonitabel (TT) koht, kus on kirjas, mis mingi seisu otsinguga leitud väärtus on. Selle seisu uuesti kohtamisel pole enam vaja otsingut korrata, väärtus võetakse tabelist.

Praktikas on asi natuke keerulisem. Alpha-beta efektiivsus põhineb sellel, et paljude seisude jaoks ei arvutata selle täpset väärtust vaid see, palju ta maksimaalselt või minimaalselt väärt on. Neid ei saa omavahel segamini ajada ega ka käsitleda täpse minimax väärtusena.

Vaata siit ühte viisi, kuidas TT väärtuseid käsitleda. Näiteks beta-lõike puhul otsing katkestatakse ning teada on vaid, et väärtus on vähemalt see mis leiti. Nii pannaksegi see alampiirina kirja ja seda tohib ka järgmisel korral samas seisus beta-lõike tekitamiseks kasutada.

Sageli kontrollitakse ka, kui sügava otsinguga TT väärtus on leitud ning kasutatakse ainult neid, mille sügavus on sama suur või suurem, kui praeguse otsingu sügavus oleks ilma TT-ta.

Koos eelnevate muudatustega peaks saavutatav otsingusügavus radikaalselt suurenema ning ulatuma vähemalt 20-40 käiguni.

Hinnangufunktsioon

Nüüd on otsing efektiivne, aga suudab eristada ainult võiduseise ja kordusi. See tähendab, et vahepealsed seisud tunduvad kõik ühesugustena, mida nad kindlasti tegelikult ei ole. Täpsem hinnangufunktsioon (utility, eval) aitab mängu juhtida soodsas suunas.

Strateegiamängudes on tihti oluline tsentraalsus ja mobiilsus. See kehtib ka siin, vähemalt karu kohta. Lihtsa, aga suhteliselt hea hinnangufunktsiooni saame, kui anname jahimeestele plusspunkte, kui karu asub serval. Lisaks anname jahimeestele punkte, kui mõni jahimees paikneb karu kõrval - see piirab karu mobiilsust. Karu poolt mängides annavad samad asjad miinuspunkte.

Peavariant ja iteratiivne sügavnemine

Iteratiivset sügavnemist (iterative deepening) kasutatakse mängudes paljudeks eesmärkideks, nagu aja haldamine, transpositsioonitabelite efektiivne kasutus jne. Meie puhul on temast aga kasu peavariandi (principal variation, PV) arvestamisel.

Nimelt on tavaline fikseeritud (näiteks 20 käiguni) sügavusega otsing strateegiliselt väga rumal. Kui sama eesmärgi võib saavutada kolme või 20 käiguga, et tee ta neil vahet ning võib juhuslikult eelistada pikemat varianti - kõik sõltub sellest, mis käik otsingus ettepoole satub. Selline "edasi lükkamine" võib ebasoodsal juhul kesta lõpmatuseni. Sama efektiga tegelesime juba võiduseisu väärtuse arvutamise juures.

• alustame otsingut sügavusega 1
• jätame meelde, mis käik leiti ning liidame sügavusele 1
• järgmisel sügavusel paigutame leitud käigu otsingujärjekorras esimeseks

Sellisel viisil otsides eelistab programm käiku, mis saavutab sama tulemuse varem: kui käik A ja B viivad mõlemad karu nurka surumiseni, aga A teeb seda 3 käigu ja B 20 käiguga, siis järjestades A ettepoole, jääb ta meie valitud käiguks, isegi kui maksimumsügavusel B sama väärtuse saavutab.

Teoreetiline keerukus

Arvuta välja, kui palju on meie ülesandes toodud mängulaual erinevaid võimalikke seise. Kas on mõeldav, et teha tabel, kus iga seisu jaoks on kirjas, mis käik kõige soodsam on?

Kuna harjutuse eesmärk on alpha-beta otsinguga tutvumine, siis selliste tabelite genereerimise tehnikaid juhendis pole kirjeldatud :-)

games.Game klass

Ülalolevate muudatuste jaoks tuleb alpha-beta otsing ümber kirjutada, seega kopeeri see oma programmifaili. Ümber nimetamine pole vajalik, kuna Python teeb erinevast moodulist tulevatel funktsioonidel vahet.

infinity=WIN+1
def alphabeta_cutoff_search(state, game, d=4, cutoff_test=None, eval_fn=None):
    #sinu muudatustega kood...

Kui muudad seda, mis tingimustel otsing katkestatakse (korduste leidmisel on seda vaja), siis võib seda teha oma cutoff_test meetodiga. Selle võib panna BearGame klassi sisse, et seal olevatele andmetele mugavalt ligi pääseda:

class BearGame(games.Game):
    # ....
    def cutoff_test(self, state, depth, d=4):
        if d<depth: return True
        if self.terminal_test(state): return True
        # lisa korduvate seisude kontroll
        return False

def alphabeta_nocycles(game, state):
    def mycutoff(state, depth):
        return game.cutoff_test(state, depth, d=10)
    return alphabeta_cutoff_search(state, game, d=10, cutoff_test=mycutoff)

print(bg.play_game(games.query_player,
              alphabeta_nocycles))

Iteratiivne sügavnemine eeldab otsingu ümber väikese tsükli ehitamist:

def iterative_deepening(game, state):                                           
    # initsialiseeri game objekt (transpositsioonitabelid, PV vms)
    # ...
    for d in range(1,20):                                                       
        def mycutoff(state, depth):                                    
            return game.cutoff_test(state, depth, d=d)                   
        move = alphabeta_cutoff_search(state, game, d=d, cutoff_test=mycutoff)  
    return move                                                                 

print(bg.play_game(games.query_player,
              iterative_deepening))