Skat ist ein im Jahr 1820 in Altenburg entwickeltes Kartenspiel. Gespielt wird mit genau drei Spielern und einem Blatt bestehend aus 32 Karten. Dabei teilt sich das Spiel in zwei Teile: der Vorbereitungsphase (Reizen und Drücken) und dem eigentlichen Ausspielen. Ziel des Spiels ist es, die Karten so auszuspielen, dass das eigene Team (Einzelspieler oder Gegenspieler) die vorgegebene Anzahl an Punkten erreicht. Skat zählt zu den imperfekten Spielen, da die Karten eines Spieler nicht ersichtlich für andere Mitspieler sein dürfen.

Der Name leitet sich vom italienischen scartare ab, zu deutsch verwerfen oder abwerfen - passend zu den beiden Karten, die abgeworfen werden (dem Skat).^[1] Trotz seines stolzen Alters ist das Spiel heute noch so beliebt, dass Meisterschaften - regional und international - in regelmäßigen Abständen ausgetragen werden.^[2] 2016 wurde Skatspielen als ein deutsches immaterielles Kulturerbe von der UNESCO ausgezeichnet.^[3]

Regeln und Spielablauf

Regeln, die in diesem Artikel genannt werden, sind konform mit der Internationalen Skatordnung.^[4]

Eine Runde beginnt mit dem Austeilen der Karten. Dabei gibt es ein festes Vorgehen:
Zuerst teilt der Geber seinem linken Mitspieler die vorgegebene Kartenmenge zu, danach seinem rechten Spieler und zuletzt sich selbst. In der ersten Runde werden jeweils drei Karten gegeben. Danach wird der Skat von zwei Karten in die Mitte des Tisches gelegt. Die zweite Runde enthält vier, und die letzte nochmal drei Karten für jeden Mitspieler. Das Vorgehen wurde im rechts stehenden GIF visualisiert.

Auf Basis der Karten wird ermittelt, wie sich die drei Spieler auf beide Teams, Einzel- vs. Gegenspieler, aufteilen (Reizen). Für den Einzelspieler folgt die Entscheidung über die Aufnahme des Skates und welche Karten abgeworfen werden (Drücken). Das Ausspielen beginnt nach der Ansage des Spielmodus und endet mit dem Feststellen der Gewinnerpartei.

Ziel des Spiels ist es das vordefinierte Ziel seines Teams zu erreichen. Der Einzelspieler muss im einfachen Spiel mindestens 61 von 120 Punkten erreichen. Für das Team der Gegenspieler reicht ein Unentschieden mit 60 Punkten. Ausgehend vom Spielmodus kann diese Punktgrenze auch höher oder gar nicht relevant sein.

Spielmodi

In jeder Runde gibt der Alleinspieler einen Spielmodus an. Dieser ist bereits beim Ermitteln des Reizwertes entscheidend. Der Spieler hat die Wahl aus folgenden Trümpfen zu wählen:

• eine Farbe aus Kreuz, Pik, Herz oder Karo
• Grand
• Null

Beim Farbspiel wird genau eine Farbe gewählt, welche den Anderen beim Ausspielen überlegend sein soll. Die Menge der Trumpfkarten setzt sich aus den Karten der jeweiligen Farbe plus den vier Buben zusammen.

Der Grand ist äquivalent zum Farbspiel ohne Farbe. Es sind nur die Buben Trumpf.

Null gilt als umgedrehtes Spiel, da es sich sehr vom regulären Spielverlauf abhebt. Der Einzelspieler darf keinen einzigen Stich bekommen, ansonsten ist die Runde verloren. In diesem Modus gibt es keinen Trumpf und es gelten Sonderregeln beim Reizen und Ausspielen.

Wurde ein Trumpf gewählt, hat der Spieler die Wahl Hand oder mit Skat zu spielen. Als den Skat bezeichnet man die beiden in der Mitte platzierten Karten, die der Einzelspieler nach dem Reizen zusätzlich zu seinen Handkarten erhält. Dadurch hat dieser die Chance seine bestehende Hand aufzuwerten und zwei ungünstige Handkarten abzuwerfen. Bei einem Handspiel wird auf diese Phase verzichtet und der Skat ungesehen beiseite gelegt.

Zusätzlich gibt es noch erweiterte Spielmodi, die Veränderungen der Basis-Regeln erfordern:

• Schneider: Statt 61 Punkte muss der Herausforderer 90 Punkte holen
• Schwarz: Jeder Stich muss an den Einzelspieler gehen
• Offen/Ouvert: Die Karten des Alleinspielers werden für jeden sichtbar ausgelegt. Es müssen alle Stiche geholt werden und kann nur in Verbindung mit Hand gespielt werden. Eine Ausnahme bildet das Nullspiel, wobei Offen auch ohne Hand gespielt werden kann.

Reizen

Beim Reizen erfolgt die Aufteilung der Spieler auf die beiden Parteien, indem auktionsähnliche Punktgebote abgegeben werden. Begonnen wird mit dem niedrigsten möglichen Wert 18 und geht in vordefinierten, den möglichen Reizwerten entsprechenden Schritten höher über 20, 22, 23, 24 usw.

Die Reizwerte

