The not so random number generator

Users who are viewing this thread

saxondragon

Sergeant Knight at Arms
(store_random_in_range...aargh!

The random number generator in this scripting language is not random.. and how it works is driving me to drink! :wink:

I have had to write, rewrite and rewrite routines trying to get around this quirky behavior. I have had marginal success.

Quick example:
if I ask for 5 random numbers between a value of 1 to 10 what I should get is something like this:

1,5,3,8,4    or    9,1,8,6,4

What I get get in Mount&Blade is along these lines:
1,1,1,8,8            or                4,4,3,3,3            or            8,8,8,9,9

Time and time again I see this behavior.. and I know what causes it...but I am at a bit of a loss as to how to get around it.

It appears that every time we initiate a call to create a random number, the random number generator is seeded with some sort of value (more than likely from the clock)...our processors are so fast that the routine is seeded with the same value two or three times before the clock can increment.

For those of you (and I hope it is very few of you), that do not know this little factoid: You can seed the randomization process with a number, then ask it for a a series of random numbers and that unique string will be duplicated every time without fail for that particular seed. 

So.. if I seed a randomization process with a number ..say.. 2343242 and ask it for a number between 1 and 1 billion, it will give me the same answer every time when I seed it with that specific number.  Only when I ask it a second time or third time without re-seeding the randomization process, or I seed the randomized process with a different value, will give me different values,

Now.. imagine that when we ask in Mount&Blade for a five number sequence between 1 and 100.. and it looks at the clock (a standard way to seed the randomization process), and gives us a set of random numbers.  The processors are so fast that they seed the process each time with the same number several times before the clock changes..thus we get a string of like numbers... not random.

This is why we get these string of same numbers in a row.. you see this effect in battle when we spawn two or three troop types that look identical even though they can randomize out in very different equipment.

I am open to thoughts and suggestions..:smile:

 
Wow - reseeding the random function on every call... is blatantly stupid programming.  Daft at the least.

Perhaps petitioning TaleWorlds to fix this?

... I can't think of a single solution that isn't impossible within the module system due to its very limitations.  No string->number function, no string[char-index] function, no direct access to the seeding function, ...
 
Easiest way I can think of to resolve this is in 3 steps:

1 - Reference the time clock when the game starts (DDD:HH:MM:SS)
2 - Generate a random seed based on that value, OR use the day:time as the seed. Either would work.
3 - Use that seed for all random number generation during that session.

Granted that this would still have to be done within the game engine, but it should give at least 1 whole year before you see a repeating sequence from the seed.

EDIT:

After looking at some docs for Python, the pseudo-random number generator (http://docs.python.org/library/random.html) uses the above method as the default seeding method. So, if we could figure out how to imbed actual Python commands into our scripts, I think the random number generation could be fixed
 
It appears that every time we initiate a call to create a random number, the random number generator is seeded with some sort of value (more than likely from the clock)...our processors are so fast that the routine is seeded with the same value two or three times before the clock can increment.
Hardly. For small ranges store_random_in_range gives to many doublets, it is oddly. But for large ranges it works different. 
The code
Code:
  (store_random_in_range,reg1,0,5),
  (store_random_in_range,reg2,0,5),
  (store_random_in_range,reg3,0,5),
  (store_random_in_range,reg4,0,5),
  (store_random_in_range,reg5,0,5),
  (store_random_in_range,reg6,0,5),
  (store_random_in_range,reg7,0,5),
  (store_random_in_range,reg8,0,5),
  (store_random_in_range,reg9,0,5),
  (store_random_in_range,reg10,0,5),
  (store_random_in_range,reg11,0,5),
  (store_random_in_range,reg12,0,5),
  
  (display_message,"@ {reg1} {reg2} {reg3} {reg4} {reg5} {reg6} {reg7} {reg8} {reg9} {reg10} {reg11} {reg12}"),
produced a weird sequence
4 0 0 2 2 1 2 1 3 3 3 1 
But then I've called the code
Code:
  (store_random_in_range,reg1,0,55),
  (store_random_in_range,reg2,0,55),
  (store_random_in_range,reg3,0,55),
  (store_random_in_range,reg4,0,55),
  (store_random_in_range,reg5,0,55),
  (store_random_in_range,reg6,0,55),
  (store_random_in_range,reg7,0,55),
  (store_random_in_range,reg8,0,55),
  (store_random_in_range,reg9,0,55),
  (store_random_in_range,reg10,0,55),
  (store_random_in_range,reg11,0,55),
  (store_random_in_range,reg12,0,55),
  
  (display_message,"@ {reg1} {reg2} {reg3} {reg4} {reg5} {reg6} {reg7} {reg8} {reg9} {reg10} {reg11} {reg12}"),
it produced a sequence
33 20 17 10 46 34 30 3 19 26 13 29
I called several times and did not find anything strange.
The remainder on division of values in the last sequence by 5 are
3 0 2 0 1 4 0 3 4 1 3 4
That's still ok.
So probably the way to reduce the number of doublets is to call random from a large range and then call val_mod to put values in the certain range.
 
Thanks, Rognar.  That's an excellent solution, if annoying to have to toss that into every bit of code.  But completely usable. :smile:
 
Excellent.. Thank you.. I had not thought to do that.. That will help with some random processes I have been working on.. :smile:


Yet.. the first "lower-range" method seems to be how troops are randomized in some fashion.  Too many times I have empirically seen troops come out with identical weapons, armor, helms when they should, statistically speaking, have variances between them.

Ie.. for a troop type we have three different armors, five different weapons, two helms, three types of shields, two boots and we have 10 troops.. and when they are generated on the battle field: four have identical equipment..

I believe that while you have provided a work around for some of our randomized processes, there is still an underlying issue that is beyond our reach to correct.

Kindest regards,

Saxondragon

 
I know it is not good solution, but if avoiding clones is very necessary troop's equipment can be significantly increased by duplicating items. I have not tested but I suppose it'll lead to the same  result as increasing range  in store_random_in_range. 
 
Rongar said:
I know it is not good solution, but if avoiding clones is very necessary troop's equipment can be significantly increased by duplicating items. I have not tested but I suppose it'll lead to the same  result as increasing range  in store_random_in_range.

No.. avoiding clones is not necessary in my case, and this was merely an observation.  Your approach solved my immediate problem in initializing random location improvements and setting some to be damaged.  I was receiving results that looked very strange...

Thank you.

Best,

Saxondragon
 
Rongar said:
produced a weird sequence
4 0 0 2 2 1 2 1 3 3 3 1 
I do see, that this thread is 7,5 years old, but can't help but say that this sequence is not weird.
Random is not 130420131024, random "loves" patterns and unusual combinations, that's the entire idea of random (nothing is impossible, miracles happen, it's only a matter of "how often").
You can easily check this by performing random actions (like picking X identical objects, marking them with numbers, putting them in a bag, shaking the bag, then blindly picking 1 object, writing down its number, putting it back and repeating).
For example, right now I "produced" the following sequence while doing this with 4 identical pieces of paper:
2 1 1 3 3 3 3 4 1 3 3

Anyway, I got here checking if "The Forge" has any mentions of manual pseudo-random number generators.
Unlike Saxondragon, I need something that gives different results over time, but identical results at a certain point in the game, so that save-loads do not help.

Couldn't come up with anything better than player's renown + a lord's identifying number (just 1, 2, 3, 4 etc. counter within a certain try_for_range cycle where I need to use it), then picking a remainder after dividing the sum by 4, and as far as I understand, any possible remainder should give me roughly 25% probability.
Been wondering if there was an OSP or something with a more ... universal solution.
 
@Leonion: Try this:
Code:
# script_rand
# Input: arg1 = min arg2 = max
# Output: reg0 = random_number
# Will only work up to about a billion
("rand",[
(store_script_param_1, ":min"),
(store_script_param_2, ":max"),
	
(val_mul,"$rand_seed",1664525), # see: Numerical Recipes in C
(val_add,"$rand_seed",1013904223), # Any two odd, relatively prime numbers larger than 65536 will do

(val_sub,":max",":min"),
(try_begin),
  (gt,":max",1),
  # Handle negative numbers; store_mod is not safe there!
  (store_mod,":r","$rand_seed",1024*1024*1024),
  (try_begin),
    (lt, ":r", 0),
    (val_add,":r",1024*1024*1024),
  (try_end),
  (store_div,":range",1024*1024*1024,":max"),
  (val_div,":r",":range"),
  (try_begin),
    # Make sure we didn't exceed our range.
    # Should happen very rarely, so we can afford to be lazy and use recursion.
    (eq,":r",":max"),
    (call_script,"script_rand",0,":max"),
    (val_add,reg0,":min"),
  (else_try),
    (store_add,reg0,":min",":r"),
  (try_end),
(else_try),
  (assign,reg0,":min"),
(try_end),
]),
Might contain syntax errors, I haven't tested it. Also, you'll have to initialize "$rand_seed" somewhere. Preferably in the "game_start" script.

@ Original debate:
The last example may not be good, but this is a real problem with M&B (see the sequences in the OP - they have way more repetitions than expected). It also fits with my experiences. If you use the RNG repeatedly to do the same thing, you will get long, repeating patterns.

From that description (and what I've seen), I guess the problem is that Taleworld has simply used the RNG from some standard library without thinking. The most common mistake there (you even see this in many computer science textbooks) is to use something like r=rand()%x; to generate a number between 0 and x.
This is a Bad Idea(tm) because the type of RNG used in most standard libraries (LCG) tends to repeat very quickly in the last few bits, so you should at the very least use div instead of mod when reducing the range of numbers, like this:
while((r=rand() / (RAND_MAX / x))==x);
You might also go for a better RNG (like a Mersenne Twister), but unless you're doing cryptography or simulations, that's probably overkill. LCGs still have the advantage of being incredibly quick (they are just a multiplication and an addition).

Don't do the thing below, it causes other problems (see EDIT):
Until Taleworld fixes this, you should probably avoid relying on the last few bits of the RNG if you have issues with repeating patterns. For example, use:
Code:
(store_random_in_range,":r",0,5000), (val_div,":r",1000),
instead of
Code:
(store_random_in_range,":r",0,5),

EDIT: Tested the code, and it was indeed missing a quote somewhere. And store_mod has an, er, undocumented feature in that its result has the sign of the dividend, not the divisor (like the operation is defined mathematically). But I should have known, C and C++ usually also do it this way. Fixed both.
Also, using higher values for store_random_in_range and dividing afterwards as a workaround may be a bad idea. For large values (I tested 100000), the results seem to be noticeably skewed to the lower end. I have no idea why.
 
:shock:
Wow!
Autolykos, thank you!
But is it safe to work with such large numbers?
I mean, a couple of uses, and the number that is stored in the global variable will become enormous, and through the course of the game it will become something like googol to the power of googol.

 
Leonion said:
But is it safe to work with such large numbers?
I mean, a couple of uses, and the number that is stored in the global variable will become enormous, and through the course of the game it will become something like googol to the power of googol.
No need to be afraid there. The numbers are (very probably) stored in 32 bit integers, and if you overflow them, the excess digits are simply cut off (which is the same as taking mod 2^32 - only that it doesn't even require a calculation). In fact, they are even expected to overflow in that type of RNG.
And even if I'm wrong about the type and the numbers are stored as 64 bit integers on some systems, that doesn't matter since we are only using the last 30 bits anyway. That is what this line does:
Code:
(store_mod,":r","$rand_seed",1024*1024*1024),
I definitely don't want the first bit, since that is the sign, and overflowing into negative would lead to strange behavior with val_div. The second one, I just cut off since 1024^3 is a nice, round number...
 
Back
Top Bottom