Quantencomputer und des Skats formale Lösung

[ohne11]

Hallo liebe Community,

Wie ihr sicher schon festgestellt habt, bin ich seit geraumer Zeit nicht mehr im Forum aktiv. Das liegt an verschiedenen Umständen welche sowohl privater als auch beruflicher Natur sind. Umgekehrt heißt das nicht, dass ich das Skatspiel eingestellt habe; es nimmt jedoch nicht mehr den Stellenwert in meinem Leben ein wie noch vor einigen Jahren. An dieser Stelle möchte ich jedoch die Gelegenheit nutzen und euch an einigen Entwicklungen teilhaben lassen, welche sich überraschenderweise in der Schnittmenge meines beruflichen Schaffens und meines Hobbies befinden. Worum es dabei geht, konntet ihr gewiss bereits dem Titel entnehmen.

Seit vielen Jahren gibt es in der Mathematik einen eigenen Bereich, der sich „Spieltheorie“ nennt. Ich weiß, dass das für einige Bewanderte hier eine redundante Information ist, aber bin mir sicher, dass der ein oder andere Leser nicht so tief in der Materie steckt.
Grundsätzlich beschäftigt sich die Spieltheorie mit der Mathematik hinter Entscheidungssituationen. D.h. man versucht herauszufinden, in welchen Situationen welche Strategien besonders vorteilhaft sind und warum man wie handeln sollte, um ein bestimmtes Ziel zu erreichen. Dass es dabei recht offensichtliche Verbindungen zwischen eigentlichen „Spielen“ und realen Problemen in der Wirtschaft gibt, sieht man sicherlich schnell, wenn man versucht die optimale Monopoly-Strategie zu finden. Inwiefern ein Unternehmen, wie z.B. eine Bank, jedoch davon profitieren kann, dass mir ein Skat-Computer sagt „Spiel Karo Ass“ ist weitaus weniger unmittelbar ersichtlich.

Grundsätzlich unterteilt man Spiele ganz verschieden. Zum einen mit Hilfe des sog. Bewersdorff-Dreiecks, welches sie nach ihrem Anteil an strategischen, kombinatorischen und Glücksgehalt einordnet. Ein rein kombinatorisches Spiel ist beispielsweise Schach. Beim Schach könnte man prinzipiell perfekt spielen, wenn man nur in der Lage wäre immer alle Optionen zu durchdenken. Als rein strategisches Spiel bezeichnet man zum Beispiel Stein-Schere-Papier. Es gibt an sich keine Kombinatorik bei diesem Spiel – ich gewinne mit der richtigen Strategie schließlich immer. Ich muss dazu „nur“ wissen, was mein Gegenüber macht, dann hab ich gewonnen. Beide Spiele enthalten keine Glückskomponente. Ein reines Glücksspiel ist hingegen Roulette. Es gibt keine Strategie und keine kombinatorischen Überlegungen, die irgendwie Einfluss auf meinen Erwartungswert hätten. Skat ordnet sich ziemlich mittig in diesem Dreieck ein und besitzt in Teilen alle diese Komponenten, die sich gegenseitig beeinflussen können. Die Kombinatorik (sprich die Menge aller Verteilungen und möglicher Spielverläufe) gibt die Rahmenbedingungen für die Strategie vor – jedoch ist es schwer bis unmöglich in diesem riesigen Raum an Möglichkeiten den optimalen Zug zu finden. Und damit sind wir schon beim nächsten Punkt:

Was ist denn eine formale Lösung eines solchen Spiels?

Eine andere Möglichkeit Spiele zu einzuteilen, ist die Fokussierung auf den gegebenen Informationsgehalt. Schach ist beispielsweise ein Spiel mit perfekter Information, d.h. es gibt keine Unklarheiten – jeder Spieler sieht alles was auf dem Brett geschieht. Für solche Spiele besteht die Hauptschwierigkeit in der Berechnung in der schieren Größe des Entscheidungsbaumes. Shannon hat 1950 die potentielle Rechenzeit auf einem 2 kHz Computer auf etwa 10^90 Jahre geschätzt bei etwa 10^120 möglichen Stellungen. Da das weit, weit außerhalb der mutmaßlichen Lebensdauer des Universums liegt, ist es natürlich unsinnig, solch eine Berechnung überhaupt anzufangen. Dennoch gibt es heute Bestrebungen, mit einer neuen Technologie und völlig neuen Art zu rechnen – dem Quantencomputing - damit fertig zu werden.

