Blog

KAKO ZARADITI PARE NA INTERNETU
MONEY FOR NOTHING CUZ CLICKS NOT FREE...

KOMADORAC ZA SVA VREMENA. HOCU MOJE PARE!!!!

KOMPJUTERI I MISAONE IGRE - MIN MAX ALGORITAM

KOMPJUTERI I MISAONE IGRE
Mihal Baðonski, Novi Sad casopis Tangenta (1996/97)

Pravljenje programa sposobnih za igralje misaonih igara poput šaha ili dama slada u posebnu oblast veštačke inteligencije. Iako se svaki ovakav program može na prvi pogled znatno razlikovati od ostalih programa slične namene, ideja koja se primenjuje pri pravljenju programa je uvek ista. U osnovi svakog programa sposobnog za igranje misaone igre za dva igrača, se uvek nalazi jedan isti algoritam - takozvani MINMAX algoritam pretraživanja. Upoznavanje sa ovim algoritmom ćemo započeti primerom uz igru koji svi dobro poznajemo. Ova igra ima puno imena: Puta-nula, Krstić-kružić, Iks-oks,... U engleskom govornom području je zovu Tic-Tac-Toe (tiktakto). To je igra koja se igra na 9 polja raspoređenih u 3 vrste i kolone. Igrači igraju naizmenično. Prvi igrač upisuje znak X u jedno prazno polje a drugi igrač upisuje znak O u neko prazno polje. Pobednik je onaj igrač koji uspe da upiše tri svoja znaka u jednu od kolona ili u jednu od vrsta ili u jednu od dve dijagonale. Pretpostavimo da se prvi igrač zove A a drugi B. Na početku, igrač A ima 9 mogućnosti za početni potez (slika 1).

Igrač A hoće da pobedi, i zbog toga će izabrati onaj potez, koji ga vodi u poziciju što je moguće bolju za njega. Kako odrediti koliko je neka pozicija dobra ili loša za nekog igrača? Da bismo na ovo odgovorili, pogodno je da se svakoj poziciji dodelimo jedan broj. Recimo da je to realan broj iz intervala [-1, 1]. Ako je to pozicija jednako dobra za oba protivnika, dodelićemo joj broj 0. Ako pozicija više odgovara igraču A, dodelićemo joj broj veći od 0, i to tako da što je ta pozicija bolja za igrača B to je broj veći. Ako je to pozicija koja pametnom igrom igrača A sigurno vodi do pobede, onda joj se dodeljuje broj 1. Slična priča važi i za pozicije nepovoljne za igrača A  kojima se dodeljuju negativni brojevi. Nazovimo broj koji dodeljujemo nekoj poziciji ocenom te pozicije. Sada je jasno da će prilikom svakog svog poteza igrač A birati onaj potez koji tekuću poziciju menja u poziciju sa maksimalnom ocenom.Slično, igrač B će se uvek truditi da dođe do pozicije sa što je moguće manjom ocenom. Ako su poznate ocene svih mogućih pozicija do kojih se može doći od tekuće pozicije primenom jednog od dozvoljenih poteza, problem izbora sledećeg poteza je rešen. Ali kako dodeliti ocene  pozicijama do kojih je moguće doći od početne? Igrač A može da razmišlja na sledeći način: Poziciju 2 bi mogao oceniti, ako bi znao ocene svih pozicija do kojih igrač B može doći nakon te pozicije. To su pozicije 11, 12, ..., 18 (slika 2).

 
   
(11)    (12)  (13)  (14)  (15)   (16)  (17)  (I8) Slika 2

Pošto igrač A zna da bi nakon njegovog poteza koji vodi do pozicije 2, igrač B odabrao onaj potez koji vodi do pozicije koja ima najmanju openu,on može da zaključi da pozicija 2 sigurno vodi do one sledeće pozicije, koja je sa najmanjom ocenom. Zbog toga on poziciji 2 dodeljuje ocenu jednaku minimalnoj oceni dodeljenoj pozidijaia 11,12,,..,18.Na isti način na koji je poziiiji 2 dodeljena ocena, dodeljuju se i odene pozicijama 3, 4,..., 9. Za svaku od ovih pozicija se posmatraju svih osam sledećih pozicija, određuju se njihove ocene, bira se minimalna i dodeljuje se poziciji. Igrač A će nakon ovog ocenjivanja izabrati onaj potez, koji ga vodi do pozicije sa maksimalnom ocenom, dakle do one pozicije, nakon koje mu igrač B svojim najboljim (minimalnim) potezom nanosi najmanje štete.Igraču A je za izbor prvog poteza, dovoljno znati ocene svih mogućih pozicija do kojih se može doći jednim potezom. Da bi saznao ove ocene, igrač A mora znati ocene svih pozicija do kojih se može doći nakon dva poteza. Kako će on oceniti ove pozicije? Oceniće ih kad bude saznao ocene svih pozidija do kojih se dolazi od početne pozicije nakon tri poteza. I tako dalje, za ocenjivanje pozicija na i-tom nivou je potrebno znati ocene pozicija na (i+1)-vom nivou. Ako je na potezu igračA, traži se maksimum odgovarajućih ocena a ako je na potezu igrač B, traži se minimum.Na slici 3 vidimo grafičko predstavljalje igre. Na prvom nivou slike je početna pozicija a na desetom se nalaze završne pozicije. Kao što vidimo, neke zavriše pozicije su i na višim nivoima.Završne pozicije je moguće direktno oceniti. Ocene mogu biti: 1 pobeđuje A, 0 - nerešeno, -1 - pobeđuje B. Posle ocene ovih pozicija, igrač A može oceniti sve pozicije na devetom nivou. pa na osmom i tako dalje, sve do pozicija na drugom nivou. Pri tome za ocene pozicija na parnom nivou traži minimum a za odene na neparnom nivou traži maksi mum odgovarajućih ocena sa sledećeg nivoa. Konačno igrač A pravi svoj prvi potez. Na potezu je igrač B, koji za izbor sledećeg poteza primenjuje, postupak sličan onom koji je primenio igrač A, ali je početna pozicija u ovom slučaju drugačija. Nakon poteza igrača B, na redu je igrač A i on ponovo primenjuje opisano pretraživanje svih mogućih sledećih pozicija, i tako dalje.Pošto je igra Puta-nula suviše jednostavna, znamo da nije moguće pobediti ako oba igrača pažljivo igraju. Takođe znamo da bilo koji početni potez vodi do nerešenog rezultata. No nisu sve igre tako jednostavne kao ova. Puta-nula je zbog svoje jednostavnosti najpogodnija za objašnjavanje ovog algoritma.MIN-MAH algoritam se može formalnije, u programskom jeziku Pascal , zapisati na sledeći način:

 
FUNCTION MINMAX(Pozicija: PozTip; Nivo: INTEGER): REAL;
VAR
sledece : ARRAY [l..MaxPoz] OF PozTip;
pom, nova : REAL; 
i, brSled : INTEGER;
BEGIN
IF DovoljnoDuboko(Pozicija, Nivo) THEN
MINIMAX := Oceni(Pozicija, Nivo)
ELSE
BEGIN NadjiSledecePozicije(Pozicija, Nivo, sledece, brSled);
IF ODD(Nivo) THEN (* na potezu je prvi igrac *)
pom := -1 ELSE (* na potezu je drugi igrac *)
pom : = 1;
FOR i := 1 TO brsled DO
BEGIN 
nova := MINIMAX(sledece[i], Nivo+1); (*ocena i-te sled. poz *)
IF ODD(Nivo) THEN 
pom := MAX(pom, nova)
ELSE
pom := MIN(pom, nova)
END;
MINIMAX := pom (*rezultat je min ili max ocena sled. pozicija *)
END 
END (* MINIMAX *)