Beschreibung von Punkten und ihren Kanten zu anderen Punkten

  • Hey zusammen,


    ich habe lange nicht mehr programmiert, aber wollte mir gerne ein kleines Tool für FIFA basteln: Einen "Chemie-Optimierer"

    Es gibt sowas auch als Web-Tool (https://www.futbooster.com), aber das dauert teilweise recht lang und ich würde gerne meine PC-Ressourcen dafür nutzen und ggfs. ein paar Ideen dazu einbauen. Also wollte ich mir erstmal eine vereinfachte Version davon mit AutoIt bauen.


    Damit ich keine Spieler-Datenbanken etc. brauche, hole ich mir einfach einen gepflegten Kader via Http von einer Website, wo man sich Kader zusammenstellen (aber halt nicht derartig optimieren) kann und habe mir dann erstmal eine Funktion gebaut, die sozusagen die Auswirkung der Kanten auf die Punkte berechnet.


    Jetzt bin ich mir aber so gar nicht sicher, wie ich die Formationen am Besten in AutoIt abbilden kann. Also eine Formation besteht aus 11 Punkten, die jeweils mit ganz klar definierten anderen Punkten über Kanten (2-5 Stück) verbunden sind. Eine Kante kann den Wert eines Punktes um -1, 0, +1 oder +2 verändern.


    Also muss ich jetzt irgendwie jede einzelne Formation programmier-technisch beschreiben, damit ich das später dann "durch-loopen" kann^^ Was ist der beste Weg für sowas? Einfach ein 11er Array (0-10) und jeweils die "ID" des Punktes, zu dem es eine Kante gibt, mit in das Array schreiben?
    Beispiel: Torwart ist 0, Innenverteidiger #1 ist 1, Innenverteidiger #2 ist 2 und der Torwart hat nur Kanten zu beiden Innenverteidigern:

    #aFormation_One[0] = ["TW", 1 ,2] ;

    => Ich muss den "Namen" des Punktes auch immer wissen, da Spieler von bestimmten Positionen nachher nur auf bestimmte andere Positionen verschoben werden dürfen, um rum zu probieren. TW = Torwart z. B. bleibt immer auf seinem Punkt, ein defensiver Mittelfeldspieler darf aber auch auf die Position offensives Mittelfeld, etc. Heißt, ich brauche immer "Name" des Punktes und das Wissen, zu welchen anderen Punkten es Kanten gibt.


    Oder gibt es da "bessere" Möglichkeiten, so etwas abzubilden, auch mit dem Wissen, dass das Tool die Kantenberechnung sehr schnell machen können muss, weil die Spieler dann diverse Male auf andere Positionen verschoben werden (Neuberechnung) und das ganze dann für 30 Formationen, bis das beste Ergebnis gefunden wurde.


    Ich hoffe, es ist nicht zu kompliziert beschrieben... ^^ Damit man das Drumherum bei Bedarf besser verstehen kann, hier auch der bisherige Code:

  • Das Sieht für mich nach einem klassischen Optimierungsproblem aus.


    Habe (für genau dieses Problem) jetzt nichts programmiert, ich kann aber kurz beschreiben wie man es macht.


    Benötigte Variable:

    $InternerZustand[11][...] = Aktuelle Konstellation deiner Spieler (z.B. in einem [11][...] Array)

    $BesterInternerZustand[2] = [0] -> Zwischenspeichern des bisher besten berechneten internen Zustands, [1] -> Wert der Zielfunktion für diesen Zustand.

    $LetzteAenderung[2][2] (für 2 Spieler hier Beispielhaft)

    [0][0] Position(Index) von SpielerX in InternerZustand VOR der Variation

    [0][1] Position(Index) von SpielerX in InternerZustand NACH der Variation

    [1][0] Position(Index) von SpielerY in InternerZustand VOR der Variation

    [1][1] Position(Index) von SpielerY in InternerZustand NACH der Variation


    Benötigte Funktionen:

    Funktion zur Evaluation des (kompletten) internen Zustands zu einem einzigen int oder float Wert, der sich vergleichen lässt. Eine Konstellation mit dem Wert 5.6123 ist schlechter als eine Konstellation mit dem Wert 7.6543. Die Zielfunktion zu finden ist bei vielen Optimierungsproblemen der härteste Teil, ich glaube das geht hier aber recht einfach. Als Hilfmittel (zur Kantenbeschreibung) ist hier eine 11x11 Matrix geeignet an deren Stelle überall eine 1 steht wo eine Kante existiert und eine 0, wenn keine Kante vorhanden ist. (z.B. es gibt eine Kante zwischen [0] und [4], dann ist in der Matrix bei [0][4] eine 1).

    Funktion zur Variation des internen Zustands. z.B. 2er Vertauschung (Nimm 2 zufällige Spieler, tausche ihren Platz), oder 3er Vertauschung (Nimm 3 zufällige Spieler, verteile sie Zufällig)


    Jetzt machst du folgendes:

    Starte mit "irgendeiner" gültigen Konstellation (Fachjargon: Gültige Lösung), am besten verteilt man die Spieler Zufällig, sodass bei jedem Funktionaufruf ein anderer Startwert vorliegt.

    Berechne die Zielfunktion (Evaluation, hier kommt z.B. 3.123 heraus)

    Speichere diese Konstellation + Wert der Zuelfunktion in BesterInternerZustand.


    Loop

    Variiere (z.B. 2er oder 3er Vertauschung) den Internen Zustand EIN Mal.

    Denke daran die Änderung zu speichern, also wo waren die beiden Spieler vorher, wo sind sie jetzt?

    Berechne die Zielfunktion

    Schaue ob der Wert der Zielfunktion besser ist als der "beste" Wert

    Wenn ja -> Speichere Aktuellen InternenZustand und Wert der Zielfunktion in BesterInternerZustand

    Wenn nö -> Mache die Änderung rückgängig

    Abbruchkriterium

    EndLoop


    Als Abbruchkriterium kann man z.B. einen Zähler einbauen: Wenn sich nach z.B. 500 Schritten nichts mehr verbessert hat ist man fertig.


    Das Entspricht jetzt einer Nachbarschaftssuche "ohne Tricks".


    Warum ist ggf eine 3er Kombination auch sinnvoll?

    Das ist jetzt nur ein Erfahrungswert: Manchmal fressen sich "zu kleine" Variationen fest und eine tatsächliche Verbesserung kann nicht mehr erzielt werden, wenn nur "ein wenig" variiert wird. Dafür gibt es verschiedene Lösungsansätze:

    - Größere Variation zulassen (das wäre jetzt z.B. die 3er Vertauschung)

    - Mehrere Variationen in Folge anwenden (z.B. 2, 3, viele Vertauschungen und erst danach auf die Zielfunktion schauen)

    - Kleine Verschlechterungen zulassen (wird die Zielfunktion nur "etwas" schlechter? Dann kann man ggf trotzdem auf diesem Weg laufen)

    - etc.


    Ich würde das wie oben beschrieben programmieren und dann z.B. 500 Instanzen Laufen lassen. (also die Optimierung als Ganzes 500x mit zufälligen Startwerten durchführen) und das beste Ergebnis davon verwenden.


    Da 11 Fakultät "nur" 40Mio sind kann man das auch mit BruteForce lösen. Das wird in AutoIt vielleicht ziemlich langsam, wenn du aber noch andere Sprachen draufhast (z.B. Java (argh), C, C++, etc) müsste das eine Sache von Sekunden sein bis man das gebruteforced hat.


    Edit: Das ist ne super (teil) Hausaufgabe für neue Info-Studenten. Das merk ich mir... hehehe :D

    lg

    Mars

  • BugFix Knoten(punkte) und Kanten sind doch ganz normale Bezeichnungen?!


    Mars Danke für deine Antwort :) Ich habe versucht, etwas mehr Kontext zu geben, daher hast du glaube ich über meine Frage schon hinaus gedacht ^^ Also auf die Kern-Frage, wie ich die Beschreibung der Formation am Besten abspeichere, ist dein Vorschlag eine Matrix für jede Position in dieser Formation in einem 2D-Array anzulegen und dann jeweils bei den Kanten zu sagen, ob sie "verbunden" sind?

    Vllt. habe ich es auch noch nicht ganz durchschaut, aber das kommt mir sehr kompliziert und rechenaufwendig vor. So muss ich ja auf jeden Fall pro Position immer schon mal ein großes Array durch-"loopen". Ist es da nicht schneller, an dem Punkt zu beschreiben, mit welchen anderen Punkten er verbunden ist? Wie gesagt, von den 11 Spielern, ist ein Spieler maximal mit 5 (das ist ein sehr seltener Fall) anderen Spielern direkt verbunden.


    Wenn ich jetzt einen RM-Spieler (Right Midfield) habe, gibt es im Prinzip auch nur zwei weitere Positionen, wo er sinnvoll spielen kann (RF = Right Forward und Right Winger). Dadurch erhoffe ich mir auch, dass die Anzahl der Versuche überschaubarer bleibt. Und entsprechen, dass ich auf "zufällige Werte" und "Bruteforce" verzichten kann.


    Also meine Ausgangslange sind 11 Spieler auf 11 Positionen (da ich das Tool ja als Basis nutze, habe ich das als Start-Wert parat). Jeder Spieler kann auf einer begrenzten Anzahl von Positionen spielen (max. 5, Torwart z. B. nur als Torwart) und jeder Spieler ist berechenbar besser ("Chemie"), wenn bestimmte andere Spieler neben ihm spielen (durch die 2-5- "neben ihm"-Verbindungen / -Kanten auch vorher eindeutig feststellbar).


    Das lässt sich sicherlich auch mit Bruteforce lösen und wahrscheinlich ist das sogar programmier-technisch das einfachste und von der Dauer (zumindest in anderen Sprachen) dann auch die "beste" Lösung. Aber da ich mit AutoIt unterwegs bin und das Ergebnis auch möglichst schnell kommen soll (man muss diese Variationen der Spieler für 30 Formationen machen und dann merkt der Nutzer vllt. "ist doof" und tauscht einen Spieler aus und wirft es wieder und wieder an, bis alles passt.
    Daher gehe ich davon aus, dass ich das "optimiert" lösen muss.


    Hier auch nochmal ein Beispiel einer Formation (3-4-1-2):

    Und mal vom Code, was ich als mögliche Darstellung im Kopf hatte:

  • Das was du aufgeschrieben hast ist im Prinzip eine kondensierte Version der Matrix mit einer festen Breite von 5 + Zusatzinformationen. Ich habe einfach aus Gewohnheit eine volle Matrix vorgeschlagen, das ist hier wahrscheinlich nicht unbedingt besser...


    Wenn du schon mit Knoten und Kanten loslegen willst: Nachbarschaftsbasierte Suchalgorithmen in ungerichteten Graphen (das ist dein Stichwort :D )

    Dazu gibt es wunderbare Literatur (PS: ich hatte in dem Fach nur eine 3.... 8) ). Ein "Knoten" ist hier eine "Zulässige Lösung", also z.B. eine Liste mit 11 Spielern. Ein "Nachbar" ist eine Zulässige Lösung bei der eine kleine Variation vorgenommen wurde (z.B. 2 Spieler vertauscht). Ein Suchalgorithmus schaut sich jetzt die "Kosten" (das ist die Evaluationsfunktion/Zielfunktion um zu bewerten wie "gut" dein Team ist) im Graphen für den eigenen Knoten (irgendein Startknoten, z.B. eine zufällig zusammengewürfelte, aber zulässige Liste von 11 Spielern), sowie die benachbarten Knoten an und geht dann einen Schritt in eine "vielversprechende" Richtung (z.B. immer zum "besten" Nachbarn, oder zufallsbasiert mit 50% chance zum "besten", mit 25% zum 2t "besten", mit 12,5% zum 3t... usw.).

    Easy :part:

  • Das darüber schreiben hilft mir auf jeden Fall schon mal :) Ich bin aber auch lange aus dem Programmieren raus und komme eher aus dem Bereich Wirtschaftsinformatik :D... Das hört sich nach komplexer Literatur an und deine Beschreibung erklärt ja, was der Algo tut und noch nicht wie...

    Gibt es da eine "Abkürzung"? :D Hast du zufällig ein AutoIt-Beispiel oder kennst du eine UDF, die man auf das Problem anpassen kann oder ähnliches?


    Ich habe jetzt bisher "fertig":

    • Team von der Kader-Seite laden
    • Formation/en mit dem Team vergleichen (inkl. möglicher Positions-Modifikatoren) und Aussage darüber treffen, ob die Formation geeignet ist (von 30 Formationen werden vllt. immer nur so 10 überhaupt geeignet sein, nach der Prüfung)
    • Den Einfluss eines benachbarten Spielers auf einen bestimmten Spieler berechnen
    • Prüfen, ob eine bestimmte Position in der Formation für einen Spieler geeignet ist (inkl. möglicher Positions-Modifikatoren)


    Jetzt kommt genau der schwierige Teil, bevor ich das dann nur noch auf alle "geeigneten Formationen" anwenden muss und noch ein paar andere Boni einrechne: Ich muss alle möglichen(!) Kombinationen der Spieler in einer Formation durchlaufen, um dann jeweils die Evaluationsfunktion anzuwenden.

    => Durch die Prüfung, ob ein Spieler für die Funktion geeignet ist (an Hand seiner Position), spare ich mir auch eine Prüfung, wie der Einfluss eines nächsten Spielers jetzt genau ist. Ich möchte einfach alle möglichen Kombinationen einmal durchgehen und dann durch rechnen.


    "Rekursion" ist bei mir auch lange her, aber kann ich dafür nicht irgendwie ganz "billig" alle Positionen mit allen Spielern durchgehen und alle geeigneten (gibt dann einen Ausstiegspunkt aus diesem Loop, wenn die Position für den Spieler nicht passend ist) landen dann in einem Ergebnis-Array? Und in dem Array rechne ich dann für jede Lösung die Chemie-Werte aus und die "beste Aufstellung" für diese Formation, wird dann in einem Ergebnis-Array dieser Formation zugeordnet.


    Das sind dann immer noch einige mögliche Kombinationen, auch wenn ich aus einigen früher raus springen kann und die Abgleiche alle sehr klein sind... Im Worst-Case wird ja auch das Ziel-Array trotzdem noch lang, auch wenn ich durch die Positions-Einschränkungen stark reduziere. Es gibt natürlich auch einen Ziel-Zustand, den ich vllt. als weiteren Ausstiegspunkt für die gesamte Formation noch einbauen kann: Jeder Spieler hat mindestens 9 Chemie; denn dann gibt es keine besseren Lösungen mehr, nur ggfs. andere gute Lösungen.

    => Sind wir fast schon wieder beim Bruteforce-Vorschlag, nur ohne die zufälligen Formationen, oder? hmmm ^^

    ==> Rekursion wäre hier das richtige Stichwort, oder? (muss mich morgen mit frischem Kopf nochmal rein denken) Habe ich irgendwas übersehen und muss vllt. doch noch was zu den nachbarschaftsbasierte Suchalgos in ungerichteten Graphen lesen? :D

  • Man kann ganz billig "alle" Positionen ablaufen. Eine rekursive Version davon ist z.B:

    Hier werden jetzt "alle" Kombinationen durchlaufen. Da der Torwart IMMER Position 0 hat (und auch sonst nirgends spielt) lassen wir den aus der Permutation heraus, sodass es nur noch 10! tatsächlich relevante Kombinationen gibt. Davon sind aber die allermeisten ungültig (da nicht jeder Spieler überall spielen kann).

    Weil ich neugierig war ob der "ich nehme einfach unmengen For-Loops und lehne mich zurück" Ansatz klappt habe ich es kurz implementiert... Entweder ist da was falsch, oder es gibt wesentlich weniger gültige Permutationen als ich gedacht habe... Bei so viel Zahlensalat habe ich mich bestimmt irgendwo vertippt ^^


  • Weil ich neugierig war ob der "ich nehme einfach unmengen For-Loops und lehne mich zurück" Ansatz klappt habe ich es kurz implementiert... Entweder ist da was falsch, oder es gibt wesentlich weniger gültige Permutationen als ich gedacht habe... Bei so viel Zahlensalat habe ich mich bestimmt irgendwo vertippt

    Ich habe mal einen unabhängigen Ansatz versucht und komme auf das gleiche Ergebnis wie du.
    Sollte also wahrscheinlich so stimmen:


    Also auf die Kern-Frage, wie ich die Beschreibung der Formation am Besten abspeichere, ist dein Vorschlag eine Matrix für jede Position in dieser Formation in einem 2D-Array anzulegen und dann jeweils bei den Kanten zu sagen, ob sie "verbunden" sind?

    Vllt. habe ich es auch noch nicht ganz durchschaut, aber das kommt mir sehr kompliziert und rechenaufwendig vor.

    Die relevanten Fachbegriffe für die Google-Suche hierzu sind Adjazenzmatrix für die Abbildung als Matrix wie von Mars vorgeschlagen und als Alternative hierzu die Adjazenzliste.
    Welche Struktur man für die Knotenbeziehung in Graphen verwendet hängt hierbei vor allem davon ab ob eine Adjazenzmatrix dünn oder dicht besetzt wäre. In dem Fall hier würde ich wohl eher zu einer Adjazenzliste neigen, da jeder Knoten ja nur max. 2 Kanten haben kann (hab ich das so richtig verstanden? ne jetzt sehe ich in deinem Bild, dass es auch mehr Verknüpfungen sein können). Außerdem hat man in einer Adjazenzliste sofort alle Nachbarknoten vorliegen, während man in einer Adjazenzmatrix die komplette Spalte jeweils durchgehen müsste.

  • Mars Cool, vielen Dank! :) Mit allen Permutationen, ohne vorher die Reduzierung der möglichen Positionen zu machen, ist das wirklich ganz schön lang (bei mir 45 Sekunden). Deine "Loop-Lösung", die das direkt berücksichtigt, war die Richtung, die ich mir hätte vorstellen können (die Rekursion ist viel schwerer nachzuvollziehen ^^).

    Ich nehme auf jeden Fall die Idee mit, ein Array für die möglichen Positionen des Spielers in der Formation zu erstellen, bevor ich dann in die Permutationen gehe! Viel besser, als die Prüfung dann beim Durchgehen der ganzen Permutationen zu machen - das spart mir auf jeden Fall Frust, wenn ich nun direkt so weiter coden kann^^


    AspirinJunkie Danke für die alternative Lösung. Auch komplex für mich dem zu folgen, aber noch etwas besser "lesbar" für mich :) Damit werde ich auf jeden Fall mal etwas experimentieren!


    Mögt ihr mir noch erklären, warum ihr - und scheinbar unabhängig voneinander(?) - eine eigene Array-Funktion schreibt, statt das Array von AutoIt an dieser Stelle zu nutzen? Ist das so einfach die beste Variante, wenn man keine "gleich langen" Arrays hat und damit man nicht wie ich oben, manuell überall z. B. "Null" rein schreiben muss oder steckt da noch mehr dahinter? ^^

    *edit*

    Achso, ich verstehe... Durch das @NumParams wird dann nicht nur einfach automatisch aufgefüllt, sondern das Array (im Array) hat damit wirklich nur die Länge, die es braucht - das ist geschickt! ^^ Damit werde ich auch mal meine anderen Teile des Codes umstrukturieren!

  • AutoIt hat leider keine Methode um ein Array aus Arrays zu definieren. Wenn man die [[1,2], [3]] Syntax verwendet wird automatisch ein 2x2 Array erstellt, wobei Array[1][1] leer ist. Was man eigentlich will ist ein Array der Länge 2, welches ein Array der Länge 2 und ein Array der Länge 1 enthält.


    Der Trick über eine Funktion ist leider performancetechnisch ziemlich langsam, da hier zuerst ein viel zu großes Array erstellt wird, welches zu allem Überfluss auch noch bis zum Ende hin gefüllt wird. Zusammen mit dem Overhead durch Funktionsaufruf und ReDim ist das ziemlich lahm... Sowas sollte man also eigentlich nicht in Inner-Loops verwenden (sagte er, und verwendet es in 11 Fach verschachtelten For-Schleifen).


    Der Zugriff auf ein Array im Array ist sehr performant, wenn man ByRef auf das Element zugreift. Arrays werden bei Zuweisung mittels Gleichzeichen (in AutoIt) kopiert, hier muss man also etwas vorsichtig sein und schauen auf welchen Daten man eigentlich gerade arbeitet (Original, oder Kopie).


  • Langsam? Aber gut, wahrscheinlich macht es bei meinem Use-Case nicht so den gewaltigen Unterschied, solange ich es "nur" bei den äußeren Funktionen nutze.


    Ich habe mit der Array-Funktion jetzt auch den Teil umgebaut, in dem ich meine Formationen beschreibe und ich verstehe eine Sache nicht:


    Warum klappt mein auskommentierter Teil nicht? Meine Erwartung ist, dass ich ich das Array der ersten Formation bekomme. Das sind ja Arrays, in Arrays, in einem Array. An anderen Stellen ziehe ich auch ein Array aus einem Array und habe keine Probleme... Irgendwie stehe ich auf den Schlauch, wo mein Gedankenfehler ist oder ob ich das falsch definiert habe...

  • Der funktioniert nicht, weil $aFormations ein Array vom Typ [2][n] ist. Stattdessen möchtest du wahrscheinlich ein Array vom Typ [n] verwenden. Dafür muss aus dem $aFormations = [[ ... ], [ ... ]] ein [ ... ] werden. Also müsstest du die Arrays in Arrays nochmal kapseln.


    Damit ist $aFormations ein 1D Array welches je Element eine Formation enthält.
    Eine Formation ist ein 1D Array welches Positionen enthält.
    Eine Position ist ein 1D Array welches die Positionsdaten (Name + Kanten) enthält.

  • Vielen Dank für deine Erklärungen!

    Ich habe jetzt alles soweit durch, dass er mir mögliche Besetzungen der Formation korrekt ausspuckt (per Stichprobe kontrolliert). Für die ersten Spieler mit einer ersten Formation dauert das knapp 2 Sekunden. Ich werde noch eine Vor-Validierung der Formationen machen, sodass ich nicht alle durch gehen muss und in den 2 Sekunden sind ja auch 2 größere Arbeitsschritte mit drin. Aber die Rekursion wird wohl einen Großteil davon benötigen und dann kann sich die Zeit schon schnell addieren, zumal noch die Berechnung der Chemie dazu kommt.

    Mein Ziel ist, zu jeder passenden Formation die nach der Chemie beste Aufstellung zu finden. Das heißt, dass ich theoretisch auch Zeit sparen könnte, wenn ich die Berechnung der Chemie direkt in der Rekursion mit mache, um dann bei einer bereits "perfekten Aufstellung" die Rekursion für die Formation schon beenden könnte...


    Nun ja, morgen kommen erstmal die anderen 25 Formationen mit in den Code und die Chemie-Berechnung und dann lasse ich das über alle Formationen laufen und das Ergebnis etwas besser ausgeben :)


    Hier auf jeden Fall mal der aktuelle Stand, falls das mal jemand gebrauchen kann oder auch gerne, falls mal jemand Lust hat drüber zu fliegen, für Feedback, wo ich Dinge "besser" machen könnte. ^^


    Erster, erfolgreicher Lauf, mit drei wirklich möglichen Aufstellungen: