Der-Dennis: Problem-/Lösungsname gesucht

Beitrag lesen

Hallo dedlfix,

Das Spielfeld wird ausgewürfelt und ich kann es mir anschauen, um mir eine Strategie zu überlegen, wie ich mich da durchschlagen kann.

Das ist schon mal gut und darauf zielte auch eine meiner Fragen ab. Wenn das gesamte Spielfeld sowie die ganzen Randbedingungen (in dem Fall z.B. die Gegenstände an den einzelnen Stationen) von Anfang an bekannt sind hast Du mit den Optimierungsverfahren gute Möglichkeiten, eine zufriedenstellende Lösung zu finden.

Das ist aufwendig, weil eine Menge zu berechnen ist.

So, wie ich mir das vorstelle, wahrscheinlich sogar viel zu aufwändig, wenn Du mit sowas wie Brute-Force darauf losgehen willst. In dem Zusammenhang finde ich die Sessa-Legende immer schön anschaulich, auch wenn man es sich intuitiv kaum vorstellen kann.

In der Form kommt es nicht wieder, es gibt nur andere, anders ausgewürfelte. Die Stationen sind an anderen Plätzen, lediglich Anfang und Ende sind immer an festen Positionen.

Wenn es nicht wiederkommt, spräche das meiner Meinung nach am ehesten für Reinforcement-Learning-Ansätze oder vergleichbares. Voraussetzung ist dafür natürlich, dass Du den Algorithmus gewissermaßen "trainieren", also z.B. 1000 Runden spielen kannst, ohne dass dies einen Einfluss auf ein zukünftiges Spiel hat (darauf zielte meine andere Frage ab).

Das Feld inklusive der Stationen ändert sich nicht mehr, wenn man es einmal bekommen hat. Das dürfte die Definition von statisch erfüllen.

Ja, genau. Auch wenn ich mich mit der "statisch/dynamisch"-Definition in diesem Bereich immer noch nicht anfreunden kann. Allgemein geht es dabei darum, ob Du alle folgenden Aktionen "im Voraus sehen" kannst (statisch; gute Lösung wahrscheinlich) oder ob eine Aktion wiederrum eine Aktion auslöst, d.h. Du musst erst etwas tun, damit Du "anschließend sehen" kannst, wie sich die Randbedingungen (oder das Spielfeld oder was-auch-immer) geändert haben (dynamisch; einigermaßen gute Lösungen sind, wenn überhaupt, nur durch statistische Methoden möglich). Wie gesagt, ich finde diese Definition nicht glücklich, hoffe aber, Du weißt, worauf ich hinaus möchte. Noch "schlimmer" als "dynamisch" wird's bei praktisch allen Ansätzen nur noch, wenn man nicht mal die Möglichkeit für ein Training des Algorithmus hat, weil jeder Versuch Auswirkungen auf den nächsten hat (wie vorher schon beschrieben).

Heißt "bestmöglich" jetzt "die absolut beste Lösung" oder "eine optimale Lösung, die der besten sehr nahe kommt"? Wenn ersteres: Je nachdem, wie komplex "das Spiel" an sich ist, ist das praktisch ausgeschlossen. [...]

Das werde ich dann sehen, wenn ich es implementiere. Die absolute beste wäre optimal, einfach nur irgendwie erfolgreich durchkommen wäre auch eine mögliche Lösung, wenn die andere zu rechenintensiv ist.

So wie ich mir Deine Aufgabenstellung mittlerweile vorstelle bin ich mir relativ sicher, dass Du eine allgemeingültige, beste Vorgehensweise nicht wirklich finden kannst, sofern denn überhaupt eine existiert (für eine einzelne Runde könnte das unter Umständen aber möglich sein). Ich selbst wundere mich z.B. immer wieder (und das wird wahrscheinlich auch immer so bleiben), dass Fakultäten völlig unintuitiv sind und ich mir, obwohl ich es eigentlich wissen müsste bzw. weiß, einfach immer wieder vor Augen führen muss, wie schnell die wirklich steigen (Beispiel: Ein Plot von WolframAlpha mit Potenz/Polynom/Fakultät; man beachte besonders die Abzisse, schon bei einer "Komplexität" (Algorithmus-Komplexität bzw. -Laufzeit könnten übrigens weitere Stichwörter sein) von 7 geht die Fakultät buchstäblich "durch die Decke"; das Sessa-Beispiel habe ich zum Vergleich auch mal reingepackt).

Ansonsten könnte ich mir vor dem Hintergrund, was Du bisher zu der Problemstellung gesagt hast, vorstellen, dass Du beispielsweise spielübergreifend Reinforcement-Learning-Ansätze verwenden kannst und pro Runde sowas wie Ant-Colony-Optimization verwendest (die intern übrigens auch meist wieder auf RL-Ansätze zurückgreift; Ant-Colony muss auch nicht das am besten passende Verfahren sein, ich persönlich finde diese Bionik-Ansätze aber immer wieder faszinierend und sie funktionieren erstaunlich gut).

Aus Erfahrung wäre ein weiterer Tipp, sich das Spielprinzip genau anzuschauen und Dir selbst Regeln aufzustellen (ähnlich wie in diesem Beispiel, als es um Schere-Stein-Papier ging, auch wenn die Intention da eine andere war; wenn Du solche Regeln wie A schlägt B (bzw. A ist (fast) immer die bessere Wahl im Gegensatz zu B) findest, minimiert das die Komplexität meist enorm und hilft sehr beim "Training"). Erster Schritt ist immer die Minimierung der Komplexität (unter anderem durch das Aufstellen einfacher Regeln).

Als letztes Stichwort für eine Recherche hätte ich noch das Stichwort Fuzzylogik für Dich. Das löst zwar nicht das eigentliche Problem, kann Dir aber bei einer einzelnen Entscheidungsfindung (bei Dir: z.B. an einer Station) sehr hilfreich sein.

Gruß, Dennis