Sonderkolloquium, Prof. Gerold Jäger, Universität Umeâ, Schweden / am 09.03.2017

09.03.2017 von 11:00 bis 12:30

Institut für Informatik, Christian-Albrechts-Platz 4, Raum 910 (CAP 4)

Titel: Optimale Strategien für die Black-Peg-Variante des Statischen Masterminds und des Statischen AB-Games

Abstract: Mastermind ist ein Logikspiel für zwei Personen, das im Jahre 1970 erfunden wurde und sich seit zu einem populären Gesellschaftsspiel entwickelt hat, das über 50 Millionen Mal verkauft wurde. Die beiden am Spiel beteiligten Spieler werden als Codemaker und Codebreaker bezeichnet. Der Codemaker legt zu Beginn des Spiels einen vierstelligen Farb-Code fest, der aus sechs Farben ausgewählt wird. Der Codebreaker versucht, diesen Code zu erraten, indem er einen gleichartigen Farb-Code als Frage verwendet und vom Codemaker eine Antwort erhält, wie nahe seine Frage am zu erratenden Farb-Code ist. Für jeden Stift, der sowohl in Farbe als auch in Position richtig ist, gibt der Codemaker einen schwarzen Stift in der Antwort und für jeden Stift, der nur in der Farbe richtig ist, einen weißen Stift. Mit Hilfe dieser Antwort kann er weitere Fragen stellen, die auf dasselbe Weise beantwortet werden, und dies geschieht solange, bis der Codebreaker den Farb-Code erraten hat. Eine natürliche Erweiterung ist es, statt einenm vierstelligen Farb-Code einen p-stelligen mit beliebigem p zu erlauben und statt 6 Farben c Farben mit beliebigem c zu erlauben. Insbesondere in den letzten 10 Jahren hat sich Mastermind zu einem vielbeachteten Forschungsthema entwickelt. Im Jahre 2006 wurde gezeigt, dass Mastermind NP vollständig ist. Des Weiteren wurden Anwendungen von Mastermind in der Komplexitätstheorie, Bioinformatik und Kryptographie untersucht und es wurden Schranken und optimale Strategien für viele Mastermind-Varianten bewiesen, oft indem entweder konstantes p oder konstantes c betrachtet wurden. In diesem Vortrag betrachten wir eine Kombination von drei Mastermind-Varianten: 1. Das AB-Game, das sich von Mastermind unterscheidet, indem sowohl in dem Farb-Code als auch bei den Fragen die Stifte alle verschiedene Farben haben müssen. 2. Die Black-Peg-Variante, in der der Codemaker nur schwarze Stifte als Antwort gibt. 3. Statisches Mastermind, in dem der Codebreaker eine bestimmte Anzahl von Fragen gleich zu Beginn des Spieles gibt, dann alle Antworten erhält und schließlich nur noch einen weiteren Versuch hat, den richtigen Farb-Code zu erraten.
Goddard hat im Jahre 2003 optimale Strategien für das originale Statische Mastermind vorgestellt, und zwar für den Fall von p=2, p=3, p=4 Stiften. In diesem Vortrag wird eine Strategie für die Black-Peg Variante des Statischen Mastermind mit p=2 Stiften vorgestellt und deren Zulässigkeit und Optimalität bewiesen. Des Weiteren werden Strategien für p=3, c=2, c=3 vorgestellt, deren Optimalitätsbeweis ein offenes Problem darstellt. Schließlich 9 weitere Paare (p,c) presentiert, deren Zulässigkeit und Optimalität mit Hilfe eines Computerprogramms gezeigt werden konnte. Am Ende des Vortrags wird über Work-in-Progress berichtet, und zwar über zulässige und optimale Strategien für die Black-Peg-Version des AB-Games. Insbesondere geht es um die Fälle von p=2 Stiften und p=c Stiften. Der letzte Fall ist besonders interessant, aber auch anspruchsvoll, da der Farb-Code und die Fragen Permutationen entsprechen.

Prof. Srivastav

Diesen Termin meinem iCal-Kalender hinzufügen

zurück