04 Jul, 2011, Rarva.Riendf wrote in the 21st comment:
Votes: 0
Quote
What bug are you talking about? I'm not aware of any bug.
If you think there is a bug, why not explain it and give us a patch?

You stated it yourself: rand was perticulary bad in mst OS's at the beginning of them. It is not the case anymore. Unless you want a perticualr behaviour for specific reasons ( I doubt you would in a mud) you are way better using the method I gave to have a real random distribution. Because Random is not only about getting a random number in the first place. It is also in not getting more of some than other.

Quote
It was presented as possible clue that the statement it was posted in response to just may be in error.

No, not in error, just unlikely.
04 Jul, 2011, Scandum wrote in the 22nd comment:
Votes: 0
From what I gathered random number seeds differ between machines, probably added for security but rather annoying for game design, which would be one reason to use a good custom random number generator with seed support that isn't influenced by hardware. Unless there's some way to figure out the offset difference between machines for rand().
04 Jul, 2011, Lyanic wrote in the 23rd comment:
Votes: 0
Mersenne Twister. That is all.
04 Jul, 2011, Rarva.Riendf wrote in the 24th comment:
Votes: 0
Scandum said:
From what I gathered random number seeds differ between machines, probably added for security but rather annoying for game design, which would be one reason to use a good custom random number generator with seed support that isn't influenced by hardware. Unless there's some way to figure out the offset difference between machines for rand().

Why is the seed annoying for game design ? I can understand why the random sequence being different from machine to machine be a problem (and then, as a matter of fact no I cannot understand as if you want a random number, it is to actually NOT know what it will be). But seed, especially since all rand() worth its salt has a way to set it) I cannot see.
04 Jul, 2011, Ssolvarain wrote in the 25th comment:
Votes: 0
Tyche said:
Heck, I barely write enough code to sell to maintain my own crack addiction.


Cut out the middle-men. Come work for me and I'll pay you in crack, a dark basement room and a few bowls of oatmeal a day. 40 ounce is negotiable, but don't expect any that cost over $1.25.
05 Jul, 2011, Tyche wrote in the 26th comment:
Votes: 0
Scandum said:
From what I gathered random number seeds differ between machines, probably added for security but rather annoying for game design, which would be one reason to use a good custom random number generator with seed support that isn't influenced by hardware. Unless there's some way to figure out the offset difference between machines for rand().

Exactly. You'd want any generator functions to perform identically on whatever server you happen to be running on.
Something like the following is probably sufficient, portable (not to 16-bit systems though) and performs well:
#define P_RAND_MAX 2147483647
static unsigned long p_next = 1;
int p_rand (void) {
int result;
/* ANSI-C portable implementation */
p_next = p_next * 1103515245 + 12345;
result = p_next & P_RAND_MAX;
/* improve randomness by swapping byte 1 with byte 3 */
result = (result & 2130771712) | ((result & 255) << 16) | ((result & 16711680) >> 16);
return result;
}
void p_srand (unsigned int seed) {
p_next = seed;
}
05 Jul, 2011, Scandum wrote in the 27th comment:
Votes: 0
Rarva.Riendf said:
Why is the seed annoying for game design ? I can understand why the random sequence being different from machine to machine be a problem (and then, as a matter of fact no I cannot understand as if you want a random number, it is to actually NOT know what it will be). But seed, especially since all rand() worth its salt has a way to set it) I cannot see.

One example is using a player's vnum as a seed to create a random personal dungeon. That way the player will have the same dungeon each time they visit as you use the same seed, without the need to save the entire dungeon. In the same manner you can create random objects with dozens of modifiers while only needing to store the random seed.

One downside is that you can't change the engine without the objects changing, but using a solid top down design you can make minor changes with only minor consequences.
05 Jul, 2011, Runter wrote in the 28th comment:
Votes: 0
Tyche said:
Scandum said:
From what I gathered random number seeds differ between machines, probably added for security but rather annoying for game design, which would be one reason to use a good custom random number generator with seed support that isn't influenced by hardware. Unless there's some way to figure out the offset difference between machines for rand().

Exactly. You'd want any generator functions to perform identically on whatever server you happen to be running on.
Something like the following is probably sufficient, portable (not to 16-bit systems though) and performs well:
#define P_RAND_MAX 2147483647
static unsigned long p_next = 1;
int p_rand (void) {
int result;
/* ANSI-C portable implementation */
p_next = p_next * 1103515245 + 12345;
result = p_next & P_RAND_MAX;
/* improve randomness by swapping byte 1 with byte 3 */
result = (result & 2130771712) | ((result & 255) << 16) | ((result & 16711680) >> 16);
return result;
}
void p_srand (unsigned int seed) {
p_next = seed;
}


What would be an appropriate source for the seed? I've seen the process id number used in some codebases.
05 Jul, 2011, Rarva.Riendf wrote in the 29th comment:
Votes: 0
Scandum said:
Rarva.Riendf said:
Why is the seed annoying for game design ? I can understand why the random sequence being different from machine to machine be a problem (and then, as a matter of fact no I cannot understand as if you want a random number, it is to actually NOT know what it will be). But seed, especially since all rand() worth its salt has a way to set it) I cannot see.

One example is using a player's vnum as a seed to create a random personal dungeon. That way the player will have the same dungeon each time they visit as you use the same seed, without the need to save the entire dungeon. In the same manner you can create random objects with dozens of modifiers while only needing to store the random seed.

One downside is that you can't change the engine without the objects changing, but using a solid top down design you can make minor changes with only minor consequences.

The seed is not the problem here (you can set one on every rand function), the problem would be the control of the random algorithm itself as it could give you a different sequence on another server/machine/update of the os.
So yes in this case you would need to control the algorithm. I would like to know if this pattern is actually used in games. Cost of Storing/Cost of Generating.
And it makes evolution in generation quite impossible without wiping the info. So…actual use of this of just talking about theories ?
05 Jul, 2011, Tyche wrote in the 30th comment:
Votes: 0
Runter said:
What would be an appropriate source for the seed? I've seen the process id number used in some codebases.


It really doesn't matter. Obviously, if you don't set a seed that varies, anything that calss rand calls during the process of
loading or population will be repeatable across restarts.

Of course, if you are going to use rand as a generator function it should be something you store
or calculate. For example, we used (character->level*key->vnum) as the seed for picking a given lock.
If you were generating a random dungeon/area, the coordinates of the entrance, or the objid/vnum of the exit,
would probably be a good seed to use. So you don't need to store it anywhere, if it's set from something
you already use.
06 Jul, 2011, Scandum wrote in the 31st comment:
Votes: 0
Tyche said:
For example, we used (character->level*key->vnum) as the seed for picking a given lock.

One downside of that approach is that a character would be able to pick a certain lock, gain a level, and no longer be able to pick it. Using character->vnum + key->vnum would give a consistent result.

It's a good example of a situation where you want seeding to be consistent between servers.
07 Jul, 2011, David Haley wrote in the 32nd comment:
Votes: 0
Scandum said:
One downside of that approach is that a character would be able to pick a certain lock, gain a level, and no longer be able to pick it.

No… it means that the number of tries before a successful pick might be different.

Unless, of course, you're using your seed to determine ahead of time whether the lock is pickable, rather than the probability of any particular attempt to pick the lock succeeding.
08 Jul, 2011, Scandum wrote in the 33rd comment:
Votes: 0
David Haley said:
Scandum said:
One downside of that approach is that a character would be able to pick a certain lock, gain a level, and no longer be able to pick it.

No… it means that the number of tries before a successful pick might be different.

You'd need a private seed for that to work, and somehow determine the first pick attempt. It's highly unlikely that was the intended behavior.

David Haley said:
Unless, of course, you're using your seed to determine ahead of time whether the lock is pickable, rather than the probability of any particular attempt to pick the lock succeeding.

In D&D you get only one pick attempt per lock, which I assume was the behavior being simulated.
30 Apr, 2013, Vigud wrote in the 34th comment:
Votes: 0
Quote
It was Michael Chastain that added that code to Merc. I guess anyone who bothers to read, understand and implement an algorithm from Knuth, must be a fucking idiot crack smoker.
I recently got interested in pseudo-random number generators. I started from Knuth and wrote a straight-forward, canonical implementation of the Mitchell-Moore algorithm. I was surprised how verbose the implementation from Merc was. I don't understand why it was done this twisted, illegible way:
/*
* I've gotten too many bad reports on OS-supplied random number generators.
* This is the Mitchell-Moore algorithm from Knuth Volume II.
* Best to leave the constants alone unless you've read Knuth.
* – Furey
*/
static int rgiState[2 + 55];

void init_mm( )
{
int *piState;
int iState;

piState = &rgiState[2];

piState[-2] = 55 - 55;
piState[-1] = 55 - 24;

piState[0] = ( ( int )current_time ) & ( ( 1 << 30 ) - 1 );
piState[1] = 1;
for( iState = 2; iState < 55; iState++ )
{
piState[iState] = ( piState[iState - 1] + piState[iState - 2] ) & ( ( 1 << 30 ) - 1 );
}
return;
}

int number_mm( void )
{
int *piState;
int iState1;
int iState2;
int iRand;

piState = &rgiState[2];
iState1 = piState[-2];
iState2 = piState[-1];
iRand = ( piState[iState1] + piState[iState2] ) & ( ( 1 << 30 ) - 1 );
piState[iState1] = iRand;
if( ++iState1 == 55 )
iState1 = 0;
if( ++iState2 == 55 )
iState2 = 0;
piState[-2] = iState1;
piState[-1] = iState2;
return iRand >> 6;
}


The code I came up with looks like this:
#define L 37U
#define K 100U

static unsigned long int sequence[K];
static unsigned int b = L, a = K;

void init_mm(unsigned long int seed) {
unsigned int i;

for (i = 0; i < K * 2; i++)
sequence[i % K] = seed = (1664525 * seed + 1013904223);

return;
}

unsigned long int number_mm(void) {
a++;
b++;
return sequence[a % K] += sequence[b % K];
}
30 Apr, 2013, Lyanic wrote in the 35th comment:
Votes: 0
Vigud said:
I started from Knuth and wrote a straight-forward, canonical implementation of the Mitchell-Moore algorithm.

Just a word of advice, and you may already be aware of this: the Mitchell-Moore algorithm makes for an absolutely horrible PRNG.

If you're looking into implementing something that you want to use as the PRNG for a real game, check out something like Mersenne Twister.
30 Apr, 2013, Vigud wrote in the 36th comment:
Votes: 0
I don't think M-M is absolutely horrible, especially if you compare it to MT. First of all, properly set up M-M can yield OK results in the dieharder set of tests, which I think is already better than you need in your typical 10-player MUD. The most outstanding feature of MT, which is greatness of the period of sequences that MT produces, doesn't buy you much – it's not like it will be 19937/1280 times more random than M-M can ever be. MT is not cheaper than M-M in both CPU cycles and size of the state. And I personally find it harder to implement.

If you know reasons for which Mitchell-Moore should be considered absolutely horrible, please let me know.
30 Apr, 2013, quixadhal wrote in the 37th comment:
Votes: 0
I've never found the system PRNG to be bad enough to not use it for purposes of human-playable games. Maybe in 1990, that wasn't the case, but can anyone really say that their players suddenly stopped crying about the computer "cheating" because they switched random number generators?
01 May, 2013, Lyanic wrote in the 38th comment:
Votes: 0
Vigud said:
I don't think M-M is absolutely horrible, especially if you compare it to MT. First of all, properly set up M-M can yield OK results in the dieharder set of tests, which I think is already better than you need in your typical 10-player MUD. The most outstanding feature of MT, which is greatness of the period of sequences that MT produces, doesn't buy you much – it's not like it will be 19937/1280 times more random than M-M can ever be. MT is not cheaper than M-M in both CPU cycles and size of the state. And I personally find it harder to implement.

If you know reasons for which Mitchell-Moore should be considered absolutely horrible, please let me know.

Actually, the issue I raise with Mitchell-Moore is insufficient entropy. This is primarily due to its tendency toward clustering of numbers generated in a subset of the overall range. It evens out over VERY LARGE sample sizes, but if you're talking about usage for a game - you're not dealing with VERY LARGE sample sizes. Mersenne-Twister, while being more computationally expensive, works well over small and medium sample sizes. It was designed with Monte Carlo algorithms in mind.

There is a fair amount of academic literature to back this up, some of which I contributed to once upon a time. It was part of a research project I did once in graduate school - comparative statistical analysis of various PRNG algorithms. I'd cite some articles, but I don't have access to academic journals anymore. I'm also far too lazy.

quixadhal said:
I've never found the system PRNG to be bad enough to not use it for purposes of human-playable games.

I believe the system PRNG was the McKall-Tso algorithm - or at least it would've been back in your day. :-p
01 May, 2013, Vigud wrote in the 39th comment:
Votes: 0
How should I measure entropy to see that MT is better than M-M? If there's a particular test or set of tests, please share the name(s).

I know there are some ways to improve such generators, like combining with another generator; making the generator multiplicative or xor-based; increasing the tap offset; increasing the number of terms; including small odd integer multipliers. Sadly, I don't know how to combine them effectively.

Would you suggest me research papers/books to read? To narrow the material, let's say I'm more interested in learning how to create PRNGs for games like MUDs. I'm interested in all kinds and classes of generators, not just the best ones.
02 May, 2013, Lyanic wrote in the 40th comment:
Votes: 0
Vigud said:
How should I measure entropy to see that MT is better than M-M? If there's a particular test or set of tests, please share the name(s).

You can accomplish it by just running something akin to the Diehard Tests over varying sample sizes, then doing some further statistical analysis. What you're looking for is a smooth distribution of numbers (i.e. all numbers in the range equally likely to be generated for any given sample size). I don't remember enough details on my tools or methodology to give more precise info, though - it was quite a few years ago.

The PRNGs I remember researching most were Mitchell-Moore, McKall-Tso, Mersenne-Twister and ISAAC. I seem to recall ISAAC being promising, but still under development. You might want to look into that one if you haven't already.
20.0/62