Rasende Roboter für Informatiker und so

[peer]

Hi,
gestern spielten wir Rasende Roboter. Anschliessend meinte der Informatik-Student in unserer Runde, dass er überlegt, wie man einen Algorythmus zum Löaen der Probleme programmieren könnte. Ich meine, ich hätte irgendwo gelesen, dass sich bereits eine Gruppe Informatiker mit diesem POroblem auseinandergesetzt hat (oder wars eine Diplomarbeit? Roman, deine? ;-)
Weiss jemand mehr?
CIAO;
Peer

[Ingo Kasprzak]

Hi peer!
Ein Forumsteilnehmer namens "Campus" (campus@zumcampus.de) schrieb hier mal, dass ein Freund von ihm (Mathematikstudent) eine Diplomarbeit darüber schreiben will.
Sollte er Dein Posting nicht zufällig auch lesen, kannst Du ihm ja mal eine EMail schreiben!
Ciao, Ingo

[Jürgen Valentiner-Branth]

Hallo Peer,
auf der "Linken Seite, Teil 2" von Spielbox-Online, unter "Online-Spiele" steht eine rasende Computer-Version der Roboter zur Verfügung.
Habe sie noch nicht gespielt, aber vielleicht hilft´s dir ja weiter.
Spiele Grüße, Jürgen

[Carsten Wesel]

Das ist allerdings nicht wirklich ein Computerspiel, sondern nur eine kleine Spielerei.
Gruß Carsten (der zugibt auch schon auf der Seite gewesen zu sein)

[Campus]

Hi,
es stimmt, ein Freund meinerseits schreibt seine Diplomarbeit zu diesem Thema. Er ist inzwischen soweit, dass er die Tiefensuche implementiert hat, die natuerlich schweinelangsam ist (ab Schrittzahl 8 wird die Zeit eher in Stunden als in Sekunden gemessen). Zusaetzlich schreibt er an einem Branch&Bound Verfahren, das auch hervorragend arbeitet. In der Regel bekommt er da gute Ergebnisse nach 250ms. Das Problem ist, das sich nicht beweisen laesst, das die gefundene Loesung auch die beste ist. Auch wenn es in 99 von 100 Faellen der Fall ist. Nebenbei arbeitet er noch an der graphischen Oberfläche, das es also wirklich so aussieht wie das Spiel :-) und das man schrittweise die Loesung gezeigt bekommen kann. Sieht imho sehr gut aus....
Ciao
Campus

[peer]

Hi Campus,
könntest du deinen Freund fragen, ob er mir seine email-Adresse mailt? Ich würde die dann an meinen Freund weiterleiten. Dann können die Informatiker untereinander fachsimpeln...
ciao,
Peer

[Attila]

Tja, da man nicht weiss was die anderen machen ist das wohl ziemlich schwierig. Das ganze ist nicht deterministisch und manchmal sind die laengere Wege einfach besser als kuerzere, da man nicht so stark auf bestimmte Kartenkombinationen angewiesen ist.
Ich behaupte man das ich gegen jedes Programm gewinne (einfach so ! ;-) ) !
Ausserdem sind Programme nicht so gemein wie ich ! ;)
Gruss
Atti

[Attila]

Ohmann ...
Da bin ich mal wieder im falschen Film. Meiner hiess "RoboRally" (wie auch sonst) ...
Klar ist der Rasende Roboter deterministisch. Man braucht einfach "nur" a'la "brute force" Eiskalt alles durchrechnen. Wenn man dann noch ein Limit in der Tiefe setzt (z.B. 30 Zuege), dann geht das flux. Hat man eine Lösung mit X Zuegen gefunden, begrenzt man die Tiefe auf X-1 und rechnet weiter.
Einzig die Darstellung des Brettes macht etwas Programmierarbeit.
Atti

[Campus]

denn in der Regel sind pro Stellung 8 Zuege erlaubt, was in Schrittiefe 10 bereits 1*10^9 Variationen bedeutet. Da wirst Du mit BruteForce nicht besonders weit kommen... :-)
Ciao
Campus

[Attila]

Brute Force rechnet man das in ein paar minuten durch. Probiere es aus.
Atti

[Campus]

Hab ich. Leider geht das eben nicht in ein paar Minuten (es sei denn Du hast einen Cluster zu hause stehen), denn es geht nicht nur um das Durchlaufen der virtuellen Baumstruktur, sondern Du musst auch noch den ganzen Kram mitschleppen, welcher Roboter sich woher bewegt hat etc....
Ciao
Campus

[Hartmut]

