Gestelltes Problem
Ich glaube, ich bin ein komischer Typ. Komisch hier im Sinne von merkwürdig. Ich denke mir nämlich gern Lösungen für Probleme aus. So kam mir unlängst in einer Rätselzeitschrift meiner Mutter ein “Finde die zehn Unterschiede”-Bilderrätsel unter. Das habe ich dann mit der Digiknipse fotografiert. Jetzt müssten, in der einfachen Lösungsvariante, nur beide Bilder aus dem Gesamtbild ausgeschnitten und dann abwechselnd angezeigt werden. Dabei würden dann die Unterschiede “blinken”. Die etwas fortgeschrittenere Variante würde direkt eine Bildsubtraktion durchführen.
Meine Mutter fand diesen rechnergestützten Lösungsansatz unmoralisch und vielleicht bewegt mich auch Faulheit dazu, Probleme abschliessend lösen zu wollen.
Dieses Mal war es Minesweeper. Mir ging schon länger im Kopf herum, dass und wie man da etwas machen könnte. Ich wollte ein Programm schreiben, welches Minesweeper fernsteuert.

Algorithmus
Zunächst musste ich ein Minesweeperfenster finden und mir das Spielfeld kopieren. Dieses wurde dann nach diesen Bitmaps:
  
  
  
  
  

durchsucht. Damit hatte ich also in meinem Programm ein Abbild der aktuellen Spielsituation. Diese wurde auf zwei verschiedene Weisen analysiert.
1. Dumm
Dabei wird nach Zahlen-Zellen gesucht, die genau so viele geschlossene Zellen in ihrer Umgebung haben, wie es ihrem Zahlenwert entspricht. Wenn also eine 1er-Zelle nur ein geschlossenes Feld in ihrer Umgebung hat, wird dieses markiert. Das Markieren geschieht, indem ein rechter Mausklick mit den passenden Koordinaten an das Minesweeper-Fenster geschickt wird. Danach wird für alle Zahlenzellen ein Klick mit beiden Maustasten, der alle offensichtlich gelösten Felder aufdeckt, geschickt.
2. Schlau
Hier wird ein Ausschnitt von 4×4 Zellen über das Spielfeld bewegt. Es werden dann für alle geschlossenen Zellen alle Belegungsmöglichkeiten durchiteriert. Die Iteration sieht so aus:
int NextIt( int pos )
{
if ( pos >= ITW * ITW )
return false;

if ( IterationsZellen[ pos / ITW ][ pos % ITW ].ZelleOrig == CVALZU )
{
// Wenn sie 0 ist, auf 1 und raus
if ( IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert == 0 )
{
IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert = 1;

return true;
}
// Sonst auf 0 und nächsthöhere erhöhen
IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert = 0;
}

return NextIt( pos + 1 );
}
Rekursion muss nicht immer sein, aber hier ist sie echt lecker. Es werden dann alle möglichen Belegungen anhand der Zahlenfelder bewertet, wobei entschieden wird, ob sie eine gültige Minenverteilung darstellen. Wenn ein Feld bei allen gültigen Minenverteilungen leer ist, wird es geöffnet. Ein Feld, welches bei allen gültigen Minenverteilungen eine Mine hat, wird markiert.

Tja, trotz der Massen an Mausklicks und der vielen Bildschirmabzüge ist das Programm dann doch relativ schnell. Wieder ein Problem gelöst…

Screenshots:

Gestelltes Problem
Freecell macht mich immer ganz kirre, da hat man dann mit dem falschen Stapel angefangen und auf einmal ist nichts mehr frei, Statistik: “30%, aktuell 17-mal verloren”. Das ist Stress pur!
Warum kostbare Freizeit verschwenden, wenn man solche Probleme per Programm lösen kann?

Algorithmus
Vor der Frage nach dem Algorithmus stand die nach dem Aussehen der Anwendung. Einfach nur Text “Zug von Stapel drei nach vier.” erschien mir nicht ausreichend. Deswegen habe ich erst einmal alle Karten bei Freecell geklaut und als einzelne .bmp-Dateien abgelegt. Da ich mittlerweile auch ganz gern mal den Borland-C++-Compiler benutze, ging der Teil mit der Anzeige der Karten auf einem grünen Spieltisch relativ schnell. Wie in Freecell aus der ausgewählten Spielnummer die Anfangsstellung entsteht, habe ich noch nicht ergründen können. Deshalb wurde das Spiel 21145 fest im Programm verdrahtet. Jetzt mussten ja nur noch zu einer Stellung alle möglichen Züge ermittelt und dann für jeden Zug rekursiv das Gleiche getan werden, bis man auf eine Stellung stiess, wo alle Karten abgelegt waren. Pustekuchen. Die ersten Läufe dieser Version schafften über 100.000 Stellungen, ohne zu einer Lösung zu kommen. Bei Freecell gibt es nämlich reversible Züge. Deshalb wurde eine Liste der schon besuchten Positionen hinzugefügt. Damit konnten auch andere Formen der Stellungswiederholung ausgeschlossen werden. Trotzdem hatte ich ein Programm welches es schaffte in 10 Sekunden 200-mal zu verlieren, aber trotzdem nicht zur Lösung fand. Das lag daran dass es bei Freecell sehr viele Stellungen gibt. Es war notwendig, dem Programm auf der Ebene der möglichen Züge eine Richtung vorzugeben. Statt alle Zugmöglichkeiten wahllos durchzuprobieren, wurde für jeden Zug eine Bewertung berechnet. Die Züge mit der besten Bewertung wurden dann als erste ausprobiert. Eine gute Stellung hat folgende Eigenschaften: möglichst viele freie Plätze, möglichst gut sortierte Stapel, keine eingeklemmten Karten mit kleinem Wert. Damit gings dann. Hat ja auch immerhin fünf Tage gebraucht.
So sieht das dann aus:

(451 Positionen getestet, Rekursionstiefe 318, gemerkt 450 Stellungen, bis jetzt 38-mal verloren)