Kinderspiel „Wer ist es“: für Data Science Begeisterte

In Teil 1 dieser Serie habe ich erklärt, wie ich mit meinem sechsjährigen Sohn Justus das Spiel „Wer ist es gespielt“ und wir uns gemeinsam überlegt haben, mit welchen Tipps und Tricks man dem Gewinn ein kleines bisschen näherkommt. Um nun noch ein bisschen tiefer ins Thema einzutauchen, stelle ich die Frage: Wie und warum funktioniert diese Strategie?

Um zu verstehen, warum diese Strategie funktioniert, hilft ein bisschen Wahrscheinlichkeitstheorie. Wenn ich eine bestimmte Ja-nein-Frage stelle, dann berechnet sich der Erwartungswert der Anzahl Karten, die nach der Antwort auf die Frage noch übrigbleiben, als

Dabei ist n die Gesamtanzahl Karten, die noch vorhanden sind, und k ist die Anzahl Karten, für die die Antwort auf die Frage „ja“ ist. In beiden Fällen wird die Karte, die der Gegner raten muss, nicht mitgezählt. Für die Berechnung des Erwartungswerts gehen wir von der Annahme aus, dass alle Karten, die noch übrig sind, mit gleicher Wahrscheinlichkeit die Lösung sein können. Da die Karte, die wir raten müssen, am Anfang zufällig und ohne Tricks aus einem Kartenstapel gezogen wurde, ist diese Annahme plausibel. Etwas weniger offensichtlich ist es, ob es wirklich reicht, sich auf die jeweils nächste Frage zu konzentrieren, oder ob man noch ein wenig besser werden kann, indem man bis zum Ende des Spiels alle verbleibenden Züge durchrechnet. Die Frage lasse ich hier mal offen – ich freue mich aber über Überlegungen dazu!

Wir wollen natürlich, dass nach unserer Frage möglichst wenige Karten übrigbleiben. Darum wollen wir diejenige Frage stellen, für die der obige Erwartungswert möglichst klein ist. Der Wert n ist für alle Fragen (in derselben Spielrunde) derselbe; sie unterscheiden sich nur in dem Wert für k. Welche Werte für k liefern nun den kleinsten Erwartungswert? Da hilft ein bisschen Kurvendiskussion. Die zweite Ableitung des obigen Erwartungswerts nach k ist konstant 4/n, also immer positiv. Wenn wir also eine Nullstelle der ersten Ableitung finden, haben wir auch unser Minimum gefunden. Die erste Ableitung ist 4k/n-2, die Nullstelle ist also k=1/2 n. Wenn das nicht genau zu erfüllen ist, weil es keine passende Frage gibt, so muss man eine Frage wählen, für die die Differenz von k und 1/2 n möglichst klein ist. Das passt genau zu unserer Strategie, die wir oben beschrieben haben. Die kann man nämlich auch so formulieren: Wähle diejenige Frage, für die die kleinere der beiden Zahlen k und n-k möglichst groß ist.

Wer auf Ableitungen etwas weniger Lust hat, kann sich natürlich die Funktion für den Erwartungswert auch mal für verschiedene Werte von n plotten, um das Minimum auf eine etwas weniger rigorose, aber dafür möglicherweise anschaulichere Weise zu finden. Das Ergebnis ist eine schöne Parabel, wie man zum Beispiel für n = 10 hier mit Hilfe von Wolfram Alpha nachvollziehen kann. Papier und Bleistift tun es zum Zeichnen natürlich auch.

Programmieren für Data-Science-begeisterte (Fast-)Erwachsene: eine Spielstrategie im Überblick

In jedem Schritt für diverse Fragen die Karten zählen zu müssen, ist zugegebenermaßen etwas mühsam. Wäre es nicht schön, schon im Voraus ein für alle Mal zu wissen, welche Fragen man stellen muss? So ganz ist das natürlich nicht machbar, denn wir haben ja gesehen, dass die Karte, die der Gegner raten muss, auch eine gewisse Rolle spielt. Wenn wir die aber mal vernachlässigen, kann man schon auf die Idee kommen, eine optimale Spielstrategie mal als Baum aufs Papier zu zeichnen.

Da zur Data Science immer auch Daten gehören (klingt lachhaft selbstverständlich, ist aber in der Praxis nicht immer allen Beteiligten klar) und natürlich ein bisschen Programmcode, wird es höchste Zeit, dass wir beides jetzt noch einbauen. Wir schreiben also ein kleines Programm, das den Spielbaum berechnet und ausgibt. Der Quellcode ist hier zu finden, und wer möchte, kann das Notebook ohne Installationsaufwand direkt auf Google Colab ausprobieren (siehe Link am Anfang des Notebooks). Wer das Programm auf der eigenen Maschine ausprobieren möchte, muss für die schöne grafische Aufbereitung des Spielbaums graphviz installieren, was unter Umständen etwas mühsam ist.

