Skip to content

Leseridee für Programmierwettbewerb

Letztes erreichte die freiesMagazin-Redaktion eine E-Mail mit einer Idee zu einem neuen Programmierwettbewerb. Es ging darum, eine KI zu Ricochet Robots zu entwickeln.

Ich habe dem Leser abgesagt, weil es mit Robo Ralley ja schon mal ein ähnliches Thema gab. Daneben stelle ich mir vor, dass eine KI dazu sehr simpel aussieht.

Aufgabe: Von der Startposition aus muss der Roboter in möglichst wenig Zügen zum Ziel. Dabei kann er sich in jede Richtung bewegen, dann aber immer so weit, bis er gegen ein Hindernis prallt.

Meine Lösung wäre aus dem Spielbrett einen gerichteten Graphen zu machen, dann den Dijkstra-Algorithmus laufen zu lassen und schon wäre man fertig.

Sieht da jemand einen Denkfehler oder ist das wirklich so simpel? Oder hat jemand einen anderen Lösungsvorschlag?

Trackbacks

Keine Trackbacks

Kommentare

Ansicht der Kommentare: Linear | Verschachtelt

Dirk Deimeke am :

Ganz so einfach ist es nicht. Da sich alle Figuren auf dem Feld auch (mehrfach) bewegen dürfen, was dazu führt, dass sie als Helfer fungieren können.

Es gilt auch nicht irgendeine Lösung zu finden, sondern die mit den wenigsten Zügen.

Dee am :

Bei einem Wettbewerb, dem man noch einigermaßen beherrschen will, würden die Teilnehmer nicht gleichzeitig interagieren, sondern jeder Bot steht einzeln auf dem Feld. Aber selbst dann kann man, jedes Mal, wenn man am Zug ist, den Graph aufbauen und Dijkstra anwenden.

Und Dijkstra sucht den Weg des geringsten Gewichts = der geringsten Züge.

Ich frage mich aber grad, wenn sich alle nacheinander bewegen, wie der letzte dann überhaupt noch planen kann, wo er ankommt. Das ist doch dann einfach nur Zufall, je nachdem, wo sich die Mitspieler hingestellt haben, oder?

Dirk Deimeke am :

Nein, nicht ganz. Jeder darf alle Figuren beliebig oft ziehen, es gibt keine Spieler-Figuren.

Wenn die Aufgabe ist, mit dem roten Roboter ein bestimmtes Feld anzusteuern, kannst Du beispielsweise den gelben irgendwo hinziehen, um ihn dort als Hindernis zu benutzen, wenn er für den nächsten Zug im Weg steht, kannst Du ihn auch wieder wegbewegen.

Dee am :

Danke für die Erklärung, hätte meinen eigenen Link genauer lesen sollen. ;)

Das macht die Berechnung natürlich etwas komplexer. Sprich, man darf einen Teil der Hindernisse – nichts anderes ist es ja im Prinzip – frei verschieben, um zum Ziel zu kommen.

Ehrlich gesagt würde ich das wiederum aber nicht als Wettbewerb anbieten, da es einfach zu komplex ist. Selbst mit nur einem Hindernis sind die Möglichkeiten, die man durchrechnen muss, zu groß.

Aber natürlich die Frage: Gibt es da einen besseren Ansatz als Brute Force? Ich würde immer noch meine Graphen oben nehmen, müsste aber für jede Hindernis- und Roboterbewegung einen neuen Graphen erstellen und Dijkstra anwenden.

Dirk Deimeke am :

Das Problem ist NP-hart, keine Frage und ich kann gut verstehen, dass Du es nicht aufnehmen möchtest.

Mir fehlen sowohl Wissen wie auch Ideen, wie man das umsetzen kann. Im Wikipedia-Artikel sind zwei Lösungen verlinkt.

Dirk Deimeke am :

Gerade vergessen. Der Wettbewerb für die Spieler besteht darin, die Lösung mit den geringsten Zügen zu wählen.

Wenn jemand eine Lösung gefunden hat, sagt er laut die Anzahl der Züge und dreht eine Sanduhr um. Bis zum Ablauf der Sanduhr kann jeder Spieler, auch der ursprüngliche, weniger Züge in die Menge werfen.

https://de.wikipedia.org/wiki/Rasende_Roboter

Kommentar schreiben

Die angegebene E-Mail-Adresse wird nicht dargestellt, sondern nur für eventuelle Benachrichtigungen verwendet.
Formular-Optionen