Spieltheoretische Analyse von Skatspielen

Mathematische Zusammenhänge des Skatspieles

Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 25. Nov 2024 18:26

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. :tot:

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 klhe07 klhe08 klhe09, 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. klkrko klkr10 klkras ), 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 :)
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ohne11 » 26. Nov 2024 11:04

Hallo Thomas,

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

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. :lol: 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.
"Viele Menschen sind gut erzogen, um nicht mit vollem Mund zu sprechen, aber sie haben keine Bedenken, es mit leerem Kopf zu tun."

- Orson Welles

http://gruenejungsdresden.wordpress.com/
Benutzeravatar
ohne11
 
Beiträge: 2236
Registriert: 24. Nov 2013 15:23
Wohnort: Dresden

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 26. Nov 2024 15:36

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.
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ohne11 » 26. Nov 2024 15:42

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
"Viele Menschen sind gut erzogen, um nicht mit vollem Mund zu sprechen, aber sie haben keine Bedenken, es mit leerem Kopf zu tun."

- Orson Welles

http://gruenejungsdresden.wordpress.com/
Benutzeravatar
ohne11
 
Beiträge: 2236
Registriert: 24. Nov 2013 15:23
Wohnort: Dresden

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 26. Nov 2024 15:53

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.
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skatfuchs » 26. Nov 2024 18:05

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. klka07 klka08 klka09 . 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.
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 8138
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 26. Nov 2024 18:17

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

Skatfuchs hat geschrieben: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 :P ).
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skatfuchs » 26. Nov 2024 19:55

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.
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 8138
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skymaster » 26. Nov 2024 21:32

Ich würde En Deux spiele nehmen.
Zähl' Trumpf und Augen allemal, so hast du nie die "Qual der Wahl", ob Abzuwerfen oder Stechen, und must für's Spiel nicht auch noch blechen!
Benutzeravatar
Skymaster
 
Beiträge: 1908
Registriert: 7. Sep 2005 19:25
Wohnort: Würzburg

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 4. Dez 2024 20:06

Skatfuchs hat geschrieben: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)

Skatfuchs hat geschrieben: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.

Skatfuchs hat geschrieben: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?
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skatfuchs » 5. Dez 2024 00:39

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.
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 8138
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 5. Dez 2024 00:56

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
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 5. Dez 2024 19:39

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

ThomasR hat geschrieben:
  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.
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ohne11 » 6. Dez 2024 12:57

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.
"Viele Menschen sind gut erzogen, um nicht mit vollem Mund zu sprechen, aber sie haben keine Bedenken, es mit leerem Kopf zu tun."

- Orson Welles

http://gruenejungsdresden.wordpress.com/
Benutzeravatar
ohne11
 
Beiträge: 2236
Registriert: 24. Nov 2013 15:23
Wohnort: Dresden

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skatfuchs » 6. Dez 2024 15:48

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.
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 8138
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 6. Dez 2024 17:07

Vielen Dank euch beiden!

ohne11 hat geschrieben: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 :razz:
Und falls jemand diese Zahlen doch verwenden will, ist zu beachten dass {ArithmetischesMittel(…)}^30 < ArithmetischesMittel(…^30)

Skatfuchs hat geschrieben: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. :ja:
Solange keine Betriebsgeheimnisse diskutiert werden, plädiere ich da für offene Kommunikation :top:
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon spock2009 » 10. Dez 2024 05:18

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 klkr10 klkras klkabu als Sequenz ansiehst gibt es offensichtlich Beispiele in denen klkras 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.
spock2009
 
Beiträge: 827
Registriert: 3. Feb 2011 03:15

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 10. Dez 2024 06:56

Vielen Dank für deinen Beitrag, spock2009!

spock2009 hat geschrieben: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 klkr10 klkras klkabu als Sequenz ansiehst gibt es offensichtlich Beispiele in denen klkras 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 klkabu die niedrigste Karte und klkras 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 :D 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
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 10. Dez 2024 07:10

Hier ist übrigens erwähntes Gegenbeispiel:


MH spielt ♥️Herz.

Gegenspieler 1 (am Zug):
kras kr09 ka10
Alleinspieler:
kabu heas he10
Gegenspieler 2:
krbu kr08 kr07

Es sind noch 46 Punkte im Spiel.

GS1 spielt
8. ka10

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

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

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 klkras bei VH sitzt, sonst ist das Spiel ohnehin verloren.
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon ThomasR » 20. Dez 2024 00:04

Ein kleines Update, nachdem ich nun etwas intensiver gegoogelt habe:

Es gibt wohl eine kleine Community skatspielender Forscher, welche eine Reihe von Papers dazu fabriziert haben. In diesen werden fast alle meine Fragen beantwortet. Man findet mehr dazu, wenn man statt nach Skat auch nach Bridge sucht, das ist spieltheoretisch etwas ähnlich.

