SameGame

SameGame, auch The Same Game ist ein populäres Computer-Puzzlespiel, das in verschiedensten Varianten auf einer Vielzahl von Plattformen implementiert wurde. Es gibt Versionen für Handys, graphische Taschenrechner, Spielekonsolen und für nahezu jede Form von Computern im eigentlichen Sinne. Häufig wird das Spiel als Freeware oder unter einer Open-Source-Lizenz verbreitet.

Spiel

Ein Spielzug in SameGame.

Bei SameGame ist ein rechteckiges Spielfeld mit Spielsteinen verschiedener Sorten gefüllt. Die Steine sind in Spalten und Zeilen angeordnet. Das Spiel ist ein Spiel für Einzelspieler. Der Spieler versucht, möglichst viele Steine vom Spielfeld zu entfernen. Es lassen sich nur solche Steine entfernen, die an andere Steine derselben Art angrenzen. Entfernt werden dann alle gleichartigen aneinander angrenzenden Steine gemeinsam. Steine, die sich oberhalb der entfernten Steine befinden, fallen herunter, bzw. rücken spaltenweise von rechts auf, wenn eine ganze Spalte frei wird. Dadurch entstehen durch fast jeden Zug des Spielers neue Steinkombinationen (außer wenn sich die entfernten Steine alle am oberen Rand der Steinmenge befunden haben). Je nach Regelvariante erhält der Spieler für jeden entfernten Stein Punkte oder in Abhängigkeit von der Anzahl der auf einen Schlag entfernten Steine. Gebräuchlich sind auch Bonussysteme. In einigen Varianten wird auch die benötigte Anzahl an Zügen bewertet, die zum Erreichen eines bestimmten Punktestandes (oder des vollständigen Abräumens des Spielfeldes) notwendig war.

Typische Varianten des Spiels ordnen drei bis fünf Steinsorten zufällig in zehn bis zwanzig Spalten und acht bis zwölf Zeilen an. Manchmal ist dies auch durch den Spieler einstellbar. Der Schwierigkeitsgrad steigt mit der Anzahl der Steinsorten.

Durch die verbreitete Verwendung von bunten und manchmal kitschigen Bildern für Spielsteine und Hintergründe, begleitet von Animationen und untermalt von verschiedenen Soundeffekten hat das Spiel häufig den Charakter eines typischen "Daddelspiels".

Theorie

Eine typische Ansicht in der Ausgangsstellung

Trotz der einfachen Regeln ist SameGame ein anspruchsvolles, abstraktes Logikspiel, das auch in komplexitätstheoretischen Abhandlungen der Theoretischen Informatik untersucht wurde. Bereits die Frage, ob ein Spielfeld vollständig geleert werden kann, ist, für nicht triviale Fälle, NP-vollständig (vermutlich sehr schwierig zu lösen). Ein Spielfeld in einer möglichst kurzen Zugfolge leerzuräumen ist ein schwieriges Optimierungsproblem, das aufgrund der NP-Vollständigkeit nach heutigem Kenntnisstand in akzeptabler Rechenzeit nur heuristisch gelöst werden kann. SameGame eignet sich somit auch, neue Optimierungsverfahren zu testen. Interessant ist dabei die Tatsache, dass im Gegensatz zu anderen NP-vollständigen Problemen (z. B. Problem des Handlungsreisenden, engl. Traveling Salesman Problem), jeder Spielzug und damit jeder Optimierungsschritt nicht umkehrbar alle folgenden Züge beeinflusst, und damit u. U. bereits im ersten Schritt über den Erfolg des gesamten Optimierungsversuchs entschieden wird. Gängige heuristische Lösungsstrategien, die versuchen, durch lokale Optimierungen globale Minima zu erzielen stoßen deshalb auf Schwierigkeiten (z. B. simulierte Abkühlung).

SameGame unterscheidet sich von einigen anderen einfachen Computerspielen, wie z. B. Tetris, dadurch, dass es zur Klasse der Spiele mit vollständiger Information gehört, d. h. zu jedem Zeitpunkt des Spiels ist dem Spieler der Zustand des Spiels bekannt und alle möglichen zukünftigen Stellungen lassen sich aus diesem Zustand ableiten, ohne dass Zufallselemente einwirken. Spiele wie Schach und Go gehören ebenfalls zu dieser Klasse von Spielen.

Im Gegensatz zu guten Lösungsverfahren ist das Spiel selbst einfach zu programmieren und eignet sich deshalb auch gut für die Ausbildung.

Geschichte

SameGame wurde 1985 ursprünglich als 'Chain Shot' von Kuniaki Moribe erfunden und in einem japanischen Computermagazin verbreitet. Unter dem Namen SameGame erschien es im Jahr 1992 für Unix in einer Version von Eiji Fukomoto. Das Spiel ist auch unter dem Namen "Clickomania" (eine Freeware-Version) populär geworden. Bei einigen Pocket PCs ist es unter dem Namen "Jawbreaker" vorinstalliert.

Weblinks

• More Games of No Chance- Das Buch mit dem Artikel über die Komplexität von SameGame (unter dem Namen Clickomania)
• klickklack.org - Im Browser spielbare JavaScript-Version (unter GPL) mit Highscore
• Im Browser spielbare Java-Version (Memento vom 17. Januar 2008 im Internet Archive) mit Sourcen (unklare Lizenz - aber die Sourcen sind direkt im Browser betrachtbar)
• Mah-jongg.ch - Same Game: Im Browser spielbare Version in DHTML, kein Plugin nötig
• Cube Crush: Im Browser spielbare ActionScript 3-Version, Flash Player notwendig