Modelul formal
Un joc cu suma zero e definit prin: stari S, stari terminale T ⊆ S, functie de evaluare v: T → R, functie de tranzitie next: S×A → S, si alternanta jucatorilor MAX/MIN.
Complexitatea exponentiala
Fara optimizari, minimax exploreaza b^d noduri (b = branching factor, d = adancime). Pentru sah: b ≈ 35, deci la 8 mutari: 35^8 ≈ 2.2 trilioane. Pentru Go: b ≈ 250, imposibil si la 4 mutari.
Alpha-beta pruning
Algoritmul mentine doua valori:
- α: cea mai buna valoare garantata pentru MAX
- β: cea mai buna valoare garantata pentru MIN
Cand α ≥ β, ramura e taiata. In cel mai bun caz, alpha-beta reduce complexitatea la b^(d/2) — dublul adancimii explorabile cu acelasi cost.
Functii de evaluare
In jocurile unde arborele e prea mare, se foloseste o functie de evaluare e(s) care estimeaza valoarea unei stari fara a explora complet. Exemple:
- Sah: suma valorilor pieselor + bonus de pozitie
- Go: teritoriu + influenta
MCTS vs Minimax
MCTS castiga acolo unde minimax pierde: branching factor mare si functie de evaluare dificila. Go e exemplul clasic — MCTS a facut posibil ce minimax nu putea.