Die Anstrengungen konzentrieren sich auf diverse Optimierungen von Alpha-Beta, welche dann mit blumigen Namen wie Transposition Tables, Fastest-Cut-First, Killer Heuristic etc. garniert werden.

Manche davon sind sehr effektiv, andere zeigen bei meiner Implementierung keinen Effekt, oder sind sogar kontraproduktiv. Ich kann mir das nur so erklären, dass die Autoren ihre Ideen gegen zufällig generierte Spiele testen, während meine Tests gegen tatsächlich gespielte laufen. Garbage in, garbage out…
(Ein Beispiel ist die Heuristik: Spiele immer die höchste Karte aus, was in realen Spielen sehr fragwürdig ist)

Von der wissenschaftlichen Qualität der Publikationen bin ich eher mittelmäßig begeistert. Manche sind gut, manche nachweislich fehlerhaft, andere führen "Beweise" nach dem Motto "ist doch klar" an, wieder andere konzentrieren sich darauf, experimentelle Daten zu vermuteten Optimierungen ohne theoretische Grundlage aufzuführen. In der Praxis durchaus brauchbar, aber ist das wirklich Wissenschaft?

Jedenfalls habe ich jetzt genug Input, und da ich bisher keine einzige Open-Source-Implementierung gefunden habe, fühle ich mich bestärkt, meine Engine fertigzuschreiben.

Im übrigen wurde meine eingangs genannte Hypothese in einer etwas stärkeren Form bewiesen, aber nur für den Spieler in Vorhand. Auch ansonsten scheinen sich die Forscher nicht wirklich an die Strategien für MH und HH heranzuwagen. Ist wohl zu kompliziert.
ThomasR
 
Beiträge: 11
Registriert: 22. Nov 2024 12:22

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skatfuchs » 20. Dez 2024 13:13

Hallo,

ich gebe ThomasR Recht, dass man da im Internet und diversen Foren sehr widersprüchliche Sachen darüber erfährt, was mit Wissenschaftlichkeit wenig zu tun hat.
Auch mit der Graphentheorie kommt man da nicht sehr weit.

Für uns ist das Glaskastenproblem schon länger gelöst; siehe hier den Fox im Forum.
Wir nutzen das auch, um Verbesserungen bei der KI nachzuweisen, in dem wir je 100T Spiele je nach Kategorie zuvor mit Hilfe des Glaskastens lösen und danach mit unserer KI, wobei das Ziel besteht, sich immer mehr dem Glaskasten zu nähern.
Wir lassen die KI auch sich selbst trainieren, die spielen da ein komplettes Spiel in ca. 1s; damit kann man 100T Spiele in 2h spielen lassen.
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 8138
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon spock2009 » 23. Dez 2024 08:46

Skatfuchs hat geschrieben:Wir lassen die KI auch sich selbst trainieren

Ich hoffe das funktioniert. Es wäre denkbar, dass die "eine" KI mit seltsamen Ausspielen auf seltsame Ausspiele der "anderen" KI rücksicht nimmt und sie sich so gegenseitig in abwegigen Spielweisen bestärken.
spock2009
 
Beiträge: 827
Registriert: 3. Feb 2011 03:15

Re: Spieltheoretische Analyse von Skatspielen

Beitragvon Skatfuchs » Gestern 15:24

spock2009 hat geschrieben: Ich hoffe das funktioniert. Es wäre denkbar, dass die "eine" KI mit seltsamen Ausspielen auf seltsame Ausspiele der "anderen" KI rücksicht nimmt und sie sich so gegenseitig in abwegigen Spielweisen bestärken.


Hallo,

diese Gefahr besteht wohl eher nicht. In der ersten äußeren Selbstlernstufe geht es mehr darum, sich eine eigene Datenbasis für das Reizen, die Erkennbarkeit und Auswahl von Spielen, das Trumpfspiel, das Anspiel im Allein- und Gegenspiel zu schaffen etc.
Je nach Qualität der KI-Spieler ändert sich das nämlich, wie man auch an dem "Fox" sieht, wo es eine extra Kategorie gibt, bei der nur die besseren Spieler gewertet wurden, wofür es aber wesentlich weniger Spiele gibt. Der Schnitt der menschlichen Spieler lag bei den ca. 200 Mio Spielen bei ca. 850 Punkten/Serie und da liegen wir schon deutlich drüber.
Pro Tag schaffen die KI-Spieler ja schon ca. 1 Mio Spiele und schaffen damit eine bessere Spielbasis.
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 8138
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz


Zurück zu Skat und Mathe

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast