Freigeisterhaus Foren-Übersicht
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   NutzungsbedingungenNutzungsbedingungen   BenutzergruppenBenutzergruppen   LinksLinks   RegistrierenRegistrieren 
 ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

Minesweeper

 
Neues Thema eröffnen   Neue Antwort erstellen   Drucker freundliche Ansicht    Freigeisterhaus Foren-Übersicht -> Wissenschaft und Technik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Wolf 359
registrierter User



Anmeldungsdatum: 01.12.2005
Beiträge: 9

Beitrag(#380670) Verfasst am: 01.12.2005, 22:17    Titel: Minesweeper Antworten mit Zitat

Hallo!
Ich lese schon einige Zeit bei euch mit und habe mich jetzt einmal dazu entschlossen etwas aktiver teilzunehmen. Aber kommen wir gleich zum Thema...

In letzter Zeit verbrachte ich wiedermal einige Zeit damit Minesweeper zu spielen und da kam mir die Idee, dass man diesen Vorgang (also das Spielen) sicher auch mittels eines Programms automatisieren könnte. Schließlich folgt man beim Spielen einfachen logischen Regeln, und wenn man dadurch nicht weiter kommt kann man noch die Wahrscheinlichkeiten für die zur Wahl stehenden Felder berechnen. Bei der Profi-Spielstufe läuft es in den meisten Fällen darauf hinaus, dass man mit reiner Logik nicht weiter kommt, und so muss man meistens raten.

Jedenfalls könnte man mit einem solchen Programm experimentell ermitteln wie groß die Wahrscheinlichkeit ist eine bestimmte Spielfeld-Konfiguration erfolgreich lösen zu können. (Vorausgesetzt ist ein streng logisches Vorgehen beim Spiel)

Desweiteren habe ich auch noch darüber nachgedacht, ob man diese Wahrscheinlichkeit auch ohne ein solches Computerprogramm ermitteln kann. Kann man das Spiel in ein mathematisches Modell umsetzen und somit ganz leicht diese Wahrscheinlichkeiten ermitteln? - Ich denke schon. Das wäre doch mal eine interessante Aufgabe für einen Mathe Studenten oder nicht?
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
step
registriert



Anmeldungsdatum: 17.07.2003
Beiträge: 22782
Wohnort: Germering

Beitrag(#380680) Verfasst am: 01.12.2005, 22:36    Titel: Antworten mit Zitat

Das Problem der NP-Vollständigkeit von minesweeper kam mir irgendwie bekannt vor, aus meiner Uni-Zeit ...

Voila:

http://www.minesweeper.de/links.html
http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

Willst Du 3 Pfund Kaffee gewinnen?
http://www.rz.rwth-aachen.de/mata/index.php

Viel Spass!
_________________
Was ist der Sinn des Lebens? - Keiner, aber Leere ist Fülle für den, der sie sieht.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Critic
oberflächlich



Anmeldungsdatum: 22.07.2003
Beiträge: 16339
Wohnort: Arena of Air

Beitrag(#380748) Verfasst am: 02.12.2005, 02:20    Titel: Re: Minesweeper Antworten mit Zitat

Wolf 359 hat folgendes geschrieben:
Jedenfalls könnte man mit einem solchen Programm experimentell ermitteln wie groß die Wahrscheinlichkeit ist eine bestimmte Spielfeld-Konfiguration erfolgreich lösen zu können. (Vorausgesetzt ist ein streng logisches Vorgehen beim Spiel)

Desweiteren habe ich auch noch darüber nachgedacht, ob man diese Wahrscheinlichkeit auch ohne ein solches Computerprogramm ermitteln kann. Kann man das Spiel in ein mathematisches Modell umsetzen und somit ganz leicht diese Wahrscheinlichkeiten ermitteln? - Ich denke schon. Das wäre doch mal eine interessante Aufgabe für einen Mathe Studenten oder nicht?


Jetzt nur einmal so ein paar Minuten lang gegoogelt und quergelesen und dann ins Blaue geschossen:

Da hast Du gerade ein offenes Problem gefunden: In [1] heißt es dazu, daß gerade die interessanten Fragen im allgemeinen noch nicht geklärt sind, nämlich
- ob unter einer partiellen Aufdeckung von Feldern, d.h. auf Basis der Zahlen, die darauf stehen und die Anzahl der benachbarten Minen angeben, ein Feld sicher aufgedeckt werden kann, und
- und die groß die Wahrscheinlichkeit ist, daß sich auf einem Feld eine Mine befindet, unter der Annahme, daß die Minen im allgemeinen quer über das Brett gleichverteilt sind.

Die erste Frage will [1] mit einem Konsistenzprüfer testen, indem er sie auf eine seiner Meinung nach analoge Fragestellung reduziert, nämlich ob sich eine gegebene Menge von Zahlen auf aufgedeckten Feldern realisieren läßt, wenn eine bestimmte Verteilung von Minen gegeben ist. Es läuft also auf das Aufstellen einer Menge logischer Formeln heraus, die einerseits die allgemeinen Entscheidungsregeln und andererseits die aktuelle Aufstellung ausdrücken, die dann auf Widerspruchsfreiheit überprüft werden muß, was eben ein NP-vollständiges Problem ist [3], also exponentiell lange im Verhältnis zur Größe der Darstellung im Rechner dauern kann (aber nicht unbedingt 2^n, da man NP-vollständige Probleme aufeinander reduzieren, also vereinfacht als andere NP-vollständige Probleme ausdrücken kann, und es z.B. für Erfüllungsbarkeitsprobleme Algorithmen im Bereich um 1.2^n gibt, aber das ist Haarspalterei - dauert trotzdem viel zu lange).

Ein Beispiel für ein solches Regelwerk durfte die "Wumpus-Welt" [2] sein. Laut [3] muß man dieses Regelwerk nicht selbst aufstellen, sondern kann es von einem Lernsystem "erlernen" lassen, und dies soll sogar so gut sein, daß es den durchschnittlichen Spieler schlagen kann. Dazu muß man "lediglich" ein paar Grundfunktionen vorgeben.

Vielleicht ist, was Strategien angeht, auch [4] interessant, weil es dort um Strategien für "Minesweeper" geht. Im fünften Kapitel in [5] werden die Strategien und auch die Wahrscheinlichkeitsschätzungen erläutert:

Die geschätzte Wahrscheinlichkeit (die exakte Wahrscheinlichkeit kann eben wegen dieser NP-Eigenschaft in polynomieller Zeit nicht bestimmt werden, und ein Exp-Zeit-Algorithmus würde ein bißchen lange brauchen), daß in einem nicht aufgedeckten Feld x eine Mine iegt, ergibt sich demnach als p(x) = m / (m+f), wobei m die Anzahl der Beschriftungen von Nachbarfeldern ist, die nahelegen, daß das Feld x eine Mine enthält, und f die Anzahl der Beschriftungen, die implizieren, daß x frei ist.

Ich stelle mir jetzt vor, daß ein KI-Spieler, wenn er die Wahl zwischen mehreren Feldern hat, das Feld aufdecken würde, wo die Wahrscheinlichkeit am kleinsten ist, auf eine Mine zu stoßen, und das Feld markieren würde, wo die Wahrscheinlichkeit am größten ist.

Bei den Dateien unter [4] ist auch ein .jar-File dabei, das eine unter Java ausführbare Implementierung der in [5] dargestellten Strategien enthält.

[1] Demaine, Erik, "Playing Games with Algorithms: Algorithmic Combinatorial Game Theory", http://arxiv.org/pdf/cs.CC/0106019
[2] Kleta, Henry G., "Sprache verstehen", http://www.fh-wedel.de/~si/seminare/ss01/Ausarbeitung/c.sprache/5_2.html
[3] Pena Castillo, Lourdes und Wrobel, Stefan, "Learning Minesweeper with Multirelational Learning", http://kd.cs.uni-magdeburg.de/~pena/papers/IJCAI03.pdf
[4] Pedersen, Kasper, "The Complexity of Minesweeper and strategies for game playing", http://www.dcs.warwick.ac.uk/~kasper/Minesweeper ; http://www.dcs.warwick.ac.uk/~kasper/Minesweeper/Files
[5] http://www.dcs.warwick.ac.uk/~kasper/Minesweeper/Files/report.pdf
_________________
"Die Pentagon-Gang wird in der Liste der Terrorgruppen geführt"

Dann bin ich halt bekloppt. Mit den Augen rollen

"Wahrheit läßt sich nicht zeigen, nur erfinden." (Max Frisch)
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Wolf 359
registrierter User



Anmeldungsdatum: 01.12.2005
Beiträge: 9

Beitrag(#381208) Verfasst am: 03.12.2005, 12:51    Titel: Antworten mit Zitat

Interessant, da hab ich die Komplexität des Spiels anscheinend unterschätzt.
Außerdem habe ich auf einer der verlinkten Seiten noch Strategien gefunden, die ich noch nicht kannte. Man sollte eben nie vorschnell urteilen. Verlegen
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
JTB
Niemand



Anmeldungsdatum: 17.03.2004
Beiträge: 429

Beitrag(#382300) Verfasst am: 06.12.2005, 02:23    Titel: Antworten mit Zitat

Ich vermute, es wird in den vielen Links auch drinstehen - aber mein Mitbewohner hat mir erzählt (und zumindest auch empirisch gezeigt), dass bei MineSweeper das erste Feld nie eine Mine ist. Das muss man bei Berechnungen beachten.
_________________
Und genau dann, als ich alle überzeugt hatte, wurde mir klar, dass ich mir irrte.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen   Drucker freundliche Ansicht    Freigeisterhaus Foren-Übersicht -> Wissenschaft und Technik Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.



Impressum & Datenschutz


Powered by phpBB © 2001, 2005 phpBB Group