Algoritem Minimax: Razlika med redakcijama

Redakcija: 12:23, 26. oktober 2006

Igralca v šahovski igri izmenjujeta poteze in oba poskušata izbrati najboljšo svojo potezo oz. maksimirati svojo vrednost, posledično pa minimizirati nasprotnikovo. Tako glede na trenutno pozicijo identificiramo igralca MIN in MAX. V začetni poziciji igralca MAX predstavlja beli igralec, ki je na potezi. Igralca MIN pa predstavlja črni igralec. Na osnovi opisanega lahko formuliramo algoritem za igranje iger med dvema nasprotnikoma s popolno informacijo in ničelno vsoto. To naredimo tako, da simuliramo obnašanje igralcev MIN in MAX oz. ti. algoritma MINIMAX.

Algoritem MINIMAX lahko optimiziramo tako, da spremenimo predznak vrednosti nasprotnikove ocenitve. Tako se rezultat ocenitve nasprotnika preslika v oceno trenutnega igralca. Ta optimizacija zahteva tudi spremembo v ocenitveni funkciji. Ocenitvena funkcija v tem kontekstu vrne pozitivno vrednost, če je pozicija boljša za igralca na potezi oz. negativno, če je pozicija boljša za igralca, ki ni na potezi. Opisan algoritem se imenuje NEGAMAX. V primerjavi z MINIMAX algoritmom vsebuje dosti manj kode in omogoča lažje vzdrževanje (dodajanje in odstranjevanje funkcionalnosti) programa.

Prikazana algoritma sta relativno enostavna in neučinkovita. Temeljita na MINIMAX načelu in sistematično preiskujeta celotno iskalno drevo. Ker algoritma preiskujeta celotno iskalno drevo, je časovna zahtevnost $w^{d}$ . Vejitveni faktor v iskalnem drevesu oz. povprečno število nadaljevanj v poziciji je 35. Tako je npr. za globino 6 potrebno preiskati drevo velikosti $1.8 \cdot 10^{9}$ vozlišč ali za globino 10 drevo $2.8 \cdot 10^{15}$ vozlišč.

Povezave

@@ Vrstica 2: / Vrstica 2: @@
 Algoritem MINIMAX lahko optimiziramo tako, da spremenimo predznak vrednosti nasprotnikove ocenitve. Tako se rezultat ocenitve nasprotnika preslika v oceno trenutnega igralca. Ta optimizacija zahteva tudi spremembo v ocenitveni funkciji. Ocenitvena funkcija v tem kontekstu vrne pozitivno vrednost, če je pozicija boljša za igralca na potezi oz. negativno, če je pozicija boljša za igralca, ki ni na potezi. Opisan algoritem se imenuje NEGAMAX. V primerjavi z MINIMAX algoritmom vsebuje dosti manj kode in omogoča lažje vzdrževanje (dodajanje in odstranjevanje funkcionalnosti) programa.
+Prikazana algoritma sta relativno enostavna in neučinkovita. Temeljita na MINIMAX načelu in sistematično preiskujeta celotno iskalno drevo. Ker algoritma preiskujeta celotno iskalno drevo, je časovna zahtevnost <math>w^{d}</math>. Vejitveni faktor v iskalnem drevesu oz. povprečno število nadaljevanj v poziciji je 35. Tako je npr. za globino 6 potrebno preiskati drevo velikosti <math>1.8 \cdot 10^{9}</math> vozlišč ali za globino 10 drevo <math>2.8 \cdot 10^{15}</math> vozlišč.
 == Povezave ==