Nach der letzten Artikelserie zum Thema Computergrafik (keine Angst – die vorgebrachten Themenwünsche habe ich weiter auf dem Radar) geht es mit der neuen Artikelserie in einen gänzlich anderen Themenbereich. Wie bereits im letzten Artikel angedeutet, möchte ich mich etwas mit der Frage beschäftigen, wie die Informatik eingesetzt werden kann, um wissenschaftliche Theorien zu überprüfen. Das Mittel der Wahl ist hier die Simulation – und die soll uns auch in einigen (etwas loser verteilten) Artikeln beschäftigen. Wir wollen uns dabei nicht nur auf verbale Beschreibungen beschränken, sondern die ein oder andere Simulation auch tatsächlich einmal programmieren – und los geht es.
In der Presse ist des Öfteren zu lesen, dass diese oder jene Theorie mit Computersimulationen überprüft wurde – insbesondere im Bereich der Klimawissenschaften hört man oft davon. Das liegt nun aber natürlich nicht daran, dass hier Simulationen besonders oft zum Einsatz kommen, sondern eher daran, dass die Presse über diesen Bereich tendenziell öfter berichtet – aber das ist ein anderes Thema und soll hier nicht zur Debatte stehen. Fakt ist, dass in sehr vielen Bereichen der Wissenschaft Computersimulationen zum Einsatz kommen; das ist übrigens nicht nur auf die technischeren Bereiche beschränkt – prinzipiell lässt sich fast alles simulieren, was einigermaßen mathematisch beschrieben werden kann.
Damit wären wir dann auch schon beim Kernpunkt einer jeden Simulation: der mathematischen Beschreibung. Alle Simulationen folgen weitgehend dem gleichen Schema. Zuerst wird die zu untersuchende Problematik mit Hilfe eines formalen (in der Regel mathematischen) Modells beschrieben. Das Modell umfasst dabei zum einen eine Beschreibung des Zustands der Welt (mit Welt ist damit die Problemumgebung gemeint) und zum anderen Regeln, nach welchen sich dieser Zustand ändern kann. Die Begriffe “Zustand” und “Regel” sind hierbei sehr weit gefasst und können – je nach Problem – vollkommen unterschiedliche Dinge beschreiben, aber das werden wir im Verlauf der Artikelserie noch sehen.
Im Anschluss an die Definition des Modells wird der Ausgangszustand definiert; das ist der Zustand der Welt, mit welchem die Simulation beginnen soll. Der Ausgangszustand kann dabei entweder fest gewählt sein, wenn er nämlich eine bestimmte Hypothese darstellen soll, die mit Hilfe eines (genau definierten) Modells untersucht werden soll (wenn etwa untersucht werden soll, wie sich eine bestimmte Verteilung von Individuen einer Population langfristig auf die Entwicklung innerhalb der Population auswirkt); oder er wird (mehr oder weniger) zufällig gewürfelt, wenn der Fokus der Simulation eher auf dem Modell liegt und der Ausgangszustand nicht so wichtig ist (die Simulation von Teilchen in Physiksimulationen ist hierfür ein Beispiel).
Sind Modell und Ausgangszustand bestimmt, kann die eigentliche Simulation beginnen. Die besteht nun darin, dass die im Modell definierten Regeln ausgehend vom Ausgangszustand immer wieder auf den Zustand angewendet werden – es wird also eine (meist zeitliche) Entwicklung des Zustandes simuliert. Die Simulation wird nach einer festgelegten Anzahl von Regelanwendungen (man spricht mitunter auch von Runden) abgebrochen – oder wenn ein vorher definierter Zielzustand erreicht wurde.
Das ist bisher zwar alles wunderbar abstrakt und unkompliziert, aber die eigentliche Frage bleibt noch offen: wie wird eine derartige Simulation tatsächlich umgesetzt? Das könnte nun auch wieder an konkreten Beispielen rein verbal beschrieben werden, aber das wäre langweilig. Wir wollen daher an dieser Stelle ganz konkret werden und eine Simulation auch selber einmal programmieren. Für dieses erste Beispiel werde ich die Programmiersprache JavaScript wählen, da sie sich einfach im Browser ausführen lässt und die Beschreibungen damit sehr einfach nachvollzogen werden können. Wer mit dem Programmieren allgemein noch nicht vertraut ist, dem empfehle ich die entsprechende Artikelserie (Punkt: Programmierung); ein kurzer Ausflug in die Artikelserien zum Thema Web-Programmierung (Punkt: Web) kann dabei auch nicht schaden. 1
1 Wer den hier aufgeführten Code ausprobieren möchte, der erstellt einfach eine neue Datei auf seinem Computer, welche die Dateiendung “.html” trägt (also z.B. “test.html”). Diese Datei muss dann in einem Texteditor (Microsoft Word ist kein Texteditor) geöffnet werden; die hier beschriebenen Inhalte werden dann einfach in die Datei kopiert (Speichern nicht vergessen) und diese dann per Doppelklick im Standardbrowser geöffnet.
Zu Anfang jeder Simulation steht natürlich die Problembeschreibung. Für das Beispiel habe ich das Ziegenproblem ausgewählt, da es zum einen relativ leicht verständlich und zum anderen auch sehr leicht zu simulieren ist. Eigentlich wäre es zwar kein üblicher Kandidat für eine Simulation, aber die Prinzipien lassen sich daran sehr gut veranschaulichen.
Der Kern des Ziegenproblems ist der folgende: in einer Spielshow hat ein Kandidat die Wahl zwischen drei verschiedenen Toren. Hinter einem Tor befindet sich der eigentliche Preis, hinter den anderen beiden Toren jeweils eine Ziege (daher der Name des Problems) als Nicht-Preis. Der Kandidat wählt eines der Tore, woraufhin der Moderator des Spiels eines der anderen Tore öffnet, hinter dem sich eine Ziege befindet. Anschließend wird der Kandidat vor die Wahl gestellt: möchte er bei seinem gewählten Tor bleiben oder zum noch verschlossenen Tor wechseln. Die Frage ist: was ist die beste Strategie, um die Gewinnchancen zu maximieren? Sollte das Tor gewechselt werden oder eher nicht? (Das eigentliche Problem ist etwas komplexer als hier beschrieben, soll aber für die Simulation nicht weiter von Interesse sein; bei Interesse kann im entsprechenden Wikipedia-Artikel nachgelesen werden, und falls nach der Lektüre die Frage aufkommt: wir betrachten allein den Fall des ausgeglichenen Moderators).
Bildlich dargestellt also:
(Quelle: Wikipedia)
Die intuitive Antwort bei dieser Frage ist meist: es ist egal, ob man wechselt oder nicht. Zum Zeitpunkt der Frage sind noch 2 Tore geschlossen – hinter einem davon befindet sich eine Ziege, hinter dem anderen der Preis. Egal, welches Tor man wählt, man hat eine Chance von 50%, den Preis zu gewinnen. Richtig? Falsch. Es kann mathematisch gezeigt werden, dass es günstiger ist, das gewählte Tor in jedem Fall zu wechseln, da die Gewinnchancen damit auf 2/3, also etwa 66% steigen. Wer am mathematischen Beweis dafür interessiert ist, möge in der Wikipedia lesen – wir wollen dieses Problem hier aber per Simulation lösen.
Das Modell der Simulation ist denkbar einfach: der Zustand der Welt besteht aus den Informationen darüber, hinter welchem Tor sich der Preis befindet, welches Tor durch den Kandidaten initial gewählt wurde und theoretisch auch noch, welches Tor durch den Moderator geöffnet wurde (diese Information können wir sogar verwerfen – dazu gleich mehr). Die Regeln der Simulation sind ebenso einfach: haben wir durch unsere Wahl (Tor wechseln oder nicht wechseln) das Tor mit dem Preis erwischt, erhalten wir einen (imaginären) Punkt. Führen wir diesen Versuch n mal aus und zählen dabei, wie oft der Wechsel des Tores (bzw. der Nicht-Wechsel) zum Erfolg geführt hat, erhalten wir damit eine Einschätzung der Gewinnchancen. Je öfter wir den Versuch wiederholen, desto genauer wird natürlich die Abschätzung. Mit diesen sehr einfachen Grundlagen können wir das Problem auch schon simulieren.
Da das Problem mit Hilfe von JavaScript und HTML simuliert werden soll, müssen vorher noch einige technische Details geklärt werden; so benötigen wir ein Eingabefeld für die Anzahl der Versuche und Ausgabefelder für die gemessenen Ergebnisse; zusätzlich noch einige Hilfsfunktionen. Der folgende Code baut diese Testumgebung auf; für die eigentliche Simulation ist er nicht erforderlich, soll hier aber der Vollständigkeit halber aufgeführt werden (wer sich nicht dafür interessiert, kann ihn also einfach überspringen):
<!–
function getRandom( min, max ) {
var r;
do {
r = Math.random();
} while( r == 1.0 );
return min + parseInt( r * ( max-min+1 ) );
}
function getTries() {
var tries = parseInt( document.form.tries.value, 10 );
if ( isNaN( tries ) ) {
alert(“Bitte eine Zahl eingeben.”);
document.form.tries.focus();
return 0;
}
return tries;
}
// Hier folgt gleich die eigentliche Funktion “run”.
//–>
</script>
<form name=”form” action=””>
<table border=”0″ cellpadding=”0″ cellspacing=”4″>
<tr>
<td align=”right”>Anzahl Versuche: </td>
<td><input name=”tries” type=”text” size=”12″
maxlength=”8″></td>
</tr>
<tr>
<td><input type=”button” value=”Simulieren”
onclick=”run()”></td>
</tr>
<tr>
<td align=”right”>Nicht wechseln:</td>
<td><input name=”stay” type=”text” size=”12″
maxlength=”12″ readonly></td>
</tr>
<tr>
<td align=”right”>Immer wechseln:</td>
<td><input name=”switch” type=”text” size=”12″
maxlength=”12″ readonly></td>
</tr>
</table>
</form>
Der Code tut nichts weiter als im unteren HTML-Teil ein Formular mit einem Eingabe-Feld, einem Button und 2 Ausgabefeldern zu definieren; mit dem Button wird die noch zu implementierende Funktion run verknüpft. Im oberen JavaScript-Teil werden zwei Funktionen getRandom und getTries definiert. Erstere liefert eine Zufallszahl im Bereich der angegebenen Werte, die zweite liest die eingegebene Anzahl von Versuchen aus dem Eingabefeld aus (und vermeldet eine Fehlermeldung, wenn dabei etwas schiefging).
Der eigentlich interessante Code erfolgt nun in der Methode run, die wir hier implementieren:
Als erstes wollen wir in einer Variable tries die Anzahl der durchzuführenden Versuche speichern:
Sicherheitshalber fahren wir mit der Simulation nur fort, wenn die Anzahl der Versuche größer als 0 ist (die Methode getTries liefert auch 0 zurück, wenn die Eingabe fehlerhaft ist):
Als nächstes wollen wir zwei Variablen anlegen, welche zählen, ob ein Wechsel des Tores bzw. der Nicht-Wechsel zum Erfolg geführt hat:
var sw = 0;
Und als nächstes folgt auch schon die eigentliche Simulation. So oft, wie angegeben, wollen wir das tun, was es zu tun gilt (die Variable i läuft dabei von 0 bis tries, bedingt also so viele Schleifendurchläufe, wie erwünscht):
Das besondere an dieser Simulation ist, dass sich der Zustand der Welt in jedem Durchlauf neu ergibt und nicht aus dem letzten Lauf übernommen wird. Der Zustand besteht aus der Position des Tores mit dem Preis und aus unserem gewählten Tor – wir benötigen dafür also 2 Variablen, die wir zufällig bestimmen. Die möglichen Werte 0, 1 und 2 stehen dabei für die drei zur Verfügung stehenden Tore:
var tryPos = getRandom( 0, 2 );
Als nächstes folgt die Auswahl der Strategie und damit entweder der Wechsel des Tores oder das Verbleiben beim bisherigen. Um Rechenzeit und Programmieraufwand zu sparen, erledigen wir beide Schritte mit einem mal und legen dabei die folgende Überlegung zugrunde:
Wir wissen, dass der Moderator immer ein Tor öffnet, hinter dem sich kein Preis befindet. Nach Bestimmung des Gewinntores und der eigenen initialen Wahl kann also das durch den Moderator geöffnete Tor vernachlässigt werden; welches genau das ist (0, 1 oder 2), spielt dabei auch keine Rolle, denn nach dem Öffnen sind lediglich 2 Tore übrig – das selbst gewählte und das andere, wobei sich hinter einem von beiden der Preis befindet. Die Entscheidung beschränkt sich hierdurch auf lediglich 2 Alternativen: soll gewechselt werden oder nicht.
Weiterhin wissen wir: wechseln wir das gewählte Tor nicht und hatten von Anfang an das richtige Tor gewählt, so ist das als Erfolg zu verbuchen (da wir ja den Preis bekommen). Wechseln wir dagegen, obwohl wir initial das Tor mit dem Preis gewählt hatten, so haben wir einen Misserfolg. Umgekehrt gilt: wechseln wir nicht, obwohl wir nicht das Tor mit dem Preis gewählt haben, ist dies ein Misserfolg; ein Wechsel beim initial falschen Tor führt dagegen zu einem Erfolg. Zusammengefasst: beim Nichtwechseln haben wir Erfolg, wenn wir initial das richtige Tor gewählt hatten, beim Wechsel haben wir Erfolg, wenn das initial gewählte Tor nicht das richtige wahr. Entsprechend können wir dann auch die Erfolge zählen: ein Erfolg fürs Nichtwechseln, wenn gewähltes Tor und Gewinntor übereinstimmen, ein Erfolg fürs Wechseln, wenn dies gerade nicht der Fall ist. Als Code lässt sich das folgendermaßen ausdrücken:
++stay;
if ( tryPos != winPos )
++sw;
}
Fehlt nur noch, die erhaltenen Ergebnisse auszugeben:
document.form.switch.value = ( sw/tries*100 ).toFixed( 5 ) + “%”;
}
}
Hier noch einmal die Funktion im Ganzen:
var tries = getTries();
if ( tries != 0 ) {
var stay = 0;
var sw = 0;
for ( var i = 0; i < tries; ++i ) { var winPos = getRandom( 0, 2 ); var tryPos = getRandom( 0, 2 ); if ( tryPos == winPos ) ++stay; if ( tryPos != winPos ) ++sw; } document.form.stay.value = ( stay/tries*100 ).toFixed( 5 ) + "%"; document.form.switch.value = ( sw/tries*100 ).toFixed( 5 ) + "%"; } }
Damit haben wir sämtliche Funktionalität programmiert, um unsere Simulation durchzuführen. Fügt man die hier gezeigten Codeausschnitte zusammen und fügt sie in ein HTML-Dokument ein, so ergibt sich das folgende Formular, welches auch gleich mit einer Zahl gefüllt (bitte langsam vorantasten – zu große Zahlen könnten den Rechner zu stark belasten) und ausprobiert werden kann (wichtig: JavaScript muss hierzu im Browser aktiv sein):
Wenn eine genügend große Zahl eingegeben wird, bestätigt sich hiermit auch die eingangs getroffene Aussage, dass uns das Wechseln des Tores eine Gewinnchance von ungefähr 66% beschert.2
Wir haben hiermit also ein (zugegebenermaßen relativ unspannendes) Problem durch Simulation gelöst. Im nächsten Artikel der Reihe wollen wir ein etwas komplexeres Problem simulieren – Vorschläge hierfür können gern eingereicht werden (ansonsten habe ich schon die ein oder andere Idee).
2 Aufmerksame Leser werden natürlich völlig zu recht bemerken, dass sich das Ergebnis allein schon aus der Zählweise ergeben muss. Dies ist hier auch lediglich die abgekürzte Version der Simulation; eigentlich müsste man sie komplett ausführen, mit der Simulation des Öffnen eines Tores, einem anschließenden zufälligen Nicht-/Wechsel und der Überprüfung auf einen Gewinn – das würde aber den Rahmen eines Artikels sprengen und dabei zum gleichen Ergebnis führen (was ich auch verifiziert habe).
Kommentare (22)