Ruprecht Karls Universität Heidelberg

Fun QuoVadis

From Informatik-Vorkurs
Jump to: navigation, search


Weil es Spass macht: Das Schiebespiel 'Quo Vadis' lösen

Manche von Ihnen kennen vielleicht das Schiebespiel 'Quo Vadis': Auf einem 4×5 Einheiten großen Spielfeld liegen zehn Blöcke unterschiedlicher GrĂ¶ĂŸe, darunter ein 2×2 großer Block oben in der Mitte (im Bild gelb). Es sind nur 2 einzelne Felder frei. Durch Verschieben der Blöcke soll der große Block zum 'Ausgang' bugsiert werden, der sich unten in der Mitte befindet. Zu Beginn des Spiels sieht die Anordnung so aus:

Startposition des 'Quo Vadis' Spiels

Das sieht gar nicht so schwer aus, hat es aber in sich! Wir wollen ein Programm schreiben, das dieses (und Ă€hnliche) Spiele lösen kann. ZunĂ€chst wollen wir einfach nur irgendeine Lösung finden. Aber dann suchen wir natĂŒrlich die (eine) kĂŒrzeste Lösung! Das ist keine leichte Aufgabe. Sie erfordert solide C++ Kenntnisse und scharfes Nachdenken!

Wie kann man das lösen?

Wir können unserem Programm keine 'intelligente' Strategie beibringen (z.B.'der große Block muß am horizontalen 2×1 Block vorbei, also muss der auf die Seite geschoben werden...'). Wir lösen das Problem also 'brute force' durch Ausprobieren:

  1. Wir beginnen mit dem Startspiel (so wie oben gezeichnet).
  2. Wir prĂŒfen, ob wir fertig sind, also ob der große Klotz unten in der Mitte liegt.
  3. Wenn nicht, suchen wir alle möglichen ZĂŒge, die es von der aktuellen Position aus gibt (hier: 4 ZĂŒge).
  4. Wir fĂŒhren alle möglichen ZĂŒge der Reihe nach durch und erhalten jeweils eine neue Spielposition. Mit dieser Position beginnen wir bei Schritt 2.

Wir probieren also durch rekursive Aufrufe einer Methode solve() alle Möglichkeiten durch. Es wird schnell klar, dass diese Methode so nie endet, denn man kann ja einen Block immer wieder vor- und zurĂŒck schieben. Wir mĂŒssen daher in jeder neuen Spielposition ĂŒberprĂŒfen, ob wir diese Position schon mal hatten. Dann brauchen wir nicht weiter zu machen. Da es auf dem Spielfeld nur endlich viele Positionen gibt (wenn auch einige...) sind wir sicher irgendwann fertig.

Um diesen wichtigen Vergleich machen zu können benötigen wir eine globale Datenstruktur, in der wir alle bearbeiteten Spiele (Positionen) abspeichern. Wichtig ist hierbei, dass zwei Spiele schon gleich sind, wenn an gleichen Positionen gleich geformte Steine liegen - wir verlangen nicht, dass die Steine alle genau an den selben Positionen liegen (von den 1×2 Steinen z.B. gibt es 4 StĂŒck, sagen wir A,B,C,D. Nun ist es egal, ob in der Anfangsposition A links vom 2×2 Klotz liegt und B rechts oder umgekehrt.). Das macht das Programm etwas komplizierter, aber die Suche wesentlich schneller!

Wir mĂŒssen den obigen Ablauf also verĂ€ndern und nach dem zweiten Schritt prĂŒfen, ob es das Spiel schon gab. Wenn nicht, mĂŒssen wir es neu in die Struktur eintragen.

Wenn wir das so programmieren, bekommen wir heraus ob es eine Lösung gibt und finden ggf. irgendeine. Diese ist aber meist nicht optimal. Stellen Sie sich den einfachen Fall vor, dass im Feld nur der gelbe Klotz liegt. Diesen können wir auf direktem Weg in 3 ZĂŒgen zum Ausgang schieben, es geht aber auch im Zickzack mit mehr ZĂŒgen. Welche Lösung unser Programm findet hĂ€ngt davon ab, in welcher Reihenfolge die möglichen ZĂŒge ausprobiert werden. Probieren wir es z.B. immer erst nach unten, dann finden wir sofort die beste Lösung. Probieren wir z.B. rechts / links / oben / unten, dann finden wir einen umstĂ€ndlichen Zickzackweg. Wie kann man nun die kĂŒrzeste Lösung finden (genauer: eine kĂŒrzeste Lösung, denn es kann mehrere gleich gute Lösungen geben)? Eine Möglichkeit besteht darin, zu jeder abgespeicherten Spielposition in unserer Liste zu vermerken, wie viele ZĂŒge bis dahin nötig waren. Wenn wir dann beim Vergleich eine Position finden, und wir dorthin mit weniger ZĂŒgen gekommen sind, dann ersetzten wir diese. Gleichzeitig mĂŒssen wir uns noch merken, wie (also z.B. von welchem VorgĂ€nger aus) wir in diese Position gekommen sind, um spĂ€ter den Weg rekonstruieren zu können.

Eine mögliche Datenstruktur

Um eine gute Datenstruktur anzulegen und sinnvolle Methoden festzulegen mĂŒssen wir ĂŒberlegen, was wir zur Implementierung der obigen Strategie brauchen:

  • Wir mĂŒssen die Positionen aller Blöcke festlegen können
  • Wir mĂŒssen fĂŒr einen Block prĂŒfen können, ob man ihn nach rechts / links / oben / unten schieben kann
  • Wir mĂŒssen ihn schieben können, also das Spiel geeignet verĂ€ndern können
  • Wir mĂŒssen neue Spiele dynamisch erzeugen können
  • Jedes Spiel muss wissen, wie viele ZĂŒge es von der Startposition weg ist.
  • Wir mĂŒssen Spiele vergeichen können. Dazu erzeugen wir aus dem Spiel einen Hash-Wert (hier einfach eine Zahl), der so gemacht ist, dass er fĂŒr gleiche Spiele identisch ist. Es mĂŒssen dabei nur gleich geformte Blöcke an gleichen Positionen liegen, s.o.

Hier ist ein vereinfachter Vorschlag fĂŒr eine Datenstruktur:

struct TXY {int x, y;};
typedef TXY TDirection;
 
class TBlock { public: TXY size; };
 
class TGame {
public:
             TGame         (TGame * = NULL);         // constructor
  void       SetBlock      (int, TBlock * const, TPos); // set (existing) ith entry. can be used in Move
  void       AddBlock      (TBlock * const, TPos);   // add a new block
  bool       IsSolved      (void);
  bool       CanMove       (int i, TDirection Dir);  // can block i move to Dir?
  void       Move          (int i, TDirection Dir);  // do the move
  void       Solve         (void);                   // here it happens!
  THashValue GetHash       ();                       // calculate a hash value
  void       BuildFromHash (THashValue);             // reconstruct gamne from
 
  TPos       BlockPos  [NBLOCK];                     // xy-Positions of the blocks
  TBlock *   BlockType [NBLOCK];                     // remember the shape of the blocks
  TBlock *   BlockPt   [NX][NY];                     // pointers to blocks (or NULL)
  int        CoveredBy [NX][NY];                     // index of covering block, -1 for free
  int        Level;                                  // number of moves up to this game
  int        nblock;                                 // number of blocks actually used
  TGame *    parent;                                 // game from which we came
};
 
std::ostream & operator << (std::ostream &, TGame *);

