Analyse einer modifizierten Version des Kartenspiels „Krieg“

Question

Ein einfaches Spiel, das normalerweise von Kindern gespielt wird, wird das Spiel des Krieges von zwei Personen gespielt, die ein Standard -Deck mit 52 Spielkarten verwenden. Zunächst wird das Deck gemischt und alle Karten werden zwei die beiden Spieler behandelt, so dass jeweils 26 zufällige Karten in einer zufälligen Reihenfolge haben. Wir werden annehmen, dass die Spieler beide Decks untersuchen (aber nicht ändern), damit jeder Spieler die Karten und Kartenbestellungen in beiden Decks kennt. Dies wird in der Regel in der Praxis beachtet, würde jedoch nichts darüber ändern, wie das Spiel gespielt wird, und hilft, diese Version der Frage vollständig deterministisch zu halten.

Dann enthüllen die Spieler die höchsten Karten aus ihren jeweiligen Decks. Der Spieler, der die größere Karte enthüllt (gemäß der üblichen Reihenfolge: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Königin, König, Ass) gewinnt die Runde und platziert zuerst seine Karte (die hohe Karte) am Ende seines Decks und dann am unteren Rand des Decks (in der Regel wird die Reihenfolge der Reihenfolge nicht durchgesetzt, aber um die erste Version dieser Frage deterministisch zu halten, dann ist die Reihenfolge nicht durchgesetzt, sodass die Reihenfolge nicht durchgesetzt wird. Eine Bestellung wird erzwungen).

Im Falle eines Unentschieden enthüllt jeder Spieler vier zusätzliche Karten von der Spitze seiner Decks. Wenn die vierte Karte, die von einem Spieler gezeigt wird Das Gewinner des Decks (in der ersten In-In-Erstausstattung; mit anderen Worten, ältere Karten werden zuerst zuerst platziert), gefolgt von den Verliererkarten (in derselben Reihenfolge).

Im Falle der nachfolgenden Beziehungen wird der Vorgang wiederholt, bis ein Gewinner des Unentschieden bestimmt ist. Wenn ein Spieler keine Karten mehr hat und das Unentschieden nicht weiter brechen kann, wird der Spieler, der immer noch Karten hat, zum Gewinner erklärt. Wenn beide Spieler Karten ausgehen, um gleichzeitig zu spielen, wird das Spiel zum Unentschieden erklärt.

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

Da das Spiel bisher beschrieben wurde, ist weder Fähigkeiten noch Glück an der Bestimmung des Ergebnisses beteiligt. Da es eine begrenzte Anzahl von Permutationen von 52 Karten gibt, gibt es eine begrenzte Anzahl von Möglichkeiten, wie die Decks ursprünglich behandelt werden können, und es folgt, dass (da die einzigen staatlichen Informationen im Spiel der aktuelle Zustand der Decks beider Spieler sind ) Das Ergebnis jeder Spielkonfiguration kann a priori entschieden werden. Sicherlich ist es möglicherweise, das Kriegsspiel und aus dem gleichen Grund zu verlieren, um es zu verlieren. Wir lassen auch die Möglichkeit offen, dass ein Kriegsspiel zu einem Unentschieden oder in einer unendlichen Schleife führen kann. Für die oben beschriebene vollständig deterministische Version kann dies der Fall sein oder nicht.

Mehrere Variationen des Spiels, die versuchen, es interessanter zu machen (und nein, nicht alle beinhalten es, es in ein Trinkspiel zu machen). Ein Weg, an den ich gedacht habe, um das Spiel interessanter zu machen, besteht darin, den Spielern die Erklärung automatischer "Trumps" in bestimmten Runden zu ermöglichen. In jeder Runde können entweder Spieler (oder beide Spieler) "Trump" erklären. Wenn ein Spieler "Trump" erklärt, gewinnt dieser Spieler die Runde, unabhängig von den gespielten Karten. Wenn beide Spieler "Trump" erklären, wird die Runde als Unentschieden behandelt und das Spiel wird entsprechend fortgesetzt.

Man kann sich eine Vielzahl von Regeln vorstellen, die die Fähigkeit der Spieler zu Trump einschränken (unbegrenztes Trumping würde immer zu einem Krawattenspiel führen, wie die Spieler in jeder Runde übertrumpft). Ich schlage zwei Versionen vor (direkt auf meinem Kopf; interessantere Versionen in dieser Richtung sind wahrscheinlich möglich) des Krieges, basierend auf dieser Idee, aber die Verwendung verschiedener Trumpfbegrenzungsmechanismen:

1. Frequenzkrieg: Die Spieler dürfen nur übertrumpft, wenn sie in den vorherigen $ K $ -Runden nicht übertrumpft haben.
2. Rachekrieg: Die Spieler dürfen nur übertrumpft, wenn sie in den vorherigen K $ -Runden keine Runde gewonnen haben.

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

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

Um klar zu sein, denke ich an eine "Strategie" als einen festen Algorithmus, der feststellt, was der Spieler anhand der Strategie übertrumpft. Zum Beispiel ist der Algorithmus "Trump, wann immer Sie können" eine Strategie und ein Algorithmus (ein heuristischer Algorithmus). Eine andere Möglichkeit, was ich frage, ist Folgendes:

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

Verweise auf Analysen solcher Spiele werden geschätzt (ich bin mir der Analyse dieser Version des Krieges oder der im Wesentlichen gleichwertigen Spiele nicht bewusst). Die Ergebnisse für alle $ k $ sind interessant und geschätzt (beachten Sie, dass $ k = 0 $ zu unbegrenztem Trumping führt, was ich bereits besprochen habe).

Answer 1

Wenn ich richtig verstehe, stehen allen Spielern alle Informationen über das Spiel zur Verfügung. Das heißt, die Startkonfiguration und alle möglichen Bewegungen sind beiden Spielern bekannt (vor allem, weil beide Spieler die Karten des anderen Spielers betrachten können). Dies macht das Spiel zu einem Null-Sum-Spiel mit perfekten Informationen. Daher gibt es eine perfekte Strategie für beide Spieler, die das beste Ergebnis in jedem Spiel für diesen Spieler erzielen würden. Dies wurde 1912 vom deutschen Mathematiker Ernst Zermelo bewiesen.

Ich weiß nicht, was die Strategie ist, aber man könnte sich vorstellen Min-Max-Algorithmus.

Der Baum für jedes Spiel hätte die Hände der beiden Spieler. Die Zweige im Baum entsprechen den Bewegungen der Spieler. Im einfachsten Fall bestehen diese darin, einfach die erforderlichen Karten festzulegen. In den fortgeschritteneren Fällen kann der "Trump" -Bezug gemacht werden. Interne Knoten des Baumes erfassen Sie die aktuelle Kartenkonfiguration zusammen mit Informationen über den Status WRT 'Trumps'. Die Blätter des Baumes entsprechen den Endspielpositionen, die mit beispielsweise +1 für einen Sieg für Spieler 1, 0 für ein Unentschieden und -1 für einen Sieg für Spieler 2 gekennzeichnet sind. Ignorieren Sie für den Moment die Spiele.

Jetzt funktioniert der Min-Max-Algorithmus wie folgt (aus Sicht von Spieler 1). Angenommen, es betrachtet einen Knoten, bei dem Spieler 1 eine Bewegung macht und dass die folgenden Knoten mit einer +1, 0 oder -1 (die mit einem +1, 0 oder -1) kommentiert werden auszahlen) zusammen mit den Auswahlmöglichkeiten, die der Spieler treffen muss, um das angegebene Ergebnis zu erzielen. Player 1 wählt einfach den Knoten mit der größten Auszahlung aus, verzeichnet die Auszahlung und die Auswahl, die erforderlich ist, um dies zu erhalten. Für den Knoten, in dem Player 2 den Umzug vornimmt, wird der Knoten mit der minimalen Auszahlung gewählt und die Auswahl erfasst. Dies spiegelt wider, dass Player 2 die niedrigste Punktzahl anstrebt, um zu gewinnen. Dies wird an den Baum ausgegeben. Die an jedem Knoten aufgezeichneten Auswahlmöglichkeiten 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 Bewegungen variieren kann.

Potenziell Looping -Konfigurationen Kann in den Spielbaum eingebaut werden, indem einfach Schleifen hinzugefügt werden, die zu einer bereits gesehenen Konfiguration zurückkehren (wenn sie von oben berechnet). Für solche Knoten nehmen Sie den größten festen Punkt, wenn es sich um einen Knoten handelt, an dem Spieler 1 spielt und der am wenigsten feste Punkt, wenn Spieler 2 spielt.

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

Ob es eine starke oder schwache Gewinnstrategie für einen der Spieler gibt oder nicht, hängt vom Ergebnis des Min-Max-Algorithmus ab, der auf alle Bäume angewendet wird. Aber es gibt sicher viele von ihnen ... das Berechnen des Baumes für einen ist wahrscheinlich ziemlich einfach, da es nicht sehr viele Möglichkeiten gibt, die im Spiel getroffen werden.