Minimax

Minimax stellt eine Partie als Baum von Möglichkeiten dar. Jeder Zweig ist ein Zug, und jede Ebene wechselt zwischen der einen und der anderen Seite. Eine Schachengine, also ein Programm, das Stellungen analysiert und Züge auswählt, betrachtet ihre eigenen Möglichkeiten und anschließend die stärksten Antworten des Gegners. Die zentrale Annahme ist vorsichtig: Sie verlässt sich niemals darauf, dass der Gegner einen Fehler macht.

Auf den Ebenen, auf denen die Engine zieht, behält der Algorithmus das günstigste Ergebnis. Auf den Ebenen des Gegners behält er das für die Engine ungünstigste Ergebnis, weil angenommen wird, dass der Gegner bestmöglich Widerstand leistet. Diese Werte werden anschließend von zukünftigen Stellungen zur aktuellen zurückgeführt. Die Ausgangszüge lassen sich daher danach vergleichen, was jeder gegen die beste Verteidigung garantieren kann.

Eine praktische Suche kann nur selten die gesamte Partie untersuchen. An ihrer Tiefengrenze verwendet sie eine Bewertungsfunktion, also eine Formel, die schätzt, welche Seite besser steht. Eine tiefenbegrenzte Minimax-Wahl ist daher kein absoluter Beweis. Sie hängt davon ab, wie weit gesucht wurde und wie genau diese Schätzung war. Außerdem kann sie unter dem Horizonteffekt leiden, bei dem eine wichtige Folge knapp hinter der Abbruchgrenze liegt.

Engines machen dieses Grundmodell mit Techniken wie der Zugsortierung effizient, die vielversprechende Möglichkeiten zuerst untersucht, damit bedeutungslose Zweige früher verworfen werden können. Andere Systeme, darunter die Monte-Carlo-Baumsuche, verteilen ihren Aufwand anders, verfolgen aber dasselbe praktische Ziel: den Zug zu ermitteln, der am zuverlässigsten erscheint.