More RNG woes

This forum is for the Lua scriptable clone of DM/CSB called Dungeon Strikes Back by Sophia. Use DSB to build your own highly customised games.

Moderator: Sophia

Forum rules
Please read the Forum rules and policies before posting.
Post Reply
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

More RNG woes

Post by kaypy »

I've been a bit suspicious for a while, but I'm now pretty certain that there's something broken about dsb_rand_seed. (I think it may be a property of the Mersienne Twister in general- if the seed clears most of the internal state then what the rng puts out will be pretty bad for a long time)

Test case: startup.lua with

Code: Select all

	rngseed = dsb_rand(0,65535)
	rngseed = 65536 * rngseed + dsb_rand(0,65535)
	__log("initing rng:")
	__log(rngseed)
	dsb_rand_seed(rngseed)
	
	__log("testing rng:")
	for i=0,100 do
		__log(tostring(dsb_rand(0,65535)))
	end
should give a random init seed, followed by a sequence of random numbers as generated by that seed.

The sequence "should" be random, but seems to follow one of a handful of patterns.
Friends don't let friends eat worm round
User avatar
Sophia
Concise and Honest
Posts: 4239
Joined: Thu Sep 12, 2002 9:50 pm
Location: Nowhere in particular
Contact:

Re: More RNG woes

Post by Sophia »

I'm not denying that there may be a problem, but it's also true that we humans are good at spotting patterns even where there might not be any, so, depending on the parameters of your test, there may or may not be a real issue here. I guess it depends on what a 'handful of patterns' really means.

