Spieltheoretische Analyse von Skatspielen

[ThomasR]

Hallo liebe Skatbrüder!

Ich würde gern verstehen, wie Skatfox oder ähnliche Analysesoftware den besten Zug in einer gegebenen Spielsituation findet.
Solche Software behandelt Skat spieltheoretisch als Spiel mit vollständiger Information, d.h. alle Spieler spielen während der Analyse mit offenen Karten; psychologische Spielchen sind ausgeschlossen.
In der Fachsprache sagt man statt "den besten Zug finden" auch "das Spiel lösen".

Also wie löst man nun ein gegebenes Spiel?

Mein naiver Ansatz lautet: alles ausprobieren (vgl. Minimax-Algorithmus).
Schnell sieht man, dass das zu einer kombinatorischen Explosion führt, d.h. die Anzahl der möglichen Spielverläufe kann in die Milliarden gehen und ist praktisch nicht durch Ausprobieren zu lösen.

Nächste Idee: Alpha-Beta-Suche. Das heißt salopp gesagt, man probiert nur soweit aus, bis man feststellt, dass die aktuell untersuchte Variante die bisher beste Lösung sicher nicht übertreffen kann.

Weitere Optimierung: gewisse Züge kann man schon ausschließen, z.B. wenn der Spieler alle 3 Luschen einer Farbe hat , muss ich nicht alle durchprobieren, sondern das Ergebnis ist für alle gleich.

Hypothese: Hat der Spieler am Zug eine fortlaufende Sequenz von Karten einer Farbe (z.B. ), so muss man nur die höchst- und niedrigstwertige Karte untersuchen.
(Bei Nullspielen reicht es sogar eine beliebige Karte zu wählen, das sollte klar sein.)

Außerdem kann man programmatisch leicht erkennen, ob der Alleinspieler alle restlichen Stiche macht bzw. keinen Stich mehr machen kann.

Nun meine Fragen:

1. Gibt es vielleicht einen noch besseren Algorithmus?
2. Wie kann man die obige Hypothese beweisen? Ich habe es im Gefühl, dass sie richtig sein muss, aber ich kann das nicht zweifelsfrei begründen.
3. Welche Optimierungsmöglichkeiten habe ich vergessen? (Mal von Caching und Parallelisierung abgesehen)
4. Wie kann man anhand einer gegebenen Kartenverteilung die Anzahl der möglichen Spielverläufe berechnen?

Als kleines Hobbyprojekt möchte ich eine kostenloses freies (Open Source) webbasiertes Skat-Analysetool schreiben, und hoffe, dass ihr mir hier weiterhelfen könnt, weil mein erster Prototyp viel zu langsam ist. Besten Dank

[ohne11]

Hallo Thomas,

witzig, dass das Thema genau jetzt aufkommt, da heute mein Preprint dazu erschienen ist.

Was klassische Solver machen, wie du bereits korrekt festgestellt hast, ist für gegebene Kartenverteilungen das Spiel als Spiel mit perfekter Information behandeln. Daraus resultiert die Augenzahl auf die eine bestimmte Karte führt als Nash-GG des darunterliegenden Teilbaumes.
Dass das nicht die spieltheoretische Lösung ist, sollte klar sein. Denn relevant ist nicht, wie hoch ich das Spiel schlage, sondern dass ich möglichst viele Verteilungen schlage. Und dafür ist der Pik König, der bei gegebener Verteilung nur auf 62 führt u.U. viel besser als Kreuz Bube der auf 74 führt.

D.h. was du klassisch tun müsstest, ist den Solver auf alle möglichen Restverteilungen anzuwenden. immerhin sind das nur noch (22ü10)*(12ü10), da du wenigstens deine eigenen Karten kennst und diese einzigartig sind.

Es gibt für solche imperfect-information games auch Ansätze wie counterfactual-regret minimization zB. Mein Vorschlag wäre, das Ganze auf einem Quantencomputer laufen zu lassen und einfach alle Verteilungen * alle Spielverläufe parallel durchzurechnen um dann die Gewinnäste zu zählen und die Karte mit dem größten Unterraum an Gewinnästen ist folglich jene, die die Payoff-Funktion maximiert.

Ich mach mal einen eigenen Thread dazu auf.

[ThomasR]

Hallo ohne11,

ich glaube, wir reden hier von verschiedenen Themen.

Mir geht es wirklich nur um die Analyse unter vollständiger Information.
Eine KI, die nur ihre eigenen Karten kennt, ist natürlich auch interessant, soll aber in diesem Thread erstmal außen vorbleiben.

[ohne11]

Hallo Thomas,

ja das stimmt.

Aber da du meintest: "In der Fachsprache sagt man statt "den besten Zug finden" auch "das Spiel lösen".
"

ist es denk ich wichtig zu sagen, dass ebenjener Zug keiner ist, den man aus der perfekten Information ableiten kann. Die spieltheoretische Lösung von Skat ist die Karte, die bei unbekannter Restverteilung den höchsten Ertrag bringt, d.h. die meisten Äste schlägt.

Grüße

[ThomasR]

Ja, um es nochmal anders zu formulieren:

Die beiden Spiele

• Skat
• "Skat mit offenen Karten"

sind zwei unterschiedliche Spiele, die spieltheoretisch andere Lösungsansätze erfordern.

Mich interessiert nur das letztere, und dabei eine Lösung, die auch praktisch berechenbar ist.

[Skatfuchs]

Hallo ThomasR,

"Nun meine Fragen:
1.Gibt es vielleicht einen noch besseren Algorithmus?
2. Wie kann man die obige Hypothese beweisen? Ich habe es im Gefühl, dass sie richtig sein muss, aber ich kann das nicht zweifelsfrei begründen.
3. Welche Optimierungsmöglichkeiten habe ich vergessen? (Mal von Caching und Parallelisierung abgesehen)
4. Wie kann man anhand einer gegebenen Kartenverteilung die Anzahl der möglichen Spielverläufe berechnen?"

Meine konkreten Antworten:
zu 1. Den gibt es, wir verwenden ihn für die implementierte KI hier im Forum. Einen großen Teil davon findest du schon in meinem oben stehenden Buch.
zu2. Die Hypothese gilt nur bei Karten mit gleichem Augenwert; z.Bsp. . Ansonsten stimmt diese nicht, da natürlich der Augenwert vordergründig zum Sieg im Skatspiel beiträgt.
zu 3. Infos aus der Reizung; Infos aus dem Anspiel, der Kartenzugabe, dem Abwerfen und dem Wimmeln.
zu 4. Mit den jetzigen Technischen Möglichkeiten, vor allem von Endgeräten gar nicht. Du musst zuvor den Suchbaum deutlich einschränken, erst dann wird es was.

Ich gehe dabei davon aus, dass du doch das reale Skatspiel mit unvollständiger Info meinst; denn für das andere ist das Problem ja schon längst gelöst, vgl. den Fox hier.

Ich hoffe, dir etwas geholfen zu haben.

[ThomasR]

Vielen Dank für die Antwort, aber wir reden immer noch aneinander vorbei

Ich gehe dabei davon aus, dass du doch das reale Skatspiel mit unvollständiger Info meinst; denn für das andere ist das Problem ja schon längst gelöst, vgl. den Fox hier.

Eben das ist mein Punkt: ich meine tatsächlich das Spiel mit vollständiger Information und würde gern einfach nur verstehen, wie der Fox funktioniert (ohne bis zum Ende des Universums zu rechnen ).

[Skatfuchs]

Hallo,

in der Regel ist das ein optimierter Minimax-Algorithmus für das Skatspiel, der effektiv programmiert wurde. Der hier wurde vor ca. 10 Jahren sogar noch in Java programmiert; ist aber auch noch schnell genug. Welche Programmiersprache benutzt du?
Fange doch einfach zuerst mal damit an; eine Lösung für eine bekannte Kartenverteilung zu finden und nicht gleich alle mit der optimalen Augenzahl.

[Skymaster]

Ich würde En Deux spiele nehmen.

[ThomasR]

in der Regel ist das ein optimierter Minimax-Algorithmus für das Skatspiel, der effektiv programmiert wurde.

Willst du Details zu den Optimierungen im Fox verraten, oder ist das ein Betriebsgeheimnis? (wofür ich Verständnis hätte)

Welche Programmiersprache benutzt du?

Da das ganze rein im Browser laufen soll, habe ich JavaScript verwendet. Man könnte natürlich auch mit WebAssembly draufhauen, aber ich glaube nicht, dass die Programmiersprache da so viel ausmacht.
Ich brauche Performance-Verbesserungen in der Größenordnung 1000x.


Kleiner Einblick in den aktuellen Stand. Hier sieht man, dass das schon ganz gut funktioniert. Ist natürlich alles noch ne große Baustelle, aber die Analyse-Engine ist gut getestet und rechnet zuverlässig. Nur eben langsam. Ein Worst Case findet sich hier, da wartet man dan mehrere Minuten.

Fange doch einfach zuerst mal damit an; eine Lösung für eine bekannte Kartenverteilung zu finden und nicht gleich alle mit der optimalen Augenzahl.

Macht das einen Unterschied? Beim Minimax bekommt man die Augenzahl doch gratis, oder?

[Skatfuchs]

Hallo Thomas,

ich verstehe nicht, warum du dir diese Mühe machen willst?
Es gibt hier diese perfekte Lösung, einschließlich der Berechnung der Skatlegung mit 6 potentiellen Karten und die ist für jedermann kostenlos nutzbar.
Das Programm ist vor über 10 Jahren geschrieben wurden und es macht mir da eine große Mühe, alle Abstraktionen und Abbruchkriterien nochmals heraus zu suchen und für dich nachvollziehbar zu gestalten.
Außerdem interessiert das hier wohl nur dich und nicht die anderen Skatfreunde, zumal das reale Skatspiel ja nur mit einer unvollständigen Info arbeitet, was wesentlich schwieriger zu lösen ist und meine ganze Aufmerksamkeit und Konzentration kostet.
Ich hatte dir da vor Tagen schon eine separate mail geschrieben, damit wir die anderen Skatfreunde nicht langweilen.

[ThomasR]

Ja, so ist das nun mal mit Open Source: obwohl die "perfekte" Lösung schon existiert, setzt sich trotzdem nochmal jemand hind und schreibt das neu.

[ThomasR]

Ich komme auf das eigentliche Thema zurück, und gebe ein Update über meinen derzeitigen Wissensstand

1. Gibt es vielleicht einen noch besseren Algorithmus?
2. Wie kann man die obige Hypothese beweisen? Ich habe es im Gefühl, dass sie richtig sein muss, aber ich kann das nicht zweifelsfrei begründen.
3. Welche Optimierungsmöglichkeiten habe ich vergessen? (Mal von Caching und Parallelisierung abgesehen)
4. Wie kann man anhand einer gegebenen Kartenverteilung die Anzahl der möglichen Spielverläufe berechnen?

1. Nach meinem derzeitigen Kenntnisstand gibt es keinen. Ich habe einiges zum Spiel ohne vollständige Information gefunden, aber für die Analyse mit vollständiger Information ist wohl Alpha-Beta nach wie vor das Mittel der Wahl.
2. Ich habe ein Gegenbeispiel gefunden mit MH am Zug als AS. Ein Gegenbeispiel für MH am Zug mit AS in HH sollte es auch geben. Meine Hypothese hat für HH am Zug weiter Bestand. Für die anderen Fälle bin ich nicht sicher.
3. Es ist für die optimale Funktion des Algorithmus entscheidend,
   
   1. In jedem Schritt den jeweils besten Zug zuerst auszuprobieren, oder so früh wie möglich.
   2. Eine Evaluierungsfunktion zu finden, die möglichst präzise die minimal möglichen Punkte des Gegenspiels vorhersagt.
   Gut zusammengefasst ist das z.B. hier: https://artint.info/3e/html/ArtInt3e.Ch14.S3.html
   Die Analyseengine muss also nicht nur dumm ausprobieren, sondern auch noch etwas schlau sein. Natürlich kann sie nicht mit Sicherheit den besten Zug voraussagen, aber im besten Fall implementiert sie eine Heuristik/Strategie, mit der die Karten nach geschätzer Qualität absteigend sortiert und in dieser Reihenfolge ausprobiert werden.
4. Schwierig. Oder gar praktisch unmöglich? Ich habe mal ein paar Farbspiele bis 18 Restkarten durchgezählt, und dann exponentiell interpoliert. Die Ergebnisse liegen im Bereich 6x10^10 bis 7x10^13. Das ist natürlich sehr ungenau, gibt aber zumindest mal eine grobe Idee der Größenordnung. Falls das das richtige Modell ist.
   Mit Sicherheit kann man sagen, dass das richtige Ergebnis zwischen 10! ≈ 3x10^6 und (10!)^3 ≈ 5*10^19 liegen muss, was allerdings recht unbrauchbar ist.

