MathHammer 2.0: Armeezusammenstellung als MILP

oder: Warum der SPAM! inhärent ist.

Hallo Zusammen,

in den letzten Tagen wurde ja viel über SPAM! diskutiert, ob er schlecht ist, ob er gut ist, wie er zu bekämpfen sei, oder dass man sich als Dirty-Casual mal nicht so anstellen sollte, denn der SPAM gehöre nunmal zu einem kompetitiven Spiel dazu. Die Sinnhaftigkeit dieser Diskussionen sei mal dahingestellt, aber sie haben mich zum denken angeregt. Viele haben ja gesagt SPAM! ist inhärent im System und man wird ihn nie wegbekommen. Kann man diese Behauptung beweisen? Oder zumindest überzeugende Argumente finden warum man ihr glauben sollte?

Als guter Ingenieur habe ich natürlich sofort versucht, das Problem zu abstrahieren und mir ein Gedankenmodell zu erstellen. Dabei ist folgendes herausgekommen:

  • Im Grunde ist die Armeezusammenstellung in meiner Vorstellung ein gemischt-ganzzahliges lineares Optimierungsproblem (Mixed-integer linear problem = MILP).
  • Die Optimierungsvariablen entsprechen der Anzahl der Instanzen eines Datasheets. Ich bezeichne sie im folgenden mit der Variable d.
  • Für die gewählten Datasheets werden die Power-Points aufsummiert. Diese Summe muss unter einem Limit bleiben.
  • Jedem Datasheet ist eine Battlefield-Role zugeordnet. Aus dem Produkt einer Mapping-Matrix und der Variable d erhält man die Anzahl von Units mit der jeweiligen Battlefield-Role in einer Armee. Dieser Vektor ist nach oben und unten durch die Detachments begrenzt. Im Beispiel habe ich einfach mal ein Battalion als Limit gesetzt.
  • Für jedes Datasheet gibt es eine abstrakte Effektivitätszahl. Momentan ist diese geraten, aber eigentlich ist sie eine Funktion des Datasheets, der Ausrüstung und des erwarteten Metagams (=den Szenarien). Lintu hat einige wunderbare Artikel über die Berechnung von Effektivitätszahlen für Einheiten veröffentlicht. Ich gehe hier erstmal davon aus, dass wir diese Zahlen irgendwoher bekommen können. Im Zweifel könnte man sogar Data-Mining betreiben, wenn man eine formale Repräsentation (=Codierung) der Armeelisten hätte, aber das führt hier zu weit.
  • Für jedes Datasheet gibt es noch weitere Beschränkungen in Form von oberen und unteren Schranken. Dies kann die vorhandenen Modell in der eigenen Sammlung oder besondere Turnierregeln darstellen (Highlander, Trippelung verboten, nur 1 Hive Tyrant pro Detachment 😉
  • Ziel ist es, unter Variation der Anzahl von Instanzen für jedes Datasheet die summierte Effektivität der Armee zu maximieren, wobei das Punktelimit und die Detachment-Limitierung eingehalten werden.

Dieses sehr einfache lineare Modell zeigt dann auch wunderbar das übliche Verhalten bei Turnierlisten. Die beste Einheit jedes Slots wird bis zum Limit dupliziert, danach wird die zweitbeste Einheit ausgewählt, und so weiter, bis das Punktelimit erreicht wird. Dafür muss man auch eigentlich keine Berechnung ausführen, eine Betrachtung der Karush-Kuhn-Tucker Bedingungen der Zielfunktion wird für den linearen Fall das gleiche Ergebnis sagen: das Optimum liegt immer an den Randbedingungen. Wenn also ein Turnierspieler rational agiert wird er zu einem ähnlichen Ergebnis kommen. Natürlich wird jeder seine eigenen Effektivitätszahlen im Kopf haben (die ja Metagame-abhängig sind) und somit zu leicht anderen Zusammenstellungen kommen.

Warum hab ich das Ganze also durch exerziert? Zum einen, weil es mir Spaß gemacht hat das Thema einmal theoretisch zu modellieren. Zum anderen, weil ich die Idee habe, das Modell noch weiter zu verfeinern. Neben der einfachen linearen Effektivität könnte es einen bilinearen Term geben, der die Wechselwirkungen (=Synergien) zwischen zwei Einheiten bewertet. Ein Carnifex alleine ist vielleicht nicht so gut, aber mit Old-One-Eye in der Armee steigt seine Effektivität. Das gleiche gilt für die üblichen Buff-Charaktere wie Guilliman, Cawl, etc. Das Problem ist nun natürlich die Matrix mit Wechselwirkungsparametern zu füllen. Wie sehr verbessert ein Charakter denn jetzt eine Einheit? Im Grunde ist auch hier wieder Lintu gefragt, der das mit seinen probabilistischen Ansätzen sicher beantworten kann.
Eine weitere offensichtliche Erweiterung des Modells ist natürlich die Berücksichtigung von einzelnen Modellen und Ausrüstung, dann mit Matched-Play Punkten. Hierdurch wächst die Komplexität natürlich enorm, vor allem wenn man Wechselwirkungen zwischen Einheitenprofilen und Waffen berücksichtigen will (e.g. ein Melter ist auf einem Tau-Commander effektiver als auf einem Crisis-Suit).

Ich habe das Modell mit Hilfe der Software AMPL aufgestellt und gelöst. AMPL gibt es als kostenlose Demo-Version (mit reduziertem Umfang): https://ampl.com/try-ampl/download-a-free-demo/

Als letztes füge ich noch die drei Dateien an, die das Modell implementieren:
Gleichungen des Modells:

Code:

set Datasheets;
set Roles;

param P {j in Datasheets }; # Power point cost for datasheet
param K {j in Datasheets }; # Effectiveness/value of datasheet (=guess)

param LD {j in Datasheets}; # lowerbound for datasheet (= personal preference)
param UD {j in Datasheets}; # upperbound for datasheet (= available models in collection)

param LR {i in Roles};        # lowerbound for battlefield role, taken from detachments
param UR {i in Roles};        # upperbound for battlefield role, taken from detachments

param Map {j in Datasheets, i in Roles}; # Which datasheet has which battlefield role

var d {j in Datasheets} integer >=0, <= 10; # How many instances of each datasheet does the army have
var s {i in Roles } >=0;            # How many datasheets of each role does the army have

var p1;                            # power point cost for the selected units
var pTotal;                        # total power point cost for the army

maximize Effectiveness: sum { j in Datasheets } K[j]*d[j];

subject to UnitPoints: p1 = sum { j in Datasheets } P[j]*d[j];
subject to Points: pTotal = p1;
subject to P_limit: 0 <= pTotal <= 100; subject to DatasheetLimits {j in Datasheets}: LD[j] <= d[j] <=UD[j]; subject to BattlefieldRoles1 {i in Roles}: s[i] = sum { j in Datasheets } Map[j,i]*d[j];
subject to BattlefieldRoles2 {i in Roles}: LR[i] <= s[i] <=UR[i];


Daten für Tyraniden:

Code:

set Datasheets :=  BroodLord HiveTyrant Swarmlord TyranidPrime Tervigon Neurothrope OldOneEye
          TyranidWarriors Genestealer Termagants Hormagaunts RipperSwarms
          TyrantGuard HiveGuard Zoanthropes
          Exocrine Tyrannofex Carnifex;

set Roles := HQ Elite Standard FastAttack HeavySupport Flyer Transport;

#Battlefield roles are for a single battalion detachment
param:            LR        UR :=
HQ                1        3
Elite            0        3
Standard        3        6
FastAttack        0        3
HeavySupport    0        3
Flyer            0        2
Transport        0        99;

#P is taken from the codex, K is guessed, LD and UD correspond to your collection and /or preferences         
param:            P        K    LD    UD:=
BroodLord        8        2  0  3
HiveTyrant        9        3  0  1
Swarmlord        15        2  0  3
TyranidPrime    6        1  0  3
Tervigon        13        1  0  3
Neurothrope    4        2  0  3
OldOneEye        10        1  0  3
TyranidWarriors 5        1  0  3
Genestealer    4        3  0  3
Termagants        3        1  0  3
Hormagaunts    3        1  0  3
RipperSwarms    2        2  0  3
TyrantGuard    7        1  0  3
HiveGuard        7        3  0  3
Zoanthropes        6        2  0  3
Exocrine        11        4  0  3
Tyrannofex        11        3  0  3
Carnifex        6        2  0  3;

#Mapping Table between datasheet and battlefield role
param Map:
                HQ    Elite    Standard    FastAttack    HeavySupport    Flyer    Transport :=
BroodLord          1      0          0              0              0                  0          0
HiveTyrant        1      0          0              0              0                  0          0
Swarmlord        1      0          0              0              0                  0          0
TyranidPrime    1      0          0              0              0                  0          0
Tervigon        1      0          0              0              0                  0          0
Neurothrope    1      0          0              0              0                  0          0
OldOneEye        1      0          0              0              0                  0          0
TyranidWarriors 0      0          1              0              0                  0          0
Genestealer    0      0          1              0              0                  0          0
Termagants        0      0          1              0              0                  0          0
Hormagaunts    0      0          1              0              0                  0          0
RipperSwarms    0      0          1              0              0                  0          0
TyrantGuard    0      1          0              0              0                  0          0
HiveGuard        0      1          0              0              0                  0          0
Zoanthropes        0      1          0              0              0                  0          0
Exocrine        0      0          0              0              1                  0          0
Tyrannofex        0      0          0              0              1                  0          0
Carnifex        0      0          0              0              1                  0          0;


Script zum schnellen Testen des Modells:

Code:

reset;
model warhammer.mod;
data tyranids.dat;
option solver cplex;

solve;
display d ;
display s;
display pTotal;


Die optimale Lösung für die gewählten (*hust* geratenen) Parameter lautet:

Code:

ampl: include test.run;
CPLEX 12.8.0.0: optimal integer solution; objective 43
4 MIP simplex iterations
0 branch-and-bound nodes
d [*] :=
      BroodLord  2
      Carnifex  0
      Exocrine  3
    Genestealer  3
      HiveGuard  3
    HiveTyrant  1
    Hormagaunts  0
    Neurothrope  0
      OldOneEye  0
  RipperSwarms  3
      Swarmlord  0
    Termagants  0
      Tervigon  0
  TyranidPrime  0
TyranidWarriors  0
    Tyrannofex  0
    TyrantGuard  0
    Zoanthropes  0
;

s [*] :=
      Elite  3
  FastAttack  0
      Flyer  0
          HQ  3
HeavySupport  3
    Standard  6
  Transport  0


Eigentlich bin ich mit dem Post 10 Tage zu spät. :rolleyes: Aber ich hoffe ihr habt trotzdem Spaß an so einem übertrieben komplexen, verquasten Theorieverhau. Ich würde mich auf jeden Fall über Input und Feedback freuen.

Dieser Artikel stammt von einer der angeschlossenen Quellen. Bitte honoriere die Arbeit der Autoren indem du ihren Webseite besuchst.

Artikelquelle besuchen
Autor: NukleonGW-FanworldGW-FanworldGW-Fanworld

Powered by WPeMatico

Anzeige:
Eis.de