Has the Random Numbe Generator been tested?

[ohioastro]

I ask this question because there is a pretty strong tendency in the game for what I'd call "clumping." Stores tend to have groups of very similar items, and some of these trends persist for the entire game. I notice this especially with wild infusions, as I value the double category ones (physical / magical, etc.) and usually have to find them in shops. I will either find many or none. Another example is vaults. I've run across the same vault, same creatures, and exactly the same items on different levels. I've seen five copies of the same vault on some levels (e.g. Urkis). Similar comments apply to escorts - there is a tendency to get the same kind of escort multiple times - and frequently in the same place.

These could be random, of course. But there are well-known problems in numerics where some (supposedly) random number generators actually return the same numbers. It'd be worth checking this.

I'd also encourage thinking about spreading these sorts of things around some if this is intentional. As it is currently set up the stores have much less effective stock than the numbers suggest because of the duplications, for example, and it's more interesting to deal with different kinds of vaults than to repeat the same one over and over.

[omero]

Funny. That's exactly what got me to rant a bit over here: http://forums.te4.org/viewtopic.php?f=39&t=37493
I thought it was just bad luck, but then I keep opening shops that always have duplicate items or many several items with almost identical stats...
Cheers!

[tiger_eye]

T-Engine uses a library that generates pseudo-random numbers via the Mersenne Twister method. It creates a high quality and long sequence of random numbers at relatively good speed. I wouldn't recommend any other single generator for T-Engine.

About the clumping... well, as DarkGod would say, "Random is random" . If you want less clumping, then you want items created and chosen in a less random way.

[Nimmy]

Oops, too late, tiger_eye answered.

To add on this: For the vaults in Tempest Peak, it's deliberate. You can only have two vaults in this map: a money vault (vault filled with money, and probably enemies) or the "circle" vault, you are probably thinking about this one.

[nate]

Curious about this, I did a quick test. rng.float is not working at the precision it pretends to, that's for sure.

Put the following code in your favorite talent:

Code: Select all

		local randTable = {}
		local duplicates = 0
		for i=1, 10^6 do
			local rand = rng.float(0,1)
			if not randTable[rand] then randTable[rand] = true
			else duplicates = duplicates +1 end
		end
		game.logSeen(game.player, "Number of duplicates is "..duplicates)
		randTable = {}
		duplicates = 0
		for i=1, 10^6 do
			local rand = math.random()
			if not randTable[rand] then randTable[rand] = true
			else duplicates = duplicates +1 end
		end
                game.logSeen(game.player, "Number of duplicates with math.random is "..duplicates)

Now try it out. rng.float() routinely gets 100, 120 duplicates. math.random() gets none.

Distribution of the randoms is a different matter; I didn't test that, but it's definitely testable.

edit: Tested distribution. Since you're talking about gross problems with distribution, I decided just to eyeball it. Inserted into mod/class/game.lua/_M:display():

Code: Select all

	-- Now the ui
	self.uiset:display(nb_keyframes)
	--begin insert
	local count = 10^6
	local size = 100
	local distro = {}
	for i=1, count do
		local rand = rng.range(1, size)
		distro[rand] = (distro[rand] or 0)+1
	end
	local expected = count/size
	local width = game.w/size
	for i=1, size do
		local xPos = (i-1)*width
		local height = game.h*distro[i]/(2*expected)
		core.display.drawQuad(xPos, game.h-height, width, height, 255, 0, 0, 255)
	end
	--end insert
	-- "Big News"
	self.bignews:display(nb_keyframes)

Eyeballing it, doesn't look like any distribution problems from rng.range. You can play with the parameters if you'd like.

[tiger_eye]

Curious about this, I did a quick test. rng.float is not working at the precision it pretends to, that's for sure.

"rng.float" returns a single precision floating point number. This is part of why the underlying generator is so fast. But, since all numbers in Lua are double precision, it may appear to "pretend" to be double precision.

Although I haven't played with the generator or the underlying statistics, I would definitely expect some duplicates when generating 1e6 single precision numbers uniformly between 0 and 1.

Anyway, kudos, nate, for actually getting your hands dirty and playing around with it!

[nate]

"rng.float" returns a single precision floating point number. This is part of why the underlying generator is so fast. But, since all numbers in Lua are double precision, it may appear to "pretend" to be double precision. Although I haven't played with the generator or the underlying statistics, I would definitely expect some duplicates when generating 1e6 single precision numbers uniformly between 0 and 1.

Thanks for the info. Wolfram Alpha conveniently refuses to understand (2^32)! so I suppose I'll never know what the exact probabilities are I guess it's not really 2^32 since it's such a limited range anyways.

EDIT: Modified it to do 10^5 trials instead, with rng.float(1,2); I get 0-2 duplicates per run, pretty evenly distributed.

Single precision floating point, if I understand correctly, should have 2^23 values between every power of 2. So the odds of a single duplicate in 10^5 single precision numbers between 1 and 2 is:

(2^23)!/((2^23-10^5)!*(2^23)^(10^5))

which you can plug into Wolfram Alpha without choking it (although I can't understand how, 2^23! is a pretty big number). What are the odds? About E-260.

Of course, it's a bit of a spherical cow situation, since rng.float needs to return evenly distributed numbers, and I don't believe the 2^23 inside every power of 2 are evenly distributed. Sadly, WA won't handle (2^23)!/((2^23-x)!*(2^23)^(x))=0.5.

Edit: trying to test to establish the range of values for rng.float(1,2) ran me out of memory at 2^25 table entries, which is weird, because that should only take 256 megabytes.

[Nimmy]

Your computation is wrong. See Birthday paradox http://en.wikipedia.org/wiki/Birthday_problem

If your RNG can take n different values, and you sample k values of it, the expected numbers of collisions is
k*(k-1)/(2*n)
(there are k*(k-1)/2 different pairs, each of them has a 1/n chance of being a collision, use linearity of expectation to conclude)

So basically, as (10^6)^2 is big compared to 2^24 (even 2^32), you should see a lot of collisions on average.
It is small however compared to 2^53 (number of bits of the mantissa for double precision)

[nate]

Thank you! My error was that I was calculating the odds of no collisions.

The interesting thing here is that I'm seeing about one collision in 10^5 trials. I should see that in a space of 2^32, not 2^24 or 2^23. I guess the rng is creating the space across the entire range of single precision floating points and then collapsing into the requested range. Really interesting that it can use that whole space. Also really interesting that probability works

[Nimmy]

Actually, I just realized that the "single precision" thing is just an approximation, and not really what is happening.
What is happening is that the RNG gives a 32 bit number, and this number is divided by 2^32 to obtain a number between 0 and 1. This means that basically you obtain a number in double precision (because it is coded in a variable of type double) hence 64 bits (53 of mantissa), of which only 32 bits might be nonzero. This is not single precision, this is better.

So float(0,1) might give you in theory 2^32 different values.
float(1,2) is internally more or less the same as 1 + float(0,1). (look at genrand_real in file SMFT.h)

[ohioastro]

Interesting!

In this case it may be worth adding an extra layer to the random rolls...namely, to check on whether there is already a prior entry on the tables. For example, when rolling a vault check on whether a given type has already been seen; if so, roll again and accept whatever happens. Or roll again using only vaults that haven't happened yet, at least until all have happened once.

This would definitely help with store items, e.g. reroll if an item with the same basic flavor exists in the same store.

Escorts are a bit trickier, in the sense that it can be an advantage to have several of the same flavor. But I do think that it would be better for the game if the locations were standardized; e.g. 2 in Daik, 2 in Old Forest, 2 in Dreadfall, 1 in Reknor, 2 in the starters; level random.

[b0rsuk]

But how often is the generator seeded ? I noticed I got very similar items in some games, for example I played two Marauders in a row and both got Wrap of Stone and Wanderer's Rest before Dreadfell.

[darkgod]

It doesnt matter, the rng is called far too often and randomly to have any chance of generating big macroscopic events like the same artifact.
Every single particle efefct calls it every frame, so to ensure the same string of random numbers you would have to (at least) play at the very exact same precise speed, not missing a single frame, or using one too much

[Grey]

Also note that humans are very good at spotting patterns in random noise.

[cttw]

There is a free tool to test randomness, called Dieharder.

http://www.phy.duke.edu/~rgb/General/dieharder.php

I don't have time to apply it to tome right now. I've seen some hard-to-believe stuff in tome, but nothing that couldn't just be explained by bad luck.