I've been thinking of improving crawl's pseudo-random number generator and would like some input.
Currently we're using Mersenne's Twister (MT), a very common, mostly well behaved pseudo-random number generator. MT is fairly quick, has an absurd period (2^19937 - 1), and passes most empirical statistical tests. Disadvantages include predictability (an issue in tournaments), susceptibility to bad initial states (lots of zeros lead to bad outputs), large state space leading to slow serialization. We address predictability by hashing eight consecutive MT outputs with SHA-256, which is a bit time consuming. One better approach might be to XOR the output of a cryptographically secure block cipher operating in counter mode with the output from a statistically robust pseudo-random number generator. I'd like to see us using a more appropriate generator. There are several with comparable (or better) statistical properties. Ideally any generator we use should: * Be resistant to prediction by a player. * Pass standard empirical RNG tests (Diehard, TestU01, BigCrunch) * Have a sufficiently long period (how many times could we invoke the generator in a game?) * Have a small state to aid serialization. * Exhibit good performance. Are there other criteria that we should apply? Other considerations? I think one of David Jone's generators (adapted from some generators developed by the late George Marsaglia, described here: http://www.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf) could satisfy these goals. Cheers, Brendan ------------------------------------------------------------------------------ Create and publish websites with WebMatrix Use the most popular FREE web apps or write code yourself; WebMatrix provides all the features you need to develop and publish your website. http://p.sf.net/sfu/ms-webmatrix-sf _______________________________________________ Crawl-ref-discuss mailing list Crawl-ref-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/crawl-ref-discuss
