Analyse einer modifizierten Version des Kartenspiels "War"

Als einfaches Spiel, das normalerweise von Kindern gespielt wird, wird das Kriegsspiel von zwei Personen mit einem Standardstapel von 52 Spielkarten gespielt. Zunächst wird das Deck gemischt und alle Karten werden zu zweit ausgeteilt, sodass jeder Spieler 26 zufällige Karten in zufälliger Reihenfolge hat. Wir gehen davon aus, dass die Spieler beide Stapel untersuchen (aber nicht wechseln) dürfen, damit jeder Spieler die Karten und die Reihenfolge der Karten in beiden Stapeln kennt. Dies geschieht normalerweise in der Praxis, ändert jedoch nichts an der Art und Weise, wie das Spiel gespielt wird, und trägt dazu bei, diese Version der Frage vollständig deterministisch zu halten.

Dann decken die Spieler die obersten Karten aus ihren jeweiligen Decks auf. Der Spieler, der die größere Karte aufdeckt (in der üblichen Reihenfolge: 2, 3, 4, 5, 6, 7, 8, 9, 10, Bube, Dame, König, Ass), gewinnt die Runde und legt zuerst seine Karte (die hohe Karte) am unteren Rand seines Decks, und dann die Karte seines Gegners (die niedrige Karte) am unteren Rand des Decks (in der Regel wird die Reihenfolge nicht erzwungen, aber die erste Version dieser Frage deterministisch zu halten, z eine Bestellung wird erzwungen).

Im Falle eines Gleichstands deckt jeder Spieler vier zusätzliche Karten von der Oberseite seines Decks auf. Wenn die vierte von einem Spieler gezeigte Karte höher ist als die vierte von einem anderen Spieler gezeigte Karte, gewinnt der Spieler mit der höheren vierten Karte alle Karten, die während des Gleichstands gespielt wurden Gewinnerstapel (in der Reihenfolge First-In, First-Out; mit anderen Worten, ältere Karten werden zuerst unten abgelegt), gefolgt von den Karten des Verlierers (in derselben Reihenfolge).

Bei späteren Unentschieden wird der Vorgang wiederholt, bis ein Gewinner des Unentschieden feststeht. Wenn ein Spieler keine Karten mehr hat und das Unentschieden nicht fortsetzen kann, wird der Spieler, der noch Karten hat, zum Gewinner erklärt. Wenn beiden Spielern die Karten ausgehen, um gleichzeitig zu spielen, wird das Spiel für unentschieden erklärt.

Runden werden gespielt, bis einem Spieler die Karten ausgehen (dh er hat keine Karten mehr in seinem Deck). Zu diesem Zeitpunkt wird der Spieler, der noch Karten hat, zum Gewinner erklärt.

Wie das Spiel bisher beschrieben wurde, sind weder Geschick noch Glück bei der Bestimmung des Ergebnisses beteiligt. Da es eine endliche Anzahl von Permutationen von 52 Karten gibt, gibt es eine endliche Anzahl von Möglichkeiten, wie die Decks anfänglich behandelt werden können, und daraus folgt, dass (da die einzige Statusinformation im Spiel der aktuelle Status der Decks beider Spieler ist ) Das Ergebnis jeder Spielkonfiguration kann a priori festgelegt werden. Sicher ist es möglich, das Kriegsspiel zu gewinnen und es aus dem gleichen Grund zu verlieren. Wir lassen auch die Möglichkeit offen, dass ein Kriegsspiel zu einem Unentschieden oder einer Endlosschleife führen kann. für die oben beschriebene vollständig deterministische Version kann dies der Fall sein oder nicht.

Verschiedene Variationen des Spiels, die versuchen, es interessanter zu machen (und nein, nicht alle beinhalten, es zu einem Trinkspiel zu machen). Eine Möglichkeit, die ich mir überlegt habe, um das Spiel interessanter zu gestalten, besteht darin, den Spielern zu ermöglichen, in bestimmten Runden automatische "Trümpfe" zu deklarieren. In jeder Runde kann jeder Spieler (oder beide Spieler) "Trumpf" erklären. Wenn ein Spieler "Trumpf" erklärt, gewinnt dieser Spieler die Runde, unabhängig von den gespielten Karten. Erklären beide Spieler "Trumpf", wird die Runde als Gleichstand gewertet und das Spiel entsprechend fortgesetzt.

Man kann sich eine Vielzahl von Regeln vorstellen, die die Trumpffähigkeit der Spieler einschränken (unbegrenztes Trumpfen würde immer zu einem Unentschieden führen, da die Spieler jede Runde trumpfen würden). Ich schlage zwei Versionen von War vor (von Anfang an, interessantere Versionen in dieser Richtung sind wahrscheinlich möglich), die auf dieser Idee basieren, aber unterschiedliche Trumpfbegrenzungsmechanismen verwenden:

1. Frequenzkrieg: Spieler dürfen nur trumpfen, wenn sie in den vorhergehenden Runden nicht trumpfen konnten .$k$
2. Rache-Krieg: Spieler dürfen nur trumpfen, wenn sie in den letzten Runden keine Runde gewonnen haben .$k$

Nun zu den Fragen, die für jede der oben beschriebenen Versionen gelten:

1. Gibt es eine Strategie, bei der bei einigen möglichen anfänglichen Spielkonfigurationen der Spieler, der sie verwendet, immer gewinnt (stark gewinnende Strategie)? Wenn ja, wie lautet diese Strategie? Wenn nein, warum nicht?
2. Gibt es eine Strategie, bei der der Spieler, der sie verwendet, für einige der möglichen anfänglichen Spielkonfigurationen immer gewinnen oder ein Unentschieden erzwingen kann (Gewinnstrategie)? Wenn ja, wie lautet diese Strategie? Wenn nein, warum nicht?
3. Sind ihre anfänglichen Spielkonfigurationen so, dass es keine Gewinnstrategie gibt (dh ein Spieler, der eine feste Strategie kann immer von einem Spieler besiegt werden, der eine feste Strategie S 'verwendet )? Wenn ja, was sind sie und erklären?$S$$S'$

Um es klar zu sagen, ich stelle mir eine "Strategie" als festen Algorithmus vor, der festlegt, bei welchen Runden der Spieler, der die Strategie verwendet, trumpfen soll. Zum Beispiel ist der Algorithmus "Trump when you can" eine Strategie und ein Algorithmus (ein heuristischer Algorithmus). Eine andere Art zu fragen ist:

Gibt es eine gute (oder nachweislich optimale) Heuristik für diese Spiele?

$k$$k=0$

Wenn ich es richtig verstehe, stehen beiden Spielern alle Informationen zum Spiel zur Verfügung. Das heißt, die Startkonfiguration und alle möglichen Züge sind beiden Spielern bekannt (hauptsächlich, weil beide Spieler die Karten des anderen Spielers anschauen können). Dies macht das Spiel zu einem Nullsummenspiel mit perfekten Informationen. Somit gibt es eine perfekte Strategie, die beiden Spielern zur Verfügung steht, um das beste Ergebnis in jedem Spiel für diesen Spieler zu erzielen. Dies wurde 1912 vom deutschen Mathematiker Ernst Zermelo bewiesen.

Ich weiß nicht, was die Strategie ist, aber man könnte sich vorstellen, einen großen Spielbaum dafür zu erstellen und einen Computer zu veranlassen, die Strategie mit dem Min-Max-Algorithmus für mich zu finden .

Der Baum für jedes Spiel hätte als Wurzel die Hände der beiden Spieler. Die Zweige im Baum entsprechen den Zügen der Spieler. Diese bestehen im einfachsten Fall aus dem einfachen Ablegen der erforderlichen Karten. In den fortgeschritteneren Fällen kann der Trumpfzug ausgeführt werden. Interne Knoten des Baums zeichnen auf, wie die aktuelle Konfiguration der Karten aussieht, und geben Auskunft über den Status der Trümpfe. Die Blätter des Baums entsprechen den Endspielpositionen, die mit +1 für einen Sieg für Spieler 1, 0 für einen Gleichstand und -1 für einen Sieg für Spieler 2 gekennzeichnet sind. Ignorieren Sie vorerst die Looping-Spiele.

Jetzt funktioniert der Min-Max-Algorithmus wie folgt (aus Sicht von Spieler 1). Angenommen, es wird ein Knoten betrachtet, an dem Spieler 1 einen Zug ausführt, und die Knoten darunter werden mit +1, 0 oder -1 (der Auszahlung) gekennzeichnet) zusammen mit den Entscheidungen, die der Spieler treffen muss, um das gegebene Ergebnis zu erhalten. Spieler 1 wählt einfach den Knoten mit der größten Auszahlung aus, zeichnet diese Auszahlung auf und legt fest, welche Auswahl erforderlich ist, um diese zu erhalten. Für den Knoten, bei dem Spieler 2 den Zug ausführt, wird der Knoten mit der niedrigsten Auszahlung ausgewählt und die Auswahl wird aufgezeichnet. Dies zeigt, dass Spieler 2 die niedrigste Punktzahl anstrebt, um zu gewinnen. Dies wird auf den Baum übertragen. Die an jedem Knoten aufgezeichneten Entscheidungen entsprechen der besten Strategie, die ein Spieler treffen kann. Die endgültige Auszahlung bestimmt, wer gewinnt. Dies ist letztendlich eine Funktion in Bezug auf die Auszahlung, obwohl die genaue Wahl der Züge variieren kann.

Potenziell loopende Konfigurationen können in den Spielbaum integriert werden, indem einfach Loops hinzugefügt werden, die zu einer bereits gesehenen Konfiguration zurückkehren (wenn von oben gerechnet wird). Für solche Knoten nehmen Sie den größten Fixpunkt, wenn es sich um einen Knoten handelt, auf dem Spieler 1 spielt, und den geringsten Fixpunkt, auf dem Spieler 2 spielt.

Beachten Sie, dass wenn Sie nicht angenommen hätten, dass beide Spieler beide Decks untersuchen könnten, dieser Ansatz nicht zutreffen würde. Das Spiel würde dann einen Zufall beinhalten und die ausgewählte Strategie wäre spielspezifisch.

Ob es für einen der Spieler eine starke oder schwache Gewinnstrategie gibt oder nicht, hängt vom Ergebnis des Min-Max-Algorithmus ab, der auf alle Bäume angewendet wird. Aber es gibt sicher eine Menge von ihnen ... Den Baum für einen zu berechnen, ist wahrscheinlich ziemlich einfach, da im Spiel nicht sehr viele Entscheidungen getroffen werden.