Eine häufige Beschwerde in Videospielen ist, dass die KI der Gegner schlechte Entscheidungen trifft. Aus diesem Grund betrügen sie in manchen Fällen direkt betrügen, aber manchmal passiert das Gegenteil, und sie zeigen sehr effektive Strategien in Spielen, die wir als „einfach“ bezeichnen können. Einer der Gründe ist die Anwendung des Minimax-Theorems, eines Algorithmus, der das Ziel hat, den maximalen erwarteten Verlust in Spielen mit zwei Teilnehmern und vollständiger Information für beide Seiten zu minimieren.
Viele Spiele verbergen Informationen vor den Teilnehmern als Teil ihrer Mechanik. Denken Sie nur an den „Fog of War“ klassischer Spiele (StarCraft und Civilization kommen in den Sinn). Mit diesem Mittel kann die KI 20 oder 30 Einheiten wie durch Zauberei beschwören, ohne dass du es merkst (unter anderem), und seine Beseitigung ist ein wesentlicher Schritt, sei es durch das Aussenden von Einheiten zur Erkundung oder durch die Entwicklung von Technologien, die seinen Effekt aufheben (wie die Satelliten in Civ).
Aber was passiert, wenn die Information perfekt ist? Wie verhält sich eine künstliche Intelligenz, wenn es nichts zu verbergen gibt, und alle Elemente des Spiels von Anfang an bekannt sind? Eine der vielen Möglichkeiten für den Entwickler ist die Implementierung des Minimax-Theorems. Die offizielle Beschreibung spricht von einer „Methode zur Entscheidungsfindung, um den maximalen erwarteten Verlust zu minimieren“, und das mag auf den ersten Blick einfach erscheinen, aber es verdient eine tiefere Untersuchung:
Minimax-Theorem: Optimale Lösungen für Nullsummenspiele
Der Kanal BitBoss leistet hervorragende Arbeit bei der Zusammenfassung des Minimax-Algorithmus, und das Beste daran ist, dass er weniger als vier Minuten dauert. Grundsätzlich funktioniert Minimax bei Nullsummenspielen, das heißt, dass unser Gewinn oder Vorteil zum Verlust für den Gegner wird. Schach ist ein klassisches Beispiel für ein Nullsummenspiel mit vollständiger Information, aber das Video zeigt uns einen einfacheren Weg und verwendet Tic-Tac-Toe als Referenz.
Jede Phase des Spiels kann mit einer Zahl definiert werden, positiv für einen Spieler und negativ für den anderen. Die Strategie des Minimax-Algorithmus versucht, den besten verfügbaren Zug auszuwählen, wobei er vollständig annimmt, dass der Gegner ebenfalls den besten Zug gegen ihn wählt. Wenn eine Minimax-KI einen Sieg mit einer positiven Zahl erreicht, werden ihre Entscheidungen versuchen, den Weg zu wählen, der diese Zahl begünstigt.
Das Diagramm zeigt die letzten sechs möglichen Züge einer KI in einer Tic-Tac-Toe-Partie. Vier davon drücken einen Sieg für die KI (gelb) mit einer Bedingung von 1 aus, und die anderen beiden für den menschlichen Spieler (blau) mit -1. Die Züge werden von unten nach oben oder von hinten nach vorne analysiert: Da der KI nur noch ein Zug bleibt, werden die Werte für jeden in den vorherigen Schritt übernommen. Nach derselben Logik hat der menschliche Spieler zwei Züge, die ihm ein -1 garantieren, und einen dritten, der ihn zwingt, 1 zu wählen. Daher sichert sich die KI den Sieg, indem sie Druck auf diesen Weg ausübt, der mit einem Kreuz in der Mitte beginnt.
Offensichtlich ist dies ein zu einfaches Beispiel, das nur dank der natürlichen Grenzen von Tic-Tac-Toe möglich ist. Wenn wir die Minimax-Methode auf hochkomplexe Spiele wie Schach oder Go übertragen, wächst exponentiell, und die Anwendung von Minimax wird unpraktikabel. Eine mögliche Lösung ist es, die Tiefe der Erkundung zu begrenzen, und im Allgemeinen reicht das völlig aus, um den n00bs eine Lektion zu erteilen.
