minesweeper eindeutig lösbar

[bananenmarmelade]

die frage ist kann man alle minesweeperprobleme eindeutig lösen, nachdem man die ersten ~5 klicks gemacht hat, und ein kleines feld an zahlen hat. damit meine ich nicht, mal an einer stelle nicht weiter kommen, und dann raten. viel eher geht es darum, dass man dann diese fragezeichen setzt und sich mögliche minenpositionen überlegt, und diese mit den informationen, die man hat vergleicht. es ist also eher ein theoretisches oder informatisches problem.

 

[Valhalla]

hab noch nie ein minesweeper spiel verloren was nicht auf fehler meinerseits beruhte. und ich hab ca 6monate stundenlang beim zivi gezockt

 

[shaoling]

Es kann auch im späteren Spiel zu Situationen kommen, in denen man mit 50%-Chance raten muss. Hatte ich ein- oder zweimal.

 

[Teegetraenk]

Gibt oft keine eindeutige Möglichkeit, und das locker 5-6 Mal pro Spiel. Fragezeichen sind übrigens für Newbs.

 

[lt-trainee]

[ ] immer lösbar
[x] ab und an ist 50-50 Chance

 

[aMrio]

Original geschrieben von sHaO-LiNg
Es kann auch im späteren Spiel zu Situationen kommen, in denen man mit 50%-Chance raten muss. Hatte ich ein- oder zweimal.

ein oder zweimal? entweder spielst du nur newbie level oder aber du hast es erst 4 mal gespielt.

 

[Albstein]

Minesweeper hat nicht immer eine eindeutige Lösung und ist NP vollständig.

http://www.claymath.org/Popular_Lectures/Minesweeper/

http://www.inf.fu-berlin.de/lehre/SS07/Seminar-Algorithmen-Komplexitaet/minesweeper.pdf

 

[shaoling]

Original geschrieben von aMrio
ein oder zweimal? entweder spielst du nur newbie level oder aber du hast es erst 4 mal gespielt.

Keine Ahnung, vielleicht wars auch etwas öfter.
Ich hab meist das Fortgeschrittenen-Feld gespielt, bis ich irgendwann das Profi-Feld geschafft hab. Danach hab ich dann recht schnell das Interesse verloren.

 

[aMrio]

also spätestens ab profi hat man pro spiel mehrere situationen wo man einfach nur noch raten kann und deswegen hass ich das spiel ~

 

[shaoling]

Hab Profi nur einmal durchgespielt, ums mal geschafft zu haben. Mehr Freude hatte ich daran, das mittlere Feld möglichst schnell zu lösen.

 

[Teegetraenk]

Mensch, bin total eingerostet. Aber wie gesagt, man hat locker 2-3 50/50 Situationen, also gehört auch Glück dazu.

 

[aMrio]

ok, vielleicht check ichs nicht, aber wie lösen ohne raten?

 

[Teegetraenk]

Gar nicht, aber ich könnte schwören, dass das Feld links unter der 2 am linken Rand _keine_ Mine ist

 

[Didier]

Ne, Amrio das ist eindeutig. Die zwei ganz links braucht noch eine Mine. Also ist entweder das linke oder das zweitlinkeste eine Mine.

Folglich hat die zweite 2 von links bereits zwei Minen und das dritte Feld von links ist garantiert keine Mine. Danach kannst Du sicher sein, dass das 2., 4. und 5. von links Minen sind wegen der 3. 2 von links und der 3 und das ganze löst sich auf. Witzigereise hat Pivo mit seiner Intuition sogar recht. Ganz links ist keine Mine.

Nichtsdestotrotz gibt es natürlich Situationen in denen man raten muss, und sie kommen in nem Profi Spiel schon hin und wieder vor, 5-6 mal erscheint mir aber übertrieben.

 

[bananenmarmelade]

Original geschrieben von Albstein
Minesweeper hat nicht immer eine eindeutige Lösung und ist NP vollständig.

http://www.claymath.org/Popular_Lectures/Minesweeper/

http://www.inf.fu-berlin.de/lehre/SS07/Seminar-Algorithmen-Komplexitaet/minesweeper.pdf

danke erstmal.

