(done) Seeding the RNG

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

(done) Seeding the RNG

Post by kaypy »

It's been a few months and I'm back to start seeing how badly I can abuse DSB again.

Would it be possible to add a function to set the seed for the RNG?

On my last iteration on ProbablySolvable I had one bit of the dungeon which seemed to break the rules. This no doubt indicates a bug somewhere, but things are too random to figure out what was going on. If I could run the generator of a logged seed value, then if it happens again I could deterministically regenerate the dungeon and log enough of that chunk to see exactly what is happening.

I had looked into just including a native lua implementation of MT, but it turns out the LUA version in DSB doesn't have bitwise ops, and hand-rolling them would add another thick layer of clunkiness to what I already thought was likely to run painfully slow (and I do use a *lot* of random numbers here)...

From what I can see, MT implementations tend to have a throw-in-a-32bit-number-and-it-seeds-the-whole-setup function, so hopefully it would just be a matter of exposing that as dsb_seedrand or something...

(I dug around the exe with a hex editor in case there was some function that wasn't documented yet, but couldn't see anything with seed or rand except the existing dsb_rand function...)

thanks
Kris
Friends don't let friends eat worm round
User avatar
Paul Stevens
CSBwin Guru
Posts: 4318
Joined: Sun Apr 08, 2001 6:00 pm
Location: Madison, Wisconsin, USA

Re: [featurerequest] Seeding the RNG

Post by Paul Stevens »

A Mersenne Twister seems like overkill for your purpose.
You are not trying to keep secrets from the Russians.
If Sophia does not feel like supplying the needed function,
why not implement your own using a linear congruential generator
or a combination of several if you are totally paranoid.
Speed is a definite advantage of such generators and any
patterns in the resulting numbers will certainly not be evident
in such an application as yours.
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: [featurerequest] Seeding the RNG

Post by kaypy »

Yeah that's my fall back plan. Mostly I was looking at MT because:

1) I wanted to be able to drop-in-replace the dsb_rand (rather than changing all the random numbers in my code) which is currently an MT so I had vague ideas of consistency.

2) I wasn't sure if a simple LCRNG wouldn't suck a bit too much and MT was the first thing that came up for "deterministicly random but not a sucky LCRNG"

3) It was really easy to find implementation code for MT right up until I got to the point of running it and finding DSB's LUA5.1 doesn't have bitwise ops.
Friends don't let friends eat worm round
User avatar
Paul Stevens
CSBwin Guru
Posts: 4318
Joined: Sun Apr 08, 2001 6:00 pm
Location: Madison, Wisconsin, USA

Re: [featurerequest] Seeding the RNG

Post by Paul Stevens »

A good linear congruential generator will not be 'sucky'.
But unless you have a LUA with builtin 64-bit integer
support, you need to watch out for the maximum precision
available in LUA's double precision arithmetic (about 53 bits).
I hope Sophia will provide the seeding function. That is
certainly your best option.
User avatar
Sophia
Concise and Honest
Posts: 4239
Joined: Thu Sep 12, 2002 9:50 pm
Location: Nowhere in particular
Contact:

Re: [featurerequest] Seeding the RNG

Post by Sophia »

DSB already uses Mersenne Twister, so whether it's overkill or not, it's already there, because the previous RNG was definitely "sucky." :mrgreen:

I'll look into being able to set the seed.

(Do we have to care about modulo bias? I haven't so far...)
User avatar
Paul Stevens
CSBwin Guru
Posts: 4318
Joined: Sun Apr 08, 2001 6:00 pm
Location: Madison, Wisconsin, USA

Re: [featurerequest] Seeding the RNG

Post by Paul Stevens »

whether it's overkill or not, it's already there
I was not suggesting that the Mersenne Twister was overkill
for DSB. kaypy was thinking of implementing his own
random generator and I thought something simpler would
be sufficient for his purpose. Less chance of mistake, for
one important thing.
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: [featurerequest] Seeding the RNG

Post by kaypy »

Paul Stevens wrote:A good linear congruential generator will not be 'sucky'.
This kind of assumes that one I whack together in a hurry is likely to be 'good'... 8-)
Sophia wrote:I'll look into being able to set the seed.
Thankyou! If it turns out to be a pain don't put too much effort into it (I'm not sure anyone else will ever need it). I'm just hoping it is just a matter of exposing a function that is already there.
Sophia wrote:(Do we have to care about modulo bias? I haven't so far...)
I was thinking about trying do run some stats and figure out whether there is any modulo bias in the system- the MT generator I was looking at had it go via floating point to get the integer range so I wasn't sure if the DSB one might do the same. Then I did some back of the envelope calculations to try to get an idea of of the likely scope of the issue.

If we are looking at a 32bit MT then if I collect ints in the range 1..42million I would need to get enough data to measure a 1% difference in bias.

I think I'm going to go with "no we don't care about modulo bias" 8-)
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: (done) Seeding the RNG

Post by Sophia »

I've added dsb_rand_seed to DSB 0.67. It takes one parameter, the desired random seed.

Nothing in there has required any data file or Lua updates, so here are new .exe's which should be enough. I'll push an actual "real" update when I've had a chance to do a little more testing.

Edit: An actual DSB 0.67 has been released, here
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: (done) Seeding the RNG

Post by kaypy »

Awesome! Thanks
Friends don't let friends eat worm round
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: (done) Seeding the RNG

Post by kaypy »

I was hacking away at getting pits into my random dungeon, and my mystery glitch recurred with seed 1714009441. Poking around, seems I had some variables sneaking into global scope and being accidentally reused later.

So chalk up one bug kill for seedable RNGs 8-)
Friends don't let friends eat worm round
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: (done) Seeding the RNG

Post by kaypy »

One thing I am seeing that's a touch weird (not a problem per se, just odd) is that the dungeon as loaded in DSB is sliiightly different to the same seed loaded in ESB. The dungeon layout is the same, but item placements vary.

This is rather odd as both of these happen in the same function build_dungeon(), so I can't see why the RNG would start behaving differently halfway through... (If they happened in different parts of the code I would just think something internal was calling an RNG...)

Hmm. Maybe some dsb_* function has an RNG call in one but not the other?
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: (done) Seeding the RNG

Post by Sophia »

That's exactly what it is. The results for items diverge because DSB invokes the RNG when placing items but ESB doesn't, in order to generate the random pixel offsets of items lying on the floor. These obviously don't matter in ESB so it doesn't generate them.

This is one of those things that's fixable if it actually ends up being a problem, but I'm not sure if it's worth effort. Is maintaining a consistent RNG sequence across DSB and ESB a goal that is worth caring about?
User avatar
Paul Stevens
CSBwin Guru
Posts: 4318
Joined: Sun Apr 08, 2001 6:00 pm
Location: Madison, Wisconsin, USA

Re: (done) Seeding the RNG

Post by Paul Stevens »

My unsolicited advice: Fix it. The editor and engine must agree in every detail.
kaypy
Artisan
Posts: 171
Joined: Sun Jan 19, 2014 7:11 am

Re: (done) Seeding the RNG

Post by kaypy »

If it's just a matter of adding in a few spurious RNG calls then it may be worth some minimal effort on the principle of the matter.

I wouldn't consider it a big deal though. Until this thread there wasn't even a repeatable RNG to worry about...

And does anyone other than me (and the original Chaos Hack) even use the RNG in ESB-land?
Friends don't let friends eat worm round
Post Reply