The Mana World Forums

Doofus wrote:

Nard wrote:The chances are exactly the same if you submit the furs one by one or if you come with a lot

In theory one would expect this but then how is the random number generator reseeded?

I have faith in mt19937. Note that every time you click "next" or a menu option, there has been a pause so an unknown number of additional calls has been made anyway.

o11c wrote:From a mathematical perspective, rand(30) will require an average of 30 calls to be successful

It is an error to think about random events on an average point of view only, especially with low probability events (highly dissymmetric probability distribution functions) which is the case of geometric one with low parameter. Dispersion aspect and confidence intervals must be taken into account to dimension random based event results or some players may experience bad disagreements (see upper). To prevent such disagreement and lead to easier choices it might be better to use draws in a finite number set (leading to hypergeometric distribution and derived) or limit the number of draws by script. Without such a choice there is NO way to exclude the possibility that a player will not fall into the bad luck pit; seed and random generator have nothing to do with that.

rand(30) gives a number between 0 (or 1) and 30 with uniform probability of 1/30 as an average of 15 and has nothing to do with success or fail if the result is not compared to a previously chosen number.

Indications:
In a Bernouilli trialbased drawing (with probability of success p)

• The number of trials up the first success obeys to geometric law and has 99% chances to be inferior to: [ln(1-0.99)/ln(1-p)]=[-2/lg(1-p)] (Forest bow, Agostine, Innkeeper)
• The size N of the required sample to get k successes with 99% is roughly included within the limits:
  {{sqrt[(1-p)*(2.5758)²+4*k] ± 2.5758}/(2*p)}²
  provided that both (1-p)*N and p*N are greater than 5 (Moivre-Laplace approximation of the binomial law)
  example: applies to blue sage quest with some approximation

Doofus wrote:

Nard wrote:The chances are exactly the same if you submit the furs one by one or if you come with a lot

In theory one would expect this but then how is the random number generator reseeded? Hopefully purveyors of Douglas Adams events are aware of the need for external sources of entropy - A bistromatic drive is really not that hard to code.

In post:http://forums.themanaworld.org/viewtopi ... 3&p=120962Freeyorp says:

Freeyorp101 wrote:tmwAthena uses a mersenne twister to generate random numbers, not rand() directly.

Mersenne twister (which o11c refers to as "mt19937") is widely recognized a highly reliable algorithm (as long as you don't use it for encryption). I think this sophisticated tool is rather an over-dimensioned choice, and that a direct call to the C random() function (linear congruential algorithm) would be fairly enough for game needs (and maybe faster too).A small math library would perhaps be useful to developers and avoid headaches to them when they have to deal only with script integer functions . The random generator has little influence in the way it is used in game, as even spatial or time correlation in mob spawning would not cause any special problem but your death

Nard

edit: Formula {{sqrt[(1-p)*(2.5758)²+4*k] ± 2.5758}/(2*p)}² is wrong, use instead:
{{sqrt[(1-p)*(2.5758)²+4*k] ± 2.5758*(1-p)}/(2*p)}²

Nard wrote:Mersenne twister (which o11c refers to as "mt19937")

Technically, Mersenne twister is a family, and mt19937 is just the most common one. Not all Mersenne twisters have the good properties that this one does.

Nard wrote:I think this sophisticated tool is rather an over-dimensioned choice, and that a direct call to the C random() function (linear congruential algorithm)

Ignoring the difference between rand() and random(), and the fact that rand() is not guaranteed to be any particular algorithm and random() is nonlinear, and that rand() follows random() on recent systems:

both rand() and random() only return results between 0 and RAND_MAX, which may be as low as 32767, which is low enough to cause problems.

Note that an LCG has a *very* short period for repeated random calls where the upper bits are discarded (which is the case since we use modulus).

Note also that an LCG requires writing to the state every call, whereas mt19937 only requires writing to the state every 624 calls, which is better memory behavior. The fact that there is a computation lag on some calls is insignificant due to the high number of calls per timer cycle and network delays.

The purpose of my former post was to indicate that the random number generation had nothing to do with the extreme valuse that players may encounter in game. These values have to do with the way random values are used in script instead, through the probability distribution which is used. Thus I gave a few formulas to help developers to choose the parameters they use.

I don't think there is a need to change anything in the server random number generator as it is a good, reliable and fast one. I still think that a simpler one could have been sufficient for scripting and any random based server game function (even a 32767 resolution, more than 4 digits, or "short" period would be enough for script and mob spawning). And if not, the rand48() family of functions is still available. TMW is not a turbulence process, at least I hope so!

In a math library, I would include some non uniform generators, such an Bernouilli, Binomial, Poisson, hypergeometric, normal, ... trials, with parameters choice, as developer's job is to concentrate on game aspects and not on maths problems. And eA script does not allow many maths as far as I know.

Nard