Ausnahmsweise mal etwas, was nichts mit Kryptographie und IT-Sicherheit zu tun hat.
Während einem Spiel Cluedo, bei dem es darum geht mittels eigenen (eigene Karten) und fremde Informationen (fremde Karten) auf neue Informationen (Lösungskarten) zu schließen, habe ich mir die Frage gestellt, in wie fern die Informatik einem an dieser Stelle helfen kann. Zunächst eine Spielbeschreibung von Wikipedia.de:
Auf dem Spielplan ist der Grundriss eines Hauses mit neun Räumen und dem Flur dargestellt. In diesem Haus ist Dr. Schwarz (auch Graf Eutin) ermordet worden und alle Mitspieler übernehmen im Verlaufe des Spiels die Rolle eines Detektivs. Am Anfang wird von jedem Kartenstapel der Verdächtigen, Mordwerkzeuge und Mordzimmer jeweils eine Karte verdeckt gezogen. Diese gilt es im Laufe des Spiels zu ermitteln. Alle übrigen Karten werden an die Mitspieler verteilt. Diese können nun durch geschickte kombinierte Verdächtigungen, die sie immer den anderen Mitspielern vortragen, erfahren, welche Karte diese besitzen. Dadurch muss jeder auf den korrekten Mörder, die Tatwaffe und den Tatort Rückschlüsse ziehen. Wer zuerst diese drei Fragen richtig beantworten kann, hat gewonnen. Wer allerdings eine falsche Anklage erhebt, scheidet aus. Es existieren mit sechs Verdächtigen, sechs Tatwaffen und neun Räumen insgesamt 324 verschiedene Lösungskombinationen.
Die Anzahl der Möglichkeiten ist also die Mächtigkeit aus dem Kreuzprodukt: Verdächtige (Täter) x Waffen x Räume. Bei 3 Spielern erhält jeder Spieler 6 Karten auf die Hand (3*6+3). Je nachdem von welchem Typ diese Karte sind, verringert sich die Lösungsmenge zunächst. Nun hat jeder Spieler das Ziel, diese Menge auf 1 zu reduzieren, indem er anderen Spielern Fragen stellt (Täter – Waffe – Raum). Sofern der nächste Spieler in der Runde eine (oder mehrere) dieser genanntne Karten besitzt, muss sie, allerdings im Verborgenen, dem Fragesteller gezeigt werden. Damit kann dieser die mögliche Lösungsmenge weiter vermindern.
(1) Diese Menge mit Hilfe der eigenen Karte und die Karten, die einem von anderen gezeigt worden sind zu reduzieren ist vergleichsweise einfach bzw. müssen nur von der Liste gestrichen werden.
Kritischer ist die Einschränkung durch Kommunikation der anderen Spieler untereinander (2). Fragt beispielsweise Spieler B nach 3 Karten und zeigt Spieler C eine dieser, ist zunächst nicht bekannt welche, außer ich besitze konkrete Informationen über 2 dieser 3 Karten und kann ausschließen, dass eine dieser vorgezeigt wurde. Kann ein Spieler auf eine Anfrage nicht antworten (3), ist dies erneut eine wichtige Information, denn wenn bekannt ist, dass alle Spieler eine Karte nicht besitzen, ist dies die gesuchte Gewinnkarte.
Es ist allerdings nur sehr schwer möglich ALLE Informationen auf einem kleinen Zettel durch Striche, Kreise und Pfeile zu notieren. Insbesondere die Auswertung fällt sehr schwer. Deshalb übergehen viele Spieler einfach Informationen welche sie zunächst nicht direkt in eindeutige Informationen umwandeln können. Lässt sich also aus einer Handlung (Spieler B zeigt Spieler C eine unbekannte Karte) nicht direkt eindeutig verarbeiten (Spieler B besitzt Karte X), wird diese Information nicht weiter notiert. Dies ist natürlich ein Fehler welcher durch die Informatik korrigiert werden soll. Daher habe ich ein 4-Tupel zur Speicherung jeder Information gewählt, welche sich aus Täter (Verdächtiger), Waffe, Raum und dem Spieler der darauf antworten konnte, zusammensetzt. Aufgrund der vorherigen Informationen und jener, die erst im weiteren Verlauf des Spiels gewonnen werden, lässt sich unter Umständen (in manchen Fällen auch nachträglich) ermitteln, um welche Karte es sich dabei gehandelt hat. Wie diese Informationsmengen (Eindeutige Karten, Mehrdeutige Karten (siehe Beispiel), Negationale Karten (falls jemand nicht Antworten kann)) zu verarbeiten sind, habe ich in einem PDF zusammengefasst. Es enthält durchaus noch einige Fehler und ist auch nicht als wissenschaftliche Veröffentlichung anzusehen – ist ist mehr eine Skizze aus der noch weiteres entstehen kann.
Hier das PDF:
http://www.cryptblog.de/cluedo1.pdf
Ich habe das Ganze auch in Java programmiert und einem Praxistest unterzogen. Dabei hat es sich durchaus bewährt – wobei die Leistung nur schwierig einzuschätzen ist, da Glück ein wichtiger Bestandteil dieses Spiels ist.
Es handelt sich dabei allerdings AUSSCHLIESSLICH um die Aufarbeitung und Auswertung bekannter Informationen. Der Algorithmus bietet keinen dominanten Lösungsweg durch das Spiel bzw. stellt (noch) nicht Fragen an andere Spieler. Dies wäre eine Arbeit, die darauf aufsetzen könnte.