Mastermind

300000

Mastermind

Gesamtzahl der Spiele: 445808

Anzahl der Ziffern		0
Ziffernbereich 1..		0
Max. Häufigkeit, mit der eine Ziffer vorkommen darf		0
Maximale Anzahl von Versuchen		0

Eine Abkürzung

Wie könnte man das ganze Problem in Teilziele zerlegen?

Was könnten ganz allgemeine Prinzipien für die Formulierung der nächsten Vermutung sein?

Nützliche Hilfsmittel:

Für die erste Phase A) ist es sinnvoll, sich alle möglichen Ziffern zu notieren, warum?

Für Phase B) ist es sinnvoll, eine Eliminierungstabelle zu haben, wie und warum?

A) Wie kann man versuchen, alle heißen Ziffern zu finden?

Welche Ergebnisse (Antworten) wären nach dem Einreichen einer Vermutung sehr nützlich?
- Wir haben Glück, wenn sich herausstellt, dass alle oder die meisten erratenen Ziffern heiß sind, aber wir haben auch viele Informationen gewonnen, wenn die beiden zurückgegebenen Zahlen beide 0 sind, weil dann keine der erratenen Ziffern in der Lösung vorkommt, d.h. alle erratenen Ziffern sind kalt. In diesem Fall können wir N Ziffern aus der Liste der möglichen Ziffern oder N Zeilen in der Eliminierungstabelle streichen.

Wenn wir nicht so viel Glück haben, was ist dann eine mögliche Strategie, um mehr heiße Ziffern zu finden?
- Nehmen wir an, dass Lösungen 4 Ziffern haben und dass die Ziffern 1,..,9 höchstens einmal vorkommen können (ansonsten ändern Sie die nächsten 3 Sätze). Wenn die Lösung 4 Ziffern enthält, erraten wir 1,2,3,4 und dann 5,6,7,8 und wissen automatisch die 9, indem wir zählen, wie viele Ziffern von 1,..,8 heiß sind. Wenn es vier heiße Ziffern gibt, dann ist 9 kalt, sonst ist es heiß. Wenn wir Glück haben und 1,2,3,4 bereits heiß sind, werden wir die anderen Ziffern nicht ausprobieren, da sie kalt sind.

Nehmen wir an, wir haben eine Reihe von Vermutungen gemacht, sagen wir 7, nach denen wir für jede Ziffer wissen, ob sie heiß oder kalt ist.
Spielt es eine Rolle, ob diese 7 Vermutungen hauptsächlich heiße oder kalte Ziffern enthielten?
- Es scheint genauso nützlich zu sein, zu raten und alle heißen Ziffern zu kennen, wie auch alle kalten Ziffern zu erraten. Denn wenn man einen Satz kennt, kennt man auch den anderen Satz. Dem ist aber nicht so. Wenn unsere Vermutungen viele heiße Ziffern enthalten, dann sammeln wir nebenbei auch zusätzliche Informationen über richtige oder falsche Positionen dieser heißen Ziffern. Wir werden diese Informationen nicht sammeln, wenn unsere Vermutungen hauptsächlich kalte Ziffern enthalten.
- Welchem Prinzip folgen wir, wenn wir Vermutungen mit vielen heißen Ziffern abgeben?
  - Prinzip 1, weil wir zusätzlich Informationen über Positionen sammeln, die später nützlich sein werden, wenn wir alle heißen Positionen kennen.
- Fallen dir Formulierungen zu Vermutungen ein, die Prinzip 2 folgen? Mit anderen Worten: Welche Art von Vermutungen liefert Antworten, die leicht verwendbar sind?
  - Um Prinzip 2 zu folgen, könnten wir eine Vermutung anstellen und sie modifizieren, indem wir eine Ziffer herausnehmen, sagen wir 5, und eine andere Ziffer hineinnehmen, sagen wir 3. Wenn die neue Vermutung weniger heiße Ziffern hat, dann ist 5 heiß und 3 ist kalt. Wenn die neue Vermutung mehr heiße Ziffern hat, dann ist 5 kalt und 3 ist heiß. Ansonsten sind 5 und 3 beide heiß oder beide kalt. Um zwischen diesen beiden Fällen zu unterscheiden, könnte man sowohl 5 als auch 3 in der nächsten Vermutung haben. Bei der Entscheidung, welche Vermutung um eine Ziffer modifiziert werden soll, folgen wir einer früheren Vermutung und wählen eine vorherige Vermutung aus, die die meisten heißen Ziffern hatte, um auch Informationen über Positionen zu sammeln und Prinzip 1 zu folgen.
Nehmen wir an, du bist der vorherigen Vermutung gefolgt und hast eine Vermutung abgegeben, bei der du nur eine Ziffer vertauscht hast, z. B. 7 mal 3, und du hast aus dem Ergebnis gelernt, dass die neue Ziffer 3 heiß und die 7 kalt ist.
Ist das alles, was du aus dieser Vermutung gelernt hast?
- Nein. Du kannst jetzt zu früheren Vermutungen zurückkehren und das Wissen, dass 3 heiß und 7 kalt ist, nutzen, um mehr Informationen aus früheren Vermutungen abzuleiten. Zum Beispiel enthielt eine frühere Vermutung die 3 und hatte nur eine heiße Ziffer, dann sind die anderen Ziffern in dieser Schätzung kalt. Die Tatsache, dass sie kalt sind, kann dir einen Hinweis darauf geben, welche anderen Ziffern durch andere Vermutungen heiß sind und so weiter.

Wenn du entschieden hast, welche Ziffern in der nächsten Vermutung enthalten sein sollen, spielt es dann eine Rolle, in welcher Reihenfolge du sie platzierst?
- Wenn du entschieden hast, welche Ziffern in der nächsten Vermutung enthalten sein sollen, spielt es dann eine Rolle, in welcher Reihenfolge du sie platzierst?
Sobald wir alle heißen Ziffern kennen, kennen wir auch alle kalten Ziffern und können deren Zeilen in der Eliminierungstabelle durchstreichen.

B) Wie können wir die Position jeder heißen Ziffer finden?

Jetzt, da wir alle heißen Ziffern kennen, welches Feedback wäre sehr nützlich?
- Wenn alle erratenen Ziffern an der richtigen Stelle sind, dann haben wir natürlich Glück und das Problem gelöst. Ein weiteres glückliches Ergebnis ist, wenn sich keine der erratenen Ziffern an der richtigen Position befindet. Dann haben wir viel gelernt und können N Felder in der Eliminierungstabelle durchstreichen.

Erinnerst du dich daran, wie wir die Eliminierungstabelle in dieser letzten Phase der Lösung verwenden können.
- Wenn alle Zeilen mit kalten Ziffern durchgestrichen sind und es eine Zeile oder Spalte mit nur einem Feld gibt, das nicht durchgestrichen ist, dann sagt uns dies, welche Ziffer diese Position in der Lösung hat und die restlichen freien Felder in dieser Spalte können durchgestrichen werden. Wenn jede Ziffer nur einmal vorkommen kann, dann können auch alle Felder in dieser Zeile durchgestrichen werden.

Wie viele Zahlen können aus den heißen Ziffern gebildet werden?
- Jede dieser Ziffernfolgen wird als Permutation bezeichnet. Die Frage ist also: Wie viele Permutationen gibt es für N Objekte, hier N Ziffern?
  Wenn alle Ziffern unterschiedlich sind, dann gibt es für die erste Ziffer N Optionen. Für jedes dieser N gibt es N−1-Optionen für die zweite Ziffer. Für jede dieser N×(N−1)-Kombinationen gibt es N−2-Optionen für die dritte Ziffer usw., insgesamt N×(N−1)×...×2×1 = N! (genannt N-Fakultät) viele.
  Wenn nicht alle Ziffern unterschiedlich sind, dann könnten wir z.B. N=4 haben und die 4 heißen Ziffern sind 2,2,2,5. Dann ist das Produkt N! = 4! muss durch 3 geteilt werden! Denn die Reihenfolge zwischen den drei 2en spielt keine Rolle. Wir bekommen 4!/3! = 24/6 = 4 (oder eleganter 4!/3! = 4×3! / 3! = 4).
- Wie viele sind das für N=3 oder N=4?
  - Wenn jede Ziffer nur einmal auftaucht, erhalten wir 3! = 3×2×1 = 6 und 4! = 4×3! = 24 Permutationen (Sequenzen/Folgen). Das sind nicht viele.
- Was bedeutet das für die Lösungsfindung?
  - Man könnte alle Zahlen (Permutationen von N heißen Ziffern) aufschreiben und sie nacheinander in Bezug auf alle früheren Vermutungen überprüfen. In der Regel bleiben nur ein oder zwei dieser Zahlen möglich, die man als nächste Vermutung ausprobieren kann.

Bitte beachte: Nach einer Vermutung wissen wir vielleicht, wie die Lösung aussehen muss, aber wir müssen die Lösung noch einreichen, um dem Computer zu beweisen, dass wir sie gefunden haben.

Wie oft muss man durchschnittlich raten, wenn man den obigen Hinweisen folgt?