das bedeutet für mich, der mitunter schon mit seinem handy auf kriegsfuß steht, dass man bisher noch keine möglichkeit gefunden hat minesweeper eindeutig zu lösen, da es zur familie der NP-probleme (?) gehört. alle NP-probleme kann mal auf einen ähnlichen sachverhalt / ähnliche problemstellungen reduzieren, die man nicht in vernünftiger (polynomieller?) zeit algorithmisch lösen kann. aber man hat auch noch nicht bewiesen, dass es unmöglich ist?

 

[Izzy]

Das Feld unter der dritten 2 von links ist keine Mine.

Edit: Zu langsam

 

[sinusx]

Original geschrieben von aMrio
ok, vielleicht check ichs nicht, aber wie lösen ohne raten?

Szenarien bilden und auf Widersprüche untersuchen.

Unter der mittleren 2 von der 2223-Kombi muss eine Mine liegen, sonst bekommst du die 2 rechts daneben nicht "voll".

 

[Didier]

Nein, NP Probleme kann man schon lösen. In welcher Zeit weiß auch keiner, man hat nur noch keinen Algorithmus gefunden, der es in polynomialer Zeit schafft.

Aber vergiss das am besten alles ganz schnell wieder, es ist hier sowieso nicht relevant. Merk Dir einfach, es gibt Situationen in denen man raten muss, ein einfaches Beispiel:
Stell Dir vor die untere linke Ecke sieht wie folgt aus, die x sind Minen und es fehlt noch genau eine um das Spiel zu vervollständigen.

xxx
??x

Edit: Ui geht das schnell hier, das bezog sich natürlich auf Bananes letzten Post.

 

[sinusx]

Andersrum kann man auch fragen, wie die Minen liegen müssten, damit der erste Klick die Lösung aufdeckt.

Das ginge nur bis zu einer bestimmten Dichte (Minen/Gesamtzahl der Felder). Wäre mal was für "Mathe für Zwischendurch".

Das hätte auch ne Aufgabe in unserer "Statistischen Mechanik"-Klausur heute sein können...

 

[voelkerballtier]

Original geschrieben von aMrio

ein oder zweimal? entweder spielst du nur newbie level oder aber du hast es erst 4 mal gespielt.

oder du bist newb und denkst ein situation sei nicht eindeutig nur weil du nicht weißt wie es weiter geht...

@Didier: also so wie ich deine Links verstehe, wird da überhaupt keine Aussage über Lösbarkeit gemacht - kannst du das vllt doch mal näher erläutern?

 

[Antrax4]

Original geschrieben von sinusx


Szenarien bilden und auf Widersprüche untersuchen.

Unter der mittleren 2 von der 2223-Kombi muss eine Mine liegen, sonst bekommst du die 2 rechts daneben nicht "voll".

#2
und aus dem selben Grund auf dem Feld unten rechts (neben der eins) keine Mine

 

[Teegetraenk]

Mal die Bestzeiten der letzten 10 Minuten.

 

[ferdi1337]

naja das erste hatte ich mal in 4 sek, einfach nur klicken

 

[Sodom&Gomorrha]

Interessant wäre auch, in wie weit sich die Situation ändert, wenn man das gute alte Wrapfield-Easteregg einschaltet
Weil dann gelten die Zahlen auch über Wände und Ecken hinaus, etwas schwieriger; aber vielleicht eindeutiger?

 

[xornado]

This thread is now about: Minesweeper Highscores im Profi Mode

Mein bestes waren 93 Sekunden ...


U ?

 

[Teegetraenk]

Keine Ahnung, aber deutlich drunter. 76 warens mal. Aber das ist auch schnurps, da um es beweisen zu können ich wieder etwas üben müsste und dazu eig. keine Böcke habe.

 

[xornado]

Original geschrieben von PivoUser_R7
Keine Ahnung, aber deutlich drunter. 76 warens mal. Aber das ist auch schnurps, da um es beweisen zu können ich wieder etwas üben müsste und dazu eig. keine Böcke habe.

76 ist wirklich sehr krass. Sehr krass. und ich habe mal ein Jahr lang 24/7 gespielt (- 6/7 für Schlaf und -1/7 für Essen und so)

 

[shaoling]

Also ich brauch für Profi ~5min.

 

[Albstein]

Also wissenschaftlich reicht eine Spielsituation um zu widerlegen, daß man Minesweeper immer eindeutig lösen kann, imho würde sogar schon das Startspielfeld dem genügen, weil man nicht sagen kann auf Feld x,y ist keine Mine also der erste Zug immer "raten" ist.

