Wie man "Minesweeper" löst (und es besser macht)

Minesweeper ist ein einfaches Spiel mit einfachen Regeln, jedoch verursachen einige seiner Konfigurationen interessante Schwierigkeiten. In diesem Artikel werden wir einen Minesweeper-Löser mit zunehmender Komplexität erstellen und darüber nachdenken, wie sich die Dynamik des Spiels mit einer allmählichen Erhöhung des Hilfsniveaus ändert. Am Ende werden wir eine neue Version des Spiels mit viel interessanterem Gameplay entwickeln.

Lokale Argumentation: Null benachbarte Minen

Im ursprünglichen Spiel wird ein automatischer Mechanismus verwendet: Wenn ein Spieler eine Zelle öffnet, neben der sich keine Minen befinden, öffnet die Spiel-Engine alle benachbarten Zellen. Dies gefährdet das Spiel nicht, sodass Sie den Computer sicher ausführen lassen können. Die Situation selbst ist dem Spieler sofort klar und beeinträchtigt das Gameplay nicht.

Diese Argumentation ist vollständig lokal: Nur eine Zelleninformation wird berücksichtigt, um über die nächste Aktion zu entscheiden.

Es ist schwierig, eine Situation zu finden, in der sich das Spiel ohne diese automatische Hilfe verschlechtern würde. Versuchen Sie, ein solches Spiel zu spielen, um eine Vorstellung davon zu bekommen, wie es funktioniert, ohne Zellen automatisch zu öffnen [im Originalartikel sind alle Beispiele interaktiv] ::

Lokale Überlegungen basierend auf der Umgebung

Für einen neuen Spieler ist es leicht zu verstehen, dass alle diese Zellen Minen sein müssen, wenn die Anzahl der benachbarten Minen, dh die in der Zelle angezeigte Anzahl, der Anzahl der unentdeckten benachbarten Zellen entspricht. Sie müssen also Flaggen darauf setzen. In ähnlicher Weise müssen die verbleibenden unentdeckten Nachbarzellen leer sein, wenn die Anzahl benachbarter Minen gleich der Anzahl benachbarter Flaggen ist.

In diesen Regeln werden eine Zelle sowie der Zustand benachbarter Zellen (offen / geprüft) berücksichtigt.

Das manuelle Implementieren dieser Regeln kann Spaß machen. Wenn Sie einen Timer hinzufügen, lernt der Spieler, wie man ihn schnell und genau anwendet. Dies macht den Minesweeper zu einem Reaktionsspiel . Was passiert, wenn wir diese Regeln automatisieren?


Eine solche Automatisierung hat einen interessanten Nebeneffekt - das Aktivieren des Kontrollkästchens kann sofort fatale Folgen haben.

Andernfalls können Situationen auftreten, die in drei Kategorien unterteilt werden können:

1. Spiele, die durch Anwendung automatischer Regeln vollständig gelöst wurden
2. Komplizierte Situationen, die mehr Zellen zum Denken erfordern
3. Zustände des Spiels, in denen es keinen logischen Weg vorwärts gibt - der Spieler kann nur zufällig wählen, möglicherweise unter Berücksichtigung der Wahrscheinlichkeiten.

Situation 1 scheint schön, aber nicht besonders interessant, wenn sie zu oft auftritt. Wären solche Spiele ohne eine automatische Lösung besser? Vielleicht nicht; Solche Spiele sind sehr einfach, selbst wenn sie manuell gelöst werden, und der Spieler ist nicht besonders daran interessiert, Spiele zu spielen, bei denen es keine Schwierigkeiten gibt. Obwohl es im Reaktionsspiel natürlich immer Schwierigkeiten gibt: Sie müssen so schnell wie möglich handeln.

Situation 2 scheint mir sehr attraktiv zu sein. Wir konzentrieren uns mehr auf das Lösen logischer Bedingungen, verbringen weniger Zeit mit präzisem Zielen und Drücken der richtigen Tasten. Dies macht Sapper eher zu einem aktiven Puzzle .

Situation 3 zerstört den ganzen Spaß. Ich habe jedoch gehört, dass einige Leute gerne zufällige Spiele spielen.

Ist es möglich, Situation 3 loszuwerden?

Komplettlösung: Globales Denken

Für die algorithmische Erkennung aller logischen Bedingungen, die für den Status des Spiels erforderlich sind, müssen wir eine umfassende Suche nach allen Status des Spiels durchführen. Minesweeper ist nachweislich eine NP-vollständige Aufgabe . Im Folgenden finden Sie ein kleines, aber interessantes und anschauliches Beispiel für den Status des Spiels mit nur einer logischen Lösung. Um diese zu finden, müssen Sie jedoch den Status des Spiels als Ganzes berücksichtigen:


Ist es möglich, den gesamten Zustandsraum des Spiels zu durchsuchen? Wie viele Variationen des Zustands gibt es?

Gegeben:

w = Feldbreite

h = Feldhöhe

k = Anzahl der Minuten

n = w

Dann ist die Anzahl der möglichen Zustände s

$$

$$s = \ begin {pmatrix} n \\ k \ end {pmatrix}$$

Für die Standardstufen "Anfänger", "Amateur" und "Profi" ergibt sich Folgendes:

$$

$$s_b = \ begin {pmatrix} 8 * 8 \\ 10 \ end {pmatrix} = 151473214816$$

$$

$$s_i = \ begin {pmatrix} 16 * 16 \\ 40 \ end {pmatrix} = 1.050 * 10 ^ {47}$$

$$

$$s_e = \ begin {pmatrix} 30 * 16 \\ 99 \ end {pmatrix} = 5.602 * 10 ^ {104}$$

Wir verstehen, dass ein naiver Ansatz hier völlig unangemessen ist. Lassen Sie uns sehen, wie ein naiver Algorithmus aussehen könnte, und herausfinden, ob er für etwas optimiert werden kann, das funktioniert.

Naiver Algorithmus

Die Aufgabe des Algorithmus besteht darin, alle logischen Bedingungen zu finden, die für den gegebenen Zustand des Feldes erforderlich sind. Es wäre schwierig, dies durch sorgfältige Abwägung der Lösungen umzusetzen. Der Computer macht es viel besser, schnell eine Reihe dummer Aktionen auszuführen.

Was können wir "dumm" machen: Generieren Sie alle möglichen Permutationen von Minenpositionen für alle verbleibenden Minen. Wenn eine solche Permutation allen offenen Zahlen entspricht, ist dies die richtige Lösung für das Spiel. Dann untersuchen wir alle möglichen Permutationen, finden alle möglichen Lösungen, wissen aber immer noch nicht, welche richtig ist.

Wenn in allen möglichen Lösungen etwas gemeinsam ist, entweder zwischen offenen Zellen oder zwischen als Minen gekennzeichneten Zellen, dann verstehen wir, dass diese Gemeinsamkeit Teil der richtigen Entscheidung für das aktuelle Feld sein sollte. Und tatsächlich: Es ist unmöglich, die richtige Lösung zu finden, die solche passenden Elemente nicht enthält, sonst hätten wir sie entdeckt.

Somit können wir alle logischen Bedingungen finden, die für den aktuellen Zustand des Feldes notwendig sind.

Zellen mit und ohne Einschränkungen

Der obige Algorithmus hat ein offensichtliches Problem: die Anzahl der Zustände, die untersucht werden müssen. Aber nicht alle Zellen sind gleich. Ungeöffnete Zellen neben einer Nummer sind offensichtlich auf diese Nummer beschränkt. Wir werden diese Zellen als begrenzt bezeichnen. Die restlichen Zellen werden wir unbegrenzt nennen.

Wenn wir den obigen Algorithmus implementieren, aber nur im Bereich der Zustände eingeschränkter Zellen suchen und zurückgehen, sobald wir die Einschränkung aufheben, können wir in vielen Spielen alle logischen Bedingungen in angemessener Zeit lösen:


Bei unbegrenzten Zellen können wir nicht herausfinden, wo sich die Minen befinden, und logischerweise wissen wir sofort davon. Dies bedeutet, dass Sie sie von der Berechnung ausschließen und nur den Standort von Minen neben offenen Zahlen berücksichtigen können.

Wir wissen jedoch, dass eine bestimmte Anzahl von Minen in viele unbegrenzte Zellen eindringen kann. Wenn es 6 Minuten und 4 eingeschränkte Zellen gibt, können in begrenzten Zellen maximal 4 Minen vorhanden sein, dh mindestens 2 Minuten müssen in unbegrenzten Zellen sein. Nach der gleichen Logik können wir manchmal feststellen, dass alle unbegrenzten Zellen leer sein müssen oder alle Minen enthalten.

In dem unten gezeigten Fall kennen wir die Positionen aller Minen, sodass die KI verstehen sollte, dass die verbleibenden Zellen nicht besetzt sind:


Im folgenden Fall kennen wir nicht die Positionen aller Minen, aber wir können verstehen, dass die verbleibende Mine in einer der beiden Zellen oben links platziert werden muss. Dies bedeutet, dass die in der unteren rechten Ecke verbleibende Zelle frei ist:

