SameGame

Gestelltes Problem
Um 2000 herum stiess ich auf ein Spiel namens “Clickomania”, das ein Klon von SameGame ist. Dabei muss man Gruppen aneinandergrenzender Spielsteine gleicher Farbe “sprengen”. Darüberliegende Steine fallen in die entstandene Lücke und am Ende sollte möglichst kein Stein mehr übrig bleiben. Das machte Spass! Da bei mir immer so viele Steine übrig blieben, grübelte ich schon damals darüber, wie man wohl für eine gegebene Stellung eine optimale Lösung finden könnte. Als ich dann mit den Handyspielen anfing, dachte ich mir, dass es interessant sein könne, einen SameGame-Solver fürs Handy zu schreiben.

Programm
Bevor ich mit dem Solver anfangen konnte, musste ich erst einmal das Spiel selbst programmieren. Das war nicht schwer, deshalb legte ich einen Schwerpunkt auf eine saubere Animation und verschiedene Designs der Spielsteine. Dazu sollte die Anzahl der noch vorhandenen Spielsteine als Siebensegmentanzeige ausgegeben werden. Dafür besorgte ich mir eine technische Zeichnung einer solchen Anzeige und übertrug die Koordinaten der einzelnen Segmente in eine Java-Klasse. Wie immer alles Handarbeit (in den untigen Screenshots aus einem Nokia 6260-Emulator ist die Anzeige etwas zu gross, auf meinem Nokia 6300 ist das besser).

Solver habe ich dann zwei gemacht, erstmal einen dummen, der einfach nur Stellen sucht, wo man klicken kann. Danach dann einen, der für jede anklickbare Gruppe den “Nachher”-Zustand ermittelt und dann zählt wieviele “verwaiste” Steine es gibt. Die Gruppe, bei der die wenigsten Waisen anfallen, wird dann geklickt. Das ist schon recht passabel aber noch nicht optimal.

Screenshots:
   

Minimax

Gestelltes Problem
Für Spiele mit voller Information gibts den MiniMax-Algorithmus. Der Rechner probiert alle möglichen Zugmöglichkeiten aus, mehrere Halbzüge im Voraus und als Mensch verliert man dann. Der Computer ist deswegen nicht intelligent, man kann ihm nur beibringen, gewisse Spiele recht gut zu spielen. Sowas hatte ich schon früher programmiert, dabei aber jedes Spiel für sich. Diesmal sollte es Java sein, fürs Handy und der Findedenbestenzug-Programmteil von den jeweiligen Spielregeln getrennt ausgeführt werden. Ausserdem sollten die Züge animiert werden.

Programm
Ich weiss nicht, wie andere Leute Programmieren, aber bei mir ists so, dass ich eigentlich von Fehler zu Fehler stolpere. Man schreibt den Code und dann hauts nicht hin, das geht mir dann im Kopf rum, warum geht das nicht, kann doch eigentlich nicht sein. Kann aber doch sein, und wenn ich dann so einen Fehler gefunden hab’, dann freue ich mich und alles ist wieder im Lot.

Es entstand dann also eine “MiniMax-Engine” und gleichzeitig ein VierGewinnt-Spiel. Als das dann lief, hab’ ich mit “Mühle” weitergemacht. Das ist beides in einem einzigen Programm vereinigt, einen Einstellungsdialog gibts auch.

Screenshots:

Das Viergewinnt hab’ ich dann gegen zwei im Internet gefundene Viergewinnts antreten lassen. Bei gleicher Halbzugtiefe waren die dann doch eher nicht so gut. Ich weiss auch warum.

Als nächstes hab’ ich dann Dame und Räuberdame gemacht. Und Halma, 3×3. Und Schach. Und Hase und Jäger.