Du bist nicht eingeloggt.

B2B-Realm Status

Social Networks

B2B auf Twitter
B2B auf Facebook

Bugtracker

Account erstellen   |   Login   |   Download / How To Play   |  FAQ   |   Support

antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

1

Samstag, 26. Juli 2014, 18:59

Zufallsproblem

Ich bin gerade eben wieder ein mal in einem Thread auf das Thema "Zufall" gestoßen.
Dabei habe ich mich daran erinnert, wie bescheiden hier die Zufälle berechnet werden. Ich hatte ja damals mal ein bisschen damit herumgetestet und festgestellt, dass der MersenneTwister durchaus funktioniert.
Es liegt also meiner Einschätzung nach kein Problem beim generieren dieser vor, sondern eher woher sie kommen.
Im Moment (sofern sich seit damals nichts verändert hat), werden alle Zahlen aus einem Pool geschöpft. Da der Generator auf eine Gleichverteilung aus ist, kommt es hier natürlich dazu, dass die gleichverteilung bei Crits und allem was man so sehen kann innerhalb von WoW, nicht unbedingt garantiert ist.
Jetzt stellt sich mir die Frage, ob man nicht jedem Player einfach seinen eigenen Genrator geben sollte, sodass zumindest solche Dinge wie Crits und dergleichen tatsächlich gleichverteilt sind.
Ist nur mal ein Gedanken Spiel, könnt euch das ja mal überlegen.
Das KÖNNTE jedenfalls diese seltsamen ChainCrits, die es hier nunmal gibt, zumindest eindämmen.

mfg


itslovelol

Meister

Beiträge: 376

Registrierungsdatum: 18.11.2012

  • Private Nachricht

2

Samstag, 26. Juli 2014, 20:09

Zitat

Im Moment (sofern sich seit damals nichts verändert hat), werden alle Zahlen aus einem Pool geschöpft.


Was meinst du damit?

Natürlich könnte man die CritChance eindämmen indem man beispielhaft bei 10% crit, sprich 1/10 crits bei jedem successful crit die Chance auf einen weiteren crit bei den nächsten 9 Spells um 1/10 reduced. Aber das ist halt RNG, ob ich 10x eine Sechs würfel oder 10x nicht?

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »itslovelol« (26. Juli 2014, 20:19)


Pyrox

Ehemaliges Teammitglied

Beiträge: 913

Registrierungsdatum: 03.09.2012

Wohnort: Berlin

Hauptcharakter: Dududa

Gilde: Daylight

  • Private Nachricht

3

Samstag, 26. Juli 2014, 20:35

Verstehe irgendwie nicht, wo der Unterschied nun wäre, ob nun ein Calculator für alle zieht oder jeder seinen eigenen hat. Diese Critverteilung, kann so oder so von der Normalverteilung abweichen, ob nun persönlich oder allgemein. War zwar noch nie der Stochastik-Pro, aber irgendwie leuchtet mir das nicht ein: Mathematische Erklärung bitte o.O
Dududa Sharaman Coraly Sisyphos Nishgratz Cosmah Sperrholz Pyrøx

antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

4

Sonntag, 27. Juli 2014, 03:18

Das Ganze ist weniger ein Mathematisches Problem wie ein logisches.
MersenneTwister berechnet entsprechende Zahlen voraus.
D.h. er hält intern eine Liste auf Zahlen (der angesprochene Pool) die dann, wenn sie gebraucht werden nochmal weiter verwertet werden und dann verworfen. Wie genau und was dabei geschieht ist erstmal Nebensache und weiß ich auch nicht so genau.
Jedenfalls hat diese Liste natürlich auch Einfluss auf die Gleichverteilung. Da aber pro Servertick mit Sicherheit 100 und mehr rnd Zahlen generiert werden, hat man als einzelner Player, der alle paar Sekunden einen neuen Spell castet, keine Chance auf eine reelle Gleichverteilung.

Das generell natürlich Abweichungen entstehen ist klar, aber so wie es momentan eben funktioniert finde ich es weniger berauschend.

Zusätzlich wird der Generator dann eben auch mit unterschiedlichen Seeds gestartet, was vll auch noch ein Vorteil sein könnte, aber nicht sein muss.

Sind halt so meine Gedanken zu dem Thema. Was denken sich denn die anderen? Völliger Stuss, oder tatsächlich einen Test wert?

p.s.: Mir ist natürlich klar, das gleichverteilt nicht automatisch heißt, das jede Zahl genau gleich oft vor kommt. Allerdings stehen die Zahlen bei der Berechnung durchaus in Abhängigkeit zueinander, da sie anhand ihrer Vorgänger berechnet werden.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »antifreak« (27. Juli 2014, 03:41)


itslovelol

Meister

Beiträge: 376

Registrierungsdatum: 18.11.2012

  • Private Nachricht

5

Sonntag, 27. Juli 2014, 05:47

Aber rand bleibt doch rand, ob ich mir nun random eine Zahl ausgeben lasse oder mit dieser eine weitere psydo random Zahl mir aus einen gegebenen Pool "errechnen" lasse?

Oder seh ich das falsch?

6

Sonntag, 27. Juli 2014, 08:47

Du wählst aus einer gleichverteilten Menge von Zufallsvariablen eine Anzahl X zufällig aus (zufällig da es ja unmöglich vorherzusagen ist wer zwischen 2 von dir benötigten Zufallszahlen so alles noch aus dem Pool schöpft)

Langfristig ergibt sich dadurch auf jeden fall wieder die selbe Verteilung wie im Pool.

Was viel eher die Frage ist: Bei wie vielen Zufallszahlen (Kardinalität deiner Stichproben) soll ein Test auf eine Gleichverteilung zu hinreichender W'keit "ein positives Ergebniss liefern".

Sprich du nimmst eine Stichprobe von 100 Zufallszahlen und testest diese auf eine Gleichverteilung: Hinreichend wäre dann wenn 95% aller Stichproben mit 100 Zahlen einer Gleichverteilung genügen.

Aber die Anzahl (hier 100) ist halt sehr entscheidend!


Was du ja bemängelst sind z.B. so Situationen Mage gegen X und der Mage crittet 5 mal hintereinander und gewinnt das Game, oder ?
Dann müsste man sich halt überlegen wieviele Zufallszahlen in einem sinnvollen Zeitintervall "gebraucht" werden und die dann extra gleichverteilt generieren lassen.
1.Server: Mangos: s1514 SD2: s2438
2.Server: CMangos: 1982

Betagan

Wandelnde Legende

Beiträge: 1 698

Registrierungsdatum: 22.08.2010

Wohnort: Kiel

Hauptcharakter: Betagan

Gilde: Bloodline

  • Private Nachricht

7

Sonntag, 27. Juli 2014, 12:02

@anti: Das Problem ist, dass ein Zufallsgenerator pro player noch nicht viel Besserung bringen wuerde. Du braeuchtest dann tatsaechlich einen pool pro Zufallsverteilung. Also einen pool fuer crit, einen fuer dodge, einen fuer..... Sonst hast du das gleiche Problem immernoch. Und dann reden wir ueber eine ganze menge Performance-Overhead.

@rest
Anti's punkt ist der, dass so ein Mersenne Twister immer 624 "Zufallfszahlen" im Block berechnet. Diese Zahlen sind untereinander gleichverteilt. Wenn man jetzt aber so einen Block mit allen Spielern shared, kann es natuerlich passieren, dass die Zahlen, die man selbst als "Zufall' bekommt, nicht gleichverteilt sind. Man bekommt vielleicht immer nur eine Zahl pro Block ab, und das kann im schlimmsten Fall sogar dann immer die gleiche Zahl sein (Unwahrscheinlich, aber in der Theorie..). Das rand() liefert also nur dann echten Zufall, wenn man nur ein einziges Experiment betrachtet. In dem Moment, wo man den selben Generator gleichzeitig fuer mehrere Experimente verwendet, hat man ggfs. einen degenerierten Fall. Es ist naemlich NICHT garantiert, dass Zahlen ueber mehrere Bloecke hinweg gleichverteilt sind, wenn man immer die 5te Zahl aus einem Block abbekommt.



itslovelol

Meister

Beiträge: 376

Registrierungsdatum: 18.11.2012

  • Private Nachricht

8

Sonntag, 27. Juli 2014, 12:08

Gute Erklärung, danke!

Wenn ich mir jetzt aber anstatt einer random Zahl, mir gleich 5 ziehe und den Mittelwert errechne, ist die Chance doch wensentlich geringer dass ich nur hohe / niedrige Zahlen aus dem Pool bekomme?

Sprich
for (int i = 0; i < 5; ++i)
{
value += rand();
}
chance = value / 5;

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »itslovelol« (27. Juli 2014, 12:22)


antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

9

Sonntag, 27. Juli 2014, 13:32

@itslovelol: So wäre aber die Chance wesentlich geringer, dass du keine 1 oder sowas bekommst. Denn für eine 1 bräuchtest du 5*1 (bzw 4*2 und 1*1 maximal) und das ist doch schon echt unwahrscheinlich. Würde also auch keine Gleichverteilung garantieren (auch wenn ich noch gar nicht checke, was du damit bezwecken willst).

@Beta: Danke für deine Worte, besser hätte ich es nicht sagen können :P
Natürlich hast du recht, wenn du sagst, das man praktisch für jeden Fall einen separaten Generator bräuchte, aber so viel performance Overhead wird dabei gar nicht verursacht. Es wird ein bisschen mehr Speicher benötigt, aber ob ich jetzt eine rnd Zahl aus einem oder mehreren Pools ziehe, wird keinen Overhead verursachen, oder was genau meinst du?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »antifreak« (27. Juli 2014, 13:53)


Betagan

Wandelnde Legende

Beiträge: 1 698

Registrierungsdatum: 22.08.2010

Wohnort: Kiel

Hauptcharakter: Betagan

Gilde: Bloodline

  • Private Nachricht

10

Sonntag, 27. Juli 2014, 16:56

ja, eigentlich nur speicher, stimmt.



Betagan

Wandelnde Legende

Beiträge: 1 698

Registrierungsdatum: 22.08.2010

Wohnort: Kiel

Hauptcharakter: Betagan

Gilde: Bloodline

  • Private Nachricht

11

Montag, 28. Juli 2014, 18:58

Mir ist noch etwas aufgefallen, was MaNGOS derzeit nicht tut aber dringend machen sollte.

Zitat von »http://de.wikipedia.org/wiki/Mersenne-Twister«


Je weniger zufällig die Startwerte sind (d. h. je ungleicher die Bits verteilt sind), umso länger ist die „Aufwärmphase“, die der Mersenne-Twister braucht, bis er gute Pseudozufallszahlen ausgibt. Die schlechtest mögliche Initialisierung besteht aus nur einem einzigen 1er-Bit und sonst lauter Nullen. Hiernach benötigt der Mersenne-Twister über 700.000 Aufrufe, bis er wieder eine gleichverteilte Bitsequenz liefert.[1] Im Zweifelsfall sollte man also etwa 800.000 Zufallszahlen generieren lassen, bevor man die Zahlen verwendet.


MaNGOS verwendet zwar einen 32bit hash für die Initialisierung, aber das ist immernoch viel zu wenig, weil der gesamte State ~20.000 bit sind.

Das sorgt dafür, dass die ersten ~800.000 Zahlen ggfs. nicht so toll sind. Wie viel macht das jetzt aus? Wenn man davon ausgeht, dass 500 Spieler alle 1.5s irgendwas tuen, was einen Zufallswurf ausloest, dann braucht es 800.000 / (500/1.5) / 60 = 40min bis wir einen guten State haben. Das wird in der Realität eher kürzer sein, weil es mehrere Rolls pro Spieleraktion geben kann und auch Aktionen der NPCs beachtet werden müssen etc, aber wenn man dann auch noch an AFK-Spieler denkt kommt es vielleicht doch wieder ganz gut hin. Ich will damit nur sagen, dass man ggfs. die ersten 40min nach einem Serverrestart keine ordentlichen Zufallszahlen bekommt.

Was kann man tuen? Einfach bei Server-Start einmal fix 800.000 Zufallszahlen generieren lassen. Ob das irgendwelche Auswirkungen hat, wer weiß. Aber es wäre auf jedenfall erstmal eine richtige Verwendung des MersenneTwisters :)



itslovelol

Meister

Beiträge: 376

Registrierungsdatum: 18.11.2012

  • Private Nachricht

12

Dienstag, 29. Juli 2014, 00:06

Was mich hier ein bisschen wundert, dass ich im Zusammenhang mit MT ganz oft den Begrifft SFMT beim googlen bekomme. So grob versteh ich was die Vorteile von SFMT sind, jedoch nicht wirklich genau wo nun der Unterschied liegt. Falls mir einer von euch das kurz Erklären könnte wärs echt lieb. Unten noch der Pastebin für cmangos switch von Mersenne-Twister zu SFMT.

http://pastebin.com/DFb3vxLh

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »itslovelol« (29. Juli 2014, 00:16)


antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

13

Dienstag, 29. Juli 2014, 00:20

Generell braucht man den ganzen outsource Quatsch gar nicht mehr. C++11 hat mitlerweile viel viel bessere rnd Generatoren im Standard. rand() war ja früher nicht wirklich zu gebrauchen (für ernsthafte Projekte).

EDIT: Was soll denn SFMT sein?


antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

15

Dienstag, 29. Juli 2014, 00:23

Keine Ahnung wie das funktioniert. Kannte ich bis dato gar nicht.


Beiträge: 200

Registrierungsdatum: 29.08.2010

  • Private Nachricht

16

Dienstag, 29. Juli 2014, 11:15

heyho


wenn ich das richtig verstehe, ist der eigentliche vorschlag der, das man die crits besser auf die spieler auffteilt, statt das einer viele crits macht und der ander weniger crits, bei etwa gleichen gear oder?


mfg

antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

17

Dienstag, 29. Juli 2014, 14:28

Jain.
Es geht hier weniger um Crits per se, sondern um alle Fälle, die etwas mit Zufall zu tun haben (wärend des Fights, aber vll auch bei proccs für den Alchi o.Ä.).
Am Besten liest du dir Betas post nochmal durch, da steht eigentlich alles ziemlich gut erklärt drin.


Duzt

Geselle

Beiträge: 75

Registrierungsdatum: 05.12.2013

  • Private Nachricht

18

Dienstag, 29. Juli 2014, 15:18

Würde das erklären warum ich 4 wochen lang nicht einen Alchiproc hatte (Strichliste geführt)? Oder regelmäßig in nem Bossfight (fury) einfach 3-4x in Folge mit beiden! Waffen verfehle und Overall dann mit 5,5% Miss für Autoatack aus dem Fight gehe. und oder sehr lange noncritphasen habe. Mir ist sogar mal Toben mit 3 Stacks ausgelaufen. Und das auf T6 nieveau.
Oder neulich in einem Bossfight ein WL 65% Crit hatte der andere aber 30% - Gearstand ähnlich, der mit 30% aber besser...

In Summe auf einen ganzen Raidabend gesehen stimmen aber die Zahlen aus dem Recount wieder fast mit der Theorie überein.

Oder gehts da um ganz was anderes?

antifreak

Drachentöter

  • »antifreak« ist der Autor dieses Themas

Beiträge: 1 366

Registrierungsdatum: 01.09.2010

Gilde: Innocence of Cræck

  • Private Nachricht

19

Dienstag, 29. Juli 2014, 15:23

Genau das ist das Problem, weswegen ich den Thread aufgemacht habe ;)


itslovelol

Meister

Beiträge: 376

Registrierungsdatum: 18.11.2012

  • Private Nachricht

20

Dienstag, 29. Juli 2014, 15:39

Aber was ich jetzt noch nicht ganz verstehe, warum ist die Verteilung denn nicht gleich wenn ich alle Zahlen aus einem Pool schöpfe als für jeden Roll einen eigenen Pool?

Zitat


Man bekommt vielleicht immer nur eine Zahl pro Block ab, und das kann im schlimmsten Fall sogar dann immer die gleiche Zahl sein (Unwahrscheinlich, aber in der Theorie..)


Das kann mir doch bei variante A und B passieren?