Author Topic: I don't understand random seeds.  (Read 18749 times)

sokol815

  • Rogueliker
  • ***
  • Posts: 85
  • Karma: +0/-0
  • Web Developer by Day, still Web Developer by night
    • View Profile
    • My Projects
    • Email
Re: I don't understand random seeds.
« Reply #30 on: April 04, 2014, 10:42:18 PM »
Woah, wait a minute. If you can play the same game twice, this means the game does not have permadeath. You can start over with exactly the same game world and if you make the same moves, the same sequence of events will occur. If you die, you can just repeat your game up to a safe number of turns earlier and continue as if nothing happened.

Obviously, this could be automated, but that wouldn't even be necessary in principle.

that would be if you used the same seeded dRNG for everything....

the way I do this is I create the world off of a seed (whether given or taken from the unix timestamp), then I go back and switch out the RNG with a random seed (unix timestamp)... this then leads to the ability to play the same world with a different in-game-playing seed.

I first use the above seeded dRNG to choose which races and creatures inhabit the world. I then go and reset the dRNG again to the same seed to actually generate the mainworld, and generate arrays of Seeds for each individual dungeon that should be generated.

Say I have 5 dungeons of depth 5, 20, 50, 100 and 40. now I have the main world generated, and I have 5 arrays of corresponding lengths with nothing but an integer seed in them.

When the PC goes to dive into one of those dungeons, the game will swap out the current RNG with the generate world RNG, reseed it with the appropriate generated seed for that level, and generate the dungeon level. It can then swap back to the RNG we were using before and populate the level.

That way you can play the same maps, but the items, danger rooms, enemies and all are different, which will allow your friend to say: "Lucky! I didn't get the dagger of dragon slaying on D3!"
My projects - http://exilania.com/landing/   |  Minotaur vs orcs -  http://exilania.com/minotaur/ |  Strife  -  http://exilania.com/strife/

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #31 on: April 05, 2014, 01:15:51 AM »
Alternatively--

dRNG for items/level/monsters etc, but  a weighted RNG for combat, spells, gas propagation, etc.

Kimchi

  • Newcomer
  • Posts: 13
  • Karma: +0/-0
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #32 on: May 24, 2014, 01:57:06 AM »
I've got a question about this, actually. What's to stop some mad programmer from seeding a random number generator with a referenced, but uninitialized integer pointer?

For example, what if the programmer wrote something like this:

Code: [Select]
int *uninitialized_ptr;
seed(*uninitialized_ptr);

Since, technically speaking, the seed function only cares about receiving an integer value, and doesn't generaly use that vlue to reference any other memory locations, I don't think it would break the code. Further, even though technically the RNG would still be deterministic, that determinism would be unreproducible because not even the programmer knew the seed, yes?

Or will this cause something to blow up somewhere in the backlands of Ohio?

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #33 on: May 24, 2014, 02:52:50 AM »
Dereferencing uninitialized pointers results in "undefined behavior," but it's not random. In principle, you can figure out what values your uninitialized pointers point to before you run the program (though I don't recommend it).

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: I don't understand random seeds.
« Reply #34 on: May 24, 2014, 04:05:23 PM »
Since the pointed memory location of an uninitialised pointer is not specified in the standard, it could point to any memory location - including a location that the operating system won't allow the program to read, or a location outside the range of the computer's memory. Some compilers may warn about the attempt to dereference an uninitialised pointer, and in some modes may convert that warning into an error that prevents compilation. So it's not very likely to run without crashing.

melville

  • Newcomer
  • Posts: 11
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #35 on: May 24, 2014, 10:55:37 PM »
Uninitialized variables can be used, a crude example:

Code: [Select]
unsigned int i, junk[100];

for (i = 0; i < 100 && junk[i] == 0; i++)
        ;

printf("Seed: %u\n", junk[i]);

Still it is a bad practice, since it relies on undefined behavior. Compiler can optimize it out, which can lead to weird situations. More information: http://kqueue.org/blog/2012/06/25/more-randomness-or-less/

If you want a seed that varies a lot why not ask kernel for entropy instead or at least use clock_gettime(2) function, which provides nanosecond precision?

Some of those issues are addressed by arc4random(3) family of functions. They don't require seeding, they take care of it on its own (reseeding also). One problem here is portability, those functions are native only on *BSD systems and Mac OS X. On Linux they can be found in libbsd library. There are also portable versions of it (working also under Windows I think), one example: https://www.mirbsd.org/a4rcontrb.htm

Function arc4random_uniform(3) is also nice, since it can be used to obtain numbers in a specified range without modulo bias. Possible issue that can occur is performance. Those are cryptography grade PRNGs, so speed is a secondary objective.
« Last Edit: May 24, 2014, 10:57:14 PM by melville »

Kimchi

  • Newcomer
  • Posts: 13
  • Karma: +0/-0
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #36 on: May 27, 2014, 04:38:59 PM »
Oh, cool Melville! So basically, there *isn't* anything preventing us from seeding the rand() function with an uninitialized pointer, but it's likely to make something go boom, am I right? I think I'll look into that clock_gettime() function, actually. It sounds promising.

melville

  • Newcomer
  • Posts: 11
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #37 on: May 28, 2014, 09:33:16 AM »
Oh, cool Melville! So basically, there *isn't* anything preventing us from seeding the rand() function with an uninitialized pointer, but it's likely to make something go boom, am I right? I think I'll look into that clock_gettime() function, actually. It sounds promising.

If you are using rand(3), seeding is probably least of your problems. Bad PRNG is still a bad PRNG, no matter how good the seed is. Even when you are using a better PRNG like Mersenne twister, time(3) is good enough in most cases - what matters is uniqueness of the seed across games. I would be more worried about a modulo bias than seed itself.

ASLR (Address space layout randomization) is used by mmap(3) on most systems, I wonder if it could be abused as a part of a seed? Still this is over complicating things in my opinion.

Example showing differences between time(3) and clock_gettime(2).

Code: [Select]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long int give_seed(void);

int
main(void)
{
        int i;

        for (i = 0; i < 20; i++)
                printf("Seed: %ld\t%lld\n", give_seed(),
                        (long long) time(NULL));

        return EXIT_SUCCESS;
}

long int
give_seed(void)
{
        struct timespec ts;

        (void) clock_gettime(CLOCK_REALTIME, &ts);

        return (ts.tv_sec ^ ts.tv_nsec);
}

I forgot to mention that arc4random(3) is non-deterministic, entropy is injected multiple times, since it is geared toward cryptographic applications. That could be a wrong usage case for roguelike, depending on your needs.
« Last Edit: May 28, 2014, 11:56:44 AM by melville »