MathHammer 2.0: Armeezusammenstellung als MILP

Die Theorie hat halt, wie bereits angemerkt, eine große Hürde bevor sie in der Realität angewendet werden kann: Sie benötigt gute Parameter. In diesem Fall sind es die "Einheiteneffektivitäten". Über eine solche Metrik wurde ja schon breit diskutiert und es hat sich jedes Mal als schwer zu knackende Nuss erwiesen. Klar ist, dass zum einen die Statline aber auch Sonderregeln, und idealerweise die Existenz andere Einheiten in der Armee (=Buffchars) berücksichtigt werden sollte. Was ich mir erhoffe ist, dass man zumindest die "relativen" Effektivitäten irgendwie abbilden kann. Wenn man realistische Werte gefunden hat, und bekannte Armeen als Ergebnis herauskommen, kann man anfangen mit den Randbedingungen zu spielen.
Mögliche Fragestellungen wären:
* Wie ändert sich die "optimale" Armee, wenn ein Modell um 10/20/30% teurer wird
* Welche Einheiten werden gewählt, wenn eine Obergrenze für eine bestimmte Einheit aktiviert wird? Gerade wenn Interaktionen berücksichtigt werden kann das Ergebnis schon stark abweichen. Beispiel Tyraniden: Wenn die HiveTyrants wirklich auf einen pro Detachment begrenzt werden, kann es vielleicht sein, dass anstelle dessen der OldOneEye und dazu noch 2 Carnifexe gewählt werden, weile diese Kombination noch effizienter ist als das zweitbeste HQ.

Im Grunde könnte man mit so einem Modell den "Hardcore"-Turnierspieler simulieren, der die Liste immer knallhart ausreizt. Also genau das, was sich viele Wünschen. Falsche Punkte könnten so frühzeitig entdeckt werden, und man müsste nicht auf ein Turnier warten bis ein menschlicher Optimierer die Lösung findet. Aber auch hier gilt Vorsicht: Jedes Modell ist nur so gut, wie die zu grunde liegende Datenbasis. Große Wunder sollte man sich nicht versprechen, aber vielleicht ein nützliche Werkzeug.

Ansonsten: Ja ich bin Ingenieur, aber habe über dem Thema der optimalen Auswahl von Verfahrensoperationen im Zusammenspiel einer Chemieanlage promoviert. Und die zugrundeliegende Mathematik ist dann sehr ähnlich. Das ist ja das schöne daran: die abstrakten Lösungsansätze lassen sich für viele Probleme anwenden, wenn man sie nur richtig herunterbricht und abstrahiert. Interessanterweise sind auch hier die zugrunde liegenden Daten oft Unsicher, und es gibt tatsächlich Methoden auch mit unsicheren/unbekannten Daten Optimierungen anzustellen. Also eigentlich genau das Problem, mit dem wir hier auch zu tun haben.

Zur Einarbeitung? Puh, das wird schwierig. Lineare Optimierung ist nicht wirklich ein Thema das der Populärwissenschaft zugänglich ist. Diese Präsentation sieht noch ganz zugänglich aus (außerdem enthält sie einen Katzentutor!! 🙂 ) https://ocw.mit.edu/courses/sloan-s...-spring-2013/tutorials/MIT15_053S13_tut01.pdf

Auf Youtube gibt es auch einige Video-Tutorials, vielleicht ist da auch was dabei: https://www.youtube.com/results?search_query=linear+programming+explained
 
Zur Einarbeitung? Puh, das wird schwierig. Lineare Optimierung ist nicht wirklich ein Thema das der Populärwissenschaft zugänglich ist. Diese Präsentation sieht noch ganz zugänglich aus (außerdem enthält sie einen Katzentutor!! 🙂 ) https://ocw.mit.edu/courses/sloan-s...-spring-2013/tutorials/MIT15_053S13_tut01.pdf

Auf Youtube gibt es auch einige Video-Tutorials, vielleicht ist da auch was dabei: https://www.youtube.com/results?search_query=linear+programming+explained

Besten Dank!
Ich fand das recht anschaulich, auch wenn ich nicht behaupten kann, dass ich diese Gleichungen dann auch auf ein reales Problem übertragen könnte...😉

Verwirrt hat mich weiter Tom, der Truthahn, den ich optisch jetzt eher nicht als "Knaben" gesehen hätte...😀
 
Wow sehr interessante Arbeit. Ich hatte schonmal daran gedacht etwas ähnliches zu versuchen. Allerdings wäre mein Ansatz gewesen die armee Liste als mehrdimensionale energiefunktion darzustellen (jeder force organisation slot eine Dimension). Das optimum ließe sich dann durch Minimierung dieser funktion finden. Zb durch simulated annealing. Bisher ist es bei mir aber daran gescheitert diese Fkt zu definieren. Vielleicht versuche ich es mal mit diesen Effektivitätszahlen!

Interesant wäre jetzt natürlich noch die Effektivitätszahlen aus dem datasheet zu berechnen (am besten in Abhängigkeit der gegnerischen Armee). Hier könnte man eventuell was aus der wahrscheinlichkeit, eine gegnerische Einheit zu verwunden basteln:
Man weißt jeder Einheit eine zielklasse vor. Ein orkboy hat Infanterie als Ziel. Ein admech dunecrawler mit neutronenlaser geht auf Fahrzeuge. Nun berechne ich die über alle gegnerischen Einheiten dieses Typs gemittelt Wahrscheinlichkeit diese zu verwunden/zerstören und lasse irgendwie noch die Punktekosten einfließen....

Mal sehen ob ich da was gebaut bekomme...
 
Zuletzt bearbeitet:
Hey danijoo, cool das dich sowas interessiert. Ich habe in der Zwischenzeit an dem Programm weitergebaut, aber bin auf ein paar Limitierungen gestoßen. Sobald man das Modell komplexer baut, kommen nichtlineare Terme ins Spiel, die von den kostenlosen Solvern nicht mehr behandelt werden können. Um also komplexe Modelle lösen zu können, wird mir wahrscheinlich nichts anderes übrig bleiben als einen nicht-deterministischen Solver wie Simulated Annealing oder einen Evolutionary Algorithm zu verwenden. Dann wird es mit den Constraints (maximale Anzahl von Datasheets, Punktelimits usw.) etwas schwieriger, aber man beliebige nichtlineare Funktionen einbauen. Das Grundproblem bleibt aber bestehen: die Lösung liegt eigentlich immer an den Constraints und ist "offensichtlich".

Zum Thema Effektivitätszahlen: Dieser Artikel von Lintu erklärt die Theorie dahinter ganz gut. http://www.tabletopmasters.de/2016/11/29/warum-entwickelt-sich-ein-meta/

Die Kernidee dahinter ist, ein Modell des Spiels zu entwickeln, dass repräsentativ für eine Vielzahl von Situationen ist, und diese anhand einer geschätzten Eintrittswahrscheinlichkeit am Spieltisch gewichtet. Das führt dann dazu, dass die Fähigkeit Schaden im Beschuss zu machen für alle 6" Intervalle bis z.B. 72" ausgewertet wird, und die Zahlen mit einer Wahrscheinlichkeit multipliziert werden, die angibt wie häufig die Situation auftritt. Damit erhält man dann eine Zahl die angibt wie gut eine Einheit im Schnitt über alle Spielsituationen austeilen kann. Die gleiche Berechnung kann man dann auch rückwärts ausführen um zu berechnen wie viel eine Einheit einstecken kann. Hier sind die Szenarien dann übliche Waffenprofile von oft gespielten Einheiten.

Der Nachteil an Statline-basierten Systemen ist die Unfähigkeit Sonderregeln korrekt abzubilden. An dieser Stelle ist man dann wieder auf heuristische Schätzungen oder Daumenregeln angewiesen. Aber man hat zumindest einen fundierten Baseline-Wert um den man herum optimieren kann.
 
Hey danijoo, cool das dich sowas interessiert. Ich habe in der Zwischenzeit an dem Programm weitergebaut, aber bin auf ein paar Limitierungen gestoßen. Sobald man das Modell komplexer baut, kommen nichtlineare Terme ins Spiel, die von den kostenlosen Solvern nicht mehr behandelt werden können. Um also komplexe Modelle lösen zu können, wird mir wahrscheinlich nichts anderes übrig bleiben als einen nicht-deterministischen Solver wie Simulated Annealing oder einen Evolutionary Algorithm zu verwenden. Dann wird es mit den Constraints (maximale Anzahl von Datasheets, Punktelimits usw.) etwas schwieriger, aber man beliebige nichtlineare Funktionen einbauen. Das Grundproblem bleibt aber bestehen: die Lösung liegt eigentlich immer an den Constraints und ist "offensichtlich".

Zum Thema Effektivitätszahlen: Dieser Artikel von Lintu erklärt die Theorie dahinter ganz gut. http://www.tabletopmasters.de/2016/11/29/warum-entwickelt-sich-ein-meta/

Die Kernidee dahinter ist, ein Modell des Spiels zu entwickeln, dass repräsentativ für eine Vielzahl von Situationen ist, und diese anhand einer geschätzten Eintrittswahrscheinlichkeit am Spieltisch gewichtet. Das führt dann dazu, dass die Fähigkeit Schaden im Beschuss zu machen für alle 6" Intervalle bis z.B. 72" ausgewertet wird, und die Zahlen mit einer Wahrscheinlichkeit multipliziert werden, die angibt wie häufig die Situation auftritt. Damit erhält man dann eine Zahl die angibt wie gut eine Einheit im Schnitt über alle Spielsituationen austeilen kann. Die gleiche Berechnung kann man dann auch rückwärts ausführen um zu berechnen wie viel eine Einheit einstecken kann. Hier sind die Szenarien dann übliche Waffenprofile von oft gespielten Einheiten.

Der Nachteil an Statline-basierten Systemen ist die Unfähigkeit Sonderregeln korrekt abzubilden. An dieser Stelle ist man dann wieder auf heuristische Schätzungen oder Daumenregeln angewiesen. Aber man hat zumindest einen fundierten Baseline-Wert um den man herum optimieren kann.

Sehr interessanter Link. Danke! Man könnte sich auch überlegen ob es Sinn macht noch einen Schritt weiter zu gehen und eine sehr vereinfachte Version des Spiels tatsächlich zu simulieren. Dh man unterteilt das Board in ein Grid (3"?) auf dem sich Einheiten bewegen und schießen können, stellt jede Armee zufällig auf und macht random moves. Am Ende jeder Simulation steht ein Fitnesswert der die Performance anzeigt. Die Energiefunktion ist dann die gemittelte Performance über viele Simulationen mit der gleichen Armeezusammenstellung. Vorteil: Man kann extrem ins Detail gehen und alle möglichen Synergien, Buffs etc modellieren. Allerdings wird es auch dabei auch beliebig kompliziert (und auch rechenintensiv).

Die Frage ist ob sich damit tatsächlich noch andere Resultate ergeben. Meine Vermutung ist das die "optimale" Lösung wahrscheinlich nicht großartig von einem Statline basierten System abweichen wird. Eventuell ließen sich damit allerdings weitere nicht ganz so optimale Lösungen (lokale Energieminima) finden. Ich würde zB. bei den meisten Armeen mindestens 2 lokale Minima erwarten, bei denen es sich jeweils um eine CC zentrierte und eine Beschuss zentrierte Liste handelt.
 
Zuletzt bearbeitet:
Eine Computersimulation um die optimale Liste für ein Tabletopspiel zu finden?! Den mathematische Reiz dahinter verstehe ich sehr gut, allerdings bin ich mir nicht sicher ob das nicht ein wenig übers Ziel hinaus ist. Andererseits würde sich das bestimmt gut verkaufen. Blöd ist dann nur, dass die Armeelisten je nach Volk dann alle gleich sind. (Bis zum nächsten FAQ)

cya
 
Solange die Kostenfunktion nur lineare Terme hat, wird sich ein konvexes Problem ergeben, das genau ein globales Optimum hat. Erst mit Termen höherer Ordnung können nicht-konvexe Einflüsse mehrer lokale Optima hervorrufen.

Um dein Beispiel aufzugreifen. Solange Nahkampf und fernkampf nur mit konstanten Wahrscheinlichkeiten gewichtet werden, wird eine Lösung immer besser sein als die andere.

Eine brauchbare Alternative könnten mehrkriterielle Optimierung sein, da man so ein Spektrum von Armeen generieren könnte die in jeder Zielfunktion (fernkampfpower, Nahkampf, Zähigkeit, Mobilität) Trade-offs aufweisen und der Anwender entscheidet dann nach seiner Präferenz was er spielen möchte.

Das schöne an so einem System wäre das man für jede Armee einen Fingerprint anhand 4-5 Kennzahlen erstellen könnte um so Armeen vergleichbarer zu machen.
 
Solange die Kostenfunktion nur lineare Terme hat, wird sich ein konvexes Problem ergeben, das genau ein globales Optimum hat. Erst mit Termen höherer Ordnung können nicht-konvexe Einflüsse mehrer lokale Optima hervorrufen.

.

Genau das wollte ich auch eben sagen!😀

Mal im Ernst: Ist das eigentlich praktisch auch machbar, was Ihr hier andenkt? Ich finde die theoretische Idee ja auch schön, aber als Laie klingt das sowohl vom Umfang als auch von der Berechnung her sehr aufwändig?!

Verlässt sich GW bei dem Spiel-Design der Editionen eigentlich auf solche Computer-Simulationen, oder machen die das "frei Schnauze"?
 
Genau das wollte ich auch eben sagen!😀

Mal im Ernst: Ist das eigentlich praktisch auch machbar, was Ihr hier andenkt? Ich finde die theoretische Idee ja auch schön, aber als Laie klingt das sowohl vom Umfang als auch von der Berechnung her sehr aufwändig?!

Verlässt sich GW bei dem Spiel-Design der Editionen eigentlich auf solche Computer-Simulationen, oder machen die das "frei Schnauze"?

Machbar ist es auf jedenfall. Ich mache beruflich das gleiche für komplexere Systeme (Simulationen von atomistischen Systemen). Es wird halt nur sehr kompliziert sowas zu schreiben wenn man das Spiel im Detail beschreiben will. Und dann ist die Frage wie schon gesagt ob man da was findet was man nicht auch einfacher finden kann (zb durch deterministische Optimierung).das müsste man einfach mal ausprobieren.