Im Gegensatz zu Schach ist Skat ein Spiel mit „imperfekter Information“. Das heißt, mir liegen eben nicht alle Informationen vor und ich muss den stetig wachsenden Informationsgehalt während des Spiels genauso in meine Entscheidungen mit einfließen lassen, wie eine ganze Reihe von plausiblen Annahmen und Zwangsvermutungen. Auf der Haben-Seite hingegen steht die Kombinatorik aus der Spielabfolge, welche – im Gegensatz zum Schach – doch deutlich begrenzt ist. Ein Spiel besteht nämlich nur aus 30 Zügen.

Wo ist also das Problem?

Das Problem für die Berechnung kommt in aller erster Linie aus der Unbekanntheit der (Rest-) Verteilung. Denn: Wie wir alle wissen, ist es für eine gegebene Verteilung kein Problem mehr, alle Spielverläufe durchzurechnen. Ihr könnt es alle machen – mit dem SkatFox!
Aber ist der Skatfox dann nicht die Lösung des Problems?

Jein.
Denn was der Skatfox macht (und das sehr gut, ich liebe dieses Tool!), ist eine bestimmte Verteilung zu analysieren und bei allseits bestem Spiel aufzuzeigen, welche Karte auf welche Augenzahl am Ende führt. Da könnte man doch denken, die Karte mit der höchsten Zahl ist die beste, oder? Und genau da unterscheidet sich die Lösung von klassischen Solvern von der spieltheoretischen Lösung der Aufgabenstellung. Die Aufgabenstellung im spieltheoretischen Sinne lautete nämlich:

[ohne11]

Maximiere die Payoff-Funktion!

Das heißt, den Erwartungswert einer Karte bei unbekannter Verteilung.
Und dabei ist es eben egal, ob Kreuz Bube auf 71 führt und Pik König nur auf 64. Wichtig ist: Beide führen auf mindestes 61 für eben diese Verteilung. Und Pik König ist besser als Kreuz Bube, wenn er 174 Verteilungen mit mindestens 61 schlägt und Kreuz Bube nur 91. Ich denke, es ist klar, worauf das hinausläuft.

Was ist also nun die spieltheoretische Lösung?
Blenden wir einmal der Einfachheit halber Dinge wie Reizung, Drückung u.Ä. aus und sagen einfach es gibt nur Handspiele und Alleinspieler wird immer Vorhand. Das ist alles implementierbar, aber bedeutet hier nur unnötigen Aufwand und stellt kein konzeptionelles Problem für die Berechnung dar.
Wenn man dies tut, dann ist ein Spiel im Wesentlichen eine Abfolge der 30 zu spielenden Karten. Die Menge aller Spiele für eine gegebene Verteilung ist die Menge aller erlaubten Permutationen (also Vertauschungen) für diese Karten. Erlaubt sind alle, welche die Regeln erfüllen, d.h. in erster Linie die Bedienpflicht. Wenn man sich der spieltheoretischen Lösung nähren will, muss man also folgendes tun:
Man betrachte die Menge aller möglichen Rest-Verteilungen. Das sind – wohlgemerkt nach Kenntnis der eigenen Karten – (22) über (10) = 42 678 636. Dann nimmt man diese gut 42 Mio Verteilungen, wendet den Skatfox auf alle dieser Verteilungen an und prüft, welche dieser Verteilungen man bei - allseits bestem Spiel – also aus eigener Kraft schlagen kann und welche Karte dafür zu spielen wäre. Alle Karten, welche für diese Verteilung auf 61+ führen bekommen eine +1 zu ihrem Value dazuaddiert, als Gewinnerkarte für diesen Ast. So fährt man fort bis man durch alle Verteilungen durch ist und schaut nicht nach der Augenzahl, auf die die einzelne Karte führt sondern auf die Anzahl der Äste, welche sie auf mindestens 61 führt. Diese führt zu einer Gewinnwahrscheinlichkeit P_win, welche dann zu einer Payoff-Funktion Pay(x,i) beiträgt
Pay(x,i) = Sum_games^n P_win(x,i)*Val(x,i) – 2*(1-P_win(x,i))*Val(x,i)
Natürlich habe ich jetzt direkt eingesetzt, dass Verlustspiele doppelt Minus gerechnet werden. Man könnte auch problemlos die 50 Extrapunkte nach dem Seeger-Fabian-System addieren, aber das spielt hier konzeptionell keine Rolle.
Die gesuchte Karte maximiert also die Payoff-Funktion und wenn wir einen Spielverlauf gefunden haben, bei dem jede Karte an jeder Stelle des Spiels (das heißt nach aktuell bekanntem Informationsstand) ein lokales Maximum aufweist (das heißt, sie ist „stabil“), dann befinden wir uns in einer Form des Nash-Gleichgewichts, eines Zustandes, bei dem es für keinen beteiligten Spieler Sinn ergibt von seiner Strategie abzuweichen. Das ist der „optimale Spielverlauf“, also die formale spieltheoretische Lösung von Skat (die muss natürlich nicht eindeutig sein, nur existieren).

Also eigentlich ganz einfach, oder?
Konzeptionell, ja. Praktisch nein. Die schiere Größe des Baumes stellt ein Problem für den Rechner dar. Und da haben wir bei der 42-Millionen-fachen Anwendung des Skatfox noch nicht einmal die Skatfindung und Drückung berücksichtigt. Man würde also sagen: Das Problem skaliert nicht. Bzw der Algorithmus nicht mit der Problemgröße. Denn, wenn der Solver für eine Verteilung 1 Sekunde rechnet, dann braucht er für 42 Mio Verteilungen knapp 1,5 Jahre. Mit Findung und Drückung vermutlich länger als ich lebe und wenn ich bedenke, dass ich 30 Karten spielen will anstatt nur einer und danach vielleicht noch ein Spiel und noch eins, dann hilft mir auch ein 1000 mal so schneller Supercomputer nicht weiter. Wir brauchen also eine neue Idee zu rechnen, die anders skaliert: nämlich nicht-exponenziell.

Wie hat man denn sowas bisher gehandhabt?

Im Allgemeinen werden Spiele mit unvollständiger Information heutzutage mit verschiedenen Methoden gelöst. Die Suche nach Nash-Gleichgewichten über den Lemke-Howson-Algorithmus, die Modellierung als Bayes'sches Spiel, bei dem die Ungewissheit auf eine probabilistische Verteilung abgebildet wird, oder die so genannte kontrafaktische Regret-Minimierung, bei der die Regret-Funktion alternativer Strategien minimiert wird, gehören zu den gängigsten Methoden, um die besten Strategien für Spiele dieser Kategorie zu finden. In letzter Zeit sind jedoch Deep-Learning-Algorithmen und Monte-Carlo-Baumsuche bei komplexeren Spielen immer beliebter geworden. Welche dieser Methoden für ein bestimmtes Problem am besten geeignet ist, hängt sehr stark vom Problem selbst, den verfügbaren Ressourcen und der gewünschten Genauigkeit der Lösung ab.

Was ist ein Quantencomputer?

Ein Quantencomputer (QC) ist eine Maschine, welche übersogenannte Quanten-Gates (unitäre Operationen) Quantenzustände manipuliert. So weit – so einfach, oder? Ich möchte an dieser Stelle nicht unnötig weit in Details gehen, damit lassen sich ganze Bibliotheken füllen. Wichtig ist: Es ist eine grundlegend neue Art zu rechnen, welche sich die Überlagerung bzw sog. „Verschränkung“ von Quantenzuständen zu Nutze macht, um hochdimensionale Probleme effizient zu lösen. Der Vorteil entsteht dabei daraus, dass Quantenteilchen in der Physik nicht nur einen Zustand annehmen können (klassisches Computing „0“ oder „1“ = ober- oder unterhalb einer Triggerschwelle bzw „Strom an“ oder „Strom aus“), sondern dass sie in einer Überlagerung vieler Zustände existieren. Die Projektion auf einen Zustand findet erst im Moment der Messung statt. Der eine oder andere kennt sicherlich das in der Pop-Kultur weit verbreitete Gedankenexperiment mit „Schrödingers Katze“.
Das heißt nun, dass in einem Quantenzustand potentiell „mehr Information“ steckt als in einem klassischen. Letztlich gibt es Probleme, welche bei wachsender Problemgröße klassisch exponenziell skalieren, also Rechenzeit ~ exp(n), wobei ein QC nur subexponenziell viele Schritte zur Lösung benötigt Rechenzeit ~Polynom(n).
Bezogen auf Skat bedeutet das, dass wir bei dem Versuch alle möglichen Restverteilungen und alle Spielverläufe innerhalb dieser Verteilungen, nicht nacheinander berechnen müssen – was Jahre dauern würde, sondern dass wir in „Echtzeit“ alle Verteilungen gleichzeitig abbilden und ausrechnen können.

Mit anderen Worten: Skat ist jetzt langweilig, weil gelöst oder wie?

[ohne11]

Mit Nichten! Was meine Co-Autoren und ich in diesem Artikel

https://arxiv.org/abs/2411.15294

getan haben, ist eine Idee auf ein Proof-of-Concept-Level zu bringen. Dabei wird systematisch skizziert, wie ein QC eine 2-Spieler-Endspielstuation mit jeweils 2 Karten lösen würde. Das alles ist auf einer QPU bzw einem Simulator mit 12 Qubits (der Grundrecheneinheit eines QC) in unserer Encodierung darstellbar. Im nächsten Schritt werden wir dieses Prinzip auf 3 Spieler mit 3 Karten ausdehnen und zeigen, dass dieser PoC prinzipiell für beliebig viele Karten erweiterbar ist. Für dieses folgende Szenario benötigen wir etwa 40 Qubits. Das ist in etwa an der Grenze dessen, was aktuell mit Emulatoren machbar ist. Solange echte Quantenhardware die klassischen Rechner noch nicht überholt hat, sind diese das Mittel der Wahl. Die besten weltweit schaffen zwischen 40 und 50 Qubits. Dem Ganzen ist keine konzeptionelle Grenze gesetzt, allerdings eine praktische. Denn im selben Maße wie Quantenalgorithmen subexponenziell zur Problemgröße skalieren, müssen natürlich klassische Rechner beim Versuch Quantensysteme zu simulieren umgekehrt skalieren. Das heißt für jedes zusätzliche Qubit müsste man die doppelte klassische Rechenleistung aufbringen. Jedem wird sofort klar, dass man da schnell an physische Grenzen für Großrechner stößt.
Um das ganze Spiel vollends abzubilden, braucht es vermutlich um die 140 bis 150 Qubits. Das wird aus o.g. Gründen niemals mit einem Simulator machbar sein. Dafür müssen wir warten bis die echte Quantenhardware so weit ist und das wird noch einige Jahre (mind 5 - 10) dauern.

Auf der anderen Seite steht die klassische Rechen-Architektur. Was ist damit eigentlich nicht in Ordnung? An sich nichts. Die kann konzeptionell genau das Gleiche ausrechnen. Wenn man den Faktor Zeit außer Acht lässt, gibt es keinen Unterschied zwischen klassischem und Quantencomputer. Das sieht man allein daran, dass man Quantencomputer simulieren kann und nur dadurch begrenzt wird, dass einem irgendwann der Rechner nicht mehr in den Raum passt, oder man keine Lust hat zwei Jahrzehnte auf das Ergebnis zu warten. Legt man für die Berechnung aller Pfade einer Verteilung 1 Sekunde als klassische Berechnungszeit zu Grunde – was sicherlich zumindest von der Größenordnung her eine plausible Annahme ist, so beläuft sich die Rechenzeit des klassischen Rechners, welcher alle Verteilungen durchrechnet auf ungefähr 87 Mio Jahre. Für eine ganze Liste mit 48 Spielen bräuchte man dann schon knapp 4,2 Mrd Jahre und man könnte nach Abschluss der Liste evtl noch beobachten wie der Sonne langsam der Treibstoff für unser Sonnensystem ausgeht und sie beim Anschwellen bestaunen. Kennt man seine eigenen Karten, reduziert sich diese Zeit für alle verbleibenden Restverteilungen – immerhin – auf ca 1,35 Jahre pro Verteilung. Dennoch zu lang für die meisten Skatturniere.

Meine Co-Autoren und ich haben einen Preprint veröffentlicht, das sich dem Problem auf einem QC annimmt. Dabei ist Vorgehensweise prinzipiell wie folgt zu verstehen:
1. Mache dir partielles Wissen zu Nutze um den Suchraum möglichst klein zu halten
2. Encodiere die Spielinformation in einem Quantenregister
3. Baue entsprechende unitäre Quanten-Gatter, um den Spielablauf und die einzelnen Operationen abzubilden
4. Messe den Endzustand
5. Projiziere auf den Teilraum, welcher die Gewinnäste enthält und ermittle das Gewicht dessen
6. Das Zählen der Äste über einen Quantenalgorithmus (Quantum Counting: Grover-Algorithmus + Quantum Phase Estimation) führt zu einem quadratischen Speedup.
7. Die Gewinnwahrscheinlichkeit bestimmt die Payoff-Funktion

Um nun einen Vorschlag zu bekommen, im Sinne einer Handlungsanweisung müsste man diesen Approach jeweils zehn mal durchführen (für jede Karte einmal) und den darunterliegenden Teilbaum analysieren. Dann bekommt man den Ertrag, welcher bei unbekannter Verteilung und Ausspiel ebenjener Karte zu erwarten ist.

Ich hoffe, ich habe einige interessierte Leser erreicht und wünsche euch allseits viel Spaß dabei.

[Skatfuchs]

Hallo,

wie bereits gesagt, so basiert der "Fox" auf einer vollständigen Information, die man aber als Spieler nicht hat. Dafür zeigt er genau an, was die optimale Skatlegung gewesen wäre, ob das Spiel bei allseits bestem Spiel überhaupt schlagbar ist und welche Karte mit wie vielen Augen zum Erfolg führt; bzw. bei Nullspielen im welchen Stich diese geschlagen wird. Ob man den Weg erkennen konnte, steht auf einem anderen Blatt Papier.

Das Skatspiel mit unvollständiger Info zu lösen, gab es schon viele Versuche, doch alle sind kläglich gescheitert. Einer der letzten war an der UNI Edmonton, wo man mit Hilfe Neuronaler Netze versuchte, das Problem zu lösen. Doch es dauerte dann ca. 5min, ehe der Computer die erste Karte spielte- da haben die meisten den wohl schon ausgemacht.

Der konzeptionelle Weg von Ohne11 ist meiner Meinung nach zwar richtig, wird sich aber auch in den nächsten 20 Jahren technisch nicht umsetzen lassen; zumal man da auch die Reizung, die Spielwahl und die Skatlegung mit betrachten muss.

Wir verfolgen da eine anderen gangbaren Weg in der Zwischenzeit: den der Abstraktion und der Wissensverwaltung. So werden die ersten 4 bis 5 Stiche danach gespielt und die Karten soweit wie möglich aufgeklärt. Danach gibt es oft "nur noch" ca. "2.000 Restverteilungen" und wir suchen die Karte, ähnlich wie Ohne 11, die bei den meisten zum Erfolg führt; und wenn es nur noch eine gibt, dann spielen wir die als "Hoffnungskarte".
Sollte jemand da Interesse haben, sich daran auch aktiv zu beteiligen, so kann er sich gern bei mir per mail melden.

[Primrose]

Wie kann ich beim Fox die ideale Drückung anzeigen lassen?

[Skatfuchs]

Wie kann ich beim Fox die ideale Drückung anzeigen lassen?

Hallo,
1. ein Spiel zur Analyse auswählen
2. Mittlerer Schalter unten rechts "Im Kartenleger öffnen" betätigen.
3. "Beste Drückung" auswählen
4. Max. 6 mögliche Karten für die Skatlegung auswählen und berechnen drücken.
5. es werden aus Zeitgründen max. 15 Kombinationen der Skatlegung berechnet und die mögliche Augenzahl bei allseits bestem Spiel angegeben.

[Primrose]

Vermutlich meinst du dann nicht diesen Link: skatfox/index.php

[Skatfuchs]

Hallo,

nein dort ist das Analysetool nicht mit implementiert.
Du musst erst einmal hier Spiele gespielt haben, die du dann nachträglich analysieren kannst, in dem du diese aufrufst: https://skat-ki.de:8080/