Der Wert eines Blattes besteht aus zwei Bestandteilen und wird wie folgt berechnet:

• maximalerReizwert = Faktor_{Trumpf} * Faktor_{Spitze} .

Zum einen ist der Trumpf entscheidend. Den wählbaren Trumpffarben und Grand wurden feste Werte zugeordnet:

• Karo = 9
• Herz = 10
• Pik = 11
• Kreuz = 12
• Grand = 24

Da der Spielverlauf eines Nullspiels anders ist (unter anderem da kein Trumpf existiert), wurden diesen Spielen fixe Werte zugeordnet. Die Werte können aus der unten stehenden Reiztabelle (siehe Abb. 2) entnommen werden.

Zum zweiten Teil der Formel werden die sogenannten Spitzen mit einbezogen. Der Spitzenfaktor x bezieht sich auf die Karte, welche die Reihe der größten (nicht-)vorhandenen Trümpfe unterbricht, wobei diese Karte der x-größte Trumpf ist. Dabei wird auf die Handkarten und den Skat geschaut - auch bei einem Handspiel. Die Regel für den Faktor der Spitze lautet demnach:

• "Wie viele der größten Trümpfe sind lückenlos im Blatt und Skat vorhanden bzw. nicht vorhanden?" + 1

Beispiel: Spitzen
Spieler A hat folgende Karten:
Bube , Bube , acht weitere Karten (kein Bube)

A kann nur bis Faktor 2 reizen, denn A hat den größten Trumpf (Bube), aber nicht den Zweitgrößten. (Mit 1, Spiel 2)

Hätte A den Buben nicht, würde sich der Wert auf 4 erhöhen, denn A hätte die drei größten Trümpfe nicht, jedoch den Viertgrößten. (Ohne 3, Spiel 4)

Zusätzlich kann der Wert der Spitzen erhöht werden, indem die zusätzlichen Spielmodi Hand, Schneider, Schwarz und Offen dazu gerechnet werden. Die möglichen Werte eines Blattes, zu denen maximal gereizt werden kann, ergeben sich aus der folgenden Tabelle:

Ein Überreizen des Reizwertes hat zur Folge, dass der Spieler so spielen muss, dass es mindestens dem gereizten Wert entspricht. Ein ungewolltes Überreizen kann unter anderem durch die Aufnahme des Skats und der dadurch auftretenden Veränderung der Spitzenkonstellation entstehen. Gelöst werden könnte dies beispielsweise indem der Spieler seine Gegenspieler "in den Schneider spielt", obwohl dies nicht vom Spieler eingeplant war.

Beispiel: Lesen der Reiztabelle
Spieler A will Karo spielen und hat nur die drei größten Buben.
A sagt an, dass er auch ohne Skataufnahme die Gegner in den Schneider spielt.

Faktor_{Karo}= 9
Faktor_{Spitzen}= 4 (Buben) +1 (Hand) +1 (Schneider) +1 (Schneider angesagt) = 7
maximalerReizwert = 9 * 7 = 63

Sollte A sich überreizt haben, hat er die Chance das Spiel zu gewinnen, indem er Schwarz oder sogar offen spielt. Andernfalls könnte A statt Karo eine höherwertigere Farbe spielen.

Der Reizprozess

Der Prozess verläuft wie folgt:

• Der Spieler rechts vom Geber (Sager) fängt an, indem dieser das Startgebot abgibt.
• Der Spieler links vom Geber (Hörer) stimmt dem Sager zu, wenn die Karten des Hörers das Gebot erreichen und dieser spielen will.
• Der Sager sagt den nächst höheren Wert an, welcher der Hörer abnickt oder verweigert.
• Will ein Spieler nicht (weiter-)reizen, gibt er dies den anderen zu erkennen. Im Falle des Sagers gibt dieser kein neues Gebot ab, im Falle des Hörers wird das Gebot des Sagers nicht angenommen.
• Sollte einer der beiden (Hörer oder Sager) nicht (weiter) reizen wollen, übernimmt der Geber und sagt den nächsten Wert an (oder passt).
• Das Reizen endet, sobald zwei von drei Spielern ein Gebot verweigert haben.
• Sollte kein Spieler reizen wollen, endet die Runde vorläufig ohne Ergebnis.

Der Spieler mit dem höchsten Gebot bzw. wer als Letztes übrig bleibt, wird zum Einzelspieler gekürt. Die anderen beiden bilden das Gegnerteam. Der zuletzt angesagte Reizwert gilt ab sofort als Richtlinie für den Herausforderer.

Drücken

Nach dem Reizen hat der Alleinspieler die Wahl den Skat aufzunehmen oder nicht. Der Skat besteht aus den zwei zusätzlichen Karten, die beim Geben verdeckt in die Mitte geworfen wurden und bisher noch niemanden angehörten. Diese beiden Karten geben dem Spieler die Chance sein Blatt, mit welchem er in das Ausspielen geht, zu verbessern und seine Trumpfwahl zu überdenken.

Wurde der Skat aufgenommen, müssen anschließend zwei Karten gedrückt, also aus dem Spiel genommen, werden, damit der Spieler wieder zehn Handkarten hat. Der Spieler darf frei aus seinem Blatt wählen. Die gedrückten Karten kommen auf den Stapel des Einzelspielers und zählen hinterher in die Wertung der Punkte mit ein. Beim Nullspiel zählen die Punkte nicht mit ein, da keine Punkte gezählt werden. Die Karten sind damit aus dem Spiel. Sobald die zwei Karten auf dem Stapel landen, wird den Gegnern der Spielmodus angesagt und das Ausspielen beginnt.

Da bei einem Handspiel der Skat ungesehen auf dem Stapel landet, braucht es hier keine Entscheidung zum Drücken, da mit den aufgenommenen zehn Handkarten vom Anfang gespielt wird. Der Skat zählt trotz des Nicht-Ansehens ebenfalls in die Punktewertung des Einzelspielers mit rein.

Ausspielen

In der Phase des Ausspielens werden die Handkarten ausgespielt und Punkte gemacht. Hier entscheidet sich, welches der beiden Teams das Spiel gewinnt. Punkte können gemacht werden, indem Stiche gewonnen werden. Innerhalb eines Stiches spielt jeder Mitspieler eine Karte aus, wobei der Spieler mit der besten Karte die drei ausgespielten Karten erhält und auf einen Stapel vor sich platziert. Diese Karten sind aus dem Spiel und werden nur noch für das Zählen am Ende relevant sein.

Der Ausspiel-Prozess

Insgesamt gibt es zehn Stiche. Es beginnt der Spieler links vom Geber mit dem Legen der ersten Karte. Gespielt wird abwechselnd und im Uhrzeigersinn. Das Spielen eines Stiches läuft immer gleich ab:

1. Spieler A spielt eine Handkarte aus.
2. Spieler B (links von A) legt eine Karte aus. Dabei muss die Farbe, die A gespielt hat, bedient werden. Kann B dies nicht, darf eine beliebige Karte ausgespielt werden.
3. Spieler C darf als Letztes seine Karte legen. Unabhängig davon was B gespielt hat, muss die Farbe von A bedient werden. Geht dies nicht, darf C frei aus seinen Karten wählen.
4. Der Spieler, welcher die Karte der höchsten Rangordnung innerhalb des Stiches gespielt hat, bekommt den Stich. Dieser Spieler eröffnet den nächsten Stich.

Rangordnung der Karten

Für die Entscheidung, wer den Stich erhält, ist es wichtig die Rangordnung der jeweiligen Karten zu kennen. Von Stich zu Stich sind die Ränge der Farben unterschiedlich, denn die genaue Reihenfolge innerhalb eines Stichs ergibt sich durch die erste geworfene Karte.

Reihenfolge nach Farbe: Buben > Trumpffarbe > Farbe der ersten Karte > andere Nicht-Trumpffarben
Rangordnung der Buben: Kreuz > Pik > Herz > Karo
Reihenfolge innerhalb einer Farbe: Ass > Zehn > König > Dame > Neun > Acht > Sieben
(Von links nach rechts gelesen: von der stärksten zur schwächsten Kategorie)

Auch wenn die Buben als gesonderte Kategorie stehen, gelten Sie als Erweiterung der Trumpffarbe. Existiert eine Trumpffarbe, darf auch durch einen Buben bedient werden. Umgekehrt reicht auch eine Karte der Trumpffarbe aus, um einen geworfenen Buben zu bedienen.

Man beachte folgende Spielmodus-abhängige Besonderheiten:

• beim Grand sind nur Buben Trumpf, also entfällt die Stufe "Trumpffarbe"
• bei Null gibt es keinen Trumpf und die Buben gehören den Farben an
• bei Null "reihen sich Zehnen und Buben ein", bedeutet die Reihenfolge innerhalb einer Farbe sieht wie folgt aus:
  Ass > König > Dame > Bube > Zehn > Neun > Acht > Sieben

Beispiel 1: Ausspielen von Nicht-Trümpfen
Trumpf:
A spielt 7
B spielt Ass
C spielt 8
C erhält den Stich, denn > und 8 > 7

Beispiel 2: Die Rolle der Buben
Trumpf:
A spielt Bube
B spielt Ass
C spielt 9
A erhält den Stich, denn Buben > >
Selbst wenn B noch einen Buben gehabt hätte, wäre die Kartenwahl regelkonform gewesen.

Beispiel 3: Der Sonderfall Null
Trumpf: Null
A spielt König
B spielt 10
C spielt Bube
A erhält den Stich, denn König > Bube > 10

Das Ende der Runde

Das Spiel endet spätestens nach dem zehnten und letztmöglichen Stich. Es gibt jedoch Situationen, in denen es sich nicht lohnt weiterzuspielen und dementsprechend abgebrochen werden kann:

• bei allen Nullspielen: sobald der Einzelspieler einen Stich macht
• bei allen schwarz-angesagten Spielen: sobald die Gegenspieler einen Stich machen
• jemand schummelt (z.B. spielt ein Spieler eine Farbe, die er im Stich vorher nicht bedienen konnte). Der schummelnde Spieler bzw. seine Partei hat automatisch verloren.

Sobald die Runde endet, werden die gewonnenen Karten addiert. Die Karten haben unabhängig von ihrer Farbe und Rangordnung folgende Werte:

• Ass: 11 Punkte
• Zehn: 10 Punkte
• König: 4 Punkte
• Dame: 3 Punkte
• Bube: 2 Punkte
• Neun, Acht, Sieben: 0 Punkte

Das Team, welches mindestens sein Punkteziel erreicht hat, gewinnt. Die Punkte der beiden Gegenspieler werden zusammengerechnet. Im Normalfall gewinnt ein Einzelspieler bei 61 Punkten und die Gegner bei 60 Punkten. Muss der Einzelspieler Schneider spielen, braucht er 90 Punkte und die Gegner 31. Bei Null und schwarzen Spielen muss nicht einmal gerechnet werden: Hat der Einzelspieler keinen bzw. alle Stiche, hat dieser gewonnen - andernfalls nicht.

Algorithmische Umsetzung

Die hier beschriebenen, modifizierten Algorithmen beziehen sich auf die langjährige Forschung und Ausarbeitung von Sebastian Kupferschmid. Zwar gibt es bereits neuere Ansätze zur Strategiefindung für Skat, dennoch bildet Kupferschmids Double Dummy Skat Solver^[5] eine Grundlage oder zumindest ein Anreiz für neue Forschungen.

Eine Skat-Runde teilt sich in die beiden Phasen "Vorbereitung" und "Ausspielen". Da diese unterschiedliche Probleme darstellen, werden sie bei der algorithmischen Umsetzung getrennt voneinander betrachtet und auf unterschiedliche Weise implementiert.

Es ist außerdem zu beachten, dass eine gefundene Lösung nicht in jedem Fall die optimale Lösung sein muss. Skat als ein imperfektes Spiel baut darauf auf, dass es verdeckte Informationen gibt. Für die Lösungsfindung eines bestimmten Problems (hier: optimale Strategie für einen gegebenen Spielstand) sind diese Informationen notwendig. Deswegen kann nur mit Approximationen gearbeitet werden, da ein präzises Vorgehen nicht immer möglich ist.^[5:1]

Vorbereitungsphase

Die Vorbereitung enthält alle Entscheidungen, welche zur Klärung der Spielbedingungen für das Ausspielen relevant sind. Bestandteile bilden das Reizen und das Drücken. Dazu zählen konkret:

• Ermittlung des Reizwertes (entschieden beim Reizen)
• Entscheidung über Aufnahme des Skats (entschieden nach dem gewonnenen Reizen)
• Weglegen zweier Handkarten (Drücken)
• Wahl des Trumpfes und des allgemeinen Spielmodus (entschieden nach dem Reizen/Drücken)

Zur algorithmischen Umsetzung beider Bestandteile wurde der k-nearest-neighbors-Algorithmus verwendet. Darin wird ein Set aus Handkarten in eine Datenbasis, bestehend aus simulierten Spielen, eingefügt. Durch die k ähnlichsten Spiele wird für die aktuelle Kartenmenge abgeleitet, ob diese den Einzelspieler zum Sieg verhelfen könnte oder nicht. Der Aufbau und die Bestandteile für die Ausführung des Algorithmus sind für das Drücken und das Reizen gleich. Jedoch gibt es kleinere Abweichungen, um die genauen Problemstellungen der beiden Phasen zu lösen.

k-nearest-neighbors für Skat

Die Idee des KNN-basierten Skats folgt der Arbeit von Kupferschmid und Keller ^[6]. Die folgenden Bestandteile des KNN müssen für diese Anwendung angepasst werden:

• Datenbasis DB (Knowledge Base)
  Für die Entscheidung auf welchen Trumpf gereizt oder gar gespielt werden soll, werden fünf Datenbasen (auch genannt knowledge base) benötigt - eine für jeden Trumpf (, , , , Grand). Zur Generierung der Knowledge Base wird eine Vielzahl (\approx 10.000) an Kartenverteilungen erstellt und mittels des DDSS (siehe Abschnitt Ausspielen) simuliert. Bei der Erstellung der Spielmenge muss beachtet werden, dass jede Karte eine gewisse Häufigkeit (\approx 10 Mal) mindestens in den Handkarten des Einzelspielers auftritt, um eine vielseitige Betrachtung an Spielmöglichkeiten zu garantieren. Jede Kartenverteilung wird mit jedem Trumpf gespielt und in die jeweilige Datenbasis eingefügt. Das erzielte Punktergebnis bildet die Klassifizierung eines Spiels.

• Kartenset x
  Die Darstellung von zehn Handkarten geschieht als ein Vektor mit acht Einträgen, welcher die Spielhand in Verbindung mit dem Trumpf beschreibt. So können die jeweiligen Handkarten-Mengen miteinander verglichen werden. Eine genaue Darstellung von x kann in der untenstehenden Tabelle abgelesen werden.
  Zu den letzten beiden Einträgen im Vektor: Um die einzelnen Trumpfkarten zu beurteilen, wurden ihnen verschiedene Werte zugeordnet. Die Begründung dessen liegt im Spiel selbst bzw. in der Rangordnung der Karten. Nur das Trumpf-Ass zu besitzen ist eine bessere Ausgangslage als nur die Trumpf-Sieben zu haben. Der Bube als mächstigste Karte garantiert einen Stich, anders als der Bube.

• Anzahl der Nachbarn k
  In der Vergangenheit hat sich k=15 als optimal gezeigt. Bei dieser Anzahl an untersuchten Objekten scheint die Quote an nicht-korrekt klassifizierten Objekten am geringsten.

• Distanzfunktion dist(x, z)
  Hier wird der Euklidische Abstand dist(x,z) = \sqrt{\Sigma_{i=1}^{n}(x_i-z_i)^2} zur Ermittlung der k ähnlichsten Spiele verwendet. ^[7]

• Evaluierungsfunktion eval(x, z_1, ... , z_k)
  Da die Spiele aus der Knowledge Base mit ihrem erreichten Punktergebnis klassifiziert wurden, erhält die neue Hand den Durchschnitt der Punkte aller Nachbarn als Klasse. Dies macht den Vergleich zwischen den Trümpfen bzw. den Klassifizierungen möglich.

Reizen mit KNN

Ziel des Algorithmus für das Reizen ist es herauszufinden, ob und welcher Trumpf für die aktuellen Karten geeignet wäre, um das Spiel als Einzelspieler zu gewinnen. Die Hand fügt sich in die fünf Datenbasen ein und erhält für jeden Trumpf einen Wert zwischen 0 und 120. Ein Trumpf t gilt als "gewinnbar", wenn die eingefügte Hand x einen Wert V^t(x) über der Schwelle s besitzt. ^[6:1]

Gewählt wird der Trumpf, der den höchsten Wert zugeschrieben bekommen hat. Sollten zwei gewinnbare Trümpfe den selben Wert haben, wird derjenige gewählt, welcher das höhere Gebot erlaubt. Aus dem resultierenden Trumpf und den zehn Karten kann dann der maximale Reizwert gebildet werden. Liegt kein Trumpf über dem Schwellenwert, wird nicht gereizt.

Um eine Differenzierung zu machen, ob der Spieler Hand oder mit Skat spielen kann, werden diese beiden Varianten unterschieden:

• Reizen auf Hand
  Hier genügt es die Knowledge Base in der Ursprungsversion zu lassen und ein Schwellenwert th = 60.
• Reizen mit Aufnahme des Skats
  Die Vorgehensweise für Handspiele könnte auch hier eingesetzt werden, jedoch bliebe der Skat bei der Klassifizierung weiterhin unberücksichtigt. Daher deklariert der Algorithmus viele gewinnbare Spiele nicht als gewinnbar. Da der Skat die Spielposition verbessern kann, wird hierzu eine Änderung in der Knowledge Base vorgenommen: Anstatt die generierten Spiele ohne Beachtung des Skats durchzuspielen, wird nun der Skat aufgenommen, gedrückt (siehe nächsten Abschnitt Drücken mit KNN) und das Spiel mit dem ggf. geänderten Kartenset simuliert. Dadurch ergeben sich für die Spiele in der Datenbasis neue, oftmals höhere Ergebnisse, die den Skat mit berücksichtigen.
  Der optimale Schwellenwert th liegt dabei zwischen 61 und 64 Punkten.

Drücken mit KNN

Die Entscheidung, welche beiden Karten abgeworfen werden sollen, kann ähnlich wie das Reizen gelöst werden. Dazu werden alle Möglichkeiten an zehn Handkarten gebildet und jeweils in den fünf Datenbasen mit dem Durchschnittswert der Nachbarn klassifiziert. Die Handkarten-Trumpf-Kombination, welche den höchsten Klassifizierungswert hält, wird gewählt. Dementsprechend werden die restlichen beiden Karten verworfen und der Trumpf angesagt.

Da es 66 Möglichkeiten gibt zwei aus zwölf verfügbaren Handkarten zu drücken und jede Möglichkeit in alle fünf Datenbasen eingefügt werden muss, ergibt sich daraus eine maximale Anzahl aus 330 Klassifizierungen. Bei Einbeziehung des Reizwertes, den die Handkarten mindestens erreichen müssen, fallen einige Kombinationen aus, z.B. könnte die Farbe Karo dank ihrer niedrigeren Wertigkeit übersprungen werden. Eine weitere Möglichkeit, um Klassifikationen einzusparen, ist das Überspringen einzelner Kombinationen für die weggelegten Karten. Beispielsweise ist das Drücken von Buben und Trumpfkarten nie sinnvoll. Demnach werden sich nur Skat-Kombinationen angeschaut, welche keine Trumpfkarten und keinen Buben beinhalten.

Auch hier ist eine Veränderung der Knowledge Base erforderlich, weil der Skat nicht berücksichtigt wurde. Zum einen addiert man zu den resultierenden Wert jeder Handkarten-Trumpf-Kombination die Punkten der gedrückten Karten. Die Karten, die verworfen wurden, zählen nach dem Ausspielen zu den Punktewerten dazu, weshalb sie zum spieltheoretischen Wert dazugerechnet werden müssen. Dafür werden zum anderen die Instanzen in der Datenbasis um die selbe Punktzahl subtrahiert.^[6:2]

Schwachstellen und mögliche Verbesserungen

Zwar erstellt der Algorithmus zufriedenstellende Resultate, allerdings existieren einige Lücken zum manuellen Skat. Im Folgenden wurden Differenzen zwischen dem Ausgangsspiel und dem beschriebenen algorithmischen Ansatz aufgezählt und Umsetzungsvorschläge für jene gemacht.

