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

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
I don't understand random seeds.
« on: March 05, 2014, 05:36:03 PM »
Can anyone explain seeds to me? I don't understand how people use it to generate random stuff. I use flash and I am not sure if it depends on language or not. I figure the best example might be something similar. Let's say I have two monsters. How does the seed effect the monster selection.

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: I don't understand random seeds.
« Reply #1 on: March 05, 2014, 05:43:42 PM »
Seeds are used to give a specific starting point to the number generator, which given the same seed will always generate the same set of numbers. This is useful for both testing randomized code by effectively freezing the randomness and making it deterministic and useful for doing things like sharing Dwarf Fortress worlds by only sharing the seed needed to make them.

The word "random" is misleading, there is no such thing as random in computing and even getting close is typically a waste of effort and a lot of effort.

ekolis

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 186
  • Karma: +0/-0
  • get ye dennis
    • View Profile
    • Ed's home page
    • Email
Re: I don't understand random seeds.
« Reply #2 on: March 05, 2014, 06:16:24 PM »
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?
The Ed draws near! What dost thou deaux?

>EAT SANDVICH

koiwai

  • Rogueliker
  • ***
  • Posts: 99
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #3 on: March 05, 2014, 06:19:41 PM »
Say, you are programming a space exploration game, and there must be 10K stars with planets or so. Instead of storing each star system, you store a single integer, the seed, for each of them, and when your ship visits the star system, you generate the system from the seed:
Code: [Select]
initialize_pseudo_random_number_generator(seed);
star_system = generate();
the seed uniquely determines the state of the PRNG, so every time you visit this star system, the PRNG will generate the same sequence of random numbers, and therefore the generated star system will allways look the same.

Optionally, if you PRNG permits that, you can do the following:
Code: [Select]

state = save_state_of_PRNG();

initialize_PRNG(seed);
star_system = generate();

restore_state_of_PRNG(state);

So, the usage of the random seed is limited to the 'generate' function call, and does not affect the subsequent commands.


On the downside, it's better to use seeds for things that cannot be easily changed by player's actions. This is why I gave an example with star systems. But they also can store landscapes, proceduraly generated textures, or things like this.
« Last Edit: March 05, 2014, 06:21:23 PM by koiwai »

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: I don't understand random seeds.
« Reply #4 on: March 05, 2014, 06:27:22 PM »
Pseudorandom number generators generate exactly the same output sequence when they get the same seed on input. This has both good sides (provide the same seed and input, and the system will behave exactly in the same way) and bad sides (if you are trying to randomly generate a key for your cryptography system, the adversary could break your cipher by trying all the possible seeds). In roguelikes, the first is usually a good thing (many games have an option of providing a "seed" to the generator, which allows two player to play in exactly the same dungeon; another use is that a game could be recorded by just recording the seed and the input), but there are potential cases where this is a problem (in an online tournament, the player could submit the layout of the first dungeon level to a program, which would try all the possible seeds and find one which matches this layout, and give the player an option to "predict" or even influence all the future dice rolls, or cheat in some other way).

I agree that the word "random" is misleading here (use "pseudorandom"), but there are better ways of generating randomness than using pseudo-RNGs (use the environmental noise collected from device drivers), and good sources of randomness are very useful in cryptography.

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: I don't understand random seeds.
« Reply #5 on: March 05, 2014, 06:36:43 PM »
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?

Often the "more perfect" part is actually "more cryptographically secure" which has more to do with what happens after the seed is obtained, in addition to the parameters of the seed itself.

Traditionally the sensor used to "randomly" seed prngs is the system clock.

For games with no competitive stakes, the default non-cryptographic prngs are fine, even if they give slightly clustered results in some cases.

+1 to koiwai's example as an in-game great use for the seed value

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #6 on: March 05, 2014, 06:54:04 PM »
Writing a custom rng could be interesting. Although I'm not that good in those kind of algorithms..

Btw, can someone explain why rand() is giving the same number when I use a command (in Teemu) that doesn't use a turn, but if another message is output and I try the same command it returns a different value. I don't understand what is going on. Shouldn't rand() return a (pseudo)random number each time it's called?

ekolis

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 186
  • Karma: +0/-0
  • get ye dennis
    • View Profile
    • Ed's home page
    • Email
Re: I don't understand random seeds.
« Reply #7 on: March 05, 2014, 07:05:32 PM »
Often the "more perfect" part is actually "more cryptographically secure" which has more to do with what happens after the seed is obtained, in addition to the parameters of the seed itself.

Traditionally the sensor used to "randomly" seed prngs is the system clock.


Well, yeah, but I'm not talking about taking a single seed and feeding it into an algorithm and never getting a new seed - I'm talking about using some unpredictable environmental input as input for a function which determines your random number. In essence, re-seeding the RNG with a new (but truly nondeterministic) input constantly.
The Ed draws near! What dost thou deaux?

>EAT SANDVICH

koiwai

  • Rogueliker
  • ***
  • Posts: 99
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #8 on: March 05, 2014, 07:12:49 PM »
ekolis:
At least in scinetific applications (and probably in crypto-), good PRNG gives you some guarantees about the distribution of the generated sequence of numbers. They also runs quickly. Many simulation techniques (like Gillespie algorithm) use a lot of random numbers, so speed is important.  Hardware sensors, in general, don't give you such guarantees about their data. They can be slow too.

Krice:
rand() returns the same number several times in a row?

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #9 on: March 05, 2014, 08:50:01 PM »
rand() returns the same number several times in a row?

When I think it harder it must be a bug in the message routine, because it's checking duplicate messages and exits when . is found, but in this case the message has two parts.

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #10 on: March 06, 2014, 12:39:04 PM »
Okay so using my previous example of two monsters how would I write it in logic steps to make it choose one or the other.

Is it have it choose a random number, then assign each monster  to one of those numbers?

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 #11 on: March 06, 2014, 12:59:49 PM »
Rand() takes the next number from the RNG sequence, which will typically be integers from 0 to MAX, or floats from 0 to 1. If you have a dice table with options 1 to 6, then you can compress the result of rand() into the set of results you want. For instance with (rand()%6) + 1 or floor(rand()*6)+1. Then you feed it into the dice table:
  • 1-2: tomato monster
  • 3-5: marmite monster
  • 6: cookie monster

  • Seed the random number generator
  • Use RNG functions to generate the first monster
  • Use RNG functions to generate the second monster
Steps 2 and 3 are very flexible and you've seen a lot of options for them in your other thread. Most of the options for generating a monster will call rand() once, so the Nth monster generated will be based on the Nth number from the RNG sequence (assuming that nothing else calls rand()).
As it says above, the same RNG seed means the same sequence of results from rand(), and that means the same monsters chosen.

TheCreator

  • Rogueliker
  • ***
  • Posts: 370
  • Karma: +0/-0
    • View Profile
    • Fame
    • Email
Re: I don't understand random seeds.
« Reply #12 on: March 06, 2014, 01:16:27 PM »
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?

What about portability? Most of smartphones don't have fans. I'm not sure about sensors, but it doesn't sound like a portable solution, either. Telling people that the game doesn't run on a computer without some piece of hardware just because the programmer doesn't know how to implement a good RNG is kind of lame, don't you think? :)
Fame (Untitled) - my game. Everything is a roguelike.

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #13 on: March 06, 2014, 01:23:24 PM »
Very often the RNG needs to be deterministic.
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #14 on: March 06, 2014, 03:00:09 PM »
Okay, so I basically need to figure out how to set the Seed for the RNG then any rand functions that come from it will always be the same. (I may need to test this out on some small tests). I would love if I could save a 6 digit number and always have the same world.