Minesweeper

[Chemiker]

Weniger eine Programmierfrage, als eine Detail-Frage zu einem Programm, letztlich dann aber doch wieder eine Frage nach Programmiermöglichkeiten...

Alle verwirrt? Gut.

Die Verteilung der Minen im Spiel Minesweeper, wie werden da die Zufallszahlen erzeugt, bzw. sind das überhaupt Zufallszahlen?

Hintergrund: Wenn das echte Zufallszahlen, eine wirklich zufällige Verteilung ist (so gut man das hinbekommen kann) sind, dann habe ich einen guten Grund ein paar hundert Male das Spiel zu spielen und das Arbeit zu nennen...;)

[][immy]

Weniger eine Programmierfrage, als eine Detail-Frage zu einem Programm, letztlich dann aber doch wieder eine Frage nach Programmiermöglichkeiten...

Alle verwirrt? Gut.

Die Verteilung der Minen im Spiel Minesweeper, wie werden da die Zufallszahlen erzeugt, bzw. sind das überhaupt Zufallszahlen?

Hintergrund: Wenn das echte Zufallszahlen, eine wirklich zufällige Verteilung ist (so gut man das hinbekommen kann) sind, dann habe ich einen guten Grund ein paar hundert Male das Spiel zu spielen und das Arbeit zu nennen...;)

ja, die sind zufällig angeordnet

du musst ja nur die position der minen zufällig bestimmen, der rest is ja pure rechenarbeit.
ist die Frage damit geklärt, oder soll da einie diskussion werden, wie zufällig man zufallszahlen nun am pc wirklich erzeugen kann?

[Spasstiger]

Gespeichert sind die möglichen Positionen bestimmt nicht. Und der Pseudo-Zufallszahlengenerator wird sicherlich auch keiner sein, der wissenschaftlichen Ansprüchen genügt. Echte Zufallszahlen gewinnt man eh nur durch Auslesen der Spannung eines Rauschgenerators.

[Chemiker]

Naja, für Monte Carlo Simulationen nutzt man ja auch Pseudozufallsgeneratoren. Allenfalls werden für den Startwert echte Zufallszahlen genutzt. Diese könnte man auch einer Tabelle von Lottozahlen entnehmen (chronologisch entnehmen).

Letztlich hätte ich gern ein Programm welches mir wie Minesweeper eine zufällige Anordnung von zwei verschiedenen Flächen (A und B) erzeugt und mir dann auszählt, wie häufig der Punkt zwischen den vier Flächen von 0, 1, 2, 3 oder 4 Flächen der Sorte A umgeben ist.
Über das Auszählen in n Fällen soll dann die wahrscheinlichste Verteilung gefunden werden, da mir leider bisher kein anderer Weg eingefallen ist, die zu bestimmen.

[Chemiker]

Ein zufälliges Array erstellen kann man mit Excel. Binär mit ROUND(RAND();0) und die Arbeitsfläche ausfüllen.

Hat jemand eine Idee wie man da nun eine Gewichtung der Anzahl der Nullen und Einsen einbringen kann, man also eine zufällige Verteilung von 79% Nullen und 21% Einsen haben möchte? Das Programm müsste zählen wie oft Eins und Null vorhanden. Dann braucht es einen Randon-Funktion was die Zellauswahl betrifft und da müssen dann einige Einsen zu Nullen werden.
Ist jemandem bekannt, ob das mit Excel machbar ist?

[Monger]

Mit einem Excel Macro, bestimmt.

Im Grunde ist das setzen von einem Minesweeper Feld ja ein ziehen ohne zurücklegen. Also: du hast eine Menge von unbesetzten Feldern. Aus diesen ziehst du jetzt zufällig ein Feld, was eine Mine haben soll, und markierst es. Dann suchst du dir aus den verbleibenden freien Feldern wieder eins zufällig aus... und wiederholst das so lange, bis alle Minen verbraucht sind.

Alternativ: du markierst die ersten X Felder, und mischst dann die Felder (z.B. mit dem Fisher-Yates Algorithmus). So wird es wahrscheinlich auch in Minesweeper gemacht, weil ob du Karten oder Spielfelder mischst, ist ja im Endeffekt egal.

[kloffy]

Hat jemand eine Idee wie man da nun eine Gewichtung der Anzahl der Nullen und Einsen einbringen kann, man also eine zufällige Verteilung von 79% Nullen und 21% Einsen haben möchte?
Es scheint du suchst nach Fisher–Yates shuffle (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)...

Edit: Monger war schneller. :)

[Chemiker]

Hm, habe es erst einmal mit =IF(RAND()<=0,79;0;1) gelöst. Scheint hinzuhauen.

Der Shuffle ist auch sehr interessant. Danke für den Hinweis!

[pest]

Hm, habe es erst einmal mit =IF(RAND()<=0,79;0;1)


das ist auch richtig so, wenn RAND() gleichverteilt zwischen [0,1) ist

bei den anderen Voschlägen wundert mich aber mal wieder nicht mehr das
ich nen 4Ghz Quad für mein EMail Programm benötige

[Chemiker]

das ist auch richtig so, wenn RAND() gleichverteilt zwischen [0,1) ist Was es sein sollte. Die Ergebnisse sehen auch ganz vernünftig aus. Schön. :)
Aber irgendwie auch verdächtig einfach...

[Monger]

bei den anderen Voschlägen wundert mich aber mal wieder nicht mehr das
ich nen 4Ghz Quad für mein EMail Programm benötige
Ich glaube, bei Minesweeper ist es vertretbar, nicht auf Performance zu optimieren! ;)
Erst recht wenn das ganze in einem Excel Makro berechnet wird...

[pest]

Ich glaube, bei Minesweeper ist es vertretbar, nicht auf Performance zu optimieren! ;)
Erst recht wenn das ganze in einem Excel Makro berechnet wird...

das hat ja nix mit performance-optimierung zu tun, sondern damit
ein triviales problem mit der holzhammermethode lösen zu wollen.

[kloffy]

das hat ja nix mit performance-optimierung zu tun, sondern damit
ein triviales problem mit der holzhammermethode lösen zu wollen.
Dann erklär mal wo da der große Performanceunterschied ist, läuft am Ende beides auf O(n) hinaus... :rolleyes:

[pest]

kannst du lesen? dankeschön

[kloffy]

kannst du lesen? dankeschön
Wie hättest du die Frage denn gerne Formuliert damit du mir erklärst was am Shuffle-Ansatz so schlecht ist? Mich stört vor allem, dass du eine Herangehensweise gegenüber einer anderen als minderwertig erklärst, obwohl beide grundverschieden sind (beim Shuffle kann man die Anzahl der Minen exakt angeben). Welche Methode man wählt hängt ja wohl von den genauen Anforderungen ab...

[Monger]

das hat ja nix mit performance-optimierung zu tun, sondern damit
ein triviales problem mit der holzhammermethode lösen zu wollen.
Ich versteh immer noch nicht was du meinst.

Fisher-Yates ist jetzt auch nicht viel komplizierter als eine Wahrscheinlichkeitsrechnung. Vorallem hat man beim Mischen nie die Gefahr, dass einem eine Karte (Spielfeld) anhand von Rundungsfehlern verloren geht.

[kloffy]

Ich versteh immer noch nicht was du meinst.

Fisher-Yates ist jetzt auch nicht viel komplizierter als eine Wahrscheinlichkeitsrechnung. Vorallem hat man beim Mischen nie die Gefahr, dass einem eine Karte (Spielfeld) anhand von Rundungsfehlern verloren geht.
Ich denke pest hat einfach das Konzept des Shuffle nicht verstanden. Für mich ist es ohne Frage der elegantere Ansatz.

#include <iostream>
#include <ctime>

template<unsigned int N>
void shuffle(int (&a)[N], unsigned int ones)
{
a[0] = int(0<ones);

unsigned int j;
for(unsigned int i=1;i<N;i++)
{
j = rand()%(i+1);
a[i] = a[j];
a[j] = int(i<ones);
}
}

int main(int argc, char *argv[])
{
srand((unsigned)time(0));

int a[10];

shuffle(a,5);

return 0;
}