KI für Sokoban
-
Da soll der Computer mithilfe eines evolutionären Algorithmus Sokoban
lösen. Will hier nicht rumtrollen. Das könnte imho wirklich so ähnlich gehen.Im Kommentar oben steht, was die Überlegung ist.
evomove() ist die Hauptroutine, die es zu korrigieren gilt.
Das ist der umzuschreibende Hauptteil, mit dem es neben
ein paar Parametern zu experimentieren gilt.
Es selektiert entweder mit einer binomialverteilten Wahrscheinlichkeit
bekannte und besser bewertete Einträge oder den aktuellen Spielzustand zum Vergleichen.
In main() ist ein Array für die Levelmap und da werden auch
die Koordinaten für die Kistenstartpositionen festgelegt.
Sind die Ränder im Array eh zugemauert, spart man die Kollisionsabfrage
für die Grenzenüberschreitung und verhindert das Crashen.
Die Framerate für die ASCII-Bildschirmausgabe wird aus Geschwindigkeitsgründen
mit einer Modulodivisionsabfrage der Anzahl Hauptschleifendurchläufe reduziert.
Expirmentiert halt damit rum und falls es irgendwann relativ zuverlässig funktioniert,
übertragt ihr die Erkenntnisse auf andere Probleme.
-
Ich glaube das wird nicht funktionieren. Bei Sokoban liegen ähnliche Rätsel nicht bei ähnlichen Lösungen. Es kann z.B. sein, das man einfach ein einziges Hindernis (oder auch ein Ziel und eine Kiste) in eine komplizierte Map einfügt und damit die Lösung komplett anders wird, weil man jetzt plötzlich alle Kisten zu anderen Zielen bringen muss. Wenn man also in einem Level sieht, das da irgendwas ähnlich ist zu einem bekannten Level, heisst es noch lange nicht, das man einfach die alte Lösung mit minimaler Änderung übertragen kann. Die neue Lösung kann von der alten Lösung ähnlich weit entfernt sein wie einfach die leere Anweisung (rumstehen und warten das plötzlich der Level gelöst ist). Für simple Level mit vielen Freiheitsgraden oder die ersten Anfängerlevel bringt das vlt. was, aber danach wird es eben schnell zu Rumraten als wüsste die AI gar nichts.
-
Ob er aus vorangegangenen Spielsituationen lernt oder nicht; es geht
darum, ob er mit seinen Entscheidungen trotzdem noch zum Minimax-Verfahren tendiert. Kiste an die Wand fahren hat abschreckende Wirkung, Kiste auf Sollposition fahren wird gut bewertet... und wenn er dann noch die
einzelnen Schritte zeitlich verkettet, kommt dann mit erhöhter
Wahrscheinlichkeit ein Minimax-Baum dabei heraus? Und nebenher könnte er auch noch die Daten umdeuten oder ergänzen. Aber den Programmablauf
nachvollziehen wird halt arg schwierig. Da gibt es ja nur noch wahrscheinliche Tendenzen.
