Runaway Robot - Ein Lösungsansatz

Wer die Seite hacker.org kennt, hat auch vielleicht schon etwas vom Spiel "Runaway Robot" gehört. Es ist eines der auf dieser Seite angebotenen Spiele, die mit Hilfe eines Bots gelöst werden können. Im Folgenden will ich meine Lösung in den Kernpunkten erklären.

Bei Runaway Robot handelt es sich um Pfadfindungsproblem, bei dem es einem Roboter gelingen soll, über einen wiederholt zu durchlaufenden Pfad durch ein Minenfeld zu spazieren, ohne dabei auf eine Miene zu treten.

Das Ziel des Roboters liegt in den grünen Feldern.

Der Pfad besteht aus Einzelschritten nach unten oder nach rechts und hat eine vorgegebene Mindest- und Maximallänge (hier 3 und 4).

Hat man sich für einen Pfad entschieden durchläuft diesen der Roboter von vorne nach hinten und fängt dann wieder von vorne an, solange nicht auf eine Miene getreten oder nicht am Ziel angelangt ist (hier führt der Pfad DDR - lies "down down right" - zum Ziel).

Mit ansteigendem Level wird das Feld größer und die Anzahl der Möglichkeiten für den Pfad wird erheblich größer.

Beim maximalen Level 512 hat das Spielfeld z.B. Abmessungen von 619*619 = 383161 Felder und der Pfad besitzt eine Minimallänge von 207 und eine Maximallänge von 361 Schritten.

D.h. es ergeben sich bei der minimalen Schrittanzahl für den Pfad alleine 2^{207} \approx 2,056880697 \cdot 10^{62} Möglichkeiten. Mit reinem Durchprobieren dauert das Finden der Lösung deshalb relativ lange. (Unter der Annahme, dass für jede Möglichkeit eine Sekunde benötigt wird, wären das   \approx 6,5 \cdot 10^{54} Jahre).

Es müssen also Überlegungen getroffen werden, um einen gültigen Pfad in erlebbarer Zeit zu finden.

Schreibe einen Kommentar

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