Resetting the seed does clear out the entire state array, which is then repopulated according to a given algorithm (which is all on the Mersenne Twister Wikipedia page if you're interested), though there is also code to fill the state array directly. If something 'more random' than a single seed can be given to populate it, then the results may be better, but I didn't delve into this part of it.

One issue with this test is that it all seems to hinge upon two calls to dsb_rand early in the program's execution. If these two results produce not-so-random random numbers, then you'll end up with a very small set of seeds and that will throw everything off. Are a limited number of seeds produced or is the problem that that different seeds still create similar patterns?

Relatedly, though this is admittedly already much bigger than most of the random numbers already generated in DSB-- does the situation improve if you increase the range of the generated random number to greater than 16 bits?
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: More RNG woes

Post by kaypy »

Would metapareidolia be the tendency to see people seeing patterns that aren't there when they are not? 8-)

I just ran the generator 5 times, of which here are 3 outputs

Code: Select all

 initing rng	 initing rng	 initing rng	'=AND(A4=B4,B4=C4)
3317054946	3828422056	2846822571	
 testing rng	 testing rng	 testing rng	
4933	4933	4933	TRUE
5429	5429	5429	TRUE
36313	36313	36313	TRUE
53288	53288	53288	TRUE
17057	17057	17057	TRUE
25266	25266	25266	TRUE
38316	38316	38316	TRUE
49095	49095	49095	TRUE
57242	57242	57242	TRUE
13110	13110	13110	TRUE
38341	38341	38341	TRUE
54594	54594	54594	TRUE
59767	59767	59767	TRUE
46819	46819	46819	TRUE
57537	57537	57537	TRUE
48131	48131	48131	TRUE
22572	22572	22572	TRUE
8578	8578	8578	TRUE
40480	40480	40480	TRUE
36570	36570	36570	TRUE
37992	37992	37992	TRUE
22797	22797	22797	TRUE
27122	27122	27122	TRUE
60397	60397	60397	TRUE
30979	30979	30979	TRUE
27820	27820	27820	TRUE
43908	43908	43908	TRUE
59486	59486	59486	TRUE
48740	48740	48740	TRUE
39737	39737	39737	TRUE
41521	41521	41521	TRUE
871	871	871	TRUE
43273	43273	43273	TRUE
12204	12204	12204	TRUE
48582	48582	48582	TRUE
28705	28705	28705	TRUE
60333	60333	60333	TRUE
41548	41548	41548	TRUE
23029	23029	23029	TRUE
46914	46914	46914	TRUE
58752	58752	58752	TRUE
59938	59938	59938	TRUE
16041	16041	16041	TRUE
56059	56059	56059	TRUE
39635	39635	39635	TRUE
33502	33502	33502	TRUE
42609	42609	42609	TRUE
23680	23680	23680	TRUE
41683	41683	41683	TRUE
6431	6431	6431	TRUE
35803	35803	35803	TRUE
4101	4101	4101	TRUE
17678	17678	17678	TRUE
45061	45061	45061	TRUE
24722	24722	24722	TRUE
16859	16859	16859	TRUE
9834	9834	9834	TRUE
13595	13595	13595	TRUE
27020	27020	27020	TRUE
23001	23001	23001	TRUE
65341	65341	65341	TRUE
21630	21630	21630	TRUE
11505	11505	11505	TRUE
7065	7065	7065	TRUE
63273	63273	63273	TRUE
30431	30431	30431	TRUE
32551	32551	32551	TRUE
55666	55666	55666	TRUE
42689	42689	42689	TRUE
60367	60367	60367	TRUE
40967	40967	40967	TRUE
64483	64483	64483	TRUE
56980	56980	56980	TRUE
26169	26169	26169	TRUE
15089	15089	15089	TRUE
6755	6755	6755	TRUE
3446	3446	3446	TRUE
58222	58222	58222	TRUE
42133	42133	42133	TRUE
52291	52291	52291	TRUE
119	119	119	TRUE
32088	32088	32088	TRUE
1815	1815	1815	TRUE
50773	50773	50773	TRUE
16786	16786	16786	TRUE
15239	15239	15239	TRUE
12650	12650	12650	TRUE
52693	52693	52693	TRUE
38681	38681	38681	TRUE
34878	34878	34878	TRUE
32598	32598	32598	TRUE
57939	57939	57939	TRUE
48171	48171	48171	TRUE
46090	46090	46090	TRUE
6156	6156	6156	TRUE
35077	35077	35077	TRUE
49129	49129	49129	TRUE
64861	64861	64861	TRUE
4457	4457	4457	TRUE
40823	40823	40823	TRUE
51351	51351	51351	TRUE
I had looked at wikipedia previously and was wondering if the seed process left it with excess zeros:
wikipedia wrote:Can take a long time to start generating output that passes randomness tests, if the initial state is highly non-random—particularly if the initial state has many zeros. A consequence of this is that two instances of the generator, started with initial states that are almost the same, will usually output nearly the same sequence for many iterations, before eventually diverging. The 2002 update to the MT algorithm has improved initialization, so that beginning with such a state is very unlikely.
It sounds like you are using the better seeding algorithm, though, so I am not sure what is going on.

Fortunately it seems to behave better if left unseeded. I wanted to be able to cache the seed for debugging ("what made the dungeon generate like *this*??") but hadn't actually gotten around to storing it usefully yet anyway. (It would be in the log file for the first time you run it, but only the first time...)

Hmm, actually, I could probably get away with something like

Code: Select all

	rngseed = dsb_rand(0,65535)
	rngseed = 65536 * rngseed + dsb_rand(0,65535)
	__log("initing rng:")
	__log(rngseed)
	dsb_rand_seed(rngseed)
	-- run through a random *length* of numbers, so even if the sequence is the same it'll give a different output dungeon
	for i=0,((rngseed%65536)+100) do
		dsb_rand(0,65535)
	end
	
	__log("testing rng:")
	for i=0,100 do
		__log(tostring(dsb_rand(0,65535)))
	end
Eventually I'll probably go spelunking through the (just now available) code to see what I can find, but that wouldn't be till I'm not halfway through a dungeon. 8-)
Friends don't let friends eat worm round
Post Reply