Zufällige Version

Wenn wir den globalen Löser automatisch ausführen, erhalten wir eine zufällig optimierte Version von Minesweeper:


Sie können die Spiele in dieser Version in drei Kategorien einteilen:

1. Spiele, bei denen der Spieler willkürliche Entscheidungen trifft und gewinnt.
2. Spiele, bei denen der Spieler willkürliche Entscheidungen trifft und verliert.
3. Spiele, bei denen KI viel Zeit benötigt und der Spieler tatsächlich argumentieren kann.

Offensichtlich ist dies ein Glücksspiel. Was ist der Reiz solcher Spiele? In logischer Hinsicht ähnelt das oben gezeigte Spiel dem folgenden:


Aber welches Zufallsspiel ist besser? Es scheint, dass die Bedeutung anderer Spiele mit Zufälligkeit in der Existenz einer komplexen Beziehung zwischen den Aktionen des Spielers und dem Gewinnen / Verlieren liegt. Um Lotterienummern zu ziehen, werden komplexe Maschinen verwendet, die es nicht eilig haben, eine Nummer auszuwählen und aus der Anzeige dieser Nummer eine ganze Show zu machen.

Vielleicht ist ein großes Feld, das automatisch entschieden wird, ein ziemlich gutes Spiel
mit Zufälligkeit, vorausgesetzt, der Spieler beobachtet das allmähliche Öffnen aller Zellen.

Können wir uns eine andere Art von Spiel einfallen lassen?

Deterministische Version

Jetzt haben wir eine KI, die in der Lage ist, alle logischen Schritte aus einem bestimmten Spielzustand zu bestimmen. Manchmal kann er keine logischen Schritte finden. In solchen Situationen muss der Spieler raten und er kann verlieren, wenn er kein Glück hat.

Was ist, wenn wir eine andere Regel hinzufügen? Wenn das Spiel keinen logischen Weg vorwärts hat, können wir um Hilfe bitten. Wenn die KI zustimmt, dass der Spieler nichts tun kann, kommt er ihm zu Hilfe. Andernfalls verliert der Spieler sofort. Das kann interessant sein. Was für eine Hilfe kann das sein? Möglicherweise müssen Sie eine Zelle öffnen, unabhängig davon, ob Minen vorhanden sind:


So haben wir Situationen, in denen man zufällig verlieren könnte, vollständig beseitigt.

Es gibt jedoch eine Ausnahme: Es besteht immer noch die Möglichkeit entarteter Situationen, in denen der globale Löser die Berechnungen nicht in angemessener Zeit abschließen kann. Leider ist dies das unvermeidliche Ergebnis, dass die Minesweeper-Aufgabe NP-abgeschlossen ist.

Wie wirkt sich die Schaltfläche "Um Hilfe bitten" auf das Gameplay aus? Es führt dazu, dass sich das Spiel mehr auf Logik konzentriert; Dies ist die "rätselhafteste" Version von "Minesweeper". Jemand könnte denken, dass das Spiel einfacher wird, aber tatsächlich wird es komplizierter. Jetzt gibt es keine Entschuldigung für die Fehler des Spielers und der Knopf wird ihn bestrafen, wenn er etwas verpasst hat. Ohne einen Knopf ist es leicht zu schließen, dass Sie alle logischen Möglichkeiten ausgeschöpft haben und die einzige Möglichkeit für die Entwicklung von Ereignissen besteht darin, zu versuchen, zufällig zu raten. Aufgrund des Vorhandenseins des Buttons muss der Spieler in dieser Einschätzung Recht haben.

Abschließend

Nachdem wir den vollständigen Solver „Minesweeper“ -Löser implementiert haben, konnten wir eine Variation des Spiels erstellen, die frei von seinem Fluch ist: Jetzt ist es unmöglich zu verlieren, da Sie zufällig wählen müssen, wenn Sie fast das gesamte Feld entschieden haben. Diese Version unterscheidet sich vom Originalspiel nur in den Momenten, in denen Sie zufällig raten müssen, sodass ich davon ausgehen kann, dass es viel mehr Spaß macht als das Originalspiel.

Zusätzlich haben wir eine Version des Spiels entwickelt, die einfache lokale Regeln automatisch löst. Ob Sie diese Hilfe nutzen, liegt bei Ihnen. Es verschiebt den Fokus des Spiels vom mechanischen Klicken zu einem rätselhafteren Gameplay. Gleichzeitig ist es nicht erforderlich, die Gameplay-Verbesserung zu verwenden, die über die Schaltfläche "Um Hilfe bitten" bereitgestellt wird.