Was ist die Gewinnstrategie für den ersten Spieler in Connect Four-Spielen?

Beste Antwort

Die eigentliche „Strategie“ ist eigentlich ziemlich komplex und beinhaltet eine umfassende Suche nach zu behandelnden Punkten mit Taktik, so ist es nicht praktisch, von Hand zu verwenden.

Andererseits sind die strategischen Einsichten und einige allgemeine Regeln für einen Menschen einfach zu verwenden und werden Sie wahrscheinlich relativ machen Guter Spieler.

Hintergrund

Beginnen wir mit einer schnellen Überprüfung von connect-4. Das Spiel wird auf einem 6 × 7-Brett gespielt. Wir können jede Zeile mit einer Zahl und jede Spalte mit einem Buchstaben kennzeichnen:

Jeder Spieler wählt abwechselnd eine Spalte aus. Ihr Stein befindet sich in der untersten offenen Zelle der Säule. Wir können ein Spiel nur mit den Spalten schreiben; Wenn zum Beispiel beide Spieler die zentrale Spalte spielen, können wir dd schreiben. Dies würde zu folgendem Board führen:

(Konventionell ist Spieler 1 blau und Spieler 2 rot.)

Ein Spiel kann gewonnen werden, indem vier Teile Ihrer Farbe horizontal, vertikal oder diagonal verbunden werden:

Ein letzter nützlicher Begriff ist eine Bedrohung , die nur drei Teile hintereinander enthält, wobei das vierte Quadrat offen ist (aber nicht unbedingt zugänglich ist). Hier hat Blau eine Bedrohung in einer Diagonale:

Strategie

Das Spiel ist gelöst: Der erste Spieler (blau) kann immer einen Sieg erzwingen. Die Kernideen hinter der Gewinnstrategie sind ziemlich einfach: Steuern von zugzwang und Steuern von ungerade / gerade Zeilen.

Zugzwang

„Zugzwang“ bedeutet als Begriff verlieren, weil Sie muss einen Zug machen. Eine einfache Illustration wäre, zwei Bedrohungen übereinander zu haben. Hier ist ein Beispiel dafür, wie Blau einen Gewinn in Spalte c mit Rot erzwingt, um sich zu bewegen:

Doppelte Bedrohungen wie diese In der Praxis besteht eine viel nützlichere Form von Zugzwang darin, nur zu warten, bis das gesamte Brett gefüllt ist und nur noch ein Zug möglich ist. Betrachten Sie das einfache Beispiel, bei dem Rot links gewinnt. Die eigentliche Kraft tritt erst nach einer Reihe von Zügen auf:

Gerade / ungerade Bedrohungen

Wer eine Bedrohung hat, die unaufhaltsam ausgefüllt wird, gewinnt am Ende. Wie wir im vorherigen Beispiel gesehen haben, kann Rot mit einer Bedrohung in einer gerade Zeile. Im Gegensatz dazu benötigt Blau eine ungerade Bedrohung, um zu gewinnen: Hier liegt die Asymmetrie im Spiel taucht auf.

Eine seltsame Bedrohung „verschließt“ eine Spalte und dreht im Wesentlichen um, wer welche Zeile erhalten kann, wenn die gesamte Boa gefüllt wird rd. Dies bedeutet insbesondere, dass eine gültige ungerade Bedrohung „stärker“ ist als eine gültige gerade Bedrohung: Wenn Blau eine ungerade Bedrohung in einer Spalte und Rot eine gerade Bedrohung in einer anderen Spalte hat, gewinnt Blau immer noch. Hier ist ein Beispiel (blau zum Spielen):

Von dieser Position aus können wir wiederholt füllen, bis wir zu a gelangen Position, an der Rot c spielen muss, weil g (mit einer ungeraden Anzahl von Stücken) zu einem blauen Gewinn führen würde Die Spalte c füllt sich, bis Rot zum Verlieren gezwungen wird:

Die Eine ungerade Bedrohung „funktioniert“, weil sie eine einzelne Spalte abschließt, um eine ungerade Anzahl von Positionen zu haben – wodurch das Brett effektiv von einer geraden Anzahl von Quadraten abgehalten wird (42) auf eine ungerade Zahl, die die Dynamik des Spiels umdreht. Dies bedeutet auch, dass wenn sowohl rot als auch blau unabhängige ungerade Bedrohungen haben, sie sich aufheben: zwei ungerade Spalten bringen die Summe wieder auf gerade.

Im Allgemeinen gibt uns die ungerade / gerade Unterscheidung den Begriff Kontrolle : Rot kontrolliert normalerweise das Spiel, aber Blau kann die Kontrolle erlangen, indem es eine seltsame Bedrohung festlegt. In der Praxis bedeutet Kontrolle, dass Sie in der Lage sind, gerade Felder zu spielen oder optional ein ungerades Feld zu spielen, aber Ihren Gegner im Gegenzug ein gerades Feld spielen zu lassen.

Taktik

Die ungerade / gerade Unterscheidung lässt uns „strategisch“ spielen – jedenfalls eine Reihe von Schritten voraus. Um konsequent zu gewinnen, müssen wir unser Wissen über langfristige Strategien mit soliden taktischen kurzfristigen Maßnahmen kombinieren. Wir müssen kleine Fallen wie diese im Auge behalten:

