Durak ist ein russisches Kartenspiel, das schon im russischen Kaiserreich gespielt wurde. Der Name des Spiels heißt übersetzt in etwa "Dummkopf" oder "Narr" und ist der Titel, den der Verlierer des Spiels temporär erhält.
Dieser Artikel beschäftigt sich unter anderem mit den Regeln des Spiels, stellt Lösungsansätze vor und präsentiert einen Vergleich dieser, definiert den Begriff von Imperfect Information Games und zeigt am Beispiel von Durak, wie man innerhalb dieser Spiele Informationen gewinnen kann. Insbesondere wird das Spiel auf einem 52-Karten Deck (2 - A) mit genau 2 Spielern betrachtet, die Regeln werden jedoch allgemein definiert.[1]
¶ Regeln [1:1]
Das Ziel des Spiels ist es, nicht der letzte Spieler zu sein, der alle seine Karten ablegen konnte und somit eine leere Hand besitzt.
Es wird üblicherweise auf einem 52-Karten (2 - A) oder 36-Karten (6 - A) Deck gespielt.
Die Anzahl der Spieler ist nicht fest, es werden jedoch mindestens 2 Spieler benötigt. Mehr als 6 Spieler sind auf einem 52 Kartendeck möglich, jedoch aufgrund der langen Wartezeit zwischen eigenen Angriffs-/Verteidigungsrunden nicht optimal.
¶ Spielbeginn
Zu Beginn des Spiels zieht jeder Spieler 6 Karten aus dem gemischten Stapel. Danach wird eine weitere Karte für alle Spieler offenbart und anschließend als letzte Karte in das Deck platziert - die Farbe dieser Karte ist nun für den Rest des Spiels als Trumpffarbe festgelegt. (Abb. 1)
¶ Angriff und Verteidigung
Nun beginnt der erste Spieler damit, den Spieler zu seiner Linken anzugreifen. Er legt eine Karte aus seiner Hand offen auf den Tisch, sollte der Spieler mehrere Karten des gleichen Rangs besitzen, darf er direkt mit beliebig vielen dieser Karten angreifen.
Die Aufgabe des verteidigenden Spielers ist es nun, jede dieser Angriffe mit Karten aus seiner Hand zu überbieten.
Überbieten ist wie folgt definiert:
- Die Karte darf mit einer Karte der selben Farbe und höherem Rang überboten werden
- Die Karte darf mit einer beliebigen Trumpfkarte überboten werden, es sei denn die angreifende Karte ist selber eine Trumpfkarte
Nun darf der angreifende Spieler weitere Angriffe mit Karten aus seiner Hand starten, wobei jeder neue Angriff stets eine Karte sein muss, dessen Rang bereits in einem anderen Angriff - als Angriffs oder Verteidigunskarte - verwendet wurde. Dabei darf es zu keinem Zeitpunkt mehr offene Angriffe geben, als der verteidigende Spieler noch Karten auf der Hand hat. (Abb. 2, 3)
¶ Ende einer Runde
Es gibt zwei Möglichkeiten, wie eine Runde beendet werden kann:
- Der verteidigende Spieler hat alle Angriffe überboten.
- Der verteidigende Spieler kann einen oder mehrere Angriffe nicht überbieten oder gibt die Runde freiwillig auf.
Im 1. Fall werden alle Karten, die zum Angreifen und Verteidigen verwendet wurden, aus dem Spiel genommen. Außerderm ist der Verteitiger in der nächsten Runde der Angreifer.
Im 2. Fall muss der erfolglose Verteidiger alle verwendeten Karten, inklusive der des Angreifers, aufnehmen und der Spieler zu seiner Linken wird in der nächsten Runde der Angreifer. Das Verlieren einer Runde führt also dazu, dass man als Angriffsspieler "übersprungen" wird.
In beiden Fällen müssen dannach alle Spieler vom Stapel nachziehen, bis sie wieder 6 Karten auf der Hand haben. Dabei beginnt der Angreifer mit dem Nachziehen. Sollte der Stapel leer sein, wird dieser Schritt übersprungen.
¶ Ende des Spiels
Das Spiel endet, sobald es nur noch einen Spieler mit Karten auf der Hand gibt. Der Stapel wird also erst von allen Spielern gemeinsam geleert und anschließend muss jeder Spieler möglichst schnell seine Karten ablegen.
Der letzte übrig bleibende Spieler mit Karten ist der Verlierer, bzw. der "Durak".
¶ Wichtige Eigenschaft: Imperfect Information
Da man in der herkömmlichen Variante von Durak keine Information über den Rest des Stapels, sowie die gegnerische Hand besitzt, gilt Durak als Imperfect Information Game.
¶ Lösungsansatz: Monte Carlo Tree Search
Die Monte Carlo Tree Search (MCTS) stellt iterativ einen Zustandsbaum über Spielzuständen auf, wobei der aktuelle Spielzustand als Startknoten verwendet wird und somit zum Wurzelknoten des Zustandsbaumes wird. In jeder Iteration wird der Baum um einen Knoten erweitert dessen korrespondierender Zustand mit einem vorher festgelegten Algorithmus solange weitergespielt ("simuliert") wird, bis das Spiel endet. So wird eine Statistik erstellt, die nach beliebig vielen Iterationen als finales Entscheidungsmittel für den nächsten Zug verwendet wird.[2]
¶ Reduktion der unbekannten Variablen [2:1][3]
Aufgrund der Eigenschaft der Imperfect Information würde der Zustandsbaum der MCTS ohne weitere Vorkehrungen einen extrem hohen Branching Faktor besitzen.
Zu Beginn eines Spiels mit 52 Karten und 2 Spielern sind genau 7 Karten bekannt und 45 unbekannt - 6 auf der gegnerischen Hand und 39 im Stapel. Somit gibt es 8.145.060 mögliche gegnerische Hände, die Gesamtanzahl verschiedener möglicher Zustände ist etwa 1,2 * 1056.
Zu diesem Zeitpunkt gibt es keine Möglichkeit diese Zahlen durch Informationsgewinn zu reduzieren, da der einzige Weg des Informationsgewinns die Beobachtung der Angriffs- und Verteidigungszüge des Gegners ist.
- Sollte die Runde in einem erfolgreich abgewehrten Angriff enden, so sind die verwendeten Karten für den Rest des Spiels nicht mehr zu berücksichtigen. Somit verringert sich die Gesamtanzahl an möglichen Karten auf der gegnerischen Hand, sowie im Stapel.
- Sollte der Gegner einen Angriff nicht abwehren können, muss dieser alle verwendeten und deswegen offengelegten Karten auf seine Hand aufnehmen. In diesem Fall haben wir Informationen über dessen Hand gewonnen, da er diese Karten nicht ablegen kann, ohne sie in einem Angriff/einer Verteidigung zu spielen.
Solange in jeder Runde stets, wenn anwendbar, eine der beiden Regeln verwendet wird und sich die nun bekannten Karten in der Hand des Gegners gemerkt werden, kann eine Spielsituation beliebig nah an ein Perfect Information Game kommen und der Branching Faktor der MCTS erheblich reduziert werden.
¶ Eliminierung der Imperfect Information
Damit eine sinnvolle Simulation durch die Simulation Phase der MCTS möglich wird, müssen vorher alle unbekannten Karten mit einem festen Wert belegt werden. Die einfachste Variante diesbezüglich ist die Determinization. [2:2]
Determinization ist eine Art des Samplings und belegt jede freie, unbekannte Variable (im Fall von Durak: jede unbekannte Karte) mit einem festen Wert. In Durak kann das durch folgenden Algorithmus sichergestellt werden:
def determinization(gamestate):
sample = copy(gamestate)
opponent = sample.players.opponent
opponentHiddenCards = []
for card in opponent.hand
if isUnknown(card)
opponentHiddenCards.append(card)
opponent.hand.remove(card)
toDraw = opponentHiddenCards.length()
sample.deck.ammend(opponentHiddenCards)
sample.deck.shuffle()
opponent.draw(toDraw)
return sample
[3:1]
Zeile 2-4: Kopiere den aktuellen Spielstand, speichere den Gegner als Variable und initialisiere die Liste an versteckten Karten des Gegners als leer.
Zeile 6-9: Speichere alle noch unbekannten Karten des Gegners in der zuvor initialisierten Liste und lösche sie aus der Hand des Gegners.
Zeile 11-15: Lege die Karten auf den Nachziehstapel und mische diesen durch. Anschließend zieht der Gegner so oft vom Stapel, wie vorher unbekannte Karten auf seiner Hand waren. Gebe anschließend den entstandenen Spielzustand zurück.
Eine Determinization mit 3 Samples ist in Abb. 4 gezeigt.
Nach Ausführung der determinization() darf die MCTS den zurückgegebenen Spielzustand als Perfect Information Game betrachten, also alle Karten aus der gegnerischen Hand, sowie den Rest des Stapels jederzeit uneingeschränkt einsehen. Die durch shuffle() entstandene Reihenfolge der Karten ist zufällig und somit wurde die Hand des Gegners und der Stapel nun mit zufälligen Werten instanziiert. Oftmals werden mehrere Samples erstellt, um einen größeren Teil des Wahrscheinlichkeitsbaumes abzudecken. Hierbei muss jedoch eine Balance zwischen Effizienz/Laufzeit und Genauigkeit des Algorithmus gehalten werden. [3:2]
¶ Andere Lösungsansätze
Außerhalb der Monte Carlo Tree Search gibt es noch andere Ansätze, um gute Spielzüge aus einer Spielsituation in Durak herzuleiten.
¶ Minimax
Obwohl der Minimax-Algorithmus eigentlich nur für Perfect Information Games geeignet ist, kann er unter der Verwendung von Determinization teilweise ebenfalls für Imperfect Information Games wie Durak verwendet werden. [3:3]
Minimax ist ein rekursiver Algorithmus der auf dem aktuellen Spielstand aufgerufen wird. Von dort aus spannt der Algorithmus einen Baum auf, mit dem eingegebenen Spielstand als Wurzel. Von jedem Knoten aus werden alle möglichen Züge rekursiv aufgerufen. Ist eine vorher festgelegte maximale Tiefe erreicht, wird eine Evaluationsfunktion aufgerufen, die (meistens mithilfe einer Heuristik) den Spielstand bewertet. Durch die rekursiven Aufrufe können die Parent-Knoten, je nachdem welcher Spieler an der Reihe ist, die Bewertung des Child-Knotens mit dem minimalen/maximalen Wert übernehmen und somit den Spielzug bestimmen, der in depth Zügen den minimalen Payout maximiert.[4]
Eine Einschränkung in Durak ist, dass der Spielbaum in den meisten Fällen einen sehr hohen Branching Faktor besitzt, wodurch die Laufzeit des Algorithmus schon bei geringer Tiefe extrem lang wird. Dies ist in Endspielen oftmals nicht der Fall, wenn der Nachziehstapel leer ist und alle Karten des Gegners bekannt sind.[4:1]
¶ Greedy
Ein weiterer, eher simpler Ansatz ist ein Greedy-Verfahren, welches immer die Karte mit dem geringsten Wert (Rang) spielt. Dabei muss beachtet werden, dass Trumpfkarten, egal welchen Rang sie haben, trotzdem die stärksten Karten im Spiel sind.[3:4]
Die Nachteile dieses Ansatzes beinhalten offensichtlich, dass nicht mehr als ein Spielzug vorausgeschaut wird und deswegen, selbst in relativ simplen Interaktionen mit Perfect Information, oftmals ein objektiv falscher Zug gewählt wird.
¶ Vergleich verschiedener Ansätze
Abb. 5 zeigt die Ergebnisse eines 1 gegen 1 Turniers mit 36 Karten und je einem Agent der Strategien MCTS mit Determinization, Minimax, Smart, Greedy und Random.[3:5]
Random spielt dabei immer einen zufälligen Spielzug und Smart wählt seinen Spielzug nach einer Heuristik, die auf den bekannten Karten des Gegners basiert.[3:6]
¶ Offene Fragen
Es bleibt offen, ob es vielleicht noch andere Ansätze gibt, die sich für ein Zugauswahlverfahren eignen, bspw. die ISMCTS (Information Set Monte Carlo Tree Search). Diese verfährt wie die herkömmliche MCTS, gruppiert allerdings mehrere Zustände, die aufgrund von Imperfect Information für den Betrachter äquivalent aussehen, in Information Sets und baut den Suchbaum über diesen Sets auf. [2:3]
Desweiteren ist Durak ein Spiel, das in sehr vielen, leicht verschiedenen Varianten existiert, weswegen es Interessant wäre, diese wissenschaftlich auszuarbeiten, um Unterschiede in der Effizienz der Algorithmen festzustellen.[3:7]
¶ Bildquellen
Abb. 1: Übernommen aus dem Onlinebeitrag https://www.kindersache.de/bereiche/spiel-spass/spieletipps/durak
Abb. 2: Übernommen aus dem Onlinebeitrag https://www.kindersache.de/bereiche/spiel-spass/spieletipps/durak
Abb. 3: Übernommen aus dem Onlinebeitrag https://www.kindersache.de/bereiche/spiel-spass/spieletipps/durak
Abb. 4: Übernommen aus dem Paper Monte Carlo tree search: A review of recent modifications and applications[2:4]
Abb. 5: Übernommen aus dem Paper Artificial Intelligence for the Card Game Durak[3:8]
¶ Referenzen
ŚWIECHOWSKI, Maciej, et al. Monte Carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 2023, 56. Jg., Nr. 3, S. 2497-2562. url ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
ZARLYKOV, Azamat. Artificial Intelligence for the Card Game Durak. 2023. url | pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
BOROVSKA, Plamenka; LAZAROVA, Milena. Efficiency of parallel minimax algorithm for game tree search. In: Proceedings of the 2007 international conference on Computer systems and technologies. 2007. S. 1-6. url ↩︎ ↩︎