Kod svih logičkih igara princip po kome se kreće u rešavanje uvek je isti. Računar nema drugi izbor nego da svoje „razmišljanje“ temelji na iscrpnoj pretrazi kroz stabla pozicija. Ova ideja je u principu sasvim ispravna, osim što u praksi nailazi na dva velika problema: vreme i memorijski zahtevi potrebni za dolazak do rešenja toliko su veliki da se ne mogu ispuniti nijednim u svemiru poznatim računarom, odnosno memorijom.
Svaka logička igra ima diskretan graf pozicija. Uzmimo neki klasičan i lako zamisliv primer logičke igre. Neću uzeti u obzir otelo (tj. reversi) pošto ne poznajem dovoljno principe, već ću uzeti igru Osam, pošto je lak(š)a za objašnjavanje, bar mi se tako čini.
Igru Osam si verovatno već sreo. Imaš kvadratno polje od 3x3 manja kvadrata u koje je uglavljeno osam pločica. Pošto ima 8 pločica a 9 mesta, logično je da je jedan kvadratić ostao prazan. Kvadratići koji su pored praznog mesta mogu se pomeriti na prazno mesto, i time ostavljaju prazno mesto na prethodnom položaju. Svaki kvadratić je označen brojem od 1 do 8 i zadatak igre je pomeranjem kvadratića od početne pozicije, gde su kvadratići slučajno razmešteni, doći do krajnje u kojoj su kvadratići poređani po redu. Ujedno sad vidiš zbog čega sam izabrao Osam kao primer igre — za razliku od šaha ili otela. Kod osmice postoji samo jedna krajnja pozicija (cilj) dok u otelu i pogotovo šahu postoji brdo krajnjih pozicija koje su definisane neposredno (ispunjena su sva polja na tabli, odnosno nečiji kralj je u „matu“).
Dakle kako bismo rešili Osam? Najprostiji pristup je ujedno i osnova svih poznatih algoritama za logičke igre: pretraga. Najpre smislimo nešto što se zove kodiranje pozicije, odnosno neko preslikavanje tako da svakoj poziciji odgovara jedan i samo jedan kod. To se recimo može uraditi na očigledan način tako što se za svako od 9 polja pamti koji kvadrat na njemu trenutno stoji (pri čemu nula označava recimo prazno mesto, a 1-8 pune kvadratiće). Kodiranje pominjem u ovom kontekstu, jer se može desiti da za praktično rešenje moraš da smisliš neki način za zapis pozicije koji će zauzimati manje mesta. To je pogotovo bitno u šahu, gde su memorijski zahtevi mnogo veći.
Zatim krenemo od zapisa početne pozicije i izgenerišemo sve moguće poteze u tom trenutku. U igri Osam mogući potezi su oni koji prebacuju susedne kvadratiće na mesto praznog i u svakom koraku ima ih najviše četiri. Sve moguće poteze koji su izgenerisani ubacimo u stablo pozicija (stablo pozicija je graf koji pokazuje sve prelaze između stanja koji se mogu ostvariti legalnim potezima). Dakle ubaciš nove (četiri) pozicije u graf i spojiš ih ivicom sa trenutnom pozicijom. Zatim se prebacuješ (nekim) redom u nove pozicije i ponavljaš ovaj postupak. Potraga se završava u onom trenutku kada nabasaš na poziciju u kojoj pločice stoje onako kako treba.
Ako si pažljivo čitao, dovde si već nanjušio problem koji se javlja kod svih logičkih igara a svodi se na pitanje
a koliko dugo treba da pretražujem. E pa odgovor je na žalost: beskonačno dugo. Jer, stablo pozicija se odmotava u beskonačnost. Kao što se vidi, nigde se nismo obezbedili da ako pretragom natrčimo na poziciju koju smo već sreli, nju ne obrađujemo na dalje jer smo je već uzimali u obzir. Gore je to što pri pretrazi ne samo što trošimo beskonačno mnogo vremena, već i beskonačno mnogo memorije: sve te generisane međupozicije moraju se negde zapamtiti. Najgore je to što broj međupozicija eksponencijalno raste (tj. jako brzo). Početna pozicija pravi nam 4 nove, od te 4 nove pozicije skoro svaka daje 4 nove (16), opet od tih 16 svaka po 4 nove itd. Memorijski prostor koji ti treba za pamćenje svega ovoga je ogroman. I ne samo to. Da bi omogućio svojoj pretrazi da ide dalje u dubinu nije dovoljno da nabaviš jači/brži/bolji/veći računar: ako želiš da omogućiš svojoj igri da gleda jedan potez više u dubinu, moraš nabaviti 4 puta više memorije. Ako želiš ići još samo jedan, moraš nabaviti 16 puta više memorije. Ubrzo svaki dodatni korak traži sve veće i veće izdatke, koji se ne mogu zadovoljiti prostim čekanjem da tehnologija napreduje i umetanjem sve novih i novih memorijskih modula. Očigledno su nas pojeli ogromni brojevi.
Pitanje je šta sada. E pa tu u igru ulaze metode veštačke inteligencije, odnosno prvi momenat gde prirodna pamet sreće veštačku. Da bi napisao program koji može da napadne bilo koju logičku igru razumnom snagom, moraš mu pomoći da „pametno“ pretražuje stablo pozicija. Prva stvar koja se u igri Osam može uraditi jeste vođenje računa o tome da se pozicije ne ponavljaju. Ali postoji još pitanja. Svakako rešenje je sakriveno negde u stablu pozicija. Ali već u prvom koraku naš put se grana na četiri strane (od izvora najmanje dva a najviše četiri putića). Može li se unapred znati koji od njih vodi najkraćom putanjom do rešenja, a koji vodi na stranputicu kojom se na kraju dolazi do cilja posle hiljada koraka? Drugo pitanje je kako tražiti: da li prvo istresti sve mogućnosti koje nudi jedan put, pa preći na sledeći, ili razvijati sve puteve ravnomerno? Prva mogućnost zove se depth first search, druga breadth first search. Traženje sa ograničenjima zove se branch and bound search. Postoje i druge varijante pretrage poput iterative deepening tehnika koje kombinuju ova dva pristupa.
Napokon pravi izazov je odabir pravog puta. Na početku svi putevi imaju istu „težinu“, dakle a priori ti isto izgledaju. Ti ne možeš unapred znati koji put vodi ka cilju, ali možeš imati „predstavu“ da je od dva puta bolji onaj koji pločice dovodi „bliže“ cilju. Ovakvi približni kriterijumi kojima se biraju „bolje“ staze za pretragu zovu se heuristike. Jedan algoritam koji podržava heurističku pretragu zove se A* (A star, iliti A sa zvezdom). To je običan algoritam za pretragu u koga „ukopčaš“ željenu heuristiku i pustiš da radi. Sa programerske strane to je sve od mudrosti što se da ugraditi.
Dobro, ali kako ja da „znam“ koja heuristika je najbolja za dati problem. Odgovor je u stilu Radovana Trećeg. Šta je bilo?! Nemamo pojma! Heuristika se bira kao posledica izučavanja problema, gut feelinga, rasporeda zvezda ili šta ti ja već znam. Za neke igre, poput šaha, smatra se da postoje strategije koje su bolje od drugih. Svako će se setiti enciklopedija otvaranja i završnica. Ovde posao postaje kreativan — treba smisliti dobru heuristiku. Za igre poput šaha postoje razvijene heuristike. Za neke druge igre heuristike ne postoje, ili bar nisu opšte prihvaćene. A neke treće igre (poput igre awari) su rešene: neki superračunar odvrteo je sve moguće pozicije i dao odgovor: pri najboljoj mogućoj igri, ishod je nerešen. Za više detalja treba posetiti sajt Univerziteta u Amsterdamu gde rade momci koji su to izveli i pročitati članak „awari is solved“. Vredi znati i to da je svetski prvak u igri dama (checkers) — kompjuterski program. Igru Otelo računari iz nekog razloga igraju mnogo bolje od čoveka.
I jedan mali link:
http://www.norvig.com
Algoritam za igru sa kartama
Re: Algoritam za igru sa kartama
