Algoritmul MINIMAX foloseste reprezentarea jocului ca un arbore cu posibile stari viitoare. La Othello, starea jocului este reprezentata
de configuratia curenta a tablei de joc, precum si de jucatorul care urmeaza sa mute. Starea curenta a jocului reprezinta radacina
acestui arbore. Fii acestu nod sunt reprezentati de toate mutarile posibile care pot fi facute. La randul lor, aceste noduri au ca
fii starile de joc dupa ce oponentul a facut mutarea lui. Frunzele acestui arbore reprezinta starile in care nici o mutare nu mai
poate fi facuta, si in acest caz un jucator a castigat sau jocul s-a terminat la egalitate.
Algoritmul MINIMAX presupune etichetarea nodurilor frunza, dupa cum acestea sunt castigatoare sau nu, si apoi urcarea in arbore
pentru etichetarea celorlate noduri, dupa urmatoarea regula: daca nodul reprezinta o mutare a adversarului, acest nod ia valoarea minima
a fiilor sai, intru-cat jucatorul advers va incerca sa aleaga cea mai buna mutare pentru el, si de ci cea mai proasta mutare pentru noi.
Daca nodul reprezinta o mutare a noastra, se alege maximul valorilor fiilor, intru-cat vom alege mutarea cea mai buna pentru noi.
Aceste consideratii ne ofera o pima varianta in pseudo-cod a algoritmului:
func minimax(n: node): int =
if leaf(n) then return evaluate(n)
if n is a max node
v := L
for each child of n
v' := minimax (child)
if v' > v, v:= v'
return v
if n is a min node
v := W
for each child of n
v' := minimax (child)
if v' < v, v:= v'
return v
Sa consideram urmaorul arbore de joc, in care am etichetat cu "+" nodurile max (noduri in care muta jucatorul nostru), cu "-"
nodurile "min" (nodurile la care muta adversarul), cu "L" nodurile frunza care reprezinta infrangere pentru jucatorul nostru
si cu "W" nodurile frunza in care jucatorul nostru castiga.
+
/ \
/ \
- -
/ \ /|\
+ L L W W
/ \
W L
Aplicand algoritmul MINIMAX pentu nodul radacina, vom obtine urmatorul arbore:
L
/ \
/ \
L L
/ \ /|\
W L L W W
/ \
W L
Obtinem astfel ca jucatorul advers poate forta jocul astfel incat el sa castige intotdeauna (situatia prezentata mai sus este
o situatie care este bine de evitat in cadrul unui joc)
Complexitatea algoritmului de mai sus este O(b^d), unde b reprezinta adancimea arborelui de joc, iar d reprezinta numarul mediu
de mutari pe care un jucator le are atunci cand este la mutare (in cazul jucului othello, d este de 7).
Expandarea intregului arbore de joc nu este posibila la orice joc. In cazul jocului Othello, acest lucru este imposibil, intru-cat
un joc normal are aproximativ 60 de mutari (cate 30 de fiecare jucator), ceea ce ar face ca arborele de joc sa aiba o adancime de
60, si deci complexitatea spatiala ar fi O(60^7), a carui explorare este foarte costisitoare ca timp, si deci nefezabila.
Solutia in acest caz este explorarea spatiului de stari doar pana la o anumita adancime. In acest fel, nodurile frunza nu vor mai fi noduri
de castig sau pierdere, ci vor fi noduri normale de joc. De aceea, se foloseste un evaluator: o functie ce evalueaza aceaste noduri
si, dupa cum pozitia este sau nu avantajoasa, intoarce o valoare mai mare sau mai mica.
In acest fel, pseudo-codul algoritmului devine(d=adancime de cautare):
fun minimax(n: node, d: int): int =
if leaf(n) or depth=0 return evaluate(n)
if n is a max node
v := L
for each child of n
v' := minimax (child,d-1)
if v' > v, v:= v'
return v
if n is a min node
v := W
for each child of n
v' := minimax (child,d-1)
if v' < v, v:= v'
return v
Sa consideram urmatorul exemplu, in care functia de evaluare a fost aplicata pentru nodurile frunza si apoi restul de noduri au fost etichetate
conform algoritmului de mai sus:
6
/ \
/ \
6 L
/ \ |\
6 8 L W
/|\ |\ |\
1 5 6 8 3 1 W
Valoarea nodului radacina este 6, intru-cat jucatorul nostru poate forta jocul astfel incat el sa ajunga, dupa doua mutari, pe o pozitia
in care valoarea nodului sa fie cel putin 6. Scrierea unui bune functii de evaluare este critica pentru rapiditatea algoritmului,
deoarece complexitatea algoritmului a devenit O(b^d*k), unde k reprezinta complexitatea functiei de evaluare. Aceasta complexitate
trebuie sa fie cel mult lineara, daca nu chiar constanta. De asemenea, functia de evaluare trebuie scrisa astfel incat sa descrie cat
mai bine situatia jocului la un moment dat, pentru a face un jucator bun. Practica spune ca este mai bine sa se face o functie de evaluare mai
simpla, iar cautarea sa se faca mai multe nivele in arbore.