Prinzessin und Monster

Das Prinzessin-und-Monster-Spiel, eingeführt von Rufus Isaacs, ist ein kontinuierliches Verfolgungs-Flucht-Spiel mit Nullsummencharakter und vollständig unvollkommener Information. Ein „Monster" sucht in einem dunklen, begrenzten Raum eine „Prinzessin", die sich versteckt; keiner kennt den Ort des anderen, bis sie zusammenstoßen. Das Spiel zeigt, warum optimale Suche zwingend gemischte (randomisierte) Strategien erfordert.

Beide Akteure bewegen sich in einem dunklen, begrenzten Raum und erfahren erst im Moment des Zusammenstoßes voneinander. Das Monster (Sucher) minimiert die erwartete Fangzeit, die Prinzessin (Versteckende) maximiert sie — ein reines Nullsummenspiel. Entscheidend: Wegen der völlig fehlenden Information gibt es keine optimale deterministische Strategie. Jede berechenbare Suchroute kann auf Dauer umgangen werden. Die Lösung verlangt gemischte Strategien — Wahrscheinlichkeitsverteilungen über mögliche Pfade — sodass die Bewegungen für den Gegner grundsätzlich unvorhersehbar bleiben.

Bei Suchproblemen unter Unsicherheit: U-Boot-Jagd, robotergestützte Such- und Rettungseinsätze, Cybersecurity-Bedrohungserkennung (das Aufspüren eines verborgenen Angreifers im Netz) und die Gestaltung von Patrouillen. Immer dann, wenn ein Sucher ein bewegliches, ausweichendes Ziel ohne verlässliche Echtzeit-Information finden muss.

Statt einer festen Route randomisierte Suchmuster einsetzen, die der Gegner nicht antizipieren kann — Unvorhersehbarkeit ist hier kein Mangel, sondern die optimale Taktik. Ergänzend lässt sich das Spiel durch bessere Sensorabdeckung verändern: Mehr Information verwandelt das Spiel mit unvollkommener Information schrittweise in eines, in dem deterministische Suche wieder funktioniert.

Ein Zerstörer, der ein U-Boot in einem Seegebiet sucht und absichtlich unregelmäßige Kurse fährt, damit das U-Boot seine Route nicht vorhersagen kann. Ein Sicherheitsteam, das einen Eindringling in einem Netzwerk jagt, der seine Spuren verwischt. Ein Patrouillenplan, der bewusst zufällige Wege wählt, damit Angreifer keine Lücke im Takt ausnutzen können.