Regeln

Die eigentliche Gewinnstrategie für das Spiel besteht aus neun Regeln, die auf den zuvor behandelten strategischen Prinzipien und der Taktik basieren.Die Regeln wurden 1988 von Victor Allis entwickelt – ich glaube, er war der erste, der das Spiel gelöst hat.

Die Regeln können „nicht immer die optimale Lösung finden: Manchmal müsste man tatsächlich nach Möglichkeiten suchen, um sich hauptsächlich mit taktischen Problemen zu befassen.

Hier sind meiner Meinung nach die wichtigsten Regeln mit den Namen, die Allis ihnen gegeben hat Es gibt einige weitere Regeln, die jedoch entweder für Sonderfälle oder nur für Kombinationen früherer Regeln gelten. Sie können alle Regeln in der aktuellen Arbeit nachlesen: Ein wissensbasierter Ansatz für Connect Four .

• baseinverse : Sie können immer eines von zwei zugänglichen Feldern beanspruchen, wenn Ihr Gegner das andere beansprucht. Sie können also immer einen Vier-in-einer-Reihe blockieren, der zwei solche Felder benötigt. Beispielsweise kann Rot immer eines der grünen Quadrate, nachdem Blau das o spielt ther:

• vertikal : Sie können jederzeit einen vertikalen Vierer hintereinander blockieren, indem Sie eines der beiden Quadrate direkt übereinander spielen. Rot kann immer die vertikalen vier in einer Reihe auf d blockieren, indem es eines der hervorgehobenen Quadrate spielt:

• claimeven : Wer die Kontrolle über das Spiel hat (dh Rot, es sei denn, Blau hat eine seltsame Bedrohung ) kann ein Quadrat in einer geraden Reihe spielen (solange dieses Quadrat nicht sofort spielbar ist). Diese Regel verkörpert die grundlegende Strategie für ungerade / gerade.
• aftereven : Wenn Sie die Kontrolle haben und eine Bedrohung in einer geraden Reihe haben, können Sie diese Reihe über claimeven spielen. Dies bedeutet, dass alle Bedrohungen in derselben Spalte über dieser blockiert sind. Zum Beispiel hier Blau kann b3 nicht spielen, da Rot eine Bedrohung für b2 darstellt:

• lowinverse : Wenn zwei Spalten mit einer ungeraden Anzahl offener Spalten vorhanden sind Quadrate, das Ergebnis ist gerade. Wenn es zwei ungerade Quadrate gibt In solchen Spalten, die nicht direkt spielbar sind, kann jeder, der das Spiel kontrolliert, mindestens eine davon spielen. Dies kann auch für Quadrate gelten, die weit davon entfernt sind, spielbar zu sein und nicht nebeneinander liegen. In diesen beiden einfachen Beispielen kann Rot mindestens eines der beiden hervorgehobenen Quadrate erhalten:

Gewinnen

Das Spiel wurde tatsächlich durch eine Kombination dieser Regeln und eine umfassende Suche gelöst – die Regeln allein reichen leider nicht aus.

Viele der Regeln hängen von der Kontrolle über das Spiel ab. Da Rot anfänglich die Kontrolle hat, kann Blau viele der Regeln erst verwenden, wenn es gelingt, eine seltsame Bedrohung zu etablieren. Blau kann eine seltsame Bedrohung darstellen, indem es einige der Regeln verwendet, die nicht von Kontrolle oder nur taktischem Denken abhängen, wie das Kombinieren von Zweiergruppen, um eine seltsame Bedrohung in der Zukunft zu garantieren.

Es stellt sich heraus, dass dies die erste ist Der Spieler kann dies gegen ein optimales Spiel tun, solange der erste Zug d1 ist. Dies bedeutet, dass der erste Spieler immer gewinnen kann. Die Suche, die dies tatsächlich festgestellt hat, wird auch in der Arbeit detailliert beschrieben.

Für menschliche Spieler ist es schwierig, mit dieser Art von Logik zu arbeiten. Glücklicherweise hat jemand anderes eine Reihe guter Öffnungen gefunden, die Sie im Allgemeinen verwenden können: Expertenspiel in Connect-Four .

Abgesehen davon habe ich alle Illustrationen mit Haskells wundervollem Diagramm -Paket erstellt. Diese ganze Antwort war eigentlich eine Übung, nur um zu lernen, wie man die Bibliothek benutzt, was ich schon seit einiger Zeit vorhabe! Sie können sich den Code auf dieses Kerns ansehen. Der Code ist chaotisch, aber es ist eine großartige Demonstration, dass Haskell entgegen der landläufigen Meinung tatsächlich großartig ist für interaktives Prototyping und Schreiben von Wegwerfcode.

Außerdem finde ich es cool zu sehen, wie Emacs SVGs und PNGs in einem Puffer in der Vorschau anzeigen kann, was mir im Wesentlichen eine maßgeschneiderte Umgebung für die Entwicklung von Bildern wie diesen bietet: