70 Septillionen
Ich wollte immer schon mal mit der WoW-API rumspielen. Neben einem WoW-Ereignis-Feed-nach-Twitter-Konverter (Status: fast fertig – das Auslesen steht, Twitter-Anbindung wäre trivial, aber ein Problem verbleibt: accountweite Erfolge werden für jeden Charakter doppelt gemeldet und es gibt in der Datenbasis kein Kennzeichen, um den echten zu finden und den anderen rauszufiltern) dachte ich an einen Ausrüstungsoptimierer.
Es folgt ein kleiner Exkurs für die nicht-WoWler:
Ausrüstungsgegenstände haben besondere Bonuswerte (z.B. +133 Punkte Stärke oder +57 Punkte Parieren). Zusätzlich können die Gegenstände individualisiert werden:
Im Endgame, also dann, wenn man sich durch die tiefsten Dungeons mit den fiesesten Bossen kloppt, kommt man ohne Ausrüstungsoptimierung nicht weit. Je nach Charakterklasse und -rasse sowie Talentspezialisierung gibt es dabei andere Idealwerte, die man erreichen sollte. Für meinen Schutz-Paladin sieht das z.B. so aus: Erstmal 2550 Trefferwertung sammeln, damit jeder Schlag trifft. Außerdem 2550 Waffenkunde sammeln, damit niemand mehr ausweichen kann (ist man ein Zwerg mit Einhandstreitkolben, braucht man stattdessen nur 2210 Punkte, das soll ja nicht zu einfach sein alles!). Beide Male ist jeder Punkt zu viel ein verschenkter Punkt, denn mehr als ‚immer treffen’ geht nicht. Man will also so nah an die Werte ran wie möglich — aber nicht unterbieten! Auf Platz drei folgt dann so viel Ausdauer wie nur möglich, danach kommt möglichst viel Meisterschaft und so weiter (Parieren und Ausweichen im Verhältnis 1:2 – oder war’s 2:1?).
Eine einfache Folge aus dem Wertesystem ist die Wahl der Gegenstände selbst: Wenn ein Boss ein paar Handschuhe mit Intelligenz und Willenskraft fallen lässt, kann ich die direkt liegen lassen, denn mit Intelligenz und Willenskraft kann ich nichts anfangen. Ausdauer muss schon sein.
Auch bei den Items, die man sich teuer kaufen kann, kann man direkt sehen: „Ah, das hier sind die Tank-Handschuhe, die will ich; die anderen, gleich teuren sind die für den Heiler, also nichts für mich.“
Komplizierter wird es dann, wenn man anfängt, umzuschmieden und zu verzaubern. Beispiel:
„Aktuell habe ich 50 Punkte Trefferwertung zu wenig. Wenn ich jetzt auf den Handschuhen Parieren in Trefferwertung umschmiede, dann kann sind das gleich 227 Punkte mehr – ich habe dann den magischen Wert erreicht, aber auch 177 Punkte verschwendet, die wären woanders sinnvoller investiert werden und Waffenkunde habe ich momentan eh noch zu wenig… Kann ich noch irgendwo weniger als 177 Punkte Trefferwertung in Waffenkunde umschmieden? Oder vielleicht einen Edelstein umsockeln? Verzauberung wechseln?“
Wenn ich momentan über ein tolles neues Item stolpere, bin ich erstmal mindestens eine halbe Stunde mit Punkte-Umkonstruktion beschäftigt — vor allem, da ich meinen Vergelter-Paladin ja auch passend einstellen muss und sich bei beidem die meisten Items überschneiden, also sich eine Änderung hier wie dort auswirkt, aber in beiden Varianten unterschiedliche Zielwerte gelten…
Wenn man (wie ich) ein detailverliebter Punkteknauserer ist und möglichst genau an die Idealwerte ran will, wird es unübersichtlich. Einfach verschiedene Sachen ausprobieren geht schnell ins Gold, da sämtliche Änderungen natürlich alles andere als kostenlos sind. Im Kopf ist mir das zu kompliziert. Verschiedene Varianten auf einem Stück Papier durchzuspielen hilft in begrenzten Einzelfällen, allumfassend geht das aber nicht, dafür ist das ganze zu umfangreich.
Wenn man (wie ich) sowieso schon mit der WoW-API rumspielen will, kommt man schnell auf die Idee: Schreib ich doch einfach ein Programm dafür!
Gesagt, getungetan. (Exkurs zu Ende)
Datenmodell: Listen von Hashes von Hashes von Listen, yay, ich mag Perl!
Charakterdaten über die API auslesen: fertig
Itemwerte über die API auslesen: fertig
Umschiederegelwerk nachprogrammieren: fertig
mögliche Verzauberungen und Edelsteine ermitteln: na ja, halbautomatisch, ich habe die für mich relevanten erstmal fest ins Programm eingetippt
Scoring-System schreiben, das eine Ausrüstungs-Konstellation bewertet, so dass ich die beste finden kann: fertig
Alle Ausrüstungsmöglichkeiten durchprobieren und den jeweiligen Score errechnen: URKS, das dauert aber doch sehr schnell sehr lange. Das geht so nicht. Erstmal nur mit 6 Items probieren… Zum Entwickeln und testen gut, aber letztendlich auch keine Lösung. Und wenn ich mehrere Threads nehme? Aber wie kommunizieren die miteinander? Queues? Huch, mehr als 9GB Speicherverbrauch, vielleicht sollte ich nicht alles in einer Queue parken, sondern die verschiedenen Schritte lieber parallel in einer Pipeline verarbeiten… Huch, was macht der hier für einen Mist, wieso ändern sich die Daten unter meinem Hintern? Ach, das sind immer noch Referenzen und keine Kopien. Wo kriege ich denn jetzt ein deep_clone() her?
Zwischenergebnis:
Ich habe haufenweise was zu Threading, Queues und Serialisierung in Perl gelernt.
7 verschiedene Programmversionen sind entstanden, die alle verschiedene Varianten zur Problemlösung benutzen. Manches hat sich sofort als Irrweg rausgestellt, manches erst später.
Der Weg ist das Ziel, interessant war’s.
Aber letztendlich: Alles für die Katz! Denn:
Endergebnis:
Die letzte Programmversion sollte die Datenmengen verringern, in dem es für jeden Gegenstand alle möglichen Kombinationen und deren Wertegerüst nur einmalig ermittelt und dann in einer Liste ablegt. Dann muss ich nachher nur noch pro Gegenstand eine fertige Liste durchgehen und nicht bei jede Kombination zig Mal unnötigerweise neu errechnen. Spart Zeit und Speicherplatz. Ein Nebeneffekt davon war: Ich weiß, bevor das große finale ‚kombiniere alle Möglichkeiten
durch und errechne den Score’ läuft, schon, wieviele Kombinationen es nachher in Summe sind, kann also die Laufzeit abschätzen oder einen Fortschrittsbalken malen.
Leider sprengte die Anzahl der Kombinationen den Rahmen eines durchschnittlichen Perl-Scalars, also musste ich auf bc(1) zum Errechnen des Ergebnisses wechseln:
Das sind über den Daumen 70 Septillionen* äh Quadrillionen** Möglichkeiten, eine Zahl mit 26 Stellen.
Selbst, wenn ich eine Milliarde Kombinationen pro Sekunde durchrechnen könnte, würde ich noch ca. 2,25 Milliarden Jahre dafür brauchen. Das ist grob die Hälfte der bisherigen Lebensdauer unseres Sonnensystems.
Programmierprojekt an dieser Stelle gestoppt, das dauert mir dann doch etwas zu lange. Das kommt halt davon, dass 16 Itemslots vorhanden sind.
Immerhin erklärt das, warum noch niemand einen Webdienst programmiert hat, der das macht, was ich mir da ausgedacht habe.
* Die 70 Septillionen sind nur ein sehr konservativer Schätzwert, da ich, nachdem ich das gesehen habe, den Code für die Edelsteinsockelung nicht mehr fertigprogrammiert habe. Aktuell wird nur mit einem (vermutlich deutlich) zu niedrigen Ansatz von 6 möglichen Steinen pro Sockel gerechnt. In der Praxis dürften das durchaus mehr sein, was dann die Anzahl der Kombinationen exponentiell erhöht…)
** Wer’s schon gemerkt hat: 70 Septillionen ist natürlich mathematisch falsch. Wolfram Alpha hat „70 septillions” ausgespuckt, da aber der US-Sprachgebrauch und der des Rests der Welt (zumindest unseres Teils davon) ab 10⁹ auseinanderdriften („billion” vs. „Milliarde”), müsste es im Deutschen „70 Quadrillionen” heißen. Weil mir das erst jetzt auffällt, ich es hier brav erkläre und ich den falschen Titel einfach schmissiger finde, heißt der Blogartikel noch so, wie er heißt.
Es folgt ein kleiner Exkurs für die nicht-WoWler:
Ausrüstungsgegenstände haben besondere Bonuswerte (z.B. +133 Punkte Stärke oder +57 Punkte Parieren). Zusätzlich können die Gegenstände individualisiert werden:
- man kann Werte nach bestimmten Regeln teilweise umschmieden (z.B. nach dem Motto „Ich bin ein Fernkämpfer, ich brauche keine Parierwertung, ich wandele das lieber in Trefferwertung um”)
- bestimmte Sachen können mit verschiedenen Verzauberungen aufgewertet werden (z.B. Handschuhe mit +170 Meisterschaft verzaubern)
- sehr gute Gegenstände haben Sockelplätze, in die verschiedene Edelsteine (oder Zahnräder) eingesetzt werden können, die ihrerseits wieder Bonuspunkte mitbringen („nehme ich jetzt einen Edelstein mit +240 Ausdauer oder lieber einen mit +300 Meisterschaft?”)
- wenn man Edelsteinsockel in den passenden Farben füllt, gibt es zusätzlich noch einen Sockelbonus (z.B. nochmal +120 Stärke extra)
- außerdem kann man Gegenstände transmogrifizieren, d.h. ihr Aussehen aufpeppen – das hat aber keine Auswirkung auf die Werte und ist deshalb an dieser Stelle egal ☺
Im Endgame, also dann, wenn man sich durch die tiefsten Dungeons mit den fiesesten Bossen kloppt, kommt man ohne Ausrüstungsoptimierung nicht weit. Je nach Charakterklasse und -rasse sowie Talentspezialisierung gibt es dabei andere Idealwerte, die man erreichen sollte. Für meinen Schutz-Paladin sieht das z.B. so aus: Erstmal 2550 Trefferwertung sammeln, damit jeder Schlag trifft. Außerdem 2550 Waffenkunde sammeln, damit niemand mehr ausweichen kann (ist man ein Zwerg mit Einhandstreitkolben, braucht man stattdessen nur 2210 Punkte, das soll ja nicht zu einfach sein alles!). Beide Male ist jeder Punkt zu viel ein verschenkter Punkt, denn mehr als ‚immer treffen’ geht nicht. Man will also so nah an die Werte ran wie möglich — aber nicht unterbieten! Auf Platz drei folgt dann so viel Ausdauer wie nur möglich, danach kommt möglichst viel Meisterschaft und so weiter (Parieren und Ausweichen im Verhältnis 1:2 – oder war’s 2:1?).
Eine einfache Folge aus dem Wertesystem ist die Wahl der Gegenstände selbst: Wenn ein Boss ein paar Handschuhe mit Intelligenz und Willenskraft fallen lässt, kann ich die direkt liegen lassen, denn mit Intelligenz und Willenskraft kann ich nichts anfangen. Ausdauer muss schon sein.
Auch bei den Items, die man sich teuer kaufen kann, kann man direkt sehen: „Ah, das hier sind die Tank-Handschuhe, die will ich; die anderen, gleich teuren sind die für den Heiler, also nichts für mich.“
Komplizierter wird es dann, wenn man anfängt, umzuschmieden und zu verzaubern. Beispiel:
„Aktuell habe ich 50 Punkte Trefferwertung zu wenig. Wenn ich jetzt auf den Handschuhen Parieren in Trefferwertung umschmiede, dann kann sind das gleich 227 Punkte mehr – ich habe dann den magischen Wert erreicht, aber auch 177 Punkte verschwendet, die wären woanders sinnvoller investiert werden und Waffenkunde habe ich momentan eh noch zu wenig… Kann ich noch irgendwo weniger als 177 Punkte Trefferwertung in Waffenkunde umschmieden? Oder vielleicht einen Edelstein umsockeln? Verzauberung wechseln?“
Wenn ich momentan über ein tolles neues Item stolpere, bin ich erstmal mindestens eine halbe Stunde mit Punkte-Umkonstruktion beschäftigt — vor allem, da ich meinen Vergelter-Paladin ja auch passend einstellen muss und sich bei beidem die meisten Items überschneiden, also sich eine Änderung hier wie dort auswirkt, aber in beiden Varianten unterschiedliche Zielwerte gelten…
Wenn man (wie ich) ein detailverliebter Punkteknauserer ist und möglichst genau an die Idealwerte ran will, wird es unübersichtlich. Einfach verschiedene Sachen ausprobieren geht schnell ins Gold, da sämtliche Änderungen natürlich alles andere als kostenlos sind. Im Kopf ist mir das zu kompliziert. Verschiedene Varianten auf einem Stück Papier durchzuspielen hilft in begrenzten Einzelfällen, allumfassend geht das aber nicht, dafür ist das ganze zu umfangreich.
Wenn man (wie ich) sowieso schon mit der WoW-API rumspielen will, kommt man schnell auf die Idee: Schreib ich doch einfach ein Programm dafür!
Gesagt, getungetan. (Exkurs zu Ende)
Datenmodell: Listen von Hashes von Hashes von Listen, yay, ich mag Perl!
Charakterdaten über die API auslesen: fertig
Itemwerte über die API auslesen: fertig
Umschiederegelwerk nachprogrammieren: fertig
mögliche Verzauberungen und Edelsteine ermitteln: na ja, halbautomatisch, ich habe die für mich relevanten erstmal fest ins Programm eingetippt
Scoring-System schreiben, das eine Ausrüstungs-Konstellation bewertet, so dass ich die beste finden kann: fertig
Alle Ausrüstungsmöglichkeiten durchprobieren und den jeweiligen Score errechnen: URKS, das dauert aber doch sehr schnell sehr lange. Das geht so nicht. Erstmal nur mit 6 Items probieren… Zum Entwickeln und testen gut, aber letztendlich auch keine Lösung. Und wenn ich mehrere Threads nehme? Aber wie kommunizieren die miteinander? Queues? Huch, mehr als 9GB Speicherverbrauch, vielleicht sollte ich nicht alles in einer Queue parken, sondern die verschiedenen Schritte lieber parallel in einer Pipeline verarbeiten… Huch, was macht der hier für einen Mist, wieso ändern sich die Daten unter meinem Hintern? Ach, das sind immer noch Referenzen und keine Kopien. Wo kriege ich denn jetzt ein deep_clone() her?
Zwischenergebnis:
Ich habe haufenweise was zu Threading, Queues und Serialisierung in Perl gelernt.
7 verschiedene Programmversionen sind entstanden, die alle verschiedene Varianten zur Problemlösung benutzen. Manches hat sich sofort als Irrweg rausgestellt, manches erst später.
Der Weg ist das Ziel, interessant war’s.
Aber letztendlich: Alles für die Katz! Denn:
Endergebnis:
Die letzte Programmversion sollte die Datenmengen verringern, in dem es für jeden Gegenstand alle möglichen Kombinationen und deren Wertegerüst nur einmalig ermittelt und dann in einer Liste ablegt. Dann muss ich nachher nur noch pro Gegenstand eine fertige Liste durchgehen und nicht bei jede Kombination zig Mal unnötigerweise neu errechnen. Spart Zeit und Speicherplatz. Ein Nebeneffekt davon war: Ich weiß, bevor das große finale ‚kombiniere alle Möglichkeiten
durch und errechne den Score’ läuft, schon, wieviele Kombinationen es nachher in Summe sind, kann also die Laufzeit abschätzen oder einen Fortschrittsbalken malen.
Leider sprengte die Anzahl der Kombinationen den Rahmen eines durchschnittlichen Perl-Scalars, also musste ich auf bc(1) zum Errechnen des Ergebnisses wechseln:
96 * 24 * 108 * 66 * 36 * 42 * 44 * 48 * 48 * 66 * 42 * 56 * 18 * 5 * 56 * 36
= 70900842907547234488811520
Das sind über den Daumen 70 Septillionen* äh Quadrillionen** Möglichkeiten, eine Zahl mit 26 Stellen.
Selbst, wenn ich eine Milliarde Kombinationen pro Sekunde durchrechnen könnte, würde ich noch ca. 2,25 Milliarden Jahre dafür brauchen. Das ist grob die Hälfte der bisherigen Lebensdauer unseres Sonnensystems.
Programmierprojekt an dieser Stelle gestoppt, das dauert mir dann doch etwas zu lange. Das kommt halt davon, dass 16 Itemslots vorhanden sind.
Immerhin erklärt das, warum noch niemand einen Webdienst programmiert hat, der das macht, was ich mir da ausgedacht habe.
* Die 70 Septillionen sind nur ein sehr konservativer Schätzwert, da ich, nachdem ich das gesehen habe, den Code für die Edelsteinsockelung nicht mehr fertigprogrammiert habe. Aktuell wird nur mit einem (vermutlich deutlich) zu niedrigen Ansatz von 6 möglichen Steinen pro Sockel gerechnt. In der Praxis dürften das durchaus mehr sein, was dann die Anzahl der Kombinationen exponentiell erhöht…)
** Wer’s schon gemerkt hat: 70 Septillionen ist natürlich mathematisch falsch. Wolfram Alpha hat „70 septillions” ausgespuckt, da aber der US-Sprachgebrauch und der des Rests der Welt (zumindest unseres Teils davon) ab 10⁹ auseinanderdriften („billion” vs. „Milliarde”), müsste es im Deutschen „70 Quadrillionen” heißen. Weil mir das erst jetzt auffällt, ich es hier brav erkläre und ich den falschen Titel einfach schmissiger finde, heißt der Blogartikel noch so, wie er heißt.
Geschrieben von 
mitch
mitch
Trackbacks
Trackback-URL für diesen Eintrag
Kommentare
Ansicht der Kommentare:
(Linear | Verschachtelt)
Sven am um :
Umm, was ist mit askmrrobot.com oder wowreforge.com?
mitch am um :
Laaangweilig :-)
Ich habe so viel Spaß mit dem Werte-Wirbeln (z.B. manuell mit meinen Excel-Tabellen), das will ich nicht aus der Hand geben.
Unabhängig davon ist zumindest mrrobot ziemlich hardcore unterwegs, das sieht zahlenmässig echt genial aus. Weiß nicht, wie die das so schnell machen, vermutlich Cachen die was. Oder nicht ganz 100% brute force - obwohl da ja auch dreimal-im-Kreis-Umschieden gemacht wird.
Ich habe so viel Spaß mit dem Werte-Wirbeln (z.B. manuell mit meinen Excel-Tabellen), das will ich nicht aus der Hand geben.
Unabhängig davon ist zumindest mrrobot ziemlich hardcore unterwegs, das sieht zahlenmässig echt genial aus. Weiß nicht, wie die das so schnell machen, vermutlich Cachen die was. Oder nicht ganz 100% brute force - obwohl da ja auch dreimal-im-Kreis-Umschieden gemacht wird.
mitch am um :
...und wie die Zeit vergeht - inzwischen bin ich doch sehr MrRobot-affin geworden, geiles Tool :-))
mitch am um :
http://www.askmrrobot.com/wow/gear
Da sind aber andere Wertegewichtungen am Start als die deutschen Spielezeitungen verkünden. Wenn das jetzt in eine Diskussion über verschiedene "Schulen" von Equipment-Optimierung mündet, mache ich das einfach so, wie ich denke :-)
Da sind aber andere Wertegewichtungen am Start als die deutschen Spielezeitungen verkünden. Wenn das jetzt in eine Diskussion über verschiedene "Schulen" von Equipment-Optimierung mündet, mache ich das einfach so, wie ich denke :-)