Loesbarkeit bei Rasende Roboter

[Campus]

Hi,

ich bin auf der Suche nach einer Aussage, ob alle moeglichen Stellungen bei Rasende Roboter auch loesbar sind. Ich meine mich zu erinnern mal was in der Richtung gelesen zu haben, konnte aber im Forumarchiv nichts diesbezuegliches finden.
Vielleicht kann mir jemand weiterhelfen.


Ciao
Campus

[Markus Barnick]

such mal hier im Forum. Es hat hier vor längerer Zeit mal eine Frage gegeben, ob man RR nicht auf Computer umsetzen kann. Da wurden Angaben zur "Lösungsmenge" gemacht...

[Campus]

Hi

> such mal hier im Forum. Es hat hier vor längerer Zeit mal
> eine Frage gegeben, ob man RR nicht auf Computer umsetzen
> kann. Da wurden Angaben zur "Lösungsmenge" gemacht...

die Loesungsmenge ist nicht die Frage, da es sich um ca 5Billionen Stellungen handelt, aber ich vermute, dass der Autor sich Gedanken ueber die Loesbarkeit gemacht hat, da Spieler bei allzuvielen unloesbaren Stellungen zu sehr frustriert wuerden. Daher wuesste ich gern, ob es entsprechende Ueberlegungen beim Spieledesign gab. Durchrechnen aller Stellungen ist ja nun leider unmoeglich. ;-)


Ciao
Campus

PS. mein Freund, der seine Diplomarbeit zu RR geschrieben hat, hat heute erfolgreich verteidigt :-)

[benjamin]

Campus schrieb:
>
> die Loesungsmenge ist nicht die Frage, da es sich um ca
> 5Billionen Stellungen handelt, aber ich vermute, dass der
> Autor sich Gedanken ueber die Loesbarkeit gemacht hat,

bestimmt. also wenn ich mir den spielplan so ansehe, würde ich (ohne irgendwelche beweise zu haben) vermuten, dass es zumindest nur sehr wenige unlösbare aufgaben gibt. auffällig ist doch beispielsweise, dass die zielfeler selbst oder ausgangspunkte der beiden direkten wege dorthin stets zu mindestens einer wand einen abstand von maximal drei feldern haben, damit man dort notfalls alle drei übrigen roboter sammeln kann, um den vierten ins ziel zu bringen. klingt kompliziert, aber vielleicht weißt du ja, was ich meine :)

> da Spieler bei allzuvielen unloesbaren Stellungen
> zu sehr frustriert wuerden.

hast du eine nicht lösbare aufstellung gefunden? wir bisher noch nicht. wir hatten mal über 80 züge, aber noch keine unlösbaren aufgaben. wobei ich allerdings der meinung bin, dass auch diese 80 züge nur durch umwege zustande kamen.

> Durchrechnen aller Stellungen ist ja nun leider unmoeglich. ;-)

wohl wahr :)

> PS. mein Freund, der seine Diplomarbeit zu RR
> geschrieben hat, hat heute erfolgreich verteidigt :-)

eine diplomarbeit zu einem spiel? genial... mein studium ergibt wieder einen sinn ;) in welchem fach und worüber genau?

benjamin

[Werner Bär]

> wir hatten mal über 80 züge, aber noch keine
> unlösbaren aufgaben. wobei ich allerdings der meinung bin,
> dass auch diese 80 züge nur durch umwege zustande kamen.

Hast du die Stellung notiert?
Wäre ein interessantes Rätsel für einen Wettbewerb.

Möglicherweise gibt es eine viel kürzere Lösung, die nur
innerhalb der Zeit niemand gefunden hat?

Werner.

[Campus]

Hi,

> > 5Billionen Stellungen
> bestimmt. also wenn ich mir den spielplan so ansehe, würde
> ich (ohne irgendwelche beweise zu haben) vermuten, dass es
> zumindest nur sehr wenige unlösbare aufgaben gibt. auffällig
> ist doch beispielsweise, dass die zielfeler selbst oder
> ausgangspunkte der beiden direkten wege dorthin stets zu
> mindestens einer wand einen abstand von maximal drei feldern
> haben, damit man dort notfalls alle drei übrigen roboter
> sammeln kann, um den vierten ins ziel zu bringen. klingt
> kompliziert, aber vielleicht weißt du ja, was ich meine :)

ich verstehe schon was Du meinst, aber das ist natuerlich keine mathematisch gueltiger Beweis :-) und so einen suche ich.

> hast du eine nicht lösbare aufstellung gefunden? wir bisher
> noch nicht. wir hatten mal über 80 züge, aber noch keine
> unlösbaren aufgaben. wobei ich allerdings der meinung bin,
> dass auch diese 80 züge nur durch umwege zustande kamen.

80 Züge erscheint mir etwas zu hoch. Statistisch gesehen haben die meisten Stellungen einen optimalen Loesungsweg von 7-8 Zuegen, und die extremen Stellungen koennen auch schon mal bis 11 Zuege benoetigen, oder eben manchmal auch nur 4.

> > PS. mein Freund, der seine Diplomarbeit zu RR
> > geschrieben hat, hat heute erfolgreich verteidigt :-)
>
> eine diplomarbeit zu einem spiel? genial... mein studium
> ergibt wieder einen sinn ;) in welchem fach und worüber genau?

Er hat Mathematik studiert und verschiedene KI-Suchalgorithmen an den RR ausprobiert. Soweit ich dass in Erinnerung habe, hat er zum einen IDA*, der mit einer heuristischen Funktion arbeitet, einen uninformierten und eine Mischung aus beiden implementiert, wobei die Mischung interessanterweise am schnellsten war, eine erste, nicht unbedingt optimale, Loesung anzubieten, und der IDA* am schnellsten die optimalste Loesung gefunden hat.

Alles sehr spannend...


Ciao
Campus

[Wolfgang Ditt]

Für das echte Brett kann ich nur vermuten, dass alle Stellungen lösbar sind. Für ein leeres Brett beliebiger Größe (also ohne Mauern) ist jede Stellung lösbar (den Beweis spare ich mir hier). Außerdem lassen sich mit Mauern nicht lösbare Stellungen bauen, ohne den Spielplan in zwei Hälfte zu unterteilen; allerdings brauche ich dazu eine Sackgasse und die gibt es auf dem RR-Spielplan nicht.

Wolfgang

[Marten Holst]

Moinle,

> Für das echte Brett kann ich nur vermuten, dass alle
> Stellungen lösbar sind. Für ein leeres Brett beliebiger Größe
> (also ohne Mauern) ist jede Stellung lösbar (den Beweis spare
> ich mir hier). Außerdem lassen sich mit Mauern nicht lösbare
> Stellungen bauen, ohne den Spielplan in zwei Hälfte zu
> unterteilen; allerdings brauche ich dazu eine Sackgasse und
> die gibt es auf dem RR-Spielplan nicht.

Mist, genau das wollte ich auch schreiben (war so stolz auf meine Leerbrettlösung... immer diese Mathematen... :))[i][/i]). Ansonsten gibt es noch die Möglichkeit, vier nichtechte "Partitionen" zu bauen (also Bereiche, die voneinander schon noch irgendwie erreichbar sind), aus denen ein Roboter alleine nicht herauskommen kann, und je einen in alle vier zu stecken. Aber ich bilde mir ein, auch mal gelesen zu haben, dass jemand für das Oribrett (bzw. die 96 Originalbretter) die komplette Lösbarkeit bei beliebigen Ausgangsstellungen bewiesen hat. Wenn ich richtig erinnere, folgendermaßen: Erst hat er aus einer Ausgangsstellung mit allen vieren in einer Ecke die Lösbarkeit bewiesen, dann eine Technik, diese "Ausgangsstellung" zu erzeugen. Oder so.

Das muss doch im Netz zu finden sein!?

Tschüß
Marten (rast jetzt hier weg)

[Britta]

Marten Holst schrieb:
>
immer diese Mathematen...
> :))[i][/i]).

Genau das!!!! Haben sie keine Probleme, dann schaffen sie sich welche. Oder kann mir jemand verraten, wozu ich die Ergebnisse dieses Threads in meinem Alltag (oder vielleicht ja auch nur beim Spiel) benötige?

Britta

[Campus]

Hi,

> Genau das!!!! Haben sie keine Probleme, dann schaffen sie
> sich welche. Oder kann mir jemand verraten, wozu ich die
> Ergebnisse dieses Threads in meinem Alltag (oder vielleicht
> ja auch nur beim Spiel) benötige?

naja, das wuerde einem bei einem positivem Beweis bei manchen Stellungen sagen, dass man zzu bloed ist, die Loesung zu finden (was mir bisher zweimal passiert ist, und ich habe mir die Stellungen nicht aufgeschrieben :-()


Ciao
Campus

[Wolfgang Ditt]

Hallo Britta,

Marten nahm an, ich wäre eine dieser Mathematen, bin ich aber nicht, sondern nur ein Matiker, ein soganannter Infor, der meist mit Computern und seltener mit Robotern zu tun hat.

Zu deiner Frage, wie du die Erkenntnis gebrauchen kann. Also, wenn du an einem Tag t, ein Spiel s spielst, möchtest du den Gewinn G bekommen. OBdA nehmen wir an, das Spiel sei Rasende Roboter, kurz RR. RR besteht aus Runden R1 bis R17, in jeder gibt es eine Ausgangsstellung A bestehend aus Spielbrett S und den Robotern Rob1 bis Rob4. Mit Hilfe einer Abbildungsvorschrift f, im Volksmund kurz Spielregel genannt, versucht nun jeder Spieler SPx den Zielzustand S (kurze Erinnerung, das Spielbrett), mit Roby (y=1 bis 4) auf dem Zielpunkt (zh,zv) zh=horizontaler Punkt, zv, vertikaler Punkt zu bekommen. Annahme ist hier, es gäbe immer eine f: A => Z.

oder kurz gesagt, wenn alle anderen grübeln, hast du den psychologischen Vorteil, dass du weist es gibt eine Lösung.

Wenn du RR nicht spielst, ist dieses Posting natürlich wertlos, was ohnehin jeder erkennen kann.

Wolfgang

[benjamin]

hallo!

Campus schrieb:
>
> ich verstehe schon was Du meinst, aber das ist natuerlich
> keine mathematisch gueltiger Beweis :-)

mathematisch nicht wirklich, aber dafür schön anschaulich und in gewissem rahmen experimentell untermauert - die beweisführung der vollständigen intuition ;)

> und so einen suche ich.

ich hab mal einige suchmaschinen befragt - leider auch ohne ergebnis..

> 80 Züge erscheint mir etwas zu hoch. Statistisch gesehen
> haben die meisten Stellungen einen optimalen Loesungsweg von
> 7-8 Zuegen, und die extremen Stellungen koennen auch schon
> mal bis 11 Zuege benoetigen, oder eben manchmal auch nur 4.

ja das kann ich so sonst auch bestätigen.

> Er hat Mathematik studiert und verschiedene
> KI-Suchalgorithmen an den RR ausprobiert.

für meinen geschmack zu theoretisch, aber interessant ist es bestimmt.

benjamin

[benjamin]

Werner Bär schrieb:
>
> > wir hatten mal über 80 züge, aber noch keine unlösbaren aufgaben.
> > wobei ich allerdings der meinung bin, dass auch diese 80 züge nur
> > durch umwege zustande kamen.
>
> Hast du die Stellung notiert?
> Wäre ein interessantes Rätsel für einen Wettbewerb

möglich ist alles... in der packung liegt zwar nichts, aber ich meine, wir hätten es mal irgendwo vermerkt. wenn es auftaucht, werde ich es mal zur diskussion stellen :)

> Möglicherweise gibt es eine viel kürzere Lösung, die nur
> innerhalb der Zeit niemand gefunden hat?

das glaube ich auch... wir haben zwar dann noch eine weile gerätselt, aber da diese lange lösung von mir war (ich fange gerne mit langen wegen an, damit die uhr läuft) war zumindest ich zu dem zeitpunkt für kurze wege irgendwie blind - wie das so ist, wenn man seine eigenen fehler sucht: man findet sie einfach nicht. kann sein, dass ich jetzt sofort einen kurzen weg sehen würde, wenn ich es mir nochmal anschaue... in diesem fall werde ich mich schämen und es keinem verraten ;)

benjamin

[Britta]

Hallo Wolfgang!

>
> Marten nahm an, ich wäre eine dieser Mathematen, bin ich aber
> nicht, sondern nur ein Matiker, ein soganannter Infor,
Macht doch wohl kaum einen Unterschied, oder? Bist eben ein Theoretiker :-P

der
> meist mit Computern und seltener mit Robotern zu tun hat.
Soweit mir bekannt ist, schließt das eine ein Voraussetzung für das andere. => Macht auch keine Unterschied :-)

>
> Zu deiner Frage, wie du die Erkenntnis gebrauchen kann. Also,
> wenn du an einem Tag t, ein Spiel s spielst, möchtest du den
> Gewinn G bekommen. OBdA nehmen wir an, das Spiel sei Rasende
> Roboter, kurz RR. RR besteht aus Runden R1 bis R17, in jeder
> gibt es eine Ausgangsstellung A bestehend aus Spielbrett S
> und den Robotern Rob1 bis Rob4. Mit Hilfe einer
> Abbildungsvorschrift f, im Volksmund kurz Spielregel genannt,
> versucht nun jeder Spieler SPx den Zielzustand S (kurze
> Erinnerung, das Spielbrett), mit Roby (y=1 bis 4) auf dem
> Zielpunkt (zh,zv) zh=horizontaler Punkt, zv, vertikaler Punkt
> zu bekommen. Annahme ist hier, es gäbe immer eine f: A => Z.

Willst du mir damit sagen, dass f(y): A (sh,sv) => Z (zh,vh) unabhängig von t immer G=Z ist?

> Wenn du RR nicht spielst, ist dieses Posting natürlich
> wertlos, was ohnehin jeder erkennen kann.

Auf diese Idee wäre ich ohne dich nicht gekommen, vielen Dank für deine Hilfe :-D

Britta (die Grundschullehrerin auch durch 6 Semester Mathe, incl. solch unsinniger Dinge wie das Schreiben eines Computerprogramms zur Errechnung von Primzahlen, durch musste)

[Wolfgang Ditt]

besser geht's ab jetz im OT-Forum unter obigen Link
Wolfgang

[Marten Holst]

Moinle Wolfgang,

> Marten nahm an, ich wäre eine dieser Mathematen, bin ich aber
> nicht, sondern nur ein Matiker, ein soganannter Infor, der
> meist mit Computern und seltener mit Robotern zu tun hat.

Hoppala, entschuldige bitte. Zur Strafe werde ich heute abend noch schnell einmal das Siedlerbuch durchwuseln... :)

Tschüß
Marten (auch nur son halber)

[Wolfgang Ditt]

Hallo Marten,

> Hoppala, entschuldige bitte. Zur Strafe werde ich heute abend
> noch schnell einmal das Siedlerbuch durchwuseln... :)

... und alle Szenarien von uns mindestens einmal spielst.

Wolfgang