Durch das Spielen dieses Spieles können Sie hautnah erleben wie ein effizienter Algorithmus entwickelt wird – mit Stift, Papier und Logik.

Das Paper-and-Pen Spiel ist ein Tree-Decomposition-Spiel namens „Catch the Virus“ – Fang das Virus. Das Spiel Catch the Virus basiert auf dem Cops and Robbers Game (Seymour und Thomas 1993), das von Professor Stefan Szeider speziell angepasst wurde, um den Besuchern bei der Lange Nacht der Forschung oder European Researchers´ Night die Möglichkeit zu geben, die Kraft ihrer eigenen Logik zu erleben und spielerisch in die Welt der Algorithmen einzutreten.

Pursuit-Evasion (Varianten, die als Cops und Räuber und Graphensuche bezeichnet werden) ist eine Familie von Problemen in Mathematik und Informatik, in der eine Gruppe versucht, Mitglieder einer anderen Gruppe in einer Umgebung aufzuspüren. Zu den taktischen Problemen gehören das Umgehen von Gegnern, das Erreichen von Gegnern, das Fangen und Senden / Reagieren auf irreführende Signale. Torrence Parsons führte die Formulierung der Umgebung ein, die als Graph modelliert ist. Netzwerke, bei denen wenige Bots ausreichen, haben eine bestimmte Struktur, die es auch ermöglicht, schwere Optimierungsprobleme effizient zu lösen. Deshalb ist die Berechnung der kleinsten Anzahl von Bots, die für ein gegebenes Netzwerk ausreicht von grosser Bedeutung für die Entwicklung effizienter Algorithmen. Unser Spiel geht auf eine bedeutende Arbeit von Seymour und Robertson (1993) zurück.

Spielregeln

Das Virus X13 ist in das Computernetzwerk der Organspendendatenbank eingedrungen. Die Informatikerin Ada will X13 fangen, indem sie mehrere Bots auf einzelne Knoten des Netzwerks legt. Wie viele Bots braucht Ada, um X13 zu fangen? Mach mit beim Spiel und rette die Daten!

Die Bots ändern ihre Position: einige der Bots werden eingesammelt und auf neue Knoten verteilt., die anderen bleiben liegen. Das Virus sieht was die Bots vorhaben, und wandert beliebig weit entlang des Netzwerkes zu einem neuen Knoten. Dabei darf das Virus nicht einen Knoten überqueren, auf dem ein Bot liegen geblieben ist. Bots die sich bewegt haben, können übersprungen werden.

Laden Sie die Regeln und das Handout herunter (PDF).

Laden Sie die Netzwerke herunter, über die sich die Bots und Viren bewegen.