Minimax

Minimax reprezintă partida ca pe un arbore de posibilități. Fiecare ramură este o mutare, iar fiecare nivel alternează între o parte și cealaltă. Un motor de șah, adică un program care analizează poziții și alege mutări, își examinează opțiunile și apoi cele mai puternice răspunsuri ale adversarului. Presupunerea sa centrală este prudentă: nu se bazează niciodată pe faptul că adversarul va greși.

La nivelurile la care mută motorul, algoritmul păstrează rezultatul cel mai favorabil. La nivelurile adversarului, păstrează rezultatul cel mai puțin favorabil motorului, deoarece presupune că adversarul va opune cea mai bună rezistență posibilă. Valorile sunt apoi propagate înapoi din pozițiile viitoare spre cea curentă. Astfel, mutările inițiale pot fi comparate prin ceea ce poate garanta fiecare împotriva celei mai bune apărări.

O căutare practică poate examina rareori întreaga partidă. La limita de adâncime folosește o funcție de evaluare, adică o formulă care estimează care parte stă mai bine. Prin urmare, o alegere minimax cu adâncime limitată nu este o demonstrație absolută: depinde de cât de departe a ajuns căutarea și de precizia estimării. Poate suferi și de efectul de orizont, când o consecință importantă se află imediat dincolo de limită.

Motoarele eficientizează acest cadru prin tehnici precum ordonarea mutărilor, care examinează mai întâi opțiunile promițătoare pentru ca ramurile irelevante să fie respinse mai devreme. Alte sisteme, inclusiv căutarea în arbore Monte Carlo, își distribuie efortul diferit, urmărind același obiectiv practic: identificarea mutării care merită cea mai mare încredere.