Patologija minimaksa

Obljubil sem, da bom pojasnil, kaj je patologija minimaksa.

Minimaks je algoritem, na katerem temeljijo domala vsi programi za igranje iger. Tovrstni programi si pri igranju pomagajo z drevesom igre. Vozlišča v njem ponazarjajo možne položaje v igri, povezave pa poteze. Koren drevesa ponazarja trenutni položaj, povezave, ki vodijo iz korena, poteze, ki so na voljo v trenutnem položaju, itd. V listih so možni izidi igre, še večkrat pa njihove ocene, saj bi za prave izide drevo morali razviti do konca igre, kar je ponavadi prezamudno. Na spodnji sliki je majhno drevo igre – iz neznanih razlogov računalničarji drevesa največkrat rišemo tako, da je koren na vrhu, listi pa spodaj.

Drevo igre

Minimaks služi izbiri najboljše poteze v korenu drevesa igre. V ta namen ocene izidov iz listov prenese proti korenu drevesa, da se na njihovi podlagi odloči, katera poteza bo prinesla največji izid. Koren je vozlišče vrste maks (rdeče), vozlišča nivo niže so vrste min (modra) in tako se nivoji izmenjujejo vse do listov (na sliki imamo le en nivo vsake vrste). Igralec, ki je na potezi v vozliščih maks, si prizadeva za čim večji izid, njegov nasprotnik, ki je na potezi v vozliščih min, pa mu seveda želi slabo in si prizadeva za čim manjši izid (od tod imena min, maks in minimaks). Modra vozlišča tako označimo z najmanjšim izidom v njihovih naslednikih (vozliščih nivo niže), rdeče pa z največjim. Oznaka v korenu na izbiro poteze sicer na vpliva, pomeni pa pričakovani izid igralca maks. Rdeča in modra povezava ustrezata potezam, ki ju igralca povlečeta – rdeča je tista, ki jo z minimaksom iščemo.

Praksa kaže, da globlje ko drevo igre z minimaksom preiščemo, bolje igramo. To ni presenetljivo, saj preiskovati globlje pomeni ‘premisliti’ več potez naprej. Ko pa so se pred dobrega četrt stoletja raziskovalci odločili to teoretično utemeljiti, so prišli do nepričakovanega odkritja, da naj bi veljalo prav nasprotno: da naj bi bile ocene izidov igre, ki so z minimaksom proti korenu prenešene z globljim preiskovanjem, manj zanesljive od tistih, ki so rezultat plitvejšega. Temu pojavu so rekli patologija minimaksa in so si ga kar lep čas prizadevali razložiti. Njihovim prizadevanjem sem se pridružil tudi sam in zdi se mi, da se mi je posrečilo najbolje do sedaj. Dognal sem marsikaj, glavna ugotovitev pa je, da so bili modeli igranja igre, ki so se izkazali za patološke, kratko malo nerodno zastavljeni.

Zdaj, ko zaključujem z doktoratom, se sprašujem, ali bi bilo bolje, da bi bil izbral kako drugo temo. Vsekakor sem bil pri patologiji minimaksa uspešen (dejansko sem jo razložil, poleg tega pa sem ugotovitve predstavil na priznani konferenci in objavil v prestižni reviji) in nemogoče je vedeti, ali bi bil kje drugje prav tako. Po drugi strani pa patolgija kake posebne uporabne vrednosti nima in tako sem postal strokovnjak za nekaj, s čimer si v prihodnje ne bom mogel dosti pomagati. A če bi si bil izbral splošno igranje iger, ni nič bolj gotovo, da bi mi kdaj prišlo prav. Edino razčlenjevanje slovenščine je nesporno uporabno, vendar je njegova uporabnost omejena na Slovenijo, pa še težavno je zaradi pomanjkanja jezikovnih virov.

Najboljša tema doktorata bi bila nekaj, s čimer bi se ukvarjalo več mojih sodelavcev, ki bi tako znali dobro presoditi njeno primernosti in mi pri delu pomagati, jaz pa bi dodal košček v mozaik znanja odseka. A žal v našem odseku to ni mogoče, ker se vsakdo ukvarja z nečim drugim. Zaradi tega ravno pretirano ne obžalujem, da sem izbral patologijo, čeprav povsem zadovoljen tudi nisem.

5 odzivov na “Patologija minimaksa

  1. Zanimivo! Kdaj boš imel pa zagovor doktorata? (zakaj se počutim malce smešno ker tikam doktorja?) Kar se pa tiče tvoje diplomske, sem pa tisti tarok dosti preigrala in šele danes izvem da je tvoj. Dobro delo. Iz česa pa je bilo tvoje magistrsko delo?
    Od vseh možnosti za tvoj doktorat mi je najbližje razčlenjevanje slovenščine, ker sem po(ne)sreči srečala cel kup ljudi iz laboratorija za računalniško jezikoslovje (a neki takšnega) in so me celo malce pripravili do razmišljanja, kaj če bi šla naslednje leto na izmenjavo v Stockholm, kjer imajo prav tostranski študij.

Dodaj odgovor

Vaš e-naslov ne bo objavljen. * označuje zahtevana polja