Minimax

Minimax stelt de partij voor als een boom van mogelijkheden. Elke tak is een zet en elk niveau wisselt tussen de ene en de andere kant. Een schaakengine, een programma dat stellingen analyseert en zetten kiest, bekijkt zijn eigen opties en daarna de sterkste antwoorden van de tegenstander. De centrale aanname is voorzichtig: het rekent er nooit op dat de tegenstander een fout maakt.

Op niveaus waar de engine aan zet is, behoudt het algoritme het gunstigste resultaat. Op de niveaus van de tegenstander behoudt het het minst gunstige resultaat voor de engine, omdat wordt aangenomen dat de tegenstander zich zo goed mogelijk verdedigt. Die waarden worden vervolgens vanuit toekomstige stellingen teruggevoerd naar de huidige stelling. Zo kunnen de beginzetten worden vergeleken op basis van wat zij tegen de beste verdediging kunnen garanderen.

Een praktische zoekactie kan vrijwel nooit de hele partij doorrekenen. Aan de dieptegrens gebruikt zij een evaluatiefunctie, een formule die schat welke kant beter staat. Een minimaxkeuze met beperkte diepte is daarom geen absoluut bewijs: zij hangt af van hoe ver er is gezocht en hoe nauwkeurig die schatting was. Ook kan zij last hebben van het horizoneffect, waarbij een belangrijk gevolg net voorbij de afkapgrens ligt.

Engines maken dit raamwerk efficiënt met technieken zoals zetordening, waarbij veelbelovende keuzes eerst worden onderzocht zodat irrelevante takken eerder kunnen worden verworpen. Andere systemen, waaronder Monte Carlo Tree Search, verdelen hun inspanning anders, maar streven hetzelfde praktische doel na: vaststellen welke zet het meeste vertrouwen verdient.