Stefannuss

Stefannuss_GUIStefannuss oder auch Stefannuß ist weder eine Person noch eine Frucht, sondern ein Brettspiel mit farbigen 4×4 Feldern und 16 farbigen Spielsteinen, unzähligen Kombinationsmöglichkeiten und, wie sich später herausstellen wird, vielen unterschiedlichen Lösungen.

Das Brettspiel ist z.B. bei der Puzzle Werkstatt Unnerstall erhältlich.

Das nebenstehende Bild zeigt die von mir programmierte Stefannuss Simulation. Sie können ja mal ihr Glück versuchen und mit einem Mausklick viele hundert Lösungsversuche starten…

Spielidee

Das Spielfeld (Board) besteht aus 4 x 4 = 16 farbige Felder. Die Farben der Felder entsprechen der Farbcodierung von Telefonkabeln und sind somit leicht zu erkennen:

Stefannuss_Board

Die einzelnen Spielfelder sind von 1 bis 16 durchnummeriert. Zum Spiel gehört auch ein Vorrat (Stock) von 16 farbigen Spielsteine (Token) mit folgender Verteilung:

Stefannuss_Stock

Spielregeln

Das Spiel ist beendet, wenn alle Spielsteine auf dem Spielfeld abgelegt wurden. Die Spielsteine müssen nach folgenden beiden Regeln auf dem Spielfeld abgelegt werden:

  • Regel 1: Gleiche Farben berühren sich weder waagerecht, senkrecht oder diagonal.
  • Regel 2: Ein Spielstein darf nie auf einem gleichfarbigen Spielfeld abgelegt werden.

Diese beiden Grundregeln machen das Stefannuss Rätsel zu einer „runden“ Sache ;-) Nach jedem Spielzug verändert sich das Spielfeld, weil die Farben der Spielfelder durch die Spielsteine abgedeckt sind und sich neue „Nachbarn“ (Neighbor) ergeben.

Lösungstrategie

Nach den ersten Lösungsversuchen war klar, dass des Rätsels Lösung eine langwierige Sache wird. Das Spielfeld verändert sich nach jedem Spielzug. Man erkennt schnell, dass die Lösungsmöglichkeiten einer baumartigen Struktur bilden. Das folgende Bild zeigt die Baumstruktur (Tree) nach 30 Schritten (Steps).

Stefannuss_Tree-after-30-steps

Stefannuss_Board-after-30-stepsDie einzelnen Knoten sind vergleichbar mit Spielsteinen die auf dem Spielfeld abgelegt werden können. Der Baum besteht in diesem Beispiel aus 43 Knoten (Nodes) zzgl. dem Wurzelkonten (Root). Vier Knoten konnten wieder gelöscht werden da die Optionen das Rätsel nicht gelöst haben. Im aktuellen Schritt wurde beispielsweise ein gelber Spielstein auf Feld 5 abgelegt:

Ausgehend von dieser Spielsituation wird geschaut, ob sich ein weiterer Spielstein aus dem Vorrat auf dem Spielfeld ablegen lässt (explore). Die unzählige Kombinationsmöglichkeiten tragen zur Verwirrung bei und man wird immer wieder in Richtung Root „zurückgeworfen“ (walk down).

Und so bin ich 2012 damit angefangen, das Rätsel mit dem Computer lösen zu lassen den schließlich ist programmieren mein Hobby. Leichter gesagt als getan, denn der Computer muss das Problem erst mal „verstehen“ bevor er sich an die Arbeit erledigen kann. Da Computer nicht denken sondern nur Prozesse und Algorithmen abarbeiten, muss das Problem zunächst zerlegt werden.

Wie viele Wege führen nach Rom? Viele!

Das Spielfeld hat 16 Felder und es gibt 5 unterschiedliche Farben bzw. Spielsteine. Das oben gezeigte Baumdiagramm zeigt einen „Baum“ mit 10 Ebenen und pro Ebene existieren bis zu 7 Optionen. Je „höher“ man sich im Baum bewegt, desto weniger Optionen gibt es. Manche Zweige sind sehr lang, andere Zweige sind wiederum sehr kurz. Wie viele Knoten müssen ausprobiert werden? Es werden einige Tausend oder sogar Millionen sein!

Gibt es nur eine Lösung oder gibt es viele Lösungsmöglichkeiten? Ergeben die vielen Wege am Ende ein gemeinsames Lösungsbild oder gibt es verschiedene Lösungen?

Nachtrag vom 23.02.2013:
Hier gibt es Informationen zu einer anderen Lösungsstrategie: https://www.neumann-s.net/stefannuss/stefannuss.htm

Programm und Datenstruktur

Das folgende Bild zeigt die Struktur vom PHP-Programcode und die MySQL-Tabellen der Stefannuss-Simulation:

Stefannuss_Program-and-data-structure

Man erkennt die drei Themenkomplexe:

  1. Anwendungsebene (GUI) und Konfiguration
  2. Stefannuss (Problemorientierte Anteil)
  3. Walking-the-Tree (Algorithmus)

Ich habe in den vorangegangenen Text immer wieder englische Begriffe in Klammern eingefügt. Diese Begriffe sind wichtig wenn man die Programme und die Datenstrukturen verstehen möchte und trauchen im Programcode sowie bei den Datenbankstrukturen immer wieder auf.

Programmstrukturen

Die Stefannuss-Simulation besteht aus mehreren PHP Dateien mit eingebetteten HTML-Code, einer CSS-Styledefinition, einer Logdatei. Die problemorientierten Programmanteile findet man in der inc.stefanuss.php und die Walking-the-Tree Programmanteile in inc.tree.php

Über die Tabelle games wird sichergestellt, dass immer nur ein Nutzer einen Lösungsversuch starten kann. Die Lösungsversuche werden Steps genannt. Aufgrund des Walking-the-Tree Algorithmus sind ~3 Steps für ein neuen Knoten im Baum notwendig. Ein Knoten entspricht einem auf dem Spielfeld abgelegten Spielstein.

Der Anwender kann entweder einen einzigen Step oder 10.000 Steps pro Game starten. Je nach Auslastung des Web-Servers ist die Ausführungszeit pro Game auf maximal 20 Sekunden beschränkt.

Die Tabellen Board und Stock sind selbstsprechend und enthalten die Daten für das Spielfeld und den Vorrat. Aufgrund der vielen Zugriffe pro Game sind die beiden Tabellen als MySQL MEMORY Tabellen definiert.

Datenstrukturen

Die sechs MySQL Tabellenwerden entweder für das Stefannuss Problem oder dem Walking-the-Tree Algorithmus genutzt.

 

Versionen & Performance

Die Performance wird hier in Schritte pro Sekunde angegeben. Wobei im Schnitt drei Schritte (Steps) pro Knoten (Node) benötigt werden. Die Performance von allen Spielen (Games) mit 10.000 Steps berechnet sich wie folgt:

Die Performance der PHP-Skripte und MySQL-Abfragen hängt natürlich von der Serverlast beim Webhoster ab. Diese Serverlast variiert je nach Tagsesteit.

Version 1) Basic4PPC Entwicklungsumgebung

Ich habe mir vor langer Zeit für meinen Pocket-PC ein BASIC Compiler (Basic4ppc) gekauft. Die Entwicklungsumgebung bildete 2012 den Auftakt einer sehr langen Entwicklungsarbeit. Mein PC (Dual-Core Celeron 2.3GHz) schafft mit dem Walking-the-Tree Algorithmus im Debugging Modus ca. 11.000 Knoten (=33000 Schritte) pro Stunde. Im EXE Modus sind es immerhin 13.000 Nodes pro Stunde. Das entspricht einer „Performance“ von ~11 Schritte / Sekunde. Das ist nicht viel! Falls alle theoretischen 7,5 Mio Möglichkeiten berechnet werden müssten, würde die Berechnung gut 10 Monate dauern ;-) Also muss ich mir einen anderen Rechner oder einen anderen Algorithmus zulegen…

Version 2) PHP & MySQL

Die Stefannuss Simulation läuft nun auf dem Server welcher auch diese Internetseite bedient. Die Laufzeit eines einzigen Spielversuchs ist auf 2000 Schritte bzw. 20 Sekunden beschränkt. Die Anzahl der Schritte pro Zeitlimit verhält sich anti-proportional zur Anzahl der Knoten im Baum (Tree). Während die Performance Anfangs noch bei  ~154 Schritte / Sekunde beträgt, so sind es nach ~140 Spielen nur noch 39 Schritte / Sekunde.

Version 3) PHP & MySQL mit optimierten Tabellen und Indexen

Nun bleibt die Verarbeitungsgeschwindigkeit konstant bei ~250 Schritte /  Sekunde. In dieser Version wurde die erste Lösung nach insgesamt ~945.000 Schritten gefunden.

Version 4) PHP & MySQL mit optimierten Tabellen und Indexen und In-Memory Tabellen

Die Tabellen für board und den stock wurden nun als MEMORY Tabellen gewandelt. Die Geschwindigkeit liegt nun konstant bei 333 Schritte / Sekunde. Die durchschnittliche Performance bei einem Baum mit 4,8 Millionen Knoten beträgt ~232 Schritte / Sekunde.

Bei theoretisch 7,5 Mio Knoten müssten 4500 Spiele  á 5000 Schritte gespielt werden. Dazu würde man mit dieser Version ~ 20 Stunden benötigen.

Version 5) Multiuser; Portabilität; Performance

Diese Version vom 06.01.2016 kann im Internet von mehreren Nutzern (Spieler) gleichzeitig genutzt werden. Ein Spiel dauert dabei maximal 5000 Schritte oder 20 Sekunden. Wenn ein Spieler ein neuen Versuch gestartet hat, ist das Programm für andere Spieler gesperrt.

Die Programmmodule und die Datenbankstruktur wurden optimiert und besser modularisiert. So lassen sich auch andere Probleme mit dem Skripten lösen. Beispielsweise wurden die Datenbanktabellen und die Skripte für „Stefannuss“ und „Walking-the-tree“ voneinander getrennt.

Die Zugriffe auf die Datenbank wurden reduziert und die Performance auf 500 Schritte / Sekunde gesteigert.

Version 6) Optimierter Tree mit MySQL In-Memory Tabellen

Diese Version optimiert den Baum und löscht unnötige Knoten. Dadurch wird der Speicherbedarf erheblich reduziert und die Tabelle nodes enthält nur noch bis zu 60 Knoten. Die Tabelle für den Baum wird nun als MEMORY Tabelle betrieben.

Version 7)  Lösungen speichern

Die Version vom 10.01.2016 Die Performance beträgt nun 645 Schritte / Sekunde. Bei ~3 Schritten pro Knoten können nun 4,8 Millionen Knoten in ~6,2 Stunden berechnet werden.

Version 8) Trennung von Stefannuss und Walking-the-Tree

Diese Version trennt das Problem (Stefannuss) vom Walking-the-Tree Algorithmus.

Version 9)  Zwischenspeicherung in PHP Array anstatt Datenbankabfragen

Die Version vom Januar 2016 optimiert die Suche nach Lösungsmöglichkeiten, indem die Suche in PHP-Arrays anstatt mit MySQL-Abfragen durchgeführt wird.

Version 10)  In-Memory Tabellen sichern

Die Version vom 12.02.2016 sichert nach jedem Spiel die schnellen MySQL In-Memory Tabellen in MyISAM Tabellen. So können auch nach einem Neustart der Datenbank die vorherigen Spiele weiter geführt werden. Die Performance liegt weiterhin bei 645 Schritte / Sekunde.

Version 11) Normalisierung von Tabellen

Mit der Version vom 15.02.2016 wurde die Tabelle board normalisiert und eine redundante Tabellenspalte entfernt. Dadurch verbessert sich die Programmlogik, reduziert sich der Speicherverbrauch der MEMORY Tabelle geringfügig und erhöht sich die Performance auf 746 Schritte / Sekunde.

Bei theoretisch 7,5 Mio Knoten (=22.500.000 Schritte) würde diese Version zur Berechnung aller Möglichkeiten ~8,4 Stunden benötigen.

Version 12) Bugfix und Contdown

Mit der Version vom 26.07.2016 wurde ein Fehler behoben und ein Countdown für den automatischen Reload eingefügt. Es wurden keine Performanceoptimierungen eingebracht.

Lösungen

Stefannuss_Board-solvedDas Programm hat nach ~945.000 Schritten einen ersten Lösungsweg gefunden. Die Lösung unterscheidet sich nicht von der Lösung die auch der Spielehersteller angegeben hat.

Der Lösungsweg wird in Form eine Liste angegeben. Die Liste zeigt den Weg (Path) vom ersten zum letzten Knoten im Baum. Die einzelnen Knoten werden in folgender Form angegeben:

Board-ID/Color

Die Board-ID wird aus Gründen der Übersichtlichkeit immer zweistellig angegeben.

Ein zweiter Lösungsweg wurde in einem Baum mit insgesamt 3.102.576 Knoten gefunden. Auch diese Lösung beginnt mit einem grünen Stein auf Feld 13:

13/green 14/red 11/yellow 16/white 08/white 09/yellow 10/white 15/gray 05/gray 07/gray 12/green 04/green 06/green 01/red 03/red 02/yellow

Der dritte Lösungsweg wurde in einem Baum mit 3.707.613 Knoten gefunden. Auch diese Weg beginnt mit einem grünen Stein auf Feld 13:

13/green 14/red 09/yellow 11/yellow 16/white 08/white 10/white 15/gray 07/gray 04/green 05/gray 12/green 06/green 01/red 03/red 02/yellow

Ein vierter Lösungsweg wurde in einem Baum mit 4.855.779 Knoten gefunden. Auch diese Weg beginnt wieder mit einem grünen Stein auf Feld 13:

13/green 14/red 09/yellow 11/yellow 08/white 16/white 10/white 15/gray 05/gray 07/gray 12/green 04/green 06/green 01/red 03/red 02/yellow

Gibt es andere Lösung als „Grün auf die 13“ ? Am 2015-09-13 18:58:30 wurde ein fünfter Versuch gestartet, bei dem „Grün auf 13“ zufälligerweise an 6. Stelle der ersten Ebene vorkommt. Aber auch dieser Lösungsversuch beginnt wieder mit green->13:

13/green 14/red 11/yellow 09/yellow 10/white 05/gray 16/white 08/white 15/gray 07/gray 04/green 12/green 06/green 03/red 01/red 02/yellow

Dieser Lösungsbaum bestand aus insgesamt 5.693.697 Knoten, benötigte 17.078.451 Versuche (=Schritte) und eine Rechenzeit von ~21 Stunden (=75.567 Sekunden).

Mit der Version 7 wurden schließlich ALLE Möglichkeiten getestet. Der komplette Baum besteht aus insgesamt 7.395.681 Knoten und der Algorithmus benötigte insgesamt 22.187.045 Schritte. Die reine Rechenzeit betrug 39.633 Sekunden bzw. 11 Stunden. Es wurden insgesamt 14.925 Lösungswege gefunden, wobei alle Lösungen wie folgt beginnen:

13/green 14/red …

Die folgende gezippte CSV-Datei enthält alle 14.925 Lösungswege:

Die erste Spalte enthält den von der Stefannuss-Simulation gefundene Lösungsweg. Die zweite Spalte enthält den sortierten Wert der ersten Spalte. Alle Werte der zweiten Spalten sind gleich! Also gibt es nur eine einzige Lösung.

Stefannuss_BoardStefannuss_Board-solvedWenn man sich nun das Ausgangsbild und die Lösung anschaut, so erkennt man bestimmte Muster:

Die Farben mit drei Steinen/Feldern bilden jeweils ein Dreieck. Die Farbe mit den vier Steinen/Feldern bildet eine Form aus zwei Dreiecken.

 

Veröffentlicht in Kopfsache Getagged mit: ,

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

*