ErklÀrungen

  • Da wir mehrere (x,y) Paare benötigen (Position, BlockgrĂ¶ĂŸe, Zugrichtung) definieren wir eine einfache TXY Struktur. Diese nehmen wir dann auch fĂŒr TDirection etc. Wir können AbkĂŒrzungen einfĂŒhren wie const TDirection UP = TDirection( 0, 1);
  • Ein TBlock enthĂ€lt nur die GrĂ¶ĂŸe des Blocks. Hier könnten wir auch eine Farbe o.Ă€. ablegen. Im Hauptprogramm definieren wir vier (konstante) Blöcke, die wir dann auf dem Spielfeld benutzen, z.B.: TBlock BLOCK_2x2 = TBlock( TXY(2, 2), ...);
  • NBLOCK ist die maximale Anzahl Spielsteine und nblock die Zahl tatsĂ€chlich vorhandener Steine.
  • In parent merken wir uns, aus welcher Position wir kamen. Das muss beim Erzeugen eines neuen Spiels gemacht werden.
  • Um die Position der Steine abzuspeichern, gibt es viele Möglichkeiten. Im gezeigten Vorschlag wird das redundant gemacht, um spĂ€ter effizient zu sein:
    • BlockType[i] enthĂ€lt die Form des i-ten Blocks (das kann im Prinzip static deklariert werden). Wir speichern hier einen Pointer auf die konstanten TBlocks BLOCK_1x1 etc. ab.
    • Die Position ist in BlockPos[i] als TPos (alias TXY) abgelegt. Der Nullpunkt jedes Blocks ist dabei unten links.
  • Mehr Info ist eigentlich nicht nötig. Um jedoch beim Ziehen schneller herauszufinden, ob ein Feld frei ist, gibt es zwei weitere Arrays:
    • BlockPt[NX][NY] vermerkt fĂŒr jedes Feld, ob da ein Block liegt und wenn ja welche Form er hat, das brauchen wir zur schnellen Ermittlung des Hash Wertes. Wir nutzen dazu wieder einen Pointer auf den entsprechenden Blocktyp. Bei einem vollen Spiel enthalten also 10 der 20 Array-Elemente Pointer of die TBlocks, die anderen 10 Elemente sind NULL.
    • CoveredBy [NX][NY] gibt an, ob ein Feld belegt ist, das brauchen wir, um schnell zu prĂŒfen, ob wir schieben dĂŒrfen. Ein leeres Feld markieren wir mit -1, bei einem belegten Feld tragen wir den Index des Blocks ein, der es ĂŒberdeckt. Das ist fĂŒr das Ausdrucken sehr nĂŒtzlich.
  • GetHash() ist tricky. Diese Funktion soll eine Zahl erzeugen, die eindeutig ein Spiel charakterisiert. Man kann z.B. das BlockPt - Array geschickt abspeichern: Es hat 20 Felder, und fĂŒr jedes Feld gibt es ja nur 5 Möglichkeiten: kein Stein, Typ 1...4. Es gibt also 5^20 Möglichkeiten, das passt in ein 64 Bit Integer (stellen Sie sicher, dass Ihr Integer so lang ist. Trick: long long int)! Arbeiten Sie in einem 'FĂŒnfersystem', in dem Sie in jeder von 20 Stellen ein Feld abspeichern, also F0 + 5*F1 + 5*5*F2..., wobei Fi eben 0-4 sein kann und die Belegung des i-ten Feldes angibt. Rechnen Sie die FĂŒnferpotenzen nicht einzeln aus, sondern klammern Sie F0 + 5 * (F1 + 5 * (...)).

Tipps zur Implementierung

Beginnen Sie mit dem Konstruktor und dem Ausgabeoperator. Definieren Sie sich dann ein paar Blöcke und implementieren Sie AddBlock() bzw. SetBlock(). Probieren Sie das aus. Dann kommen IsSolved, CanMove und Move. Beginnen Sie mit einem einfachen Spiel, in dem z.B. nur oben ein 2×2 Stein sitzt. Implementieren Sie jetzt die Hash Funktion und das Inverse und probieren Sie das mit ein paar SpielstĂ€nden aus. Legen Sie nun eine globale map (aus der stl) an, in der die gefundenen Spiel gespeichert werden:

typedef long long int THashValue;                  // bei mir sind das 64 Bit
struct TInfo {int level; THashValue predecessor;}; // Info fĂŒr jedes gespeicherte Spiel
typedef std::map <THashValue, TInfo> TGameMap;     // in solch einer map werden die Spiele abgelegt
TGameMap   GameMap;                                // hier wird die map deklariert

Implementieren Sie jetzt Solve(). Rufen Sie Solve() so lange rekursiv auf, bis Sie auf eine Lösung treffen, oder Sie ein bekanntes Spiel in GameMap antreffen. Damit sollten Sie schon EINE Lösung finden (beginnen Sie mit einfachen Spielen, bei Quo Vadis hat der Rechner schon ganz schön zu tun...)

Und zur Krönung nutzen Sie jetzt die Level-Information, die angibt, wieviele ZĂŒge Sie vom Anfangsstand weg sind (diese mĂŒssen Sie richtig verwalten!). Merken Sie sich in GameMap das Level, in dem das jeweilige Spiel auftrat und ersetzen Sie es, wenn Sie wĂ€hrend der Rekursion schneller zum gleichen Spiel gekommen sind. Als Anhaltspunkt hier die Struktur von Solve(), mit ein paar LĂŒcken, um nicht alles zu verraten:

void TGame::Solve(void)
{
  THashValue h = GetHash();                   // Hash wert ausrechnen
 
  TGameMap::iterator it = GameMap.find(h);    // Schon in der map?
 
  if (existiert) {                            // hier muss man den iterator abfragen
    if (Wert aus map ist besser)
      return;                                 // nicht weitermachen
    else
      it->second.level = Level;               // sonst: ersetzen mit aktuellem Game
      it->second.predecessor  = parent ? parent->GetHash() : 0;
  } else {                                    // existiert nicht:
    GameMap[h] = ...;                         // neuen Eintrag machen
  }
 
  if (IsSolved()) {                           // Ist dieses Game eine Lösung?
    if (Level < BestLevel) {                  // Beste Lösung merken
      BestLevel = Level;
      BestHash  = GetHash();
    }
    return;                                   // und fertig
  }
 
  if (Level >= BestLevel) return;             // TRICK zur Beschleunigung  (s. unten)
 
  for ... alle Blöcke i und Richtungen dir durchprobieren... {
    if (CanMove(i,dir)) {
      TGame * gnew = new TGame(this);        // neues Game anlegen
      *gnew = *this;                         // als Kopie des aktuellen Games
      gnew->parent = this;                   // parent brauchen wir im neuen Game 
      gnew->Level++;                         // um dem Weg zu speichern
      gnew->Move(i,dir);                     // ziehen
      gnew->Solve();                         // Hier kommt die REKURSION
      delete gnew;
    }
  }
}

Optimierungen

Zur Optimierung kann man sich (in einer globalen Variable 'BestLevel') merken, in welcher Tiefe eine Lösung gefunden wurde, und alle weiteren Suchen unterhalb diese Tiefe sofort abbrechen (denn wir wollen ja kurze Lösungen finden). Sobald eine bessere Lösung gefunden wurde, reduzieren Sie diese Variable. Ohne diese Optimierung ist Quo Vadis kaum zu lösen...

Man könnte auch darĂŒber nachdenken, dann unnĂŒtze Elemente in der map (also solche mit Level > BestLevel) zu löschen, um die map zu verkleinern und die Suche zu beschleuningen. In einer map ist die Suche jedoch sehr effizient (O(log n)), das Löschen erfordert jedoch ein internes Umstrukturieren. Bei mir hat das daher nichts gebracht.

Auf meinem Laptop dauert die Lösung mit meinem 'besten' Programm etwa 3 Minuten.

Personal tools