Examensarbeit, 2015
75 Seiten, Note: 1,0
1 Einleitung
2 Mastermind - Das Spiel
2.1 Spielausstattung
2.2 Ziel des Spiels
2.3 Vorbereitung des Spiels
2.4 Spielablauf
2.5 Ende des Spiels
2.6 Varianten
3 Schreibweise
3.1 Hinweis zur Rückmeldung
4 Mathematischer Hintergrund
4.1 Enumeration
4.2 Permutationen
4.3 Geordnete Auswahlen
4.3.1 Auswahlen mit Wiederholung
4.3.2 Auswahlen ohne Wiederholung
5 Donald E. Knuth - The Computer as a Mastermind
5.1 Die Codes des Algorithmus
5.1.1 AABB als Eröffnung
5.1.2 Versuchscodes nach der Eröffnung
5.2 Die verbleibenden Codes bestimmen
6 Die Mastermindschablone
6.1 Mastermindschablone 1/2 in Reinform
6.2 Mastermindschablone 2/2 in Reinform
6.3 Mastermindschablone 1/2 mit Drehscheiben
6.4 Mastermindschablone 2/2 mit Drehscheiben
7 Die Lösungstabelle
8 Entwurf für den Schülerzirkel
9 Mastermind - Das Spiel
9.1 Mastermind ohne Spielmaterial
9.2 Varianten zum klassischen Mastermind
10 Mathematischer Hintergrund
10.1 Enumeration
10.2 Permutationen
10.3 Geordnete Auswahlen
10.3.1 Auswahlen mit Wiederholung
10.3.2 Auswahlen ohne Wiederholung
11 Die Mastermindschablone
11.1 Die Schablone zum selber Basteln
11.1.1 Materialien für den Zusammenbau
11.1.2 Die Schablone zusammenbauen
12 Mastermind-Rätsel
12.1 Aufgabe 1 - Den Lösungscode entschlüsseln
12.2 Aufgabe 2 - 50/50 - noch zwei Möglichkeiten
12.3 Aufgabe 3 - Zähle alle verbleibenden Codes auf
12.4 Aufgabe 4 - Den Algorithmus verstehen
12.5 Aufgabe 5 - Die Lösungsschablone an wenden
12.6 Aufgabe 6 - Bestimme alle möglichen Lösungen
12.7 Aufgabe 7 - Richtige und falsche Lösungen
13 Lösungen Mastermindrätsel
13.1 Lösungen - Aufgabe
13.2 Lösungen - Aufgabe
13.3 Lösungen - Aufgabe
13.4 Lösungen - Aufgabe
13.5 Lösungen - Aufgabe
13.6 Lösungen - Aufgabe
13.7 Lösungen - Aufgabe
14 Fazit
15 Literaturverzeichnis
16 Internetquellen
17 Anhang
1 Mastermindspielfeld
2 Mastermindschablone 1/2 in Reinform
3 Mastermindschablone 2/2 in Reinform
4 Mastermindschablone 1/2 mit Drehscheiben
5 Mastermindschablone 2/2 mit Drehscheiben
6 Aufbau einer Zelle in der Lösungstabelle
7 Ansicht von oben auf die Mastermindschablone
8 Farben und Anordnung der Rückmeldung
9 Musterbeutelklammer
10 Zusammenbau der einzelnen Scheiben
11 Ansicht von oben auf die fertige Schablone Tab ellenver zeichnis
1 Mastermind mit dreistelligem Code und zwei Farben
2 Möglichkeiten nach dem ersten Zug für jede Eröffnung
3 Beispiel für alternative Eröffnungen
4 Beispiel für alternative Codes nach der Eröffnung
5 Beispiel für die Benutzung der Lösungstabelle
Mastermind ist ein beliebtes Denkspiel, das 1970 vom israelischen Postmitarbeiter Mordccai Mcirowitz erfunden wurde. Auch heute erfreut es sich noch großer Beliebtheit und wurde bisher über 55 Millionen mal als Brettspielvariante verkauft und genießt mittlerweile auch in digitaler Form die Sympathie von vielen Knoblern.1 Die Raffinesse dieses Spiels beschäftigt jedoch auch viele Wissenschaftler. So haben es sich verschiedene Interessierte aus unterschiedlichen Sparten der Wissenschaft zur Aufgabe gemacht eine möglichst optimale Strategie zu entwickeln. So auch der amerikanische Informatiker Donald E. Knuth der in seinem Artikel the Computer as a Mastermind einen Algorithmus beschreibt, der den geheimen Mastermind-Code innerhalb von fünf Zügen entschlüsseln kann. Eine rationale Spiel- und Denkweise auf Basis mathematischer Gesetzmäßigkeiten findet auch im Mathematikunterricht Beachtung. Wegen der spielerischen Grundlage ist das Spiel Mastermind eine geeignete Möglichkeit Schülerinnen und Schülern die Theorie der Kombinatorik anschaulich darzubieten und praktisch erfahren zu lassen. Voraussetzung einer adäquaten Anwendung dieser Kenntnisse ist gewiss die Fähigkeit des logischen Schlussfolgerns, die nicht nur im Unterricht einen wichtigen Faktor darstellt.
Den Sockel der Arbeit stellt eine Spielanleitung dar, auf dessen Grundlage alle weiteren Inhalte aufbauen. Dabei soll dem Leser die Spielweise von Mastermind näher gebracht und das Regelwerk verständlich aufgeführt werden. Nachdem die Darstellungsweise und Notation definiert worden ist, gehe ich in meiner Arbeit näher auf den mathematischen Hintergrund des Spiels ein. Dieser Punkt gibt einen ersten Hinweis darauf, dass das Spiel auf rein mathematischer Ebene kalkulierbar ist. Neben diesem kombinatorischen Hintergrundwissen wird vor allem auf den Artikel the Computer as a Mastermind von Donald E. Knuth eingegangen. Insbesondere der darin beschriebene Algorithmus stellt den Mittelpunkt der Arbeit dar. Dem Anspruch, diesen Algorithmus verständlich und anschaulich darzustellen, versucht die Konzeption der Mastermindschablone sowie der Lösungstabelle gerecht zu werden. Der Abschluss der Arbeit ist ein Entwurf für einen Schülerzirkel. Darin sind verschiedenste Aufgabentypen zum Thema Mastermind enthalten. Durch schlussfolgernde und argumentative Aufgaben soll das Verständnis für das Spiel verbessert und eine rationale Spielweise mit einem Gespür für Knuths Vorgehensweise entwickelt werden.
Das Kernstück der Arbeit ist zweifelsohne diesen Algorithmus schülerfreundlich zu beleuchten. Die Mastermindschablone soll ein Medium sein, dass Spielsituationen bestehend aus Rückmeldung und neuem Farbcode anschaulich darstellt und auch als Teil des Spielmaterials verwendet werden kann.
Um dieses Ziel zu erreichen war zunächst eine umfassende Kenntnis von Spielregeln und -Situationen von Nöten. Da ich in diesem Spiel ein absoluter Novize war, ging es für mich zunächst darum, das Spiel kennenzulernen und ein Gespür für die Raffinesse von Mastermind zu bekommen. Erst dann machte es für mich Sinn, mich mit dem Artikel, genauer dem Algorithmus auseinanderzusetzen. Zunächst bestand meine Aufgabe darin, diesen selbst zu verstehen, um dann mit einer Überlegung für eine anschaulichere Gestaltung zu beginnen. Zusätzlich zum Artikel verschaffte ich mir durch unterschiedliche Bücher Zugang zum mathematischen Hintergrundwissen bezüglich des Spiels. Erst durch das Zusammenspiel von unzähligem Entschlüsseln geheimer Codes und Lesen verschiedenster Literatur bekam ich nach und nach ein tieferes Verständnis für das Spiel und Knuths Algorithmus. Dieses Wissen hat im wesentlichen zur Gestaltung der Mastermindschablone und dem Schülerzirkel beigetragen.
Mastermind ist ein Denkspiel das 1970 von Mordecai Mcirowitz, einem israelischen Postangestellten erfunden wurde. Auf der Basis kombinatorischer Gesetzmäßigkeiten versucht ein Codebreaker den geheimen Code des Codemakers zu entschlüsseln.
Die Mastermind-Box enthält ein Spielfeld, Farbstifte in sechs verschiedenen Farben sowie schwarze und weiße Rückmeldungsstifte. Das Spielfeld besteht aus mehreren Codereihen in denen der Codebreaker seine Versuchscodes stecken kann. Neben jeder Reihe befindet sich ein Feld für die Signalstifte. Für den geheimen Code steht dem Codierer eine verdeckte Codeleiste zur Verfügung.2 Heutzutage wird das Spiel von verschiedenen Herstellern produziert. Je nach Version und Herstellungsjahr können die Farben und das Design der Stifte bzw. des Spielfelds variieren.
Anmerkung der Redaktion: Abbildung wurde aus urheberrechtlichen Gründen entfernt.
Abbildung 1: Mastcrmind-Spiclfcld3
Der Codemaker wählt aus sechs verschiedenen Farben einen beliebigen vierstelligen Code aus.
Der Codebreaker versucht den geheimen Code des Gegners in möglichst wenigen Zügen zu lösen.4
Vor Beginn des Spiels einigen sich die Spieler auf eine gerade Anzahl an Durchgängen, die sie machen wollen. Nach jedem wechseln Codebreaker und Codemaker ihre Aufgaben.
Nach dem Offnen der Mastcrmind-Box sollten erst die bunten Codestecker und die Rückmeldungsstifte getrennt in ein dafür vorgesehenes Fach gelegt werden.
Nachdem sich die Kontrahenten darauf geeinigt haben, wer zuerst Codierer ist, wird das Spielfeld entsprechend positioniert.[0]
Den Start macht der Codemaker: Er setzt den geheimen vierstelligen Farbcode in die dafür vorgesehene Leiste ein, sodass sein Gegenüber diesen nicht sieht.
Nun sind die Spieler abwechselnd an der Reihe:
a) Der Codebreaker setzt seinen Versuchscode - er muss die Farbe und Position der vier geheimen Codestecker herausfinden. Dazu wählt er vier Farbstecker seiner Wahl aus und steckt sie in die Öffnungen an seinem Ende des Spielbrettes.
b) Der Codemaker gibt Rückmeldung - mit den Signalstiften in schwarz und weiß informiert er den Codebreaker über dessen Lösungsversuch. Diese steckt er neben dem jeweiligen Versuch in die dafür vorgesehenen Öffnungen. Die Reihenfolge spielt keine Rolle.
Ein schwarzer Stift bedeutet, dass sich ein Farbstift auf der richtigen Position befindet.
Ein weißer Stift bedeutet, dass eine Farbe richtig entschlüsselt, jedoch noch nicht auf der richtigen Position ist.
Bleibt folglich eine Öffnung für die Signalstifte frei, so hat der Codebreaker eine falsche Farbe ausgewählt. Ein Signalstift gibt keine Auskunft darüber, um welchen Farbstecker es sich handelt.
Durch die Rückmeldung kann der Codebreaker seine Schlüsse ziehen und im nächsten Zug einen neuen Versuch starten. So wird das Spiel Runde um Runde fortgesetzt, bis der Code entschlüsselt ist bzw. das Maximum an Versuchen erreicht ist. Der richtige Code ist ermittelt, wenn vier schwarze Signalstifte als Rückmeldung erfolgen.
Pro Versuch bekommt der Codemaker einen Punkt. Wurde der Code nicht innerhalb der dafür vorgesehenen Versuchsreihen gelöst, so erhält er noch einen Bonuspunkt. Für den nächsten Durchgang werden die Rollen getauscht.5 6
Das Spiel endet, wenn die vereinbarte Anzahl an Durchgängen absolviert ist. Wer die höhere Punktzahl erreicht hat, gewinnt das Duell. ‘
Neben den klassischen Spielregeln bieten sich für die Kontrahenten einige Möglichkeiten, den Schwierigkeitsgrad des Spiels zu verändern.
Die Spieler können vor dem Duell entscheiden, ob Farben mehrfach oder einzeln verwendet werden dürfen. Eine einfache Verwendung schränkt die Anzahl möglicher Codes ein.
Eine weiteres Mittel, die Schwierigkeit zu verändern ist das Hinzunehmen bzw. Weglassen von Farben. Eine siebte Farbe kann durch Freilassen einer Öffnung erzeugt werden. Die Anzahl der Farben kann bis auf zwei reduziert werden.
Außerdem kann man die Länge des Codes variieren. Je mehr Stellen der Codemaker für seinen Code zur Verfügung hat, desto schwieriger wird es, den Code zu entschlüsseln.
Für die Rückmeldung und der Benutzung der Signalstifte ergeben sich daraus keine Veränderungen.
Die Änderungen bezüglich der möglichen Codes, sind aus den Formeln des Kapitels Mathematischer Hintergrund zu entnehmen.
Beispiel:
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 1: Mastermind mit dreistelligem Code und zwei Farben
In der Arbeit werden eine Reihe von konkreten Situationen in einem Mastermind Spiel auftreten. Um das Lesen angenehmer zu machen, benötigen wir hierzu eine Reihe von Kurzschreibweisen:
- Die sechs Farben im Spiel werden durch die Buchstaben {A,B,C,D,E,F} repräsentiert. In wenigen Ausnahmen werden die Zahlen {1,2,3,4,5,6} verwendet.
- Die Darstellung eines vierstelligen Farbcodes c = c1c2c3c4 mit c1,c2,c3,c4 G {A,B,C,D,E,F} erfolgt durch Buchstaben. Jeder Buchstabe steht für eine andere Farbe. Ein Code mit vier verschiedenen Farben lautet beispielsweise ABDF.
- Die Darstellung einer Rückmeldung r = S | aus schwarzen und weißen Stiften: S = Anzahl schwarzer Signalstifte.
ES9 = Anzahl weißer Signalstifte.
- r ist die Menge aller Rückmeldungen mit 0 < (S| + ffl) < 4, mit Ausnahme 3 , die im Spiel nicht vor kommen kann.
- Das Wort Rückmeldung tritt öfter unter der Abkürzung RM auf.
Insgesamt gibt es 14 Möglichkeiten eine Rückmeldung zu erhalten:
Abbildung in dieser Leseprobe nicht enthalten
Die Rückmeldung mit drei schwarzen und einem weißen Signalstift ist beim Mastermind nicht möglich. Befinden sich in einem Code drei richtige Farben auf der korrekten Stelle, gibt es nur noch zwei Optionen. Die vierte Stelle im Code ist entweder mit der richtigen Farbe und zwangsläufig auch auf der richtigen Position besetzt, oder die vierte Position ist falsch besetzt. Die Option richtige Farbe aber falsche Position ist nicht möglich, da jede alternative Position im Code wegen der drei schwarzen Signalstifte bereits korrekt besetzt ist.
Um das Spiel in möglichst wenigen Zügen lösen zu können, bedarf es mehr als nur Glück und Zufall. Auf Basis kombinatorischer Grundlagen und logischer Schlussfolgerungen aus den Rückmeldungen kann der Codebreaker die Menge seiner Versuche durch eine raffinierte Gestaltung der Versuchscodes möglichst gering halten.
Durch die mathematische Disziplin der Kombinatorik lässt sich vor jedem Zug die genaue Anzahl der noch verbleibenden Möglichkeiten ermitteln. Abhängig von der Rückmeldung fällt nach jedem Versuchscode eine bestimmte Anzahl an Möglichkeiten weg, wie der Lösungscode zusammengestellt sein könnte. Infolge von logischen Schlussfolgerungen aus der Rückmeldung lassen sich alle diese realisierbaren Codes ermitteln.
Unter Einbezug dieses Wissens kann der Codebreaker seinen neuen Versuchscode geschickt gestalten, sodass in Abhängigkeit der Rückmeldung möglichst viele Codes ausgeschlossen und Informationen gewonnen werden können.
Im Folgenden werden wichtige kombinatorische Prinzipien erläutert, die zum Verständnis des Spiels und des Algorithmus von Donald E. Knuth beitragen.
Ein wichtiger Gegenstand der Kombinatorik ist das Zählen der Elemente einer gegebenen endlichen Menge. Eine solche endliche Menge stellt auch die Anzahl möglicher Codes in einem Mastermind-spiel dar.
Grundsätzlich ist das explizite Auffisten, auch Enumeration genannt, eine Methode, die solche Probleme lösen kann. Ein Vorteil der Enumeration ist neben der Ermittlung der Anzahl möglicher Codes auch die genaue Bestimmung dieser.7
Vor allem im Endstadium eines Durchgangs, wenn es darum geht, den richtigen Code aus den wenigen verbleibenden Möglichkeiten durch geschickte Gestaltung des Codes zu entschlüsseln, ist das explizite Abzählen unerlässlich. Zu Beginn, wenn die Anzahl der möglichen Codes noch relativ hoch ist, stößt diese Methode jedoch an ihre Grenzen. In der Praxis würde es schlicht zu lange dauern, bis alle einzelnen Möglichkeiten aufgelistet werden.
Wie viele Möglichkeiten gibt es, sechs Farben auf vier verschiedene Positionen anzuordnen? Diese Problematik ist ein Beispiel für die Thematik der Anordnung oder der Reihenfolge von Objekten. Ganz allgemein könnte man die oben gestellte Frage auch so formulieren: Auf wie viel verschiedene Arten kann man n verschiedene Objekte auf k Positionen anordnen? Diese Anordnung von Objekten nennt man Permutation. Dabei ist es irrelevant welche Objekte (Farben, Stifte, Buchstaben, Zahlen, etc.) angeordnet werden. Deshalb wird im Folgenden mit den Permutationen der Mengen {1,2,3,4,5,6} und {A,B,C,D,E,F} gearbeitet.8
Ein vierstelliger Code beim Mastermind soll aus sechs Farben zusammengestellt werden. Der hat demnach folgende Struktur:
Abbildung in dieser Leseprobe nicht enthalten
Jede Stelle im Code kann unabhängig von den anderen besetzt werden. Folglich stehen für die erste Stelle sechs Farben zur Verfügung. Dasselbe gilt auch für die zweite, dritte und vierte Stelle im Code. Insgesamt ergeben sich
6[4] = 1296
Möglichkeiten den Code zu gestalten.9
Allgemein erhalten wir nk für die Anzahl der geordneten Aus wählen von k Elementen aus einer n-elementigen Menge mit Wiederholung. Eine Auswahl mit Wiederholung entspricht dabei einer Anordnung von Elementen, die dabei beliebig oft vorkommen dürfen. Berechnet man die Anzahl, so ist auch stets die Reihenfolge der Elemente relevant.10 Auch beim Mastermind-Code handelt es sich um eine geordnete Auswahl, denn auch hier spielt die Reihenfolge der Farben eine Rolle. Beispielsweise sind die Codes ABCD und DCBA zwei unterschiedliche Objekte. Das lässt sich alleine schon durch die Rückmeldung erklären. Stimmen die Farben des Versuchscodes mit denen des Lösungscodes überein, ist das Spiel noch nicht zwingend gelöst. Nur wenn die Reihenfolge korrekt, bzw. jede Farbe an der richtigen Stelle ist, wird der Code entschlüsselt.
Die Variation Code ohne Wiederholung der Farben ist eine beliebte Form bei Anfängern. Dabei sehen die Spielregeln vor, dass der Code keine Farbe öfter als einmal enthalten darf. Ganz allgemein enthält eine geordnete Auswahl von k aus n Ele- menten einer Menge M ohne Wiederholung jedes Element aus M höchstens einmal. An erster Stelle gibt es n Wahlmöglichkeiten, für die zweite n — 1 usw. Schließlich kommen für die k — te Stelle n — k + 1 Elemente in Frage. Die Anzahl der geordneten Auswahlen ohne Wiederholung ist somit
n(n — 1) • •• (n — k + 1).
Für Mastermind bedeutet das konkret, dass es im Falle Code ohne Wiederholung insgesamt
6 • 5 • 4 • 3 = 360
Möglichkeiten gibt, den Code zu gestalten.11
Donald E. Knuth hat im Journal Recreational Mathematics, Vol. 9(1), 1976-77 den Artikel The Computer as a Mastermind veröffentlicht.
Der amerikanische Professor für Informatik hat einen sicheren Weg gefunden, wie beim Mastermind innerhalb von fünf Zügen jeder geheime Code entschlüsselt werden kann. Sein Algorithmus ist dadurch gekennzeichnet, dass derjenige Versuchscode gewählt wird, der im maximal schlimmsten Fall (der Rückmeldung) die minimale Anzahl an verbleibenden Möglichkeiten garantiert. Mit dem sogenannten worst case ist diejenige Rückmeldung gemeint, die für einen bestimmten Versuchscode am wenigsten Codes ausschließen kann. Dafür werden alle möglichen Rückmeldungen betrachtet, die auf einen Versuchscode erfolgen könnten. Derjenige, der im worst case die kleinste Anzahl an verbleibenden Möglichkeiten garantiert, wird ausgewählt. Der Algorithmus zielt darauf ab, die Zahl maximal benötigter Züge auf ein Minimum zu reduzieren. Sogar wenn der Codierer nach jedem Rateversuch und vor seiner Rückmeldung den Code ändern würde, kann man mit dem Algorithmus von Knuth jeden Code innerhalb von fünf Zügen lösen. Die Grundlage für diesen Algorithmus ist die Eröffnung mit dem Code AABB.12
Interessant ist vor allem die Frage, warum genau der Code AABB als erster Code vorgeschlagen wird und wie alle weiteren Codes zustande kommen.
Bei der Eröffnung müssen alle 6[4] = 1296 möglichen Codes in Betracht gezogen werden.
Für die Gestaltung des ersten Codes kommen die folgenden fünf Codeklassen in Frage:
AAAA, AAAB, AABB, AABC, ABCD.
Alle anderen möglichen Codes lassen sich durch Permutation der Farben bzw. Positionen bilden. Codes, die durch solch eine Permutation ineinander überführt werden können, gehören der selben Codeklasse an.[14] Zum Beispiel sind die Codes AAAA und BBBB der selben Codeklasse zugeordnet.
Zu jeder werden dazu alle möglichen Rückmeldungen betrachtet. Knuth entscheidet sich immer für den Code, der im Sinne des worst case die niedrigste Anzahl an verbleibenden Möglichkeiten aufweist.[10]
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 2: Anzahl der Codes die nach dem ersten Zug übrig bleiben. [16]
Die jeweils größte Anzahl verbleibender Möglichkeiten ist in jeder Spalte bzw. bei13 14 jeder Codeklasse fettgedruckt. Da der worst case bei der Eröffnung AABB am geringsten ist, wählt Knuth diesen Code als ersten Zug.[1]'
Dabei wäre neben dem Muster AABB prinzipiell auch jeder andere Code dieser Codeklasse möglich (z.b. ABAB, FFCC, CDDC,...). Die Anzahl verbleibender Codes nach der jeweiligen Rückmeldung bliebe dabei gleich. Warum ist das so?
Wie oben bereits angesprochen, lassen sich die Codes, die einer Codeklasse angehören durch Permutation der Farben und Positionen ineinander überführen. Das selbe ist dementsprechend auch mit den verbleibenden Codes möglich. Auch diese lassen sich durch Umstellung der Position und Farbe aneinander angleichen. Die Anzahl der verbleibenden Codes bleibt jedoch die selbe.15 16
Beispiel:
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 3: Beispiel für alternative Eröffnungen, aus der selben Codeklasse wie AABB
Der Algorithmus würde also auch funktionieren, wenn man anstatt dem Code AABB einen anderen Code aus dieser Codeklasse nehmen würde. Will man die Codes aus dem Algorithmus von Knuth zur Hilfe nehmen, muss mit AABB begonnen werden. Ansonsten müsste man auch alle anderen Versuchscodes entsprechend anpassen.
Das weitere Vorgehen der nächsten Züge ist vom Prinzip dasselbe wie bei der Eröffnung, mit dem Unterschied, dass nun schon einige Codes durch den ersten Zug ausgeschlossen werden konnten. Für den zweiten Versuchscode im Algorithmus werden dabei nur noch diejenigen Codes in Betracht gezogen, die nach dem Code AABB und der Rückmeldung r noch möglich sind. Der Code, der im worst case die meisten Codes aus den noch vorhandenen ausschließen kann bzw. bei dem am wenigsten mögliche Codes verbleiben, wird gewählt. Nach diesem Prinzip werden auch alle anderen Codes für die nächsten Züge ausgewählt. Dabei werden für jeden Spielzug nur noch diejenigen Codes berücksichtigt, die noch möglich sind.17
Für die Versuchscodes nach der Eröffnung definieren sich die Codeklassen allerdings neu. Beim ersten Code war eine Codeklasse allein dadurch gekennzeichnet, wie viel verschiedene Objekte sich wie oft (AAAB = AABB) im Code befinden, so unterscheidet sich ein Code in den weiteren Zügen durch zusätzliche Kriterien. Dabei wird jede Stelle im Code nach folgenden Attributen besetzt:
- Neue Farbe (folglich neue Position)
- Bereits verwendete Farbe - neue Position
- Bereits verwendete Farbe - alte Position
Nach der Eröffnung AABB und der Rückmeldung 0 ] sieht der Algorithmus als nächsten Versuchscode CCDE vor. Es werden also nur neue Farben im Code verwendet. Dabei wäre der Code CECF prinzipiell auch mit dem Algorithmus von Knuth vereinbar. Auch bei diesem Code werden drei neue Farben verwendet, wobei eine davon doppelt vorkommt.
Die Anzahl verbleibender Codes würde unabhängig von der Rückmeldung die Selbe sein, denn sowohl die Versuchscodes als auch die verbleibenden Möglichkeiten würden sich wieder durch Permutation der Farben und Positionen ineinander überführen lassen.
Beispiel:
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 4: Beispiel für alternative Codes nach der Eröffnung
Die Situation vor dem ersten Zug ist einfach zu betrachten. Die Anzahl wurde zu diesem Zeitpunkt noch nicht durch den eigenen Versuchscode und der dazugehörigen Rückmeldung eingeschränkt. Eine Antwort dieser Frage gibt das Kapitel Permutationen und ist mit der Formel für die Anordnung von n Objekte auf p verschiedene Positionen zu beantworten. Die Ausgangslage vor dem ersten Zug des Spiels entspricht demnach aller 1296 Codes, die durch die Permutation der sechs Farben auf vier verschiedenen Positionen möglich sind.
6[4] = 1296
{AAAA,...,FFFF}
Nach dem ersten Zug kommen nur noch diejenigen Codes als mögliche Lösungscodes in Frage, die sich mit dem ersten Versuchscode und der Rückmeldung in Einklang bringen lassen. Mit jedem neuen Versuchscode werden die Möglichkeiten bezüglich der Gestaltung des richtigen Codes eingeschränkt. Die Anzahl verbleibender Codes berechnet sich aus der Schnittmenge aller Möglichkeiten, die nach jedem vorherigen Versuchscode und der dazugehörigen Rückmeldungen noch realisierbar sind.
Um die verbleibenden Codes zu bestimmen bedarf es exakter Schlussfolgerungen aus allen bisher gespielten Versuchscodes. Wichtige Informationen sind dabei einzelne Farben definitiv auszuschließen oder einschließen zu können. Außerdem sollten Informationen über die Position der Farben gewonnen werden.18
Die unterschiedliche Komplexität dieser Problematik soll anhand zweier Beispiele veranschaulicht werden.
Beispiel (1):
Abbildung in dieser Leseprobe nicht enthalten
Aus der Rückmeldung 0 und dem Code ABCD lässt sich relativ leicht ein Schluss ziehen: Kein Code, der einen Buchstaben {A,B,C,D} enthält, kommt noch als Lösung in Frage. Daraus folgt, dass nur noch Codes aus den Buchstaben {E,F} möglich sind. Es sind für jede Stelle genau zwei Buchstaben bzw. Farben realisierbar und die Anzahl kann durch die Formel
2[4] = 16 {EEEE EEEF EEFF FFFF}
berechnet werden.
Wie Beispiel (2) zeigt, lassen sich die verbleibenden Möglichkeiten nicht immer so leicht bestimmen.
Beispiel (2):
Abbildung in dieser Leseprobe nicht enthalten
Was leiten wir aus der Rückmeldung 10 zum Code ABCD ab?
Zunächst einmal können wir mit Sicherheit sagen, dass der Lösungscode drei Objekte aus dem Versuchscode enthält (wegen der 1-2=3 Stifte in der Rückmeldung - das schließt jedoch nicht aus, dass eines dieser drei Objekte ein zweites Mal im Code vorkommt). Diese drei der vier Objekte könnten sein:
{A,B,C}
{A,B,D}
{A,C,D}
{B,C,D}
Jeweils eines dieser drei Objekte befindet sich wegen dem schwarzen Stift an der richtigen Stelle. Da wir durch diese eine Rückmeldung noch nicht wissen können, um welchen Buchstaben es sich dabei handelt, müssen wir davon ausgehen, dass theoretisch jeder in Frage kommt.
Weiterhin wissen wir, dass die beiden anderen Buchstaben so positioniert sein müssen, dass sie nicht an der gleichen Stelle wie im Versuchscode sind.
Insgesamt ergeben sich die folgenden Muster, bei denen der Buchstabe, von dem angenommen wird, dass er auf der korrekten Position war, fettgedruckt ist. Die freie Position im Code ist mit □ gekennzeichnet.
Buchstaben, die für diese Lücke aufgrund der bisherigen Rückmeldung in Frage kommen, stehen hinter dem Muster in einer geschweiften Klammer.
Mögliche Codes bestehend aus den Objekten A,B,C
Abbildung in dieser Leseprobe nicht enthalten
verbleiben also insgesamt 132 mögliche Codes.
Die Mastermindschablone wurde konzipiert, um den Algorithmus aus dem Artikel The Computer as a Mastermind von Donald E. Knuth in anschaulicher und kompakter Form darzustellen. Mithilfe dieses Algorithmus beziehungsweise der Schablone kann jeder geheime Code im klassischen Mastermind innerhalb von fünf Zügen gelöst werden. Der Algorithmus ebnet lediglich den Weg zur Lösung. In den meisten Fällen muss der Lösungscode eigenständig entschlüsselt werden. Dafür muss der Codebreaker maximal die letzten zwei verbleibenden Codes ausfindig machen.19 Es sei denn, der Codemaker hat einen Lösungscode gewählt, der als Versuchscode des Algorithmus angetragen wird.
Die Schablone ist selbsterklärend. Alle wichtigen Informationen sind ihr selbst zu entnehmen.
[...]
1 Wgl. Klein, B. (2014). S. 413
2 Vgl. Parker. (1994).
3 Vgl. Carter Collectables. (07.02.2013). Stand 21.09.2015.
4 Vgl. Parker. (1994).
5 Vgl. Parker. (1994).
6 Vgl. Parker. (1994).
7 Vgl. Tittmann, P. (2014), S. 1.
8 Vgl. Tittmann, P. (2014), S. 2.
9 Vgl. Tittmann, P. (2014), S. 6.
10Vgl. Tittmann, P. (2014), S. 7.
11 Vgl. Tittmann, P. (2014), S. 7.
12 Vgl. Knuth, D. E. (1976), S. 2
13 Vgl. Bcwcrsdorff, J. (2012), S.241
14 Vgl. Knuth, D. E. (1976), S. 3
15 Vgl. Knuth, D. E. (1976), S. 2
16 Vgl. Bcwcrsdorff, J. (2012), S.241
17 Vgl. Knuth, D. E. (1976), S. 3
18 Vgl. Bcwcrsdorff, J. (2012), S.239
19 Vgl. Knuth, D. E. (1976), S. 2
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Kommentare