Unsere Daten sind klein und überschaubar: Es ist eine Matrix mit den Fragen in den Spalten und den Personen (Karten) in den Zeilen. Ein Matrixeintrag ist genau dann 1, wenn die Antwort auf die entsprechende Frage „ja“ ist, und 0 sonst. Diese Matrix ist so klein (24 Zeilen und 15 Spalten), dass wir sie einfach innerhalb des Notebooks definieren und nicht in eine externe Datei auslagern.

Wenn man sich die Summen pro Spalte der Matrix ansieht, bekommt man die Anzahl Karten, für die die entsprechende Frage mit „ja“ beantwortet wird. Hier kommt schon die erste Überraschung: Anders als im deutschen Wikipedia Artikel behauptet wird, haben die verschiedenen Fragen nicht alle genau fünf Karten mit Ja-Antworten. Die größte Abweichung sind die Karten mit Bart, von denen es acht gibt. Abweichungen nach unten mit vier Ja-Antworten gibt es beim Kinnbart und bei der braunen Haarfarbe. Im englischen Wikipedia-Eintrag ist die Behauptung mit den fünf Ja-Antworten übrigens nicht zu finden.

Um den Spielbaum zu speichern, benutze ich das praktische Python-Paket Anytree, das eine sehr leicht zu handhabende Implementation einer Baumdatenstruktur zur Verfügung stellt. Das Paket bietet auch eine schöne Visualisierungsmöglichkeit über graphviz.

Die Klasse game_tree bündelt dann alles, was wir für die Erzeugung des Spielbaums brauchen. Die ganze wesentliche Arbeit wird in der Methode generate_tree geleistet. Sie ermittelt nach der oben beschriebenen Methode die richtige Frage nach der oben beschriebenen Zählmethode und ruft sich dann selbst wieder auf, um für die beiden Antwortmöglichkeiten (ja oder nein) ebenfalls wieder die richtige Frage zu ermitteln. Unterwegs speichert sie die Zwischenergebnisse jeweils im Spielbaum. Wenn nur noch eine Karte übrig ist, wird die Rekursion beendet.

Wenn ich „die richtige Frage“ schreibe, ist das ein wenig ungenau. Es gibt nämlich manchmal mehr als eine Frage mit der höchstmöglichen Glückszahl. In diesem Fall wählt das Programm einfach willkürlich eine aus (die erste, die es berechnet hat). Die Lösung, die es ausgibt, ist also nicht die einzig mögliche. Es gibt andere, die ebenso gut sind.

Der erzeugte Baum hat einige interessante Eigenschaften. Der Wurzelknoten verrät uns, dass es eine gute Idee ist, als Erstes nach einem Bart zu fragen. Daran ändert sich übrigens auch dann nichts, wenn man das Wissen über die Karte einbezieht, die der Gegner raten muss. Die Frage nach dem Bart ist immer die beste erste Frage. Das liegt daran, dass ihre Glückszahl am Anfang des Spiels die 8 ist (8 Ja-Antworten und 16 Nein-Antworten), während alle anderen Fragen höchstens eine Glückszahl von 5 haben. Selbst wenn die Glückszahl also um eins kleiner wird, ist sie immer noch größer als die aller anderen Fragen.

(Tipp: Mit Klick auf das Bild vergrößert es sich)

Noch mehr Spaß und Rätsel mit „Wer ist es?“

Wenn man nach diesem Baum spielt, variiert die Anzahl Fragen, die man bis zur Lösung braucht, zwischen vier und sechs. Im Durchschnitt sind es 4,625 Fragen, sehr dicht an der informationstheoretischen unteren Schranke von rund 4,58 (Zweier-Logarithmus von 24). Es gibt also keine Strategie, die immer nur mit vier Fragen auskommt. Aber gibt es eine, die immer höchstens fünf benötigt? Ich bin gespannt auf Vorschläge.

Es gibt auch verschiedene Versionen des Spiels, die über die Jahre herausgekommen sind: Reisevarianten mit nur zwanzig Karten, verschiedene Ausgaben mit anderen Gesichtern, ja sogar eine Version mit Tieren. Wenn ihr eine andere Version besitzt als die auf meinem Foto (die aus der Kindheit meiner Frau stammt), passt das Programm doch mal für eure Version an – ich freue mich, von euch zu hören.