Maintenance for the week of March 16:
• [IN PROGRESS] ESO Store and Account System for maintenance – March 18, 6:00AM EDT (10:00 UTC) - 4:00PM EDT (20:00 UTC)

Understanding Pseudo-RNG. The effect of LCGs and uniform distribution algorithms

Rune_Relic
Rune_Relic
✭✭✭✭✭
Introduction.

ESO is not the only game where players loathe the way that RNG drop rates work.
This is a link to what WOW did to fix their problems, but the problems could have been fixed in other ways.
[outlined at end]
http://math.arizona.edu/~ercolani/pyzdek.pdf

The following table lists the parameters of LCGs in common use, including built-in rand() functions in runtime libraries of various compilers.
https://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use

RNG Analysis..
Uniform distribution
Normal distribution
Bernoulli distribution
Binomial distribution
Poisson distribution
Patterned Distribution
Discrete distribution

For the purposes of this thread and the equal chance drop rate of all items, we are limiting this discussion to uniform distribution with seed key, rather than normal distribution with standard deviation.
http://excel.officetuts.net/en/examples/random-number-generator


Understanding P-RNG, or dumbing down linear congruential generators for the masses to understand.
http://wiki.osdev.org/Random_Number_Generator

Ever wondered why you get duplicate dropped sets ?
Ever wondered why the specific item of gear never drops ?
All is about to be revealed.

Lets start by having a pack of 52 playing cards with a joker to explain LCG in a really simple form.
The 53rd joker is essential as explained later but bare with me for now.

We start with all 53 cards sorted into order, your preferred order is arbitrary, what matters is the deck has been sorted.
Lay the cards down in order from top to bottom to create a column of 53 cards.
Now create 53 labels numbered from 1-53.
Place these 53 labels in order to the left of each playing card.
What we have created here is a 1 dimensional array containing 53 playing cards.
The numbers to the left of the playing cards are the array index for each item (a unique playing card in this case)

Now get a 2nd set of matching playing cards.
Starting with 1x7 as the index, identify cards whose index are multiples of 7, and create a new column.
If the multiples exceed 53, then rollover from 53 to 1 and then 2 etc.
Thus we get new deck card order...
7, 14, 21, 28, 35, 42, 49,
3, 10, 17, 24, 31, 38, 45, 52,
6, 13, 20, 27, 34, 41, 48,
2, 9, 16, 23, 30, 37, 44, 51,
5, 12, 19, 26, 33, 40, 47,
1, 8, 15, 22, 29, 36, 43, 50,
4, 11, 18, 25, 32, 39, 46, 53
...thus we have generated an alternative linear pattern.
All 53 cards are still present, we have just rearranged them into a different sequence.
Note that there are 7 linear ramps using a multiplier of 7 just as there would be 1 linear ramp using a multiplier of 1.
Lastly, we will add 0 to the index and not shift the card sequence at all (keep things simple).


We can create an algorithm to represent this process with a simple mathematical formula.
Pool size = 53 (Modulo)
Pattern ID = 7 out of a possible 52 or pool size -1 (Multiplier)
Pattern Offset = 0 (Increment)
Pattern index = 1-53 (Seed)
(Pattern-Index * Pattern-ID + Pattern-Offset) mod 53 = Random-Index

We can also establish some rules for this algorithm.
1. The pool size must be odd otherwise even number pattern IDs do not create a valid full sequence of numbers.
2. Pool size and seed range encompass all available numbers and automatically generate 'uniform distribution'
3. The use of LCG enables the generation of a virtual array that requires no extra storage
4. The seed acts as an index into a one dimensional array given a fixed modulo, multiplier and increment.
5. There are Pool-size -1 Pattern-IDs that can be generated provided the pool size is kept odd.
6. Low Pattern-IDs have an ascending linear ramp pattern
7. High Pattern-IDs have a descending linear ramp pattern
8. Middle Pattern-IDs have a sawtooth pattern whose number of teeth equate to half the pool size.

I have attached a pdf document here, so that you can see how LCG as a P-RNG source is used to randomise the order of an array.
This document also shows how LCG Patterns can be interleaved to generate Random Noise.
https://cp.sync.com/dl/3c6709ee0#u5yix99e-nhe9fwgn-qkxa6fka-ux3stvm6


So how does this relate to ESO ?

1. If the LCG algorithm was called without incrementing the seed value, the RNG would return exactly the same number (ie same set gear piece).
So the LCG increments the seed value every time its called by default (ie changes the array index which may or may not exit the current items range).
2. That means every time a player accesses the LCG algorithm without the seed continuing in an "unbroken" sequence, does not get 'uniform distribution'
without recording/resetting the current seed key value for every player (array index), there is no way to ensure the player gets access to all available items.
3. The available item pool size is much smaller than the modulo used for the LCG algorithm, so each item represents a range of available random numbers.
This means with 100 items, modulo 1000 and a randomised complete sequence of 1000 numbers, the player needs 10 duplicate items and 1000 tries to complete the sequence.
The number of duplicates for any item at any time, is dependant on the pattern-id and discrepancy between the game item pool and the algorithm modulo pool size.
Not withstanding the issues that other players may have already removed the unique options leaving only duplicates for the player anyway.
NB Many algorithm use 2^32 as the modulo....so get pumping out those VMA runs ;)


Conclusion.

I have to assume that the requirement for true "uniform distribution" necessitates the use of the LCG algorithm to guarantee that all available numbers appear once per cycle.
[Indeed, judging by the equal distribution server side but not client side...this appears to be conclusive]
I have to assume that a generic Rand() function thats based on LCG is behind the problems with ESO RNG.
These problems can be fixed by the storage and injection of per player seed keys and much greater control over the variables used to define the LCG algorithm.
eg. using a 256 modulo for a 256 size pool (or 2x128 pattern interleave).
The problem here is using even numbers for the modulo, instantly halves the available Pattern-IDs (ie the even numbered pattern-IDs break).
But using base 2 for the pool size or modulo is what gives LCG its speed with modulo arithmetic.
I would also suggest the use of interleaved Pattern-ID that use the same modulo, as this greatly disrupts the inherent linear nature of the patterns.
There is also no reason why Pattern-IDs (interleaved or not) cant be change regularly.

In a nut shell...Please create a new LCG algorithm and track seed keys.
Edited by Rune_Relic on November 21, 2016 3:12PM
Anything that can be exploited will be exploited
  • JD2013
    JD2013
    ✭✭✭✭✭
    ✭✭✭✭✭
    That's actually very insightful. Thank you. Always wondered the mechanics behind RNG.
    Sweetrolls for all!

    Christophe Mottierre - Breton Templar with his own whole darn estate! Templar Houses are so 2015. EU DC

    PC Beta Tester January 2014

    Elder of The Black
    Order of Sithis
    The Runners

    @TamrielTraverse - For Tamriel related Twitter shenanigans!
    https://tamrieltraveller.wordpress.com/

    Crafting bag OP! ZOS nerf pls!
  • Ch4mpTW
    Ch4mpTW
    ✭✭✭✭✭
    ✭✭✭✭✭
    You actually did it. You made the thread you were talking about. Most excellent, and incredibly insightful. Definitely something I'm bookmarking both here on the forums and on my browser. A+ thread right here.
  • idk
    idk
    ✭✭✭✭✭
    ✭✭✭✭✭
    I think a CLCG is what is required.
  • AlexTech0x
    AlexTech0x
    ✭✭✭
    Sorry but after a vDSA run and getting 3/4 Greatswords i'd say the RNG of THIS game is really *** up.
  • bellanca6561n
    bellanca6561n
    ✭✭✭✭✭
    Outstanding post @Rune_Relic!!
  • Ch4mpTW
    Ch4mpTW
    ✭✭✭✭✭
    ✭✭✭✭✭
    AlexTech0x wrote: »
    Sorry but after a vDSA run and getting 3/4 Greatswords i'd say the RNG of THIS game is really *** up.

    I saw that. Lol. The loot distribution is horrible. Did you ever see my pic of double S&B? I cried on the inside when it occurred.
    pShn48e.jpg
  • vyndral13preub18_ESO
    vyndral13preub18_ESO
    ✭✭✭✭✭
    ✭✭✭✭
    I tried to read that. I think my nose is bleeding.
  • Drummerx04
    Drummerx04
    ✭✭✭✭✭
    AlexTech0x wrote: »
    Sorry but after a vDSA run and getting 3/4 Greatswords i'd say the RNG of THIS game is really *** up.

    When I took my group through vDSA, we got 4/4 greatswords. Our crap RNG drops beat your crap RNG drops :expressionless:
    PC/NA - Nightfighters, Raid Leader and Officer
    Lilith Arujo - DC sorc tank/dps/healer - Dro-m'Athra Destroyer, Gryphon Heart, Grand Warlord
    Lilith Tortorici - DC templar trials healer

    Notable Completions:
    vAS (72k), vMoL HM (160k), vAA HM (135k), vHRC HM, vSO HM (141k), vHoF HM (168k), vCR+3(129k), vDSA 45k, vMA 591k

    Original Addons:
    Lilith's Group Manager
    Lilith's Lazy Hacks - Auto Recharge/Repair
    Bot Scanner 2000
    Lilith's Command History
    Maintained Addons:
    Kill Counter
  • Yolokin_Swagonborn
    Yolokin_Swagonborn
    ✭✭✭✭✭
    ✭✭✭✭✭
    I have to assume that the requirement for true "uniform distribution" necessitates the use of the LCG algorithm to guarantee that all available numbers appear once per cycle.

    Once per cycle globally among all players? So if someone gets lucky and gets three sharpened items in a row, the game decides there isn't enough training trait in the world and slaps that on the next guy as a RNG correction?

    If that is how it works then it shows how brutal the RNG can feel. For everyone that "gets lucky" someone is forced to have an intentionally bad trait to ensure the distribution looks random at the end of the cycle.
  • Nestor
    Nestor
    ✭✭✭✭✭
    ✭✭✭✭✭
    For those who don't like to read

    https://www.youtube.com/watch?v=_tN2ev3hO14
    Enjoy the game, life is what you really want to be worried about.

    PakKat "Everything was going well, until I died"
    Gary Gravestink "I am glad you died, I needed the help"

  • disintegr8
    disintegr8
    ✭✭✭✭✭
    ✭✭
    Who cares - it is just a game. I put more effort into picking my nose than picking on RNG.
    Why? Because it is only a game and I don't need to have 'BiS' stuff to enjoy it - or maybe I am just lucky.

    Can ZOS please create an RNG rage thread so those of us who do not care about RNG can stay away from it.
    Australian on PS4 NA server.
    Everyone's entitled to an opinion.
  • Rune_Relic
    Rune_Relic
    ✭✭✭✭✭
    JD2013 wrote: »
    That's actually very insightful. Thank you. Always wondered the mechanics behind RNG.
    Ch4mpTW wrote: »
    You actually did it. You made the thread you were talking about. Most excellent, and incredibly insightful. Definitely something I'm bookmarking both here on the forums and on my browser. A+ thread right here.
    Outstanding post @Rune_Relic!!

    Thank you :blush:
    I tried to read that. I think my nose is bleeding.

    lmao.
    Just look at the pretty picture instead.
    The pdf has diagrams and stuff ;)
    Edited by Rune_Relic on November 21, 2016 10:12PM
    Anything that can be exploited will be exploited
  • mithrilaxe1
    mithrilaxe1
    Soul Shriven
    This analisys is as great as useless . You are counting the bristles of the brush ignoring the colour you are painting , which is somewhere blue , somewhere red and somewhere white (my boss used this words to tell us we were doing a useless job) . I am sure that all the game producers know very well this algorithms , and cripple that in order to keep the players playing , or farming/grinding . If we (players) could get from game what we need in a short time then a great number of us (very most part) will use the desired item for a brief time , then switch simply to another game , while waiting for new contents , to get back to this game . Players want constantly new contents , and crippling the dropping algorithms makes the new contents fresh for longer time , giving time to developers to prepare new contents . Of course , after some time , also the grinders get bored , and change game anyway , so developers want definitely force grinding to the maximum extent , but not beyond . Finding the limit of grinding is their ultimate goal , to keep us subscribing . As simple as that .
  • SublimeSparo
    SublimeSparo
    ✭✭✭✭✭
    Ch4mpTW wrote: »
    AlexTech0x wrote: »
    Sorry but after a vDSA run and getting 3/4 Greatswords i'd say the RNG of THIS game is really *** up.

    I saw that. Lol. The loot distribution is horrible. Did you ever see my pic of double S&B? I cried on the inside when it occurred.
    pShn48e.jpg

    I raise you double defending 1h axes, and i also got double double charged back to back- 1,30hours to get 4 charged weapons. Wtf
    PS4 EU CP900. PS4 NA CP600,
    vAA HM ☆ vHRC HM ☆ vSO HM ☆ vMOL
    4th Console vMOL clear,
    vMA cleared on all classes stam & magic

    My Tribe
    EU
    High Sparo - Altmer - mSo DD.
    Wood Sparo - Bosmer - sNB DD
    Nord Sparo - Nord -sDK DD/Tank.
    Bubble Girl - Imperial -sTe DD
    Succubus Sue - Breton - mNB Tank.
    Andrana Stormlock - Altmer - mTe Healer/ DD
    Elvali Marvani - Dunmer - mDK DD.
    Venemus Draconem - Redguard - sDK DD
    Jayri Leki - Redguard - sSo DD.
    Miss Jabsalot - Altmer - mTe PvP DD/ Tank
    Mireli Hlaano - Dunmer - mNB DD.
    Ms Shanks - Redguard - sNB DD/ le bank

    NA
    Dilemma Dame - Altmer - mDK DD
    Stamsorc Kitty - Redguard - sSor DD
    Aia Draconis - Imperial - sDK Tank
    Decides-Who-Lives - Argonian - mTe Healer
    You wont stop me - Altmer - mSo DD
    Stab in the dark - Khajiit - sNB DD
    Jabjabjab Beambeambeam - Dunmer - mTe DD
    Spatium Auxiliarus - Imperial - hTe Tank&bank
    Spectre - Altmer - mNB DD
    Can't-Main-Tank -Argonian - sDK offTank
  • Ackwalan
    Ackwalan
    ✭✭✭✭✭
    ✭✭✭✭✭
    This analisys is as great as useless . You are counting the bristles of the brush ignoring the colour you are painting , which is somewhere blue , somewhere red and somewhere white (my boss used this words to tell us we were doing a useless job) . I am sure that all the game producers know very well this algorithms , and cripple that in order to keep the players playing , or farming/grinding . If we (players) could get from game what we need in a short time then a great number of us (very most part) will use the desired item for a brief time , then switch simply to another game , while waiting for new contents , to get back to this game . Players want constantly new contents , and crippling the dropping algorithms makes the new contents fresh for longer time , giving time to developers to prepare new contents . Of course , after some time , also the grinders get bored , and change game anyway , so developers want definitely force grinding to the maximum extent , but not beyond . Finding the limit of grinding is their ultimate goal , to keep us subscribing . As simple as that .

    There is a tipping point. Making the grind too long will drive away just as many (paying) players as getting everything you want too quickly.
  • SublimeSparo
    SublimeSparo
    ✭✭✭✭✭
    Ackwalan wrote: »
    This analisys is as great as useless . You are counting the bristles of the brush ignoring the colour you are painting , which is somewhere blue , somewhere red and somewhere white (my boss used this words to tell us we were doing a useless job) . I am sure that all the game producers know very well this algorithms , and cripple that in order to keep the players playing , or farming/grinding . If we (players) could get from game what we need in a short time then a great number of us (very most part) will use the desired item for a brief time , then switch simply to another game , while waiting for new contents , to get back to this game . Players want constantly new contents , and crippling the dropping algorithms makes the new contents fresh for longer time , giving time to developers to prepare new contents . Of course , after some time , also the grinders get bored , and change game anyway , so developers want definitely force grinding to the maximum extent , but not beyond . Finding the limit of grinding is their ultimate goal , to keep us subscribing . As simple as that .

    There is a tipping point. Making the grind too long will drive away just as many (paying) players as getting everything you want too quickly.

    1yr grinding wgt to get perfect trait spc,
    over 1yr to get scathing mage- which i never did complete= cba to run it as so bored of the place
    1yr grinding vma for sharp or precise inferno& lightning, daggers, axes, bow. I got 2 precise axes, 1 precise lightning and the bow in both(sharpened one last week). So still missing most of what i want.
    Don't think i can be arsed with it anymore. Soul destroying boring time consuming solo grind
    PS4 EU CP900. PS4 NA CP600,
    vAA HM ☆ vHRC HM ☆ vSO HM ☆ vMOL
    4th Console vMOL clear,
    vMA cleared on all classes stam & magic

    My Tribe
    EU
    High Sparo - Altmer - mSo DD.
    Wood Sparo - Bosmer - sNB DD
    Nord Sparo - Nord -sDK DD/Tank.
    Bubble Girl - Imperial -sTe DD
    Succubus Sue - Breton - mNB Tank.
    Andrana Stormlock - Altmer - mTe Healer/ DD
    Elvali Marvani - Dunmer - mDK DD.
    Venemus Draconem - Redguard - sDK DD
    Jayri Leki - Redguard - sSo DD.
    Miss Jabsalot - Altmer - mTe PvP DD/ Tank
    Mireli Hlaano - Dunmer - mNB DD.
    Ms Shanks - Redguard - sNB DD/ le bank

    NA
    Dilemma Dame - Altmer - mDK DD
    Stamsorc Kitty - Redguard - sSor DD
    Aia Draconis - Imperial - sDK Tank
    Decides-Who-Lives - Argonian - mTe Healer
    You wont stop me - Altmer - mSo DD
    Stab in the dark - Khajiit - sNB DD
    Jabjabjab Beambeambeam - Dunmer - mTe DD
    Spatium Auxiliarus - Imperial - hTe Tank&bank
    Spectre - Altmer - mNB DD
    Can't-Main-Tank -Argonian - sDK offTank
  • Oreyn_Bearclaw
    Oreyn_Bearclaw
    ✭✭✭✭✭
    ✭✭✭✭✭
    Step one: Identify the Problem. A+ right there.
    Step two: pray to Sheogorath that the devs at ZOS finally do something about it. It is not suggested that anyone holds their breath because they will die...

    I got 8 resto staffs in a row from the VMA event. My last two runs I got Resto and Dagger. People call it RNG, but I see nothing random about it. I wish I was half as smart as I think I am so this made a little more sense. :smile:

    You earn an "insightful" from me.

    Edited by Oreyn_Bearclaw on November 21, 2016 11:42PM
  • Rune_Relic
    Rune_Relic
    ✭✭✭✭✭
    I have to assume that the requirement for true "uniform distribution" necessitates the use of the LCG algorithm to guarantee that all available numbers appear once per cycle.

    Once per cycle globally among all players? So if someone gets lucky and gets three sharpened items in a row, the game decides there isn't enough training trait in the world and slaps that on the next guy as a RNG correction?

    If that is how it works then it shows how brutal the RNG can feel. For everyone that "gets lucky" someone is forced to have an intentionally bad trait to ensure the distribution looks random at the end of the cycle.

    Pretty much.

    Given 1001 modulo and unique numbers
    That would mean RAND() would chuck out 0.000 ~ 1.000 per cycle when scaled down to 1

    If there were 10 items and the code said something like....
    random_value = RAND()
    If random_value => 0 or random value <=0.1 then give_item(1)
    If random_value > 0.1 or random value <=0.2 then give_item(2)
    ...
    If random_value > 0.9 or random value <=1.0 then give_item(10)
    [NB This assumes you want equal distribution]

    That means anytime RAND() generate a number from 0-100 player will receive item 1.
    As 1-100 could be right at the beginning of pattern-ID 1 (unsorted ascending ramp)
    That means the 1st 100 calls (index increments) to RAND() would issue 100 duplicates of item 1

    So you can see how pool size and pattern-ID can be a problem.

    Now consider that there were 10 players that logged in one after another and each increments the index as no indexes are stored per player.
    Player 1 get index 0-100 or RAND() 0.000 ~ 0.100 ...logs off
    Player 2 get index 101-200 or RAND() 0.101 ~ 0.200 ....logs off
    ...
    Player 10 get index 901-1000 or RAND() 0.901 ~ 1.000 ..logs off

    That means players 1 would have received 100 copies of item 1
    That means players 2 would have received 100 copies of item 2
    .......
    That means players 10 would have received 100 copies of item 10

    Not only did every player receive 100 duplicates, they never saw one inkling of any other set.
    This is an extreme example just to make a point.
    Edited by Rune_Relic on November 22, 2016 4:09PM
    Anything that can be exploited will be exploited
  • LeeroyGankins
    LeeroyGankins
    ✭✭
    Awesome thread! Really insightful for helping me understand the RNG process . In short the worst case scenario is not just biased loot table; it is being forced to acquire multiple junk sets before a good item is even in the table. in that light , I'm glad I quit VMA
    Edited by LeeroyGankins on November 22, 2016 5:31PM
  • idk
    idk
    ✭✭✭✭✭
    ✭✭✭✭✭
    AlexTech0x wrote: »
    Sorry but after a vDSA run and getting 3/4 Greatswords i'd say the RNG of THIS game is really *** up.

    One run, sampling 4 drops, is not in any way indicative of the loot drops overall.

    First run, precise fire dstaff. Second run precise rstaff.
Sign In or Register to comment.