8. KI in Spielen

Der beste Schachspieler der Welt kann nicht gegen die beste Schach-KI gewinnen. Auch das Spiel Go, welches lange als eine Hürde galt, in der Maschinen so schnell nicht besser als Menschen werden, wird heutzutage von Bots dominiert. Aber wie arbeiten solche Algorithmen überhaupt? Wie werden sie besser oder sind sie bereits perfekte Spieler?
Zunächst sollte klar sein, dass Maschinen das Brett ähnlich analysieren wie ein Schachgroßmeister. Der Algorithmus, der hierfür verwendet wird, heißt Minimax. Der Algorithmus versucht mehrere Züge vorauszuschauen. Hierzu erstellt er sich für jeden Zug eine Kopie des Bretts, auf dem dieser Zug gemacht wurde. Diese Züge sind sowas wie Paralleluniversen, in denen die KI einen bestimmten Zug gemacht hat. Jetzt wäre der Gegenspieler dran. Für diesen werden die Spielbretter wieder für jeden Zug kopiert und ein Paralleluniversum erschaffen. Das wird für eine bestimmte Menge an Zügen wiederholt. Dann hat man ganz viele Paralleluniversen. Diese muss man jetzt bewerten. Je besser der Zug für die KI, desto höher, je besser für den Gegner, desto niedriger der Wert. Jetzt wird geschaut, welches das beste Universum ist, was die KI erreichen kann, unter der Annahme, dass die KI versucht ein Universum mit einem möglichst besten Wert und der Gegner eines mit einem besonders niedrigen Wert zu finden. Der Zug, der zu dem besten Universum führt, ist auch der Beste.
Aber warum sucht man nicht einfach, bis das Spiel zu Ende ist? Das geht zwar, würde aber viel zu lange dauern. Denn die Menge an Paralleluniversen nimmt mit jedem Zug exponentiell zu. Die Anzahl der möglichen Positionen im Schach ist nach dem ersten Zug 20. Aber nach dem dritten Zug bereits mehr als 4800 Zugkombinationen. Je mehr Paralleluniversen man betrachtet, desto komplexer ist das Spiel.
Deswegen ist der Abbruch der Suche wichtig. Das Bewerten der Position ermöglicht eine Näherungslösung an den besten Zug. Mit der Zugbewertung steht und fällt die Effizienz dieses Algorithmus. Im Schach kann das zum Beispiel mit der Menge an zur Verfügung stehenden Figuren gemessen werden. Moderne KIs verwenden neuronale Netze, welche ein Spielbrett als Eingabe bekommen und dann ausgeben, wie gut die KI steht. Möchte man also seine KI verbessern, so braucht man also eine genauere Bewertung.
Das Beste an dem Algorithmus ist, dass er für jedes Rundenbasierte spiel funktioniert. Abgesehen von den Regeln und einer Bewertung der Paralleluniversen ändert sich zwischen den Spielen nichts. Sogar Spiele, in denen Zufall eine Rolle spielt, sind durch den Minimax Algorithmus spielbar. Es ist natürlich etwas schwerer, eine Voraussage zu treffen, aufgrund des Zufalls.
Im ersten QR-Code in Abb2 ist ein Schachbot, welcher mit Minimax arbeitet, verlinkt. Du kannst ja mal versuchen, gegen ihn zu gewinnen.