Mastermind Strategie

Neue Frage »

Mastermind1951 Auf diesen Beitrag antworten »
Mastermind Strategie
Meine Frage:
Für das Spiel Mastermind gibt es den Knuth-Algorithmus, der jede Kombination mit 5 Versuchen erraten kann. Wie könnte eine Strategie für eine leicht abgewandelte Variante des Spiels aussehen, welche sich insofern vom Original unterscheidet, dass ausschließlich gesagt wird, wie viele Farben richtig positioniert sind.

Meine Ideen:
Mir ist klar, dass das keine einfache Aufgabe ist, aber vielleicht hat ja jemand eine gute Idee.
HAL 9000 Auf diesen Beitrag antworten »

Naja, du könntest es ja ebenso wie Knuth mit einer Minimax-Strategie angehen:

D.h., zu jedem Spielzeitpunkt ist ja berechenbar, welche Menge von Varianten noch in Einklang steht mit den Ergebnissen der bisherigen Rateversuche. Der nächste Rateversuch wird nun folgendermaßen ermittelt:

Für alle Varianten ermittelt man die 5 Teilmengen von bzw. eigentlich nur deren Größen für eben die 5 möglichen Antworten richtige Positionen. Man vermerkt dann das jeweilige Maximum dieser 5 Werte. Als Rateversuch nimmt man nun die Variante, wo das vermerkte Maximum minimal ist. (Unter Umständen mag das sogar eine Variante sein, von der man garantiert weiß, dass es noch gar nicht die richtige sein kann!)

Keine Ahnung, wo man dann am Ende rauskommt - im worst-case irgendwo bei 10-20 Rateversuchen lautet meine grobe Schätzung. Einfach mal algorithmisch umsetzen!

EDIT: Hab's mal versucht zu implementieren, und bekomme dabei worst-case 10 Versuche raus (Mittelwert ca. 7,2), also am unteren Rand der von mir vermuteten Spanne.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »