Heuristiken
Wie funktioniert eigentlich ein Skatprogramm oder allgemeiner, ein vom Computer gesteuerter Teilnehmer an einem Mehrpersonenspiel? Ein weit verbreiteter Ansatz ist die Verwendung von Heuristiken. Eine Heuristik ist eine Regel der Form "Wenn die Spielsituation das Merkmal X aufweist, so tue Y". Auf Skat bezogen sind das also zum Beispiel Leitsätze wie "Kläre als Alleinspieler möglichst schnell die Trümpfe", "Spiele als Gegenspieler über den langen Weg möglichst eine blanke Karte an", "Zeige beim Abwerfen die Gegenfarbe an" und ähnlich. Ob sie nun gut oder schlecht sind, tut bei der Verwendung des Begriffs Heuristik im Weiteren Sinne nichts zur Sache. Im engeren Sinne versteht man unter einer Heuristik freilich eine sinnvolle Regel.
Eine heuristisch programmierte KI funktioniert nun im Wesentlichen so: Die Programmierer sammeln so viele sinnvolle Heuristiken, wie sie finden können. Das Programm prüft nun alle auf ihre Anwendbarkeit in der konkreten Situation und spielt dann die Karte, die von den meisten anwendbaren Heuristiken vorgeschlagen wird. Dabei kann man die Heuristiken natürlich unterschiedlich gewichten (Regel 1 zählt mehr als Regel 17) oder in vorrangige und nachrangige einteilen (Regeln 50 bis 200 werden nur geprüft, wenn keine der Regeln 1 bis 49 anwendbar war). oder noch kompliziertere Sachen machen.
Wichtig ist, dass ein solches Programm auf Erfahrungswerten basiert. Es wird niemals eigenständige Spielzüge entwickeln, sondern immer nur Bekanntes nachspielen. Insbesondere wird es keine genialen Spielzüge finden, auf die die Programmierer nicht gekommen wären. Wenn einzelne Heuristiken Unsinn sind, wird es immer wieder dieselben Fehler machen.
Der Minimax-Algorithmus
Schachcomputer verfolgen in der Regel einen anderen Ansatz. Bei der Beurteilung der Stellung wird zunächst ein sogenannter Suchbaum aufgebaut. Das muss man sich wie folgt vorstellen: Auf einem großen Blatt Papier wird die aktuelle Stellung durch einen Punkt am unteren Rand markiert. Von dort wird nach oben ein Pfeil für jeden legalen Zug gemalt und die daraus entstandene Stellung durch einen weiteren Punkt markiert. Von diesen Stellungen ausgehend wird wieder jeder legale Zug mit einem Pfeil nach oben zur daraus entstehenden Stellung markiert. Das geht so lange, wie der Computer Zeit und Speicherplatz hat. Es entsteht eine Art Baum mit der aktuellen Stellung als Wurzel, Ästen für jeden legalen Zug und Blättern in jeder erreichbaren Stellung.
Bei kleineren Spielen kann man auf diese Weise die komplette Zukunft des Spiels aufmalen und die Endstellungen dahingehend bewerten, ob sie für den KI-Spieler gewonnen (1) oder verloren (0) sind. Schach ist aber schon wieder so groß, dass nicht der gesamte Baum in den Computer passt. Deshalb wird er nach einer gewissen Zahl Züge abgebrochen und die entstandenen Stellungen mit einer Heuristik hinsichtlich ihrer Gewinnwahrscheinlichkeit bewertet, von 1 (sicher gewonnen) bis 0 (sicher verloren).
nachdem der Spielbaum aufgemalt und alle Blätter bewertet sind, werden die Züge von den Blättern rückwärts ausgewertet. Die Stellungen unmittelbar vor den Blättern bekommen einen Wert, der sich aus dem Maximum der Werte der erreichbaren Blätter ergibt, falls der KI-Spieler den letzten Zug macht, und aus dem Minimum, wenn es sein Gegner ist. Anschließend werden die Blätter aus dem Baum entfernt, so dass die soeben bewerteten Knoten die neuen Blätter sind. So geht das Spiel weiter, bis ich beim nächsten auszuführenden Zug bin. Nun wird der Zug ausgeführt, welcher zu der am höchsten bewerteten Stellung führt.
Das hört sich komplizierter an als es ist. Am Beispiel geht es vielleicht besser. Das Spiel möge so einfach sein, dass man in jeder Situation nur zwei mögliche Züge hat. Der Computer wiederum ist so klein, dass er nur drei Halbzüge fortentwickeln kann und dann die Stellungen mit Heuristiken bewertet. Im Beispiel sei Weiß am Zug und habe die Möglichkeiten A und B. Anschließend Schwarz mit den Zügen C und D. Im dritten Halbzug, der noch entwickelt wird, kann Weiß E oder F ziehen. Daraus ergibt sich folgender Suchbaum, den ich mit zufällig ausgewählten Gewinnwahrscheinlichkeiten versehen habe
_0.1__1.0__0.0_0.3___0.1_0.9___0.7_0.6
__E___F____E___F____E___F____E___F
____C________D________C________D
_________A_________________B
Da der dritte Zug von Weiß, dem KI-Spieler, auszuführen ist, werden die höheren der beiden Werte an den übergeordneten Knoten durchgereicht. Das ergibt folgende Situation
___1.0_______0.3_______0.9______0.7
____C________D________C________D
_________A_________________B
Nun wird der Zug von Schwarz ausgewertet, so dass die kleinere der Zahlen zurückgegeben wird
________0.3________________0.7
_________A_________________B
Somit ergibt sich, dass Weiß als nächstes den Zug B ausführen sollte und dann mit mindestens 70% Wahrscheinlichkeit gewinnt, sofern er selbst optimal weiterspielt und die Heuristik an den Blättern recht hatte. Sollte Schwarz nicht optimal spielen, ist die Gewinn-WSK für Weiß sogar noch höher.
Das dumme am Minimax-Algorithmus ist, dass er nur bei Spielen mit vollständiger Information funktioniert - d.h. wenn die Stellung wie beim Schach jedem Spieler vollständig bekannt ist. Skat gehört nicht dazu, denn hier kennt man zu Spielbeginn nur seine eigenen Karten und erfährt erst im Laufe des Spiels die vollständige Verteilung. In den meisten Situationen, wo man sich für eine Karte entscheiden muss, wird man sie noch nicht kennen. Dann aber kann der Computer nicht die Züge der Gegner vorhersehen.
Beim "Glaskartenskat" dagegen würde der Algorithmus gut funktionieren, wahrscheinlich könnte man sogar auf haushaltsüblichen Computern den vollständigen Spielbaum entwickeln. Dann würde der Computer optimal spielen.
Viele Welten und Minimax
Der nächste Ansatz, der laut der hier bereits vorgestellten Arbeit von Jan Schäfer erfolgreich beim Bridge gewesen sei, beruht auf folgender Idee. Man konstruiere einfach alle denkbaren Kartenverteilungen ("Welten"), führe dann in jeder Welt den Minimax durch und spiele anschließend die Karte, die im Durchschnitt über alle Welten den höchsten Erfolg verspricht. Setzen wir das obige Beispiel fort und nehmen an, in einer zweiten Welt würde Zug A einen Wert von 0.8 und Zug B einen Wert von 0.2 bekommen. Dann hätte A im Durchschnitt Wert 0.55 und B im Durchschnitt 0.45, deshalb wäre A zu spielen.
In der Praxis sind beim Skat zumindest während der ersten Züge Zigtausend Welten denkbar, so dass aus Gründen der Rechenzeit nicht alle untersucht werden können. Das ist auch gar nicht notwendig, denn wie die Arbeit von Schäfer zeigt, hat der Computer nach Untersuchung von 250 zufällig ausgewählten Welten im Normalfall ein so gutes Gefühl, dass die Hinzunahme weiterer Welten keine Verbesserung bringt. Einen Mathematiker wundert das nicht, aber das führt zu weit vom Thema weg...
Dies ist, wenn ich die Autoren richtig verstanden habe, auch der Ansatz von Siegfried und Skat-Stübl, wobei derzeit wohl weit weniger als 250 Welten untersucht werden und außerdem in den ersten Zügen statt der Suche in vielen Welten eine Heuristik bemüht wird.
Viele Welten und Heuristik
Schäfer hat dagegen nicht die Baumsuche in vielen Welten umgesetzt. Er hat in jeder simulierten Welt für jeden Zug, den die KI als nächstes tun könnte, die Stellung an ein heuristisch arbeitendes Skatprogramm übergeben, von diesem zu Ende spielen lassen und das Ergebnis als Bewertung für den Zug genommen. Sein Programm hat dann den Zug gespielt, der im Durchschnitt über alle Welten das beste Ergebnis gebracht hat.
Damit ist es ihm gelungen, ein Programm zu schreiben, dass besser war als das heuristisch arbeitende Skatprogramm, welches er als Hilfsprogramm verwendet hat.
Kritik an "Viele Welten und Minimax"
Im folgenden will ich ein paar Bedenken gegen den Ansatz von Skat-Stübl und Siegfried vorbringen. Dies soll keineswegs bedeuten, dass ich ihre Versuche als zum Scheitern verurteilt ansehe, sondern soll mögliche Schwächen des reinen Algorithmus aufzeigen, um Ansätze für Verbesserungen zu haben.
Der Algorithmus sucht die optimale Lösung für das falsche Problem
Da der Algorithmus bei der Untersuchung der Welten mit offenen Karten spielt, sucht er die bestmögliche Karte für folgendes Spiel: Der Spieler am Zug muss eine Karte ausspielen. Anschließend wird alles aufgedeckt, so dass jeder Spieler unter Kenntnis der konkreten Kartenverteilung optimal spielen kann.
Das muss aber nicht zwangsweise die beste Karte für das Spiel mit verdeckten Karten sein, da die optimale Spielweise bei bekannter Kartenverteilung oftmals völlig anders ist als bei unbekannter Verteilung. Auch die Durchschnittsbildung hilft da nicht notwendig weiter, ja ich behaupte: Im Fall von Skat tut sie es nicht. Mag sein, dass man bei Bridge damit gute Erfahrungen gemacht hat, aber das was da gilt, muss nicht auf Skat übertragbar sein.
Als Alleinspieler baut der Computer sein Spiel oft auf wenige exotische Verteilungen auf
Viele Spiele sitzen aus Sicht des Alleinspielers auf Verlust, werden aber trotzdem gewonnen, da die Gegenspieler am Anfang aus Unkenntnis der genauen Verteilung nicht optimal spielen. In solchen Spielen wird der Computer nur wenige Kartenverteilungen finden, in denen er überhaupt gewinnen kann. Der Computer sucht dann die Karte, die in solchen exotischen Verteilungen zwingend gewinnt, während die Mehrzahl der Verteilungen, nämlich die, wo er den Sieg nicht erzwingen kann, gar nicht in die Berechnung eingeht.
Als Gegenspieler vertraut der Computer darauf, dass sein Partner optimal spielt
Das klassische Anwendungsgebiet des Minimax sind 2-Personen-Spiele, wo streng abwechselnd gezogen wird (wie Schach). Skat wird zwar in der Spieltheorie als 2-Personen-Spiel bezeichnet, richtiger wäre aber 2-Parteien-Spiel, wobei eine Partei aus zwei Personen besteht. Somit kommen auf einen Zug der Partei des Alleinspielers im Durchschnitt 2 Züge der Gegenpartei. Hinzu kommt, dass die Züge nicht streng abwechselnd laufen, da der Gewinner des vorherigen Stichs zum nächsten ausspielt. Dadurch kann z.B. folgende Zugfolge entstehen
1. AS G1 G2
2. G2 AS G1
...
Wenn nun G1 von der KI simuliert wird, so ist zwischen seinen beiden Zügen zweimal sein Partner dran. Der Minimax unterstellt nun, dass alle anderen am Spiel beteiligten Personen dieselben Gedanken wie G1 haben und daher aus Sicht von G1 die für die jeweilige Partei optimalen Züge spielen. Wählt der AS einen anderen, so ist das also ein schwächerer Zug und somit steigt die Gewinn-WSK für die Gegenpartei. Also kein Nachteil. Wählt aber G2 einen anderen Zug, so ist das für die Gegenpartei schlecht und die Gewinn-WSK sinkt!
Das Problem ist nun, dass G2 möglicherweise gar nicht wissen kann, welchen Zug G1 erwartet hat.
Ohne Heuristiken geht es nicht
Gute menschliche Spieler versuchen im Gegenspiel die Karten so zuzugeben, dass ihr Partner möglichst viele Informationen über die tatsächliche Verteilung gewinnen kann. Dazu gehören dann auch solche "unausgesprochenen Absprachen" wie Gegenfarbe zeigen oder die Reihenfolge der Luschenzugabe. Oder das Eingehen auf den Reizwert. Solche überlegungen kriegt man aber nur mit Heuristiken in den Computer.
Ein schönes Beispiel ist das Zeigen von Karo-Bube:
Vorhand (spielt Kreuz)
![Kreuzbube krbu](./images/smilies/krbu.gif)
![Pikbauer pibu](./images/smilies/pibu.gif)
![Kreuz10 kr10](./images/smilies/kr10.gif)
![Kreuzkönig krko](./images/smilies/krko.gif)
![Kreuz8 kr08](./images/smilies/kr08.gif)
Mittelhand
![Karobauer kabu](./images/smilies/kabu.gif)
![Kreuz9 kr09](./images/smilies/kr09.gif)
![Kreuz7 kr07](./images/smilies/kr07.gif)
Hinterhand
![Herzbauer hebu](./images/smilies/hebu.gif)
![Kreuzass kras](./images/smilies/kras.gif)
![kreuzdame krda](./images/smilies/krda.gif)
1.
![Kreuzbube krbu](./images/smilies/krbu.gif)
![Kreuz7 kr07](./images/smilies/kr07.gif)
![kreuzdame krda](./images/smilies/krda.gif)
2.
![Pikbauer pibu](./images/smilies/pibu.gif)
Der Mensch spielt ohne zu zögern Karo-Bube, damit HH evtl. Trumpf-As schonen kann. Der Computer würde folgende Überlegungen anstellen:
Wenn HH den Herz-Buben und mindestens einen weiteren Trumpf hat, macht er einen Trumpf-Stich. In den tue ich besser den Karo-Buben als Kreuz-9, weil er 2 Augen mehr bringt. In allen anderen Fällen ist es egal, welche Karte ich zugebe. Also spiele ich jetzt Kreuz-9. Er würde nicht auf die Idee kommen, den Karo-Buben zu zeigen, da ja in seinem Algorithmus jede Welt mit offenen Karten gespielt wird. Daher tut er beim Durchspielen der Welten so, als ob HH weiß, dass MH den Karo-Buben hat.
Soviel für heute (ist sicher mehr als genug). Zu einem späteren Zeitpunkt kommt vielleicht noch mehr.