[ohne11]

Beim letzten Punkt kann ich dir helfen. Natürlich ist es unpraktikabel
(10!)^3 spielverläufe pro Verteilung durchzurechnen, da die Bedienpflicht immer zu einer drastischen Reduzierug führt. Aus der Simulation kann ich dir sagen, dass die mittlere Wahlfreiheit bei 2,844 Karten pro Farbspiel bzw 2,994 Karten beim Grand liegt. Das heißt im Mittel kann man aus knapp 3 Karten pro Zug wählen.

[Skatfuchs]

Hallo ThomasR,

in dem von dir zitierten Artikel wird ja folgendes allgemein beschrieben:
"Viel Arbeit steckt in gute Auswertungsfunktionen zu finden. Es besteht ein Zielkonflikt zwischen dem der Rechenaufwand, der zur Berechnung der Auswertefunktion erforderlich ist, und die Größe des Suchraums, der in einem bestimmten Zeit. Es ist eine empirische Frage nach dem besten Kompromiss zwischen einem komplexe Auswertungsfunktion und einen großen Suchraum."

Ich kann das nur unterstreichen, was für das Skatspiel bedeutet:
- Reduktion auf die Struktur der Karten, unabhängig von der Farbe
- Beachtung der Bedienpflicht, damit ca. 3 Karten pro Stich relevant
- Erkennung nicht gewinn- bzw. verlierbarer Spiele; am einfachsten ist das wohl bei NO-Spielen, klappt aber auch bei Farb- und Grandspielen
- Anspiel der optimalen Karte des AS und der Folgekarten. Bei Farbspielen ist der Trumpfzug in Anbetracht des Kartenstandes oft relativ einfach zu finden.
- Anspiel der optimalen Karte im Gegenspiel; auch das ist oft findbar
.....
So kann man den Suchbaum deutlich einschränken und findet eine Lösung innerhalb weniger Sekunden. Man sollte dabei beachten, wie bereits oben beschrieben, dass man nicht eine Lösung finden muss, die die meisten Augen einbringt, sondern den besten Spielertrag.

Da dies wahrscheinlich hier im Detail kaum noch jemand interessiert, so sende ich dir mal ne mail an deine Im Forum hinterlegte Adresse.

[ThomasR]

Vielen Dank euch beiden!

Aus der Simulation kann ich dir sagen, dass die mittlere Wahlfreiheit bei 2,844 Karten pro Farbspiel bzw 2,994 Karten beim Grand liegt.

Das führt also ganz grob zu einer Gesamtzahl von 2.844^30 bzw. 2.994^30, beide in der Größenordnung 10^14.
Praktisch nicht relevant, aber mein Wissensdurst ist damit gestillt
Und falls jemand diese Zahlen doch verwenden will, ist zu beachten dass {ArithmetischesMittel(…)}^30 < ArithmetischesMittel(…^30)

Da dies wahrscheinlich hier im Detail kaum noch jemand interessiert,

Ich bin dir sehr für deine Hilfe dankbar, aber woher willst du denn wissen, dass es niemanden interessiert? Selbst wenn heute hier niemand mitliest, kann es doch sein, dass schon morgen jemand genau nach diesem Thema sucht.
Solange keine Betriebsgeheimnisse diskutiert werden, plädiere ich da für offene Kommunikation

[spock2009]

Hallo ThomasR, ich finde super, dass du dich mit dem Thema auseinandersetzt und ich finde die Beitrage sehr spannend zu lesen.

Zu 1. fällt mir spontan nur das Stichwort Graphentheorie ein, mit der viel in dem Bereich optimiert wird. Da würde ich anfangen zu suchen, wenn ich den Hintern noch hoch bekäme

zu 2. Es gibt Fälle, in denen es sinnvoll sein kann in HH 10 statt Ass zu nehmen, damit der Partner weiß dass man das Ass auch noch führt. Das Argument entfällt aber bei der "vollständigen Information". Wenn du allerdings auch in Trumpf als Sequenz ansiehst gibt es offensichtlich Beispiele in denen die richtige Wahl ist.
Trotzdem könnte dieser Ansatz (allerdings "Karte mit höchstem Wert und niedrigstem Wert") Worst Case Szenarien abklopfen...

