4) Igranje igara Flashcards
Objasniti i ilustrirati determinističku igru s potpunom informacijom i sumom nula
Potpuna informacija znači da svi igrači vide trenutno stanje i nema skrivenih elemenata. Suma nula znači da koliko jedan igrač dobiva, toliko drugi gubi. Deterministička igra znači da igri postoji krajnje stanje.
Primjer je križić kružić.
Definirati igranje igara kao problem pretraživanja prostora stanja
Svaka igra ima početno stanje, funkciju sljedbenika i predikat za ispitivanje krajnjeg stanja, elementi pretraživanja prostora stanja. Osim toga ima i isplatnu funkciju koja diktira koliko igrači dobivaju odnosno gube. Pretraživanje se vrši u dubinu pa je prostorna složenost O(bm), vremenska složenost O(b^m), optimalnost, potpunost
Objasniti metodu minimax i pretpostavke na kojima se temelji
Metoda igranja u kojoj igrač MAX nastoji maksimizirati svoj dobitak, dok igrač MIN nastoji minimizirati dobitak igrača MAX. Igrači igraju naizmjenično i svaki igrač pretpostavlja da će protivnik igrati tako da maksimizira svoj dobitak i redovito slijediti tu strategiju (minimizira apsolutan gubitak)
function maxValue(s)
if terminal(s) then return utility(s)
m ← −∞
for t ∈ succ(s) do
m ← max(m, minValue(t))
return m
function minValue(s)
if terminal(s) then return utility(s)
m ← +∞
for t ∈ succ(s) do
m ← min(m, maxValue(t))
return m
Definirati algoritam minimax s dubinskim ograničenjem i objasniti njegova svojstva
Kako je moguće da ima puno stanja, a za algoritam minimax i određivanje sljedećeg stnaja je potrebno izračunati vrijednost u korijenskom čvoru, ograničavamo dubinu stabla koje stvaramo na određenu dubinu da bismo u razumnom vremenu riješili problem.
Pri dubinskom ograničenju, algoritam vraća vrijednost kraja ako je kraj pronađen među stanjima, ili heuristiku čvorova na dnu ako nijsmo dođli do ciljnog stanja. Tako je vremenska složenost još uvijek O(b^m), ali je broj grana manji, a prostorna složenost ostaje O(m). Nije ni potpun ni optimalan.
function maxValue(s, d)
if terminal(s) then return utility(s)
if d = 0 then return h(s)
m ← −∞
for t ∈ succ(s) do
m ← max(m, minValue(t, d − 1))
return m
function minValue(s, d)
if terminal(s) then return utility(s)
if d = 0 then return h(s)
m ← +∞
for t ∈ succ(s) do
m ← min(m, maxValue(t, d − 1))
return m
Objasniti heurističku funkciju igre i navesti primjere
Vrijednost h(s) je procjena isplativosti stanja s za igrača MAX, a za MIN iznosi -dobitak od MAX ili poseban iznos (gledano iz perspektive MIN-a kao da je MAX jer svatko želi sebi maksimizirati dobitak). Npr. zbroj preostalih figura na ploči, udaljenost od ciljne pozicije.
Može biti definirana kao težinska linearna kombinacija više značajki:
h(s) = w1x1(s) + w2x2(s) + · · · + wnxn(s)
Primijeniti algoritam minimax s danom heuristikom na jednostavno stablo igre
a niš, ide gas
Objasniti podrezivanje alfa-beta i dati primjere
MEtoda koja se koristi da bismo smanjili i čak prepolovili broj stanja koja razmatramo što je dobro jer taj broj raste ekponencijalno kako dalje pretražujemo. Podrezujemo kad god se za neki čvor ustanovi da potezi ni u kojem slučaju ne mogu biti povoljniji od nekog već istraženog poteza.
Ako podrezujemo ispod MIN-čvora: alfa-podrezivanje
Ako podrezujemo ispod MAX-čvora: beta-podrezivanje
Primijeniti algoritam minimax s podrezivanjem alfa-beta na jednostavno stablo igre
Ako je smo trenutno u Max čvoru i njegov lijevi min čvor je odredio neki alfa, onda nećemo ni razmatrati drugu djecu desnog min čvora ako je prvo dijete manje od alfa jer MAX sigurno neće uzeti manju vrijednost, a MIN čvor neće odabrati ostalu veću braću.