• Nullspiele ausgegrenzt
  Die Möglichkeit Null zu spielen wird hier nicht beachtet, da das Null-Spiel anderen Regeln folgt. Dazu müssen entweder andere Algorithmen verwendet werden oder die KNN-basierte Umsetzung auf Null angepasst werden (z.B. sollten n der 15 Nachbarn keine Stiche erhalten haben, wird auf Null gereizt).
• Keine Modifikationsangaben für Schneider, Schwarz und Offen
  Auch wenn eine Anpassung für Schneider und Schwarz nahliegend ist, so wurde dies in der Forschung nicht erwähnt. Eine Möglichkeit Schneider umzusetzen wäre es, den Schwellenwert th auf 90 anzuheben. Schwarz wäre analog zum Vorschlag beim Nullspiel. Gleiches gelte für offene Spiele. Hier wäre es ratsam, dass alle Nachbarn alle Stiche erhalten. Da das Erreichen jedes Stiches im Skat sehr selten vorkommt, muss unter Umständen über eine erweiterte Anzahl an generierten Spielen nachgedacht werden, um auch solche Fälle abbilden zu können.

Weitere Ansätze

Auch wenn der KNN in der Literatur großen Anklang gefunden hat, so gibt es weitere Ansätze das Problem des Reizens und Drückens umzusetzen:

• Least Mean Squares
  Sebastian Kupferschmid versuchte sich bereits bei der "Entwicklung eines Double Dummy Skat Solvers" an einer weiteren Umsetzung, nämlich mit dem LMS-Algorithmus. Dabei wird eine Hand-Trumpf-basierte Funktion durch eine Funktion basierend auf Trainingsdaten geschätzt und den Trumpf gewählt, welche die geringste Abweichung besitzt. Dieser Ansatz scheitert, da dies voraussetzen würde, dass man die Samples durch eine Lineare Funktion beschreiben könnte. Dies ist im Falle vom Skat jedoch sehr unwahrscheinlich und rechtfertigt das schwache Klassifizierungsverhalten des Algorithmus für Skat.^[5:2]

• Upper Confidence Bound Applied to Trees (UCT)
  Jan Schäfer implementierte Skat als einen UCT-Algorithmus in seiner Diplomarbeit "The UCT Algorithm Applied to Games with Imperfect Information". In der Reizen-Phase werden ähnlich zum Aufbau des Monte Carlo Tree Search zufällige Spiele mit einem durch UCT selektierten Trumpf durchgespielt und das Ergebnis für den jeweiligen Trumpf notiert. Mithilfe der UCT-Formel wird anschließend der Trumpf gewählt, welcher am besten abgeschnitten hat.^[8]

• Nullspiele als eigene Betrachtung
  Stefan Edelkamp beschäftigte sich in seinem Paper "Challenging Human Supremacy in Skat" ausschließlich mit der Umsetzung des Nullspiels auf Grundlage seines "Guided and Complete And-Or Belief-Space Search". ^[9]

Ausspielen

Mit dem gewählten Trumpf und den zehn Handkarten startet die Phase des Ausspielens. In jedem Stich soll entschieden werden, welche Handkarte zum Legen geeignet wäre, um das Spiel zu gewinnen, ohne dabei die Kartenverteilung auf die Gegenspieler zu kennen. Das im Weiteren beschriebene Konstrukt zur Umsetzung dieses Problems entstammt der Diplomarbeit von Sebastian Kupferschmid und wird in Fachkreisen Double Dummy Skat Solver, kurz DDSS, genannt.^[5:3][10].

Ein Bestandteil des DDSS bildet die Alpha-Beta-Suche, welche bereits im Umfeld von Spielen mit perfekter Information erfolgreich angewandt wurde, um den perfekten Zug für eine spezifische Situation zu finden. Da es sich beim Skat jedoch um imperfekte Information handelt, kann der beste Zug nicht anhand der tatsächlichen Spielposition errechnet werden. Um die Lösung eines solchen Problems zu approximieren, kommt eine Monte-Carlo-Simulation zum Einsatz.

Hierbei werden alle möglichen Kombinationen an bisher ungesehenen Karten generiert und auf die beiden Gegenspieler projiziert. Die Menge ist dabei konsistent zu dem bereits erlangten Wissen (z.B. konnte ein Spieler in einem vergangenen Stich nicht bedienen, so sind alle unbekannten Karten dieser Farbe dem zweiten Gegenspieler zuzuordnen). Die generierten Spiele können nun nacheinander als Spielposition für die Alpha-Beta-Suche verwendet werden, um für alle möglichen Szenarien den besten Zug zu ermitteln. Als spieltheoretischer Wert innerhalb des Suchbaums wird das resultierende Punktergebnis nach zehn Stichen verwendet. Nach dem Durchlaufen eines Baumes wird die beste Karte gemeinsam mit dem Punktewert notiert. Sind alle Verteilungen berechnet worden, wird die Handkarte ausgewählt, die in den meisten Szenarien als beste Karte ausgezeichnet wurde. Bei Gleichstand mehrerer Karten wird von diesen diejenige gewählt, die in ihren Spielen insgesamt am meisten Punkte geholt hat. Sollten hier wieder mehrere Karten infrage kommen, wird zufällig gewählt. Der Ablauf wurde in Abbildung 7 verbildlicht.

