Einführung in den Minimax-Algorithmus mit einer Java-Implementierung

1. Übersicht

In diesem Artikel werden wir den Minimax-Algorithmus und seine Anwendungen in AI diskutieren. Da es sich um einen spieltheoretischen Algorithmus handelt, implementieren wir damit ein einfaches Spiel.

Wir werden auch die Vorteile der Verwendung des Algorithmus diskutieren und sehen, wie er verbessert werden kann.

2. Einführung

Minimax ist ein Entscheidungsalgorithmus, der normalerweise in rundenbasierten Zwei-Spieler-Spielen verwendet wird . Das Ziel des Algorithmus ist es, den optimalen nächsten Schritt zu finden.

In dem Algorithmus wird ein Spieler als Maximierer und der andere Spieler als Minimierer bezeichnet. Wenn wir dem Spielbrett eine Bewertungspunktzahl zuweisen, versucht ein Spieler, einen Spielstatus mit der maximalen Punktzahl zu wählen, während der andere einen Status mit der minimalen Punktzahl auswählt.

Mit anderen Worten, der Maximierer arbeitet, um die höchste Punktzahl zu erzielen, während der Minimierer versucht, die niedrigste Punktzahl zu erzielen, indem er versucht, Bewegungen zu kontern .

Es basiert auf dem Nullsummenspielkonzept. In einem Nullsummenspiel wird die Gesamtnutzenpunktzahl unter den Spielern aufgeteilt. Eine Erhöhung der Punktzahl eines Spielers führt zu einer Verringerung der Punktzahl eines anderen Spielers. Die Gesamtpunktzahl ist also immer Null. Damit ein Spieler gewinnt, muss der andere verlieren. Beispiele für solche Spiele sind Schach, Poker, Dame, Tic-Tac-Toe.

Eine interessante Tatsache: 1997 besiegte IBMs Schachcomputer Deep Blue (gebaut mit Minimax) Garry Kasparov (den Weltmeister im Schach).

3. Minimax-Algorithmus

Unser Ziel ist es, den besten Zug für den Spieler zu finden. Dazu können wir einfach den Knoten mit der besten Bewertungspunktzahl auswählen. Um den Prozess intelligenter zu gestalten, können wir auch nach vorne schauen und die Bewegungen potenzieller Gegner bewerten.

Für jede Bewegung können wir so viele Bewegungen voraussehen, wie unsere Rechenleistung zulässt. Der Algorithmus geht davon aus, dass der Gegner optimal spielt.

Technisch gesehen beginnen wir mit dem Wurzelknoten und wählen den bestmöglichen Knoten. Wir bewerten Knoten anhand ihrer Bewertungsergebnisse. In unserem Fall kann die Bewertungsfunktion nur Ergebnisknoten (Blätter) Punkte zuweisen. Daher erreichen wir rekursiv Blätter mit Punktzahlen und verbreiten die Punktzahlen zurück.

Betrachten Sie den folgenden Spielbaum:

Maximizer beginnt mit dem Wurzelknoten und wählt den Zug mit der maximalen Punktzahl. Leider haben nur Blätter Bewertungsergebnisse, und daher muss der Algorithmus die Blattknoten rekursiv erreichen. In dem gegebenen Spielbaum ist derzeit der Minimierer an der Reihe , einen Zug aus den Blattknoten auszuwählen , sodass die Knoten mit den Mindestpunktzahlen (hier Knoten 3 und 4) ausgewählt werden. In ähnlicher Weise werden die besten Knoten ausgewählt, bis der Wurzelknoten erreicht ist.

Definieren wir nun formal die Schritte des Algorithmus:

  1. Erstellen Sie den vollständigen Spielbaum
  2. Bewerten Sie die Ergebnisse für Blätter mithilfe der Bewertungsfunktion
  3. Backup-Scores von den Blättern bis zur Wurzel, unter Berücksichtigung des Spielertyps:
    • Wählen Sie für den maximalen Spieler das Kind mit der maximalen Punktzahl aus
    • Wählen Sie für den Min-Spieler das Kind mit der Mindestpunktzahl aus
  4. Wählen Sie am Wurzelknoten den Knoten mit dem Maximalwert aus und führen Sie die entsprechende Verschiebung durch

4. Implementierung

Lassen Sie uns nun ein Spiel implementieren.

Im Spiel haben wir einen Haufen mit n Knochen . Beide Spieler müssen in ihrem Zug 1,2 oder 3 Knochen einsammeln. Ein Spieler, der keine Knochen nehmen kann, verliert das Spiel. Jeder Spieler spielt optimal. Wenn der Wert von n gegeben ist, schreiben wir eine KI.

Um die Spielregeln zu definieren, implementieren wir die GameOfBones- Klasse:

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

Darüber hinaus benötigen wir auch die Implementierung für Node- und Tree- Klassen:

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Jetzt implementieren wir den Algorithmus. Es erfordert einen Spielbaum, um nach vorne zu schauen und den besten Zug zu finden. Lassen Sie uns das implementieren:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Jetzt implementieren wir die checkWin- Methode, die ein Spiel simuliert, indem wir für beide Spieler optimale Züge auswählen. Es setzt die Punktzahl auf:

  • +1, wenn der Maximierer gewinnt
  • -1, wenn der Minimierer gewinnt

Der checkWin gibt true zurück, wenn der erste Spieler (in unserem Fall - Maximizer) gewinnt:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Hier findet die findBestChild- Methode den Knoten mit der maximalen Punktzahl, wenn ein Spieler ein Maximierer ist. Andernfalls wird das Kind mit der Mindestpunktzahl zurückgegeben:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

Lassen Sie uns abschließend einen Testfall mit einigen Werten von n (der Anzahl der Knochen in einem Heap) implementieren :

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Verbesserung

Bei den meisten Problemen ist es nicht möglich, einen vollständigen Spielbaum zu erstellen. In der Praxis können wir einen Teilbaum entwickeln (konstruieren Sie den Baum nur bis zu einer vordefinierten Anzahl von Ebenen) .

Dann müssen wir eine Bewertungsfunktion für den Spieler implementieren , die entscheiden kann, wie gut der aktuelle Status ist.

Selbst wenn wir keine vollständigen Spielbäume erstellen, kann es zeitaufwändig sein, Züge für Spiele mit hohem Verzweigungsfaktor zu berechnen.

Glücklicherweise gibt es eine Option, um den optimalen Zug zu finden, ohne jeden Knoten des Spielbaums zu erkunden . Wir können einige Zweige überspringen, indem wir einige Regeln befolgen, und dies hat keinen Einfluss auf das Endergebnis. Dieser Vorgang wird als Beschneiden bezeichnet . Alpha-Beta-Bereinigung ist eine weit verbreitete Variante des Minimax-Algorithmus.

6. Fazit

Der Minimax-Algorithmus ist einer der beliebtesten Algorithmen für Computer-Brettspiele. Es ist weit verbreitet in rundenbasierten Spielen. Es kann eine gute Wahl sein, wenn die Spieler vollständige Informationen über das Spiel haben.

Es ist möglicherweise nicht die beste Wahl für Spiele mit außergewöhnlich hohem Verzweigungsfaktor (z. B. GO-Spiel). Bei einer ordnungsgemäßen Implementierung kann es sich jedoch um eine ziemlich intelligente KI handeln.

Wie immer finden Sie den vollständigen Code für den Algorithmus auf GitHub.