Das Geographiespiel in der Theorie und seine Realisierung als App

Abstract

Das sogenannte "Geographiespiel" ist ein simples Spiel, welches dem Leser eventuell in einer Variante bekannt ist. Dabei nennen zwei Spieler abwechselnd Städtenamen, wobei diese jeweils mit dem Endbuchstaben der vorherigen Stadt beginnen müssen. Nennt Spieler A beispielsweise "Stuttgart", so kann Spieler B "Tübingen" als Antwort geben. Daraufhin wären "Nürnberg" oder "New York" mögliche Antworten. Das Ende des Spieles ist erreicht, wenn einem der beiden Spieler keine weitere Stadt einfällt und er somit das Spiel verliert. Bereits genannte Städte dürfen nicht erneut verwendet werden. Denkbar wäre auch eine Variante, in der Personen oder Automarken genannt werden. Beim Geographiespiel wird untersucht, welcher Spieler bei einer festgelegten Städteliste und optimaler Spielweise gewinnen wird. Das Spiel wird dahingehend erweitert, dass die Anzahl der Anfangs- und Endbuchstaben nun nicht mehr auf 26 festgelegt ist. Das Auswerten einer erweiterten Version des Spieles, die eine unbegrenzte Anzahl an Buchstaben zulässt, liegt in P-SPACE. Gibt es dagegen nur endlich vielen Buchstaben, liegt das Problem in P. Zudem ist es für sehr kleine Instanzen (nur 1 bzw. 2 Buchstaben) möglich, diese in logarithmischem Platz zu lösen. Ziel dieser Arbeit ist es, Instanzen mit endlich vielen Buchstaben genauer zu untersuchen. Einerseits wird der Fall mit 3 bzw. 4 Buchstaben betrachtet. Andererseits wird die Möglichkeit untersucht, das Auswertungsproblem für Schaltkreise auf das Geographiespiel mit endlich vielen Buchstaben zu reduzieren und so die P-Vollständig zu zeigen. Als praktischer Teil der Arbeit wurde das Geographiespiel als App implementiert. Dies dient der Untersuchung, mit welchem Aufwand und bis zu welchen Grad die Umsetzung realisierbar ist.