Sorry, das ist ja echt lächerlich. Ich wusste garnicht, wie "billige" Diplomarbeiten es heute so gibt. RR ist doch just-another-backtracking-case - habe ich schon zig-fach implementiert. In welchem Fach gibt's denn sowas? Etwa Informatik An welcher Uni?
Ein Algorithmus für RR ist doch nun wahrlich keine große Kunst. Sicher ist das nichts für Gelegenheitsprogrammierer, aber wenn man das Modell so aufzieht, dass Erprobung von Variationen im Baum unterbleibt, ist die Baumtiefe überschaubar, erst recht bei Vergabe eines Zuglimits. Das juckelt doch jeder PC in ein paar Minuten durch.
Hartmut (Informatiker - löst RR dennoch lieber nur mit dem Kopf)

[peer]

Hi,
wenn ich den Freund von Campus (der hat sich gemeldet und ich habe ihn an meinen Bekannten weitergeleitet) richtig verstanden hat, geht es in seiner Arbeit wohl allegemein über Problemlössungsalgorythmen und RR ist nur ein Anwendugsbeispiel.
Ob "Brute Force" tatsächlich der beste (schnellste) Algorythmus ist, wage ich mal zu bezweifeln (Pro Zug gibt es ca. 4*4=16 Möglichkeiten, folglich 16^n Möglichkeiten bei n Zügen). Allerdings bin ich kein Informatiker und mag mich daher verschätzen.
ciao,
Peer

[hartmut]

Hallo Peer,
>>> wenn ich den Freund von Campus (der hat sich gemeldet und ich habe ihn an meinen Bekannten weitergeleitet) richtig verstanden hat, geht es in seiner Arbeit wohl allegemein über Problemlössungsalgorythmen ... <<<
Das kann ich dann schon eher nachvollziehen. Ein RR-Algorithmus alleine wäre keine Kunst.
>>> Ob "Brute Force" tatsächlich der beste (schnellste) Algorythmus ist, wage ich mal zu bezweifeln (Pro Zug gibt es ca. 4*4=16 Möglichkeiten, folglich 16^n Möglichkeiten bei n Zügen). Allerdings bin ich kein Informatiker und mag mich daher verschätzen. <<<
Im ersten Ansatz ist das richtig, aber ein guter Algorithmus berücksichtigt die spezifischen Modelleigenschaften und geht über dumpfes Ausprobieren hinaus. So sollte man im Baum die Abhängigkeit bzw. Unabhängigkeit von Teilzügen berücksichtigen. Ob man erst A nach rechts, dann B nach unten oder umgekehrt zieht, ist unter leicht zu bestimmenden Voraussetzungen (A versperrt B den Weg usw.) voneinander abhängig oder nicht. Bei unabhängigen Teilzügen genügt somit das Verfolgen genau einer Kombination daraus. Die unterdrückten Kombinationen unabhängiger Teilzüge interessieren dann nicht mehr, da sie zum selben Ergebnis führen.
Hier noch etwas Stoff für unseren Diplomanden (obwohl ich glaube, soweit ist er auch ohne mich gekommen). Eine mögliche Implementierung dieser Idee: Jeder Roboter hat in jeder der vier Richtungen einen Status, ob er in diese Richtung noch ziehen soll oder nicht. Zu Beginn steht alles auf JA, außer bei den Richtungen, bei denen der Roboter schon direkt an der Wand oder neben einem anderen Roboter steht. Wenn ein Roboter zieht, setzt man den Status der Richtung, aus der er kommt, auf NEIN (vermeidet hin-und-herziehen) und auch den der Richtung, in die er gegangen ist (er steht ja nun vor der Wand oder einem anderen Roboter). Die seitlichen Richtungen gehen auf JA, sofern sie nicht ebenfalls durch Wand oder anderen Roboter direkt blockiert sind.
Der Richtungs-Status anderer (!) Roboter wird ggf. auf JA aktualisiert, wenn er auf NEIN stand und der andere Roboter (nennen wir einen beliebigen anderen Roboter B - der gezogene Roboter ist A) folgende Bedingungen erfüllt: 1. B kann das Startfeld oder Zielfeld von A erreichen bzw. überqueren (A versperrt B auf dem Zielfeld den Weg, bzw. gibt diesen auf dem Startfeld frei). Ein Zug von B sieht ja jetzt anders aus als vorher (mehr oder weniger weit). 2. Für alle überquerten Felder auf dem Weg von A wird geprüft, ob B (d.h. irgendein anderer Roboter) dieses Feld erreichen und genau darauf stehenbleiben kann (seitliche Wand bzw. anderer Roboter begrenzt den Zug). Diese Richtung von B erhält dann den Wert JA, denn wenn B direkt auf ein von A überquertes Feld zieht, wird ein Rückzug von A wieder mit JA aktiviert (siehe 1. Bedingung), da A ja dann nicht den ganzen Zug zurücknimmt, sondern nur einen Teil. Dadurch ergibt sich ein neuer Verlauf der Roboterwege.
Der Rest ist dann das, was Du Brute-Force nennst. Probier auf jeder Zug-Ebene nacheinander alle Richtungen aller Roboters aus, aber ziehe nur, wenn der Status der Kombination Roboter-Richtung auf JA steht. Die Kombinationsvielfalt mag ich nicht bestimmen, es dürfte aber ein verschwindend geringer Bruchteil Deiner Rechnung sein. Vielleicht gibt es ja noch sinnvollere Ansätze als meinen.
So man im Backtracking-Verfahren einen Zug zurücknimmt, muss man natürlich den Zustand aller Status-Variablen auf den Wert zurücksetzen, der vorher galt (für ALLE Roboter!). Die gerade erprobte Richtung des gezogenen Roboters wird natürlich auf NEIN gesetzt (mit dem ist man ja jetzt durch).
Der Algorithmus braucht sinnvollerweise eine Zugbegrenzung, da ich ad hoc irgendwelche endlosen "Kreisbewegungen" mehrerer Roboter nicht ausschließen möchte. Nach gefundener Lösung (steht Roboter X auf Zielfeld Y?) kann man die Suchtiefe auf die gerade gefundene Anzahl Züge begrenzen, was den Algorithmus ggf. beschleunigt (jenachdem, wie schnell ein Optimum erreicht werden kann, was davon abhängt, ob man zufällig mit dem "richtigen" Zug beginnt oder nicht). Ohne Lösung muss man das vorgegebene Limit erhöhen.
Allen Hobby-Programmierern viel Spaß am Tüfteln
Hartmut

[Campus]

Hi,
Du hast mit vielen Dingen recht, vergisst aber leider ein entscheidendes Detail. Es ist richtig, das in jeder Stellung nicht 16 sondern 8 Zugmoeglichkeiten existieren: jeder der vier Roboter kann maximal in zwei Richtungen abbiegen aber nicht in die Herkunftsrichtung zurueck. Dummerweise gibt es bei RR ein wichtiges Detail: ein Zug laesst sich nicht bewerten. Zwar kann man natuerlich bestimmen, wieviele Zuege man nun ins Ziel braucht, aber das ist keine Aussage, welcher Zug der anderen Roboter diese Zahl verkleinert...
Aus diesem Grunde ist es durchaus nicht trivial.
Ciao
Campus

[Hartmut]

Hallo "Campus",
wenn Du meine Ausführungen gelesen hast, dann wirst Du merken, dass es sehr wohl Sinn machen kann, einen Roboter zurückzuziehen bzw. weiterzuziehen, wenn der vorher blockierende Roboter sich entfernt hat. Natürlich macht das im unmittelbar nächsten Zug desselben Roboters keinen Sinn, kann aber durch Bewegung anderer Roboter später wieder sinnvoll werden.
Die Methode des Backtracking (für Laien: systematisches Ausprobieren, für Informatiker: Schaffen einer rekursiven Invariante des Modells) ist letztendlich stupides Ausprobieren. Alle gemachten Ausführungen und evtl. anzuwendende Heuristiken ("Es macht keinen Sinn hier weiterzumachen weil....") schränken nur den Suchraum ein, um den Algorithmus in endlicher Zeit zu terminieren, sie ändern jedoch nicht die Qualität des Verfahrens.
Was Du ansprichst, nämlich einen "guten" Zug im Hinblick auf das Ziel zu finden erfordert Bewertungsmethoden, die selbst in modernen Schachprogrammen aufwendige Bibliotheken benötigen und dann den Makel der möglichen Suboptimalität haben (ist der beste Zug auch wirklich drin?). Darum sollte es hier doch aber nicht gehen, oder?
Gefragt war doch nach einem Verfahren zur Lösung des Problems. Wenn ich ein hunderprozentig zielführendes Verfahren in endlicher Zeit zur Verfügung habe, brauche ich mich nicht mit Schätzungen und Bewertungen abgeben. Oder aus der Praxis der Optimierungsprobleme: Wenn in einem Optimierungsproblem Operations-Research-Methoden anwendbar sind, brauche ich keine Simulationsmodelle. Es ist letztlich ein Frage der Komplexität und Machbarkeit. Unter diesen Aspekten ist RR ein einfaches Problem und bedarf m.E. keiner "Bewertungsfunktion".
Viele Grüße
Hartmut

[Campus]

Hi,
ich weiss durchaus was Backtracking ist. Und stupides Ausprobieren ist halt aufgrund der Anzahl der Moeglichkeiten (bei 10 Schritten schon 1*10^9)nicht wirklich eine Loesung, es sei denn Du hast Lust Stunden auf ein Ergebnis zu warten. Und da setzt eben der Gedanke ein, Subbaeume des Variationsbaums einfach auszubleneden, indem man Stellungen als nicht guenstig klassifiziert. Und da es bei RR eben keine mathematische Wertungsfunktion fuer die Qualitaet eines Zugs gibt, liegt dort der Hund begraben. Solltest Du das anders sehen, kannst Du gern mal Deine nebenbei geschriebene Loesung posten. IMHO unterschaetzt Du das erheblich...
Nichts fuer ungut
Campus