Mines1337

Minesweeper für Fortgeschrittene

16. Dezember 2020

2018 entwickelte ich eine Minesweeper-App. Seit Anfang 2019 ist sie im (iOS-)Appstore. Eine Sache hat mich beim Minesweeper immer gestört: unlösbare Spiele. Bei Mines1337 gibt es dieses Problem nicht mehr. Alle Spielfelder sind immer lösbar. Manchmal erfordert es aber ein wenig Gehirnakrobatik. Zusätzlich gibt es neben den üblichen 3 Zell-Zuständen (unbekannt, aufgedeckt, Fahne), auch noch einen 4. Zell-Zustand: „wartend“.

In diesem Artikel will ich die Idee der App beschreiben, und worin die Unterschiede und Gemeinsamkeiten im Vergleich zu Minesweeper bestehen.

Inhaltsverzeichnis

Unlösbare Spiele: Im ersten Teil beschreibe ich das Grundproblem, und was ich genau unter einem „lösbaren“ bzw. einem „unlösbaren“ Spiel verstehe.
Ein bisschen Gehirnakrobatik: Im zweiten Teil beschreibe ich in groben Zügen, wie der Algorithmus in meiner App arbeitet.
Zellen im Wartemodus: Im dritten Teil beschreibe ich, wie Zellen bei Mines1337 aufgedeckt werden. Hier geht es um einen wesentlichen Unterschied zwischen Mines1337 und dem klassischen Minesweeper.

Unlösbare Spiele

Manchmal ist es unmöglich, zu wissen wo die Bombe ist. Im folgenden Spielfeld ist auf einem der 2 Stellen, die mit "?" markiert sind, eine Bombe. Die andere Stelle muss freigelegt werden.

?	1	0	0	...
?	3	1	0	...
F	F	1	0	...
2	2	1	0	...
...

Es ist unmöglich, zu wissen, wo die Bombe ist und welches der beiden Felder man stattdessen freilegen muss. D.h. es besteht eine 50%-Chance, dass ich mit meinem nächsten Spielzug das Spiel verliere.

Die Frage, die sich nun stellt ist: wann genau ist ein Spiel lösbar? Diese Frage macht nur Sinn, wenn das Spielfeld nicht komplett leer ist und solange das Spiel noch nicht beendet ist, d.h. es noch immer mindestens ein unaufgedecktes Feld gibt. Die Antwort ist überraschend einfach:

Ein Spielfeld ist dann eindeutig lösbar, wenn ich immer ein unaufgedecktes Feld berechnen kann, das ich aufdecken kann. (Beweis mit vollständiger Induktion.)

Um zu bestimmen, welches Feld ich als nächstes aufdecke, kann ich nur die Informationen benutzen, die ich sehe. Dazu gehört auch die Anzahl der insgesamt am Spielfeld versteckten Bomben.

Ob ein Spiel eindeutig lösbar ist, hängt natürlich auch von Informationen ab, die ich nicht sehe.

Die Generierung von eindeutig lösbaren Minesweeper-Spielen verläuft daher nach dem gleichen Prinzip wie die Generierung von eindeutig lösbaren Sudoku-Rätseln.

• Es werden zufällig 14 Bomben auf einem 10x10-Spielfeld verteilt.
• Wenn dort, wo der User als erstes hingecklickt hat eine Bombe ist => zurück zum Start
• Der Computer versucht, auf einem nicht am Bildschirm sichtbaren Spielfeld, das Spiel zu lösen. Wenn er irgendwo stecken bleibt und nicht mehr weiter kommt => zurück zum Start
• Fertig!

(Damit dieser Algorithmus effizient läuft und die App nicht nach dem ersten Click ein paar Sekunden hängt, sind ein paar Optimierungen notwendig. Daher ist der Algorithmus in Wahrheit etwas komplexer als hier beschrieben. Das Grundprinzip ist aber dasselbe.)

Das Einzige, was an diesem Ablauf nicht ganz einfach ist, ist der Algorithmus zum Lösen eines Spielfeldes. Dieser muss nämlich versuchen, ein NP-vollständiges Problem effizient zu lösen.

Eine Google-Suche nach “minesweeper solving algorithm” liefert bei mir 971000 Ergebnisse. Effiziente Algorithmen sind hier meistens relativ komplex, weil die Algorithmen deduktive Fähigkeiten modellieren müssen. Ich will daher nicht hier das 971001. Ergebnis liefern, sondern nur kurz anhand eines Beispiels zeigen, wie es gehen kann.

Ein bisschen Gehirnakrobatik

Neulich stieß ich auf eine Situation wo ich nicht mehr weiter wusste. Hatte ich einen Bug gefunden? Ist das Spiel wirklich eindeutig lösbar?

Mit 404s lag ich schon deutlich über einer guten Zeit, und so startete ich meinen Computer, um Xcode nach einem Tipp zu fragen. Dabei fand ein Algorithmus, den ich “find local contradiction” nenne, eine Lösung. Dieser Algorithmus funktioniert so:

Für alle nicht aufgedeckten Felder, die Nachbaren von einem aufgedeckten Feld sind, stelle 2 Fragen:

1. wenn ich dieses Feld aufdecken würde, und dann mit der “simple”-Strategie weiter spiele, führt das dann zu einem Widerspruch?
2. wenn ich auf dieses Feld eine Fahne setze, und dann mit der “simple”-Strategie weiter spiele, führt das dann zu einem Widerspruch?

Der Algorithmus spuckte “(5, 6) F, culprit=(7,8)” aus, was so viel bedeutet wie: „An Stelle (5,6) muss eine Bombe sein, denn wenn man annimmt, dass (5,6) sicher wäre, dann ergäbe das an Stelle (7,8) einen Widerspruch.“ Im folgenden Bild ist die erste Koordinate mit einem "X" und die 2. Koordinate mit einem "Y" gekennzeichnet. (Hinweis zum Koordinatensystem: die erste Koordinate die die X-Koordinate und geht von links nach rechts; die zweite Koordinate geht von oben nach unten. Links oben ist die Koordinate (0, 0).)

Der Algorithmus hat also versucht, Stelle (5, 6) freizulegen, und ist dann auf einen Widerspruch in Stelle (7, 8) gestoßen. Versuchen wir zu verstehen, warum das so ist:

Wir können daher mit Sicherheit sagen, dass auf (5, 6) eine Bombe sein muss.

Zellen im Wartemodus

Nun kommen wir zu dem Teil, durch den sich das von mir programmierte Spiel von anderen Minesweeper-Spielen unterscheidet: die Wartezeit von ca. 2,5 Sekunden, bevor eine angeklickte Zelle aufgedeckt wird. (Normalerweise klickt man beim Minesweeper eine Zelle an, und sie wird sofort aufgedeckt. D.h. man weiß entweder sofort, dass man auf eine Bombe gestiegen ist und daher das Spiel verloren hat, oder die Zelle wird aufgedeckt und eine Zahl (1-8) erscheint. Oder die Zelle hat keine Bomben als Nachbaren, und deshalb wird zusätzlich auch die ganze Nachbarschaft der Zelle rekursiv aufgedeckt.)

Durch die Wartezeit wird das Spiel komplizierter. Man kann dann mehr Schritte vorausdenken und mehr Felder aufdecken, obwohl man das Ergebnis früherer Spielschritte noch nicht sehen kann. Dadurch wird man gezwungen, vorauszudenken. Wenn man normales Minesweeper bereits zu oft gespielt hat, sodass man davon geistig unterfordert ist, dann ist das eine willkommene Abwechslung. Das Spiel erhält dadurch eine neue Dynamik.

Bitte alle fleißig runterladen und spielen :) Hier geht’s zum App-Download...