minmaxzoek

Minimaxzoek is een zoekalgoritme uit de kunstmatige intelligentie voor twee-speler-spellen met volledig informatie en nul-som, waarin de winst van de een gelijk is aan het verlies van de ander. Bekende toepassingen zijn schaak, dam en andere strategische spellen; het algoritme zoekt naar de zet die, onder de aanname van optimale tegenstand, de beste eindwaarde oplevert.

Werking: vanuit de huidige positie wordt een spelboom opgebouwd. Op elk knooppunt wordt afwisselend gekozen tussen max- en min-nodes: bij een max-knoop kiest de speler die de positie maximaliseert, bij een min-knoop de tegenstander die minimaliseert. Leaf-knooppunten worden geëvalueerd met een evaluatiefunctie of, bij eindtoestanden, met de werkelijke uitslag. De waarden worden teruggepropagereerd naar de wortel, zodat de eerste zet gekozen wordt die de wortelwaarde maximaliseert.

Complexiteit en optimalisaties: de zoekruimte groeit exponentieel met de diepte, doorgaans O(b^d), waarbij b het gemiddeld aantal mogelijke zetten is en d de zoekdiepte. Alpha-beta-pruning verhoogt de efficiëntie door onzichtbare takken uit te sluiten; bij ideale volgorde kan dit tot ongeveer O(b^{d/2}) leiden. In de praktijk wordt vaak depth-limited gezocht met een heuristische evaluatie, plus technieken als iterative deepening en transpositie-tabellen.

Beperkingen en varianten: minimax is geschikt voor deterministische, volledig bekende spellen zonder toeval. Het kan vastlopen bij grote spellen; daar worden varianten zoals expectimax toegepast wanneer toeval of onzekerheid in het spel zit. Als aanvulling worden vaak positiespecifieke heuristieken en betere move-ordering gebruikt.

Historie: concepten van minimax komen uit de speltheorie van von Neumann en Morgenstern; in AI werd het prominent toegepast in vroege en mid-tijdige computerchess- en damprogrammas.