zu 3. könnte ich mir vorstellen, dass man Teile von Berechnungen wiederverwenden könnte. Sind Farben verteilt, so ist die Reihenfolge in der sie vorgetragen werden vlt. irrelevant, da sie zu jeder Zeit in dem Spiel genau gleich ablaufen. Dies muss natürlich im Einzelfall geprüft werden (die Klärung einer Farbe kann zB Einschübe rausnehmen o.ä).

zu 4. Da der Ausspielende im Spielverlauf je nach gelegter Karte wechselt, sind wohl nur Abschätzungen sinnvoll. Die Berechnung der exakten Möglichkeiten dürfte ähnlich Komplex sein wie das ganze geplante Programm.

PS: Ich sehe das Programm als Übung für den nächsten Schritt, bei dem du auf die vollständige Information verzichtest. Aber um das hinzubekommen ist es mMn hilfreich erst mal das (zum Bsp von "Fox") bereits gelöste Problem gut zu verstehen und selbst zu implementieren.

[ThomasR]

Vielen Dank für deinen Beitrag, spock2009!

Zu 1. fällt mir spontan nur das Stichwort Graphentheorie ein, mit der viel in dem Bereich optimiert wird. Da würde ich anfangen zu suchen, wenn ich den Hintern noch hoch bekäme

Danke, aber mir fällt da nicht wirklich ein, was sich daraus ergeben könnte. Graphentheoretisch ist die sache klar: es handelt sich um einen (endlichen) zusammenhängenden Baum, und durch Alpha-Beta-Pruning kann man jeweils einen bestimmten Teilbaum abschneiden.

zu 2. Es gibt Fälle, in denen es sinnvoll sein kann in HH 10 statt Ass zu nehmen, damit der Partner weiß dass man das Ass auch noch führt. Das Argument entfällt aber bei der "vollständigen Information". Wenn du allerdings auch in Trumpf als Sequenz ansiehst gibt es offensichtlich Beispiele in denen die richtige Wahl ist.
Trotzdem könnte dieser Ansatz (allerdings "Karte mit höchstem Wert und niedrigstem Wert") Worst Case Szenarien abklopfen...

Genau, Karte mit höchstem und niedrigstem Wert. Für diese Betrachtung ist also die niedrigste Karte und die höchste. Und die Frage ist: gibt es Situationen, wo nur die 10 gewinnt?

Hier wäre ich für konkrete Beispiele dankbar. Ich habe wie gesagt eins gefunden mit dem Alleinspieler in MH. Intuitiv ist das aber nicht, man muss erstmal kurz drüber nachdenken, warum nur die mittelwertige Karte da gewinnt. Für die anderen Fälle steh ich noch etwas auf dem Schlauch.

zu 3. könnte ich mir vorstellen, dass man Teile von Berechnungen wiederverwenden könnte.

Super, diese Idee hatte ich auch, und habe das bereits umgesetzt Mein Tool berechnet einen Hash der aktuellen Kartenverteilung und legt das Ergebnis im Arbeitsspeicher ab. Das führt zu einer deutlichen Verschnellerung, aber nur etwa Faktor 2-3.

[ThomasR]

Hier ist übrigens erwähntes Gegenbeispiel:


MH spielt ♥️Herz.

Gegenspieler 1 (am Zug):

Alleinspieler:

Gegenspieler 2:


Es sind noch 46 Punkte im Spiel.

GS1 spielt
8.

Für den Alleinspieler ist nun die beste Karte, womit er noch +24 Punkte (-22) holen kann. Der liefert nur +23 (-23).

Der Grund ist, dass die Gegenpartei noch genau einen Stich macht, und zwar mit dem , und auf jeden Fall die abholt.
Wenn MH den spielt, dann wartet HH auf die nächste Runde, und bekommt damit und , also 1 Punkt mehr als mit und .

Dieses Szenario ist sogar einigermaßen realistisch, wenn HH mitgezählt hat, und weiß, das die Gegenpartei zwingend den einen Punkt zum Sieg benötigt. Hier muss er davon ausgehen, dass das bei VH sitzt, sonst ist das Spiel ohnehin verloren.