MinMax

Algoritmul MinMax se folosește pentru a determina cea mai bună mutare într-un 0-sum game cu 2 jucători.

Informații generale

graful (nodurile, muchiile împreună cu costurile lor)
nodul din care începe căutarea (nodul-start)
un scop dat sub forma unei condiții pe care trebuie să o îndeplinească nodul căutat (se poate oferi chiar nodul propriu-zis, condiția fiind relația de egalitate cu acest nod). Vom numi mai departe nodul care îndeplinește condiția nod-scop
o estimare (euristică) a costului de la fiecare nod din graf la nodul (nodurile) scop.

Paşi:

Generează arborele de joc până la stările scop sau o adâncime stabilită.
Estimează scorul fiecărei stări terminale (frunză).
Deplasează-te înapoi în arbore, de la nodurile frunze spre nodul rădăcină, determinând la fiecare nivel al arborelui valorile care reprezintă utilitatea (i.e. scorul) nodurilor aflate la acel nivel. Propagarea acestor valori la nivelurile anterioare se face prin intermediul nodurilor-părinte conform următoarei reguli:
- dacă părintele este un nod de tip MAX, atribuie-i maximul dintre valorile fiiilor săi;
- dacă părintele este un nod de tip MIN, atribuie-i minimul dintre valorile fiilor săi.
Ajuns în nodul-rădăcină, alege pentru MAX mutarea care îl conduce către cel mai mare scor.

Fie imaginea de mai jos:

Cât va fi valoarea din rădăcină după ce rulăm MinMax pe exemplul din imagine?

Exercițiile acestui capitol sunt accesibile aici: MinMax