|
|
| |
Algoritmul MINIMAX descris anterior are deficienta ca exploreaza parti ale arborelui de joc pe care nu ar trebui sa le mai exploreze.
Sa consideram urmatorul exemplu (si presupunem cautarea de la stanga la dreapta):
6
/ \
/
6 (a)
/ \
6 8 (b)
/|\ |\
1 5 6 8 ...
Dupa ce am explorat nodul a carui evaluare este 8, nu mai este nevoie sa exploram si restul fiilor nodului max situat imediat deasupra
(parintelui), deoarece aceste noduri nu ar face decat sa creasca aceasta valoare (a nodului b).Cum nodul parinte al nodului (b) este (a),
care este nod min, si cum am descoperit un fiu al lui a cu valoarea 6, oponentul va alege intotdeauna aceasta valoare, indiferent
ce valori vor avea nodurile "....". Evitarea explorarii unei parti din arborele de joc se numeste "alfa-beta taiere (prunning)".
Astfel, valoarea unui nod va mai fi calculata doar daca se afla intr-un anumit interval de [min..max].Astfel, pseudo-codul algoritmului devine:
fun minimax(n: node, d: int, min: int, max: int): int =
if leaf(n) or depth=0 return evaluate(n)
if n is a max node
v := min
for each child of n
v' := minimax (child,d-1,...,...)
if v' > v, v:= v'
if v > max return max
return v
if n is a min node
v := max
for each child of n
v' := minimax (child,d-1,...,...)
if v' < v, v:= v'
if v < min return min
return v
Mai trebuie sa calculam dar valorile min si max pe care le pasam recursiv mai departe. Am putea sa trimitem valorile min si max
primite de mai sus, dar nu am face mare lucru. Pentru nodurile "max", valoarea min pasata mai "jos" va fi valoarea cea mai mare gasita
pana la acel moment dintre toti fii iar valoarea max va fi cea primita de mai "sus". Pentru nodurile "min", valoarea min va fi cea primita de mai sus,
iar valoarea max va fi valoarea cea mai mica gasita pana acuma printre fii nodului curent.
Astfel, pseudo-codul devine:
fun minimax(n: node, d: int, min: int, max: int): int =
if leaf(n) or depth=0 return evaluate(n)
if n is a max node
v := min
for each child of n
v' := minimax (child,d-1,v,max)
if v' > v, v:= v'
if v > max return max
return v
if n is a min node
v := max
for each child of n
v' := minimax (child,d-1,min,v)
if v' < v, v:= v'
if v < min return min
return v
Acesta reprezinta algoritmul MINIMAX cu taiere "alfa-beta", adica cautare "alfa-beta". Complexitatea devine O(b^(d/2)*k), unde k este
complexitatea functie de evaluare (presupusa constanta), d reprezinta numarul mediu de mutari posibile la un pas si b adancimea de cautare.
|
|
|
|