Angenommen NP != P (wovon die meisten ausgehen), dann folgt daraus auch, daß Minesweeper nicht eindeutig ist. Wäre Minesweeper eindeutig lösbar könnte man einen Algorithmus angeben, der alle Felder durchgeht, abgleicht ob es eine Mine enthält oder nicht, was ja gehen würde wenn es eindeutig ist und das wäre in O(n^x) zu lösen und damit in P.

 

[Sodom&Gomorrha]

Original geschrieben von sHaO-LiNg
Also ich brauch für Profi ~5min.

Ich war gerade auf "Profi" und die Uhr geht nur bis 999 Sekunden

Außerdem muss ich gestehen, in solchen Situationen einfach nicht mehr weiterzukommen und bei ner 50:50-Chance gehe ich drauf ...

Wie geht man da heran ? Das Gleiche wie bei aMrios Beitrag, nur noch eingeschränkter.
Es geht um die vier blanken Felder, in jedem Zweierpack ist eine Mine versteckt, aber außer da wirklich zu raten komme ich auf keine plausible Lösung, die mir logisch exakt erklärt, wo und wie ich da die Mine genau orten kann. Oder ich bin einfach zu blöd.

Ach ja, Spiel mit 9 Restminen (natürlich) verloren - aber dummerweise vergessen, die Orte der Minen zu merken ...

 

[Didier]

Original geschrieben von sinusx
Andersrum kann man auch fragen, wie die Minen liegen müssten, damit der erste Klick die Lösung aufdeckt.

Das ginge nur bis zu einer bestimmten Dichte (Minen/Gesamtzahl der Felder). Wäre mal was für "Mathe für Zwischendurch".

Das hätte auch ne Aufgabe in unserer "Statistischen Mechanik"-Klausur heute sein können...

Stimmt nicht. Stell Dir vor, alle Felder bis auf ein einziges sind Minen. Dann könntest Du das Spiel mit einem einzigen Klick lösen. Da in Minesweeper der erste Klick auch nie eine Mine trifft passt das ^^

Original geschrieben von Albstein

Angenommen NP != P (wovon die meisten ausgehen), dann folgt daraus auch, daß Minesweeper nicht eindeutig ist. Wäre Minesweeper eindeutig lösbar könnte man einen Algorithmus angeben, der alle Felder durchgeht, abgleicht ob es eine Mine enthält oder nicht, was ja gehen würde wenn es eindeutig ist und das wäre in O(n^x) zu lösen und damit in P.

Komplexitätstheorie ist wahrlich nicht die Stärke dieses Forums. Meine leider auch nicht. Aber immerhin weiß ich, dass es dabei um die Rechenzeit auf einer Touring Maschine geht und diese könnte selbst wenn Minesweeper eindeutig wäre problemlos NP sein. Genaugenommen hat es sogar nichts miteinander zu tun. Ein Algorithmus kann zwar tatsächlich alle Felder durchgehen, jedoch sicherlich nicht, wie von Dir angenommen für jedes Feld in linearer Zeit entscheiden, ob dort eine Miene liegt...

Edit: Zu Gomorrha: In Deinem Fall kannst Du überhaupt nichts anderes machen als raten. Ein typisches Beispiel, das auch wirklich in fast jedem Profi Spiel mal vorkommt. Ziemlich nervig. Die Strategie ist üblicherweise so etwas am Anfang schon so weit wie möglich auszuschliessen. Beispielsweise könntest Du am Anfang einfach alle vier Ecken durchklicken, da man sich in diesen häufig am Ende aufhängt.

 

[shaoling]

Original geschrieben von Gomorrha
Wie geht man da heran ?
Es geht um die vier blanken Felder, in jedem Zweierpack ist eine Mine versteckt, aber außer da wirklich zu raten komme ich auf keine plausible Lösung, die mir logisch exakt erklärt, wo und wie ich da die Mine genau orten kann.

Geht leider nur raten.

 

[Sodom&Gomorrha]

Hmmm.
Interessant wäre, wenn Microsoft einen Mechanismus implementieren könnte, der eben solche Raten-Konstellationen verhindert - ohne dass das natürlich zu einfach würde (falls möglich).

Andererseits könnte das Programm je nach Schwierigkeitsgrad ein kleines Feld offenlegen, so dass man nicht dem Risiko unterläuft, beim ersten Feld gleich eine Mine zu erwischen. Vorher natürlich so berechnet, dass die automatische Zugvorgabe nicht einen Bereich erwischt, wo von vorneherein in der ganzen Umgebung keine Minen vorhanden sind und gleich das halbe Feld gelöst ist.

Oder das erste Feld ist IMMER ein leeres Feld und erst nach Klicken werden die Minen zufällig verteilt.

Dann wäre der Glücksfaktor nicht so problematisch. Andererseits spiele ich extrem selten Minesweeper, da ärgert mich so eine Lage halt öfter, als wenn man es gewohnt ist.

Beim Skat etwa einen Grand ohne 4 gespielt und aufgrund blöder Kartenverteilung knapp mit 59 Augen verloren. Da helfen dann auch 40+ Jahre Spielerfahrung dann nicht.

 

[Albstein]

Es geht auch nicht um lineare Laufzeit. O(n^x) ist alles andere als linear aber es ist berechenbar in polynomial begrenzer Zeit und daher P. Das wesentliche bei Minesweeper ist eben das auch von dir beschriebene Raten, was das ganze zu NP bringt. NP heißt (vereinfacht), daß es divers Möglichkeiten gibt und jede der Möglichkeiten in polynomialer Zeit geprüft werden kann und zwar von der von dir erwähnten Mehrband-Turingmaschine.

Zudem hab ich durchaus schon mit dem ersten Klick eine Mine erwischt.

Für die ursprüngliche Frage reicht aber wie gesgat bereits die Startkonfiguration als Gegenbeispiel.

 

[cyclonus]

Diese NP=?P Geschichte gilt nicht für Minesweeper allgemein sondern für ganz bestimmt konstruierte Spielfelder, ich weiss es nicht mehr ganz genau, aber man konnte damit irgendwelche logischen Nand- oder Xor-Gatter nachbauen oder sowas in der Richtung.

 

[voelkerballtier]

Original geschrieben von Albstein
Es geht auch nicht um lineare Laufzeit. O(n^x) ist alles andere als linear aber es ist berechenbar in polynomial begrenzer Zeit und daher P. Das wesentliche bei Minesweeper ist eben das auch von dir beschriebene Raten, was das ganze zu NP bringt. NP heißt (vereinfacht), daß es divers Möglichkeiten gibt und jede der Möglichkeiten in polynomialer Zeit geprüft werden kann und zwar von der von dir erwähnten Mehrband-Turingmaschine.

Abgesehen davon, dass das eine irreführende bis falsche Erklärung von "NP" ist, habe ich mal deine Links von oben durchgelesen und da wird nicht das Lösen eines Minesweeper bei gegebener Konfiguration, sondern dass Prüfen, ob die gegebene Konfiguration logisch konsistent ist (dazu muss sie nicht eindeutig sein) - das Minesweeper Consistency Problem -untersucht. Und das ist NP-vollständig.

Zum eigentlichen Thema: es wurde ja schon gesagt, dass man einen uneindeutigen Zustand problemlos konstruieren kann. Ich frage mich aber grade, ob man das auch kann, ohne den Rand zu benutzen (die Frage kam oben glaub auch schon mal)?

 

[Scarab]

Das NP-Vollständig ist doch nur eine Aussage über die Laufzeit, die zur Lösung eines Problems benötigt wird, und hat nichts mit dem Problem des Zufalls bei Minesweeper zu tun. Durch die unvollständigen Informationen gibt es halt öfter Situationen in denen keine eindeutige Antwort möglich ist und man raten muß.

Und daß selbst Minesweeper hier mal wieder im Schwanzvergleich ausartet, hätte ich nicht gedacht, kommt ihr euch nicht etwas lächerlich dabei vor?

 

[SkyHawK]

Original geschrieben von voelkerballtier
Zum eigentlichen Thema: es wurde ja schon gesagt, dass man einen uneindeutigen Zustand problemlos konstruieren kann. Ich frage mich aber grade, ob man das auch kann, ohne den Rand zu benutzen (die Frage kam oben glaub auch schon mal)?

edit: Link fixed.

 

[Eeth]

NP-VOllständig.

gg

 

[Benrath]

also klar gibts rate situationen in minesweeper, habs gerade auch wieder geteste, kommt fast in jedem spiel vor..

und ich glaube keinem der behauptet er schafft das ding in unter 100 sekunden.. musst ja mindestens jede sekunden ne Mine belegen, das wär schon mega mega freaky..

3-4 minuten fänd ich schon krass.