Um Skat als Minimax-Baum darstellen zu können, müssen zwei Anpassungen gemacht werden. Zum einen existieren drei Spieler in einer Runde. Die Gegenspieler sind als zwei MIN-Knoten pro Stich vertreten, da sie dennoch eine Partei bilden und gemeinsam spielen. Zum anderen kann die Reihenfolge der MAX- und MIN-Knoten je nach Subbaum variieren, da es keine feste Abfolge beim Skat gibt, denn derjenige, der den letzten Stich erhalten hat, beginnt im nächsten. Somit gibt es "zwischen den Stichen" keine feste Reihenfolge.

Aus dem Aufbau des DDSS ergibt sich jedoch eine Schwachstelle: Ziel der Alpha-Beta-Suche ist es ausschließlich den Punktewert zu maximieren. Dazu hat der Algorithmus die vollständige Information über den Spielstand. Beim Skat ergibt sich häufig die Situation, dass Stiche absichtlich verloren werden, um dadurch neue Informationen sammeln zu können (z.B. über die Verteilung der Trümpfe). Damit kann unter Umständen das Spiel sogar noch höher gewonnen werden als vermutet. Solche Züge würden sich hierbei nicht ergeben können.

Optimierungen der Alpha-Beta-Suche

Alle bzw. ein Großteil der möglichen Kartenverteilungen müssen betrachtet werden, um ein optimales Ergebnis zu erreichen. Braucht der Spieler eine Handkarte für den ersten Zug im ersten Stich, dann ergeben sich aus noch 20 unbekannten Handkarten 184.756 mögliche Verteilungen - beim Handspiel wäre es sogar 646.646 Verteilungen. Um diese Anzahl an Spielen in einer geeigneten Zeit durchzugehen, muss der Alpha-Beta-Algorithmus optimiert werden.

Transpositionstabellen
Durch den Einsatz von Tabellen, die bereits besuchte Spielpositionen speichern, muss eine Vielzahl an Subbäumen nicht noch einmal separat berechnet werden. Es genügt nun bei einem gleichen Spielstand den Wert aus der Transpositionstabelle zu übernehmen. Praktisch ist, dass im Skat nur Punkte gemacht werden, wenn ein Stich ausgespielt wurde, also nach genau drei Zügen. Demnach werden nur die Spielstände aufgenommen, an denen "keine Karte auf dem Tisch liegt" - also direkt vor oder nach einem Stich. Dargestellt wird ein Spielstand durch 32 Bit. 30 Bits für die Karten (ausgenommen dem Skat) und zwei Bits für den Spieler, der gerade an der Reihe ist. Anhand dieser Darstellung kann nicht gesagt werden, welcher Spieler welche Karten auf der Hand hat, weshalb sich ein Eintrag in der Tabelle nur für den selben Baum anwenden lässt. Zusätzlich wird der Punktewert aus der betrachteten Spielposition gespeichert.

Um die Subbäume wiederverwenden zu können, muss der Minimax-Baum in eine andere Form gebracht werden. Beim reinen Minimax haben die Blätter die Punkte, welche von den vorhergegangenen Knoten abhängen. Demnach hängt das Ergebnis eines Subbaumes auch von darüber liegenden Stichen ab und kann nicht für andere Subbäume übernommen werden, da deren darüber liegende Zugkombination anders ist. Somit müssen die Knoten bzw. die Stiche einzelne Werte zugeordnet werden. Somit ergibt sich für die Knoten folgende Gleichung:

M(p) = T(p) + m(p)

• M(p) bezeichne den Minimax-Wert für den Knoten p mit M → [0;120]∈\N.
• T(p) ist die Anzahl an Punkten, die bereits vor p erreicht wurden mit T → [0;120]∈\N.
  Ist p die Wurzel, so ist T(p) gleich den Punkten aus dem Skat.
• m(p) ist die Anzahl an Punkten, die ab p bis zum Ende erreicht wird mit m → [0;120]∈\N.
  Ist p ein Blatt, so ist m(p) = 0. Ist p ein MAX-Knoten, wird der maximale M-Wert der Kindknoten gewählt. Ist p ein MIN-Knoten, wird der minimale Kindknoten gewählt.

Zusätzlich existiert zu jedem Subbaum aus der Tabelle ein Flag, welches anzeigt, ob beim Berechnen eine Schranke über- bzw. unterboten wurde. So kann beim Übernehmen des Ergebnisses aus der Tabelle der aktuelle \alpha- bzw. \beta-Wert für den zweiten Subbaum korrigiert werden, falls dies notwendig ist. Dafür implementiert Kupferschmid drei Flags:

• VALID, wenn gilt: \alpha < M(p) < \beta
• LBOUND, wenn gilt: M(p) \geq \beta
• UBOUND, wenn gilt: M(p) \leq \alpha

Minimal Window Search
In manchen Spielsituationen ist eine gesamte Betrachtung des Baumes gar nicht notwendig, z.B. wenn das Spiel bereits verloren ist. Um das schneller herauszufinden, wird auf das Prinzip des Zero Window Search zurückgegriffen. Statt ein initiales Fenster [-\infty;\infty] oder die möglichen Skatwerte [0;120] zu verwenden, wird nun auf ein minimales Fenster von [60;61] gesetzt. Bei Spielmodi wie Schneider, Schwarz oder Null variieren die Grenzen entsprechend. Dadurch kann der Baum so weit beschnitten werden, dass die Erkenntnis, ob es sich um eine Gewinnposition handelt oder nicht, schnell erfolgt. Separates Zählen der Punkte sorgt dafür den Baum weiter zu verkürzen, sobald der mindestens zu erreichende Punktewert überschritten wurde. So muss nicht bis zum Ende des Baumes gerechnet werden, um zu erkennen, ob eine Partei bereits gewonnen hat. In der Abbildung steht good_-points für die eigenen, bis zum Knoten p erreichten Punkte und bad_-points für die Punkte der Gegner.

Memory Enhanced Test Driver MTD(f)
Der Ansatz von MTD(f) besteht aus den beiden vorangegangenen Optimierungen. Mithilfe des Zero-Window-Search wird für jeden möglichen Zug p der spieltheoretische Wert durch stetiges Annähern ermittelt. Durch den Einsatz der Transpositionstabellen können die aus vergangenen Durchläufen gesammelten Informationen wiederverwendet werden und machen den Algorithmus effizienter. f sollte im Bereich der möglichen Punkte [0;120] sein.

Äquivalenzklassen
Anstatt beim Evaluieren von Spielpositionen nur die Einträge aus der Transpositionstabelle zu entnehmen, welche den exakt selben Spielstand besitzen, können auch Einträge von Stichen übernommen werden, die einen ähnlichen Spielverlauf haben. Dazu werden Äquivalenzklassen von Karten einer Farbe gebildet, welche die selben Karten mit der selben Farbe stechen können oder umgekehrt. Dadurch können mehr Knoten aus den Tabellen abgelesen werden. Im DDSS funktionierte dies nur mit den Buben sowie den punktelosen Karten (7en, 8en und 9en). Die Idee der Anwendung von Äquivalenzklassen auf Transpositionstabellen folgt dem Ansatz des Partition Search von M. Ginsberg.^[5:4]

Beispiel:
C_1 = {7, 8, Dame} und C_2 = {9, König} .
Die Äquivalenzklasse von 7 wäre , da beide Karten keine der Karten aus C_2 stechen können.
Die Dame gehört nicht dazu, weil sie die 9 stechen könnte

Move Ordering
Eine optimale Anordnung der Züge innerhalb des Suchbaumes kann zum großflächigen Beschneiden und damit auch zur schnelleren Evaluierung führen, da z.B. der beste Wert bereits am Anfang gefunden wird. Es bietet sich an die beste Karte derjenigen Farbe zuerst zu analysieren, welche den geringsten Verzweigungsgrad hat, also die wenigsten Karten zum Ausspielen zur Verfügung haben. Um herauszufinden, welcher der beste Zug pro Farbe ist, wird nach jedem Durchgehen einer Verzweigung gezählt, wie oft ein Zug der Erfolgreichste war. Demnach kann Move Ordering nicht vollständig zu Beginn angewandt werden, sondern erst nach einigen Berechnungen am Baum.

Weiterer Ansatz: UCT

Ein verwandter Ansatz, um den besten Zug für ein imperfektes Spiel zu finden, ist der bereits erwähnte UCT-Algorithmus, welcher von Jan Schäfer in seiner Diplomarbeit auf das Skatspiel angewandt wurde. In der Ausspiel-Phase wird der Monte Carlo Tree Search auf die aktuelle Spielsituation angewandt und zum Schluss der Zug gewählt, welcher den besten UCT-Wert hat.^[8:1]

Referenzen

Alle Links wurden das letzte Mal geprüft am 30.01.2023 um 19:32 Uhr.
Geschrieben von: Celina Müller

Online Skat spielen: https://www.spiele-kostenlos-online.de/brettspiele/kartenspiele/skat/

Abb. 1 selbst erstellt; keine Vorlage
Abb. 2 selbst erstellt; Vorlage
Abb. 3 selbst erstellt; keine Vorlage
Abb. 4 selbst erstellt; keine Vorlage
Abb. 5 selbst erstellt; keine Vorlage
Abb. 6 selbst erstellt; keine Vorlage
Abb. 7 selbst erstellt; keine Vorlage; Bild von Kartenrückseite
Abb. 8 selbst erstellt; keine direkte Vorlage; Inspiration aus ^[5:5]
Pseudocode 1 aus: Kupferschmid, S. (2003) Entwicklung eines Double Dummy Skat Solvers. (Seite 28)^[5:6]
Pseudocode 2 aus: Kupferschmid, S. (2003) Entwicklung eines Double Dummy Skat Solvers. (Seite 31)^[5:7]
Pseudocode 3 aus: Kupferschmid, S. (2003) Entwicklung eines Double Dummy Skat Solvers. (Seite 48)^[5:8]
Pseudocode 4 aus: Kupferschmid, S. (2003) Entwicklung eines Double Dummy Skat Solvers. (Seite 60)^[5:9]