Difference between revisions of "Pseudorandom Number Generator"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 73: | Line 73: | ||
* [[Mathematician#KEntacher|Karl Entacher]] ('''2000'''). ''[http://random.mat.sbg.ac.at/results/karl/server/server.html A collection of classical pseudorandom number generators with linear structures - advanced version]''. | * [[Mathematician#KEntacher|Karl Entacher]] ('''2000'''). ''[http://random.mat.sbg.ac.at/results/karl/server/server.html A collection of classical pseudorandom number generators with linear structures - advanced version]''. | ||
* [http://www.agner.org/ Agner Fog] ('''2001'''). ''Chaotic Random Number Generators with Random Cycle Lengths''. [http://www.agner.org/random/theory/chaosran.pdf pdf] | * [http://www.agner.org/ Agner Fog] ('''2001'''). ''Chaotic Random Number Generators with Random Cycle Lengths''. [http://www.agner.org/random/theory/chaosran.pdf pdf] | ||
+ | * [[Julio César Hernández-Castro]], [https://scholar.google.es/citations?user=0q4BhD8AAAAJ&hl=en Arturo Ribagorda], [https://scholar.google.com/citations?user=BHf4l7wAAAAJ&hl=en Pedro Isasi], [https://dblp.org/pid/56/6864.html José M. Sierra] ('''2001'''). ''[https://www.tandfonline.com/doi/abs/10.1080/0161-110191889897 Genetic Algorithms Can be Used to Obtain Good Linear Congruential Generators]''. [https://en.wikipedia.org/wiki/Cryptologia Cryptologia], Vol. 25, No. 3 | ||
* [[Mathematician#GMarsaglia|George Marsaglia]] ('''2002'''). ''[http://digitalcommons.wayne.edu/jmasm/vol2/iss1/2/ Random number generators]''. [https://en.wikipedia.org/wiki/Journal_of_Modern_Applied_Statistical_Methods Journal of Modern Applied Statistical Methods], Vol. 2, No. 2. | * [[Mathematician#GMarsaglia|George Marsaglia]] ('''2002'''). ''[http://digitalcommons.wayne.edu/jmasm/vol2/iss1/2/ Random number generators]''. [https://en.wikipedia.org/wiki/Journal_of_Modern_Applied_Statistical_Methods Journal of Modern Applied Statistical Methods], Vol. 2, No. 2. | ||
* [[Mathematician#GMarsaglia|George Marsaglia]] ('''2003'''). ''[https://www.jstatsoft.org/article/view/v008i14 Xorshift RNGs]''. [https://en.wikipedia.org/wiki/Journal_of_Statistical_Software Journal of Statistical Software], Vol. 8, No. 14 | * [[Mathematician#GMarsaglia|George Marsaglia]] ('''2003'''). ''[https://www.jstatsoft.org/article/view/v008i14 Xorshift RNGs]''. [https://en.wikipedia.org/wiki/Journal_of_Statistical_Software Journal of Statistical Software], Vol. 8, No. 14 | ||
* [[Mathematician#PLEcuyer|Pierre L'Ecuyer]] ('''2004'''). ''Random Number Generation''. [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf pdf] | * [[Mathematician#PLEcuyer|Pierre L'Ecuyer]] ('''2004'''). ''Random Number Generation''. [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf pdf] | ||
+ | * [[Julio César Hernández-Castro]], [https://en.wikipedia.org/wiki/Andr%C3%A9_Seznec André Seznec], [https://scholar.google.com/citations?user=BHf4l7wAAAAJ&hl=en Pedro Isasi] ('''2004'''). ''On the design of state-of-the-art pseudorandom number generators by means of genetic programming''. [https://dblp.org/db/conf/cec/cec2004.html#HernandezSI04 CEC 2004], [https://core.ac.uk/download/pdf/29399623.pdf pdf] | ||
* [[Donald Eastlake]], [[Stephen D. Crocker]], [https://jis.qyv.name/ Jeffrey I. Schiller] ('''2005'''). ''Randomness Requirements for Security''. [https://tools.ietf.org/html/rfc4086 RFC 4086] | * [[Donald Eastlake]], [[Stephen D. Crocker]], [https://jis.qyv.name/ Jeffrey I. Schiller] ('''2005'''). ''Randomness Requirements for Security''. [https://tools.ietf.org/html/rfc4086 RFC 4086] | ||
* [[Mathematician#WHPress|William H. Press]], [[Mathematician#SATeukolsky|Saul A. Teukolsky]], [https://de.wikipedia.org/wiki/William_T._Vetterling William T. Vetterling], [https://en.wikipedia.org/wiki/Brian_P._Flannery Brian P. Flannery] ('''2007'''). ''[https://en.wikipedia.org/wiki/Numerical_Recipes Numerical Recipes. The Art of Scientific Computing], 3rd edition''. (C++ code) | * [[Mathematician#WHPress|William H. Press]], [[Mathematician#SATeukolsky|Saul A. Teukolsky]], [https://de.wikipedia.org/wiki/William_T._Vetterling William T. Vetterling], [https://en.wikipedia.org/wiki/Brian_P._Flannery Brian P. Flannery] ('''2007'''). ''[https://en.wikipedia.org/wiki/Numerical_Recipes Numerical Recipes. The Art of Scientific Computing], 3rd edition''. (C++ code) | ||
Line 128: | Line 130: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=49807 rkiss and other dependencies in syzygy] by [[Don Dailey]], [[CCC]], October 23, 2013 | * [http://www.talkchess.com/forum/viewtopic.php?t=49807 rkiss and other dependencies in syzygy] by [[Don Dailey]], [[CCC]], October 23, 2013 | ||
==2015 ...== | ==2015 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=56225 A simple PRNG using /dev/urandom] by [[Steven Edwards]], [[CCC]], May 04, 2015 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=56328 Revised source for the random game generator] by [[Steven Edwards]], [[CCC]], May 12, 2015 | * [http://www.talkchess.com/forum/viewtopic.php?t=56328 Revised source for the random game generator] by [[Steven Edwards]], [[CCC]], May 12, 2015 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=56364 Random playout vs evaluation] by [[Robert Pope]], [[CCC]], May 15, 2015 | * [http://www.talkchess.com/forum/viewtopic.php?t=56364 Random playout vs evaluation] by [[Robert Pope]], [[CCC]], May 15, 2015 | ||
Line 134: | Line 137: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=63803 random evaluation perturbation factor] by [[Stuart Cracraft]], [[CCC]], April 24, 2017 | * [http://www.talkchess.com/forum/viewtopic.php?t=63803 random evaluation perturbation factor] by [[Stuart Cracraft]], [[CCC]], April 24, 2017 | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70050 xiphos 64 bit random number] by [[Pedro Castro]], [[CCC]], February 28, 2019 » [[Xiphos]] | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70050 xiphos 64 bit random number] by [[Pedro Castro]], [[CCC]], February 28, 2019 » [[Xiphos]] | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74028 Rolling dice] by [[Harm Geert Muller]], [[CCC]], May 27, 2020 » [[Chess Engine Communication Protocol|CECP]], [[EinStein würfelt nicht!]] | ||
=External Links= | =External Links= | ||
Line 217: | Line 222: | ||
==Misc== | ==Misc== | ||
* [[:Category:Van der Graaf Generator|Van der Graaf Generator]] - Theme One (1972), [https://en.wikipedia.org/wiki/YouTube YouTube] Video | * [[:Category:Van der Graaf Generator|Van der Graaf Generator]] - Theme One (1972), [https://en.wikipedia.org/wiki/YouTube YouTube] Video | ||
− | : {{#evu:https://www.youtube.com/watch?v= | + | : {{#evu:https://www.youtube.com/watch?v=WWcJ7WeAK78|alignment=left|valignment=top}} |
=References= | =References= |
Latest revision as of 18:52, 30 June 2021
Home * Programming * Algorithms * Pseudorandom Number Generator
Pseudorandom Number Generator (PRNG),
an algorithmic gambling device for generating pseudorandom numbers, a deterministic sequence of numbers which appear to be random with the property of reproducibility. They are useful in simulation, sampling, computer programming, decision making, cryptography, aesthetics and recreation [2] - in computer chess, beside randomization of game playing, primarily used to generate keys for Zobrist hashing.
Games of chance, such as Backgammon and EinStein würfelt nicht! require PRNGs for rolling a dice. Chess and game playing programs use PRNGs to randomly choose one of several possible moves of a position from an opening book, or use random fluctuations in learning and automated tuning tasks. Game playing programs performing a Monte-Carlo Tree Search, use random playouts in their simulation phase. Don Beal and Martin C. Smith demonstrated that deeper search with random leaf values in chess yields to better play, with some interesting insights in minimax search and implications for designing and testing evaluation terms [3].
Contents
Methods
PRNGs maintain a state variable, a bitwise superset of the random number, initialized by a random seed - a constant for the same sequence each time, i.e. for Zobrist keys, otherwise, something like system time to produce varying pseudo randoms. Each call of the PRNG routine performs certain operations or bit-twiddling on that state, leaving the next pseudo random number. For various applications more or less important features are randomness, resolution, (uniform) distribution, and periodicity - topic of various randomness tests - and further performance, and portability.
Zobrist hashing with about 12*64 keys has less issues with randomness and period, but with distribution, and requires linear independence so that a small subset of all keys doesn't xor to zero. Despite selected hard-coded random constants used at compile time, many programs use an own PRNG based on recurrence relation in GF(2) such as Mersenne Twister or Xorshift.
LCG
A common method used in many library functions, such as C/C++ rand() is the linear congruential generator (LCG) based on multiply, add, modulo with integers, where some past implementations had serious shortcomings in the randomness, distribution and period of the sequence [4]. Due to such issues in rand() implementations, where lower bits are less random than higher bits, it is recommended not to use modulo X to reduce the integer range from RAND_MAX to X, but division by (RAND_MAX div X) [5] - or to use C++11's random number generation facilities to replace rand [6].
RKISS
Stockfish (since 2.0) uses an implementation by Heinz van Saanen based on Bob Jenkins' RKISS, a member of George Marsaglia's Xorshift familly.
RANROT B3
Amy by Thorsten Greiner [7] uses an implementation of Agner Fog's RANROT B3 [8], also recommended by Stefan Meyer-Kahlen as used in Shredder [9].
MT
Arasan 20.x switched to C++11 random number support using Mersenne Twister std::mt19937_64 [10] [11].
ChaCha
The Rust engine Asymptote uses the ChaCha stream cipher developed by Daniel J. Bernstein, built on a pseudorandom function based on add-rotate-xor (ARX) operations [12].
Applications
- Looking for Magics
- Genetic Programming
- Monte-Carlo Tree Search
- Opening Book
- Search with Random Leaf Values
- Simulated Annealing
- SPSA
- Zobrist Hashing
See also
Selected Publications
1950 ...
- Derrick H. Lehmer (1951). Mathematical methods in large-scale computing units. Proceedings of a 2nd Symposium on Large Scale Digital Computing Machinery, 1949, Harvard University Press, pp. 141–146
- RAND Corporation (1955). A Million Random Digits with 100,000 Normal Deviates. pdf, online
1960 ...
- John von Neumann (1963). Various techniques used in connection with random digits. von Neumann's Collected Works, Vol. 5, Pergamon Press, pdf
- M. Donald MacLaren, George Marsaglia (1965). Uniform Random Number Generators. Journal of the ACM, Vol. 12, No. 1
- Donald Knuth (1969). The Art of Computer Programming (TAOCP) - Volume 2 - Seminumerical Algorithms. Chapter 3 – Random numbers, 1st edition
1970 ...
- Joachim H. Ahrens, Ulrich Dieter, Andreas Grube (1970). Pseudo-random numbers. Computing, Vol. 6, No. 1
- George Marsaglia (1972). The Structure of Linear Congruential Sequences. in S. K. Zaremba (ed.) Applications of Number Theory to Numerical Analysis. Academic Press
- Ulrich Dieter, Joachim H. Ahrens (1973). A combinatorial method for the generation of normally distributed random numbers. Computing, Vol. 11, No. 2
1980 ...
- Scott Kirkpatrick, Erich P. Stoll (1981). A Very Fast Shift-Register Sequence Random Number Generator. Journal of Computational Physics, Vol. 40, No. 2
- George Marsaglia (1985). A Current View of Random Number Generators. Proceedings, Computer Science and Statistics: 16th Symposium on the Interface, Elsevier
- Pierre L'Ecuyer (1988). Efficient and Portable combined random number generators. Communications of the ACM, Vol. 31, No. 6
1990 ...
- Pierre L'Ecuyer (1990). Random numbers for simulation. Communications of the ACM, Vol. 33, No. 10
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery (1992). Numerical Recipes in C: The Art of Scientific Computing, 2nd edition. Chapter 7. Random Numbers
- F. Warren Burton, Rex L. Page (1992). Distributed Random Number Generation. Journal of Functional Programming, Vol. 2, No. 2, pdf
- Donald Eastlake, Stephen D. Crocker, Jeffrey I. Schiller (1994). Randomness Recommendations for Security. RFC 1750
- Donald Knuth (1997). The Art of Computer Programming (TAOCP) - Volume 2 - Seminumerical Algorithms. Chapter 3 – Random numbers, 3rd edition
- Andrew Shapira (1997). Cycle parity random number generators, and a general random number library. Ph.D. thesis, Rensselaer Polytechnic Institute, advisor Mukkai S. Krishnamoorthy.
- Makoto Matsumoto, Takuji Nishimura (1998). Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, pdf preprint
- Anna Górecka, Maciej Szmit (1998). Programowe generatory liczb pseudolosowych. Znacie - to posłuchajcie. Software 11/1998 (Polish)
2000 ...
- Karl Entacher (2000). A collection of classical pseudorandom number generators with linear structures - advanced version.
- Agner Fog (2001). Chaotic Random Number Generators with Random Cycle Lengths. pdf
- Julio César Hernández-Castro, Arturo Ribagorda, Pedro Isasi, José M. Sierra (2001). Genetic Algorithms Can be Used to Obtain Good Linear Congruential Generators. Cryptologia, Vol. 25, No. 3
- George Marsaglia (2002). Random number generators. Journal of Modern Applied Statistical Methods, Vol. 2, No. 2.
- George Marsaglia (2003). Xorshift RNGs. Journal of Statistical Software, Vol. 8, No. 14
- Pierre L'Ecuyer (2004). Random Number Generation. pdf
- Julio César Hernández-Castro, André Seznec, Pedro Isasi (2004). On the design of state-of-the-art pseudorandom number generators by means of genetic programming. CEC 2004, pdf
- Donald Eastlake, Stephen D. Crocker, Jeffrey I. Schiller (2005). Randomness Requirements for Security. RFC 4086
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery (2007). Numerical Recipes. The Art of Scientific Computing, 3rd edition. (C++ code)
- Daniel J. Bernstein (2007). The Salsa20 family of stream ciphers. University of Illinois at Chicago, pdf [13]
- Daniel J. Bernstein (2008). ChaCha, a variant of Salsa20. University of Illinois at Chicago, pdf
2010 ...
- Maciej Szmit, Anna Szmit (2011). DNS Pseudo-Random Number Generators Weakness. CN 2011, Springer
- Jeff Rollason (2015). When Completely Random is Just not Random Enough. AI Factory, February 2015
Forum Posts
1982 ...
- compact representation of chess positions by Tom Truscott, net.chess, January 7, 1982
1990 ...
- Re: Weakest Chess Program needed by Kenneth S A Oksanen, rgc, November 12, 1991
- Hash tables - Clash!!! What happens next? by Valavan Manohararajah, rgc, March 15, 1994
- Re: Hash tables - Clash!!! What happens next? by Jonathan Schaeffer, March 17, 1994
- Re: Human VS computer by Don Beal, rgc, July 11, 1994
1995 ...
- Primitive Chess Program by David Ewart, rgc, June 09, 1995
- random play by Robert Hyatt, rgcc, November 25, 1996
- Randomness in move selection by Robert Hyatt, rgcc, December 01, 1996
- Re: Interesting random chess question - What is probability to win? by Jari Huikari, CCC, October 03, 1998 » Nero
- Random chess statistics, part two by Jari Huikari, CCC, October 14, 1998
- How to create a set of random integers for hashing? by Ed Schröder, CCC, October 18, 1998
- Random numbers for C: End, at last? by George Marsaglia, sci.math.num-analysis, January 21, 1999
2000 ...
- random book moves/ random generator by Vincent Diepeveen, CCC, January 13, 2000
- Re: random book moves/ random generator by Thorsten Greiner, CCC, January 13, 2000
- Simple Learning Technique and Random Play by Miguel A. Ballicora, CCC, January 18, 2001 » Persistent Hash Table
- Why Random Number Needed In HashFunction[piece[position]] by Cheok Yan Cheng, rgcc, June 12, 2001
- Random factor in static evaluation! by Tiago Ribeiro, CCC, June 15, 2001
- Simulating the result of a single game by random numbers by Christoph Fieberg, CCC, July 03, 2001
- Simulating the result of a single game by random numbers - Update! by Christoph Fieberg, CCC, July 10, 2001
- Simulating the result of a single game by random numbers - Update! by Christoph Fieberg, CCC, August 02, 2001
- About random numbers and hashing by Severi Salminen, CCC, December 04, 2001
- Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001
- Random keys and hamming distance by James Swafford, CCC, August 16, 2002
- Random play by Russell Reagan, CCC, April 08, 2003
- 64-Bit random numbers by Martin Schreiber, CCC, October 28, 2003
- A question about random numbers by Antonio Senatore, CCC, July 22, 2004
2005 ...
- randomness of random number generators? somewhat OT by David Dahlem, CCC, October 01, 2005
- Random number mobility scores by Guest, rgcc, September 20, 2008
- Zobrist key random numbers by Robert Hyatt, CCC, January 21, 2009
- 64-bit KISS RNGs by George Marsaglia, comp.lang.fortran, February 28, 2009
2010 ...
- Transposition table random numbers by Justin Madru, CCC, July 13, 2010
- RKISS by Gerd Isenberg, CCC, January 01, 2011
- RKISS copyright? by Giorgio Medeot, CCC, March 07, 2011
- Stockfish random generator (rkiss.h) by Martin Sedlak, CCC, April 15, 2011 » Stockfish, Bob Jenkins
- MT or KISS ? by Dan Honeycutt, CCC, June 02, 2012 [14]
- rkiss and other dependencies in syzygy by Don Dailey, CCC, October 23, 2013
2015 ...
- A simple PRNG using /dev/urandom by Steven Edwards, CCC, May 04, 2015
- Revised source for the random game generator by Steven Edwards, CCC, May 12, 2015
- Random playout vs evaluation by Robert Pope, CCC, May 15, 2015
- "random mover" chess programs by Norbert Raimund Leisner, CCC, June 24, 2016
- Adding a random small number to the evaluation function by Uri Blass, CCC, September 03, 2016
- random evaluation perturbation factor by Stuart Cracraft, CCC, April 24, 2017
- xiphos 64 bit random number by Pedro Castro, CCC, February 28, 2019 » Xiphos
2020 ...
- Rolling dice by Harm Geert Muller, CCC, May 27, 2020 » CECP, EinStein würfelt nicht!
External Links
- Pseudorandom number generator from Wikipedia
- Pseudo-random number sampling from Wikipedia
- Pseudorandomness from Wikipedia
- Statistical randomness from Wikipedia
- Pseudo-random number sampling from Wikipedia
- Random seed from Wikipedia
- Cryptographically secure pseudorandom number generator from Wikipedia
Randomness
- Randomness from Wikipedia
- History of randomness from Wikipedia
- Random number generation from Wikipedia
- Hardware random number generator
- RANDOM.ORG - True Random Number Service
- RANDOM.ORG - Integer Generator
Methods
- Generating Uniform Random Numbers on [0,1 ] by Chris Lomont, March 2017
- Linear congruential generator from Wikipedia
- Lehmer random number generator from Wikipedia
- Park-Miller-Carta Pseudo-Random Number Generators
- RANDU from Wikipedia
- Linear-feedback shift register from Wikipedia
- Xorshift from Wikipedia
- A small noncryptographic pseudorandom number generator by Bob Jenkins
- ISAAC, a fast cryptographic random number generator by Bob Jenkins
- Pseudo random number generators by Agner Fog
- Random Number Generators - the pLab project by Peter Hellekalek
- Random Number Generation by Ernst Stadlober
- Random Number Generators
- Salsa20 from Wikipedia
Language Support
Basic
- BASIC Programming/Random Number Generation - Wikibooks
- Rnd Function (Visual Basic)
- The Beginner's Page: The Random Function » Atari 8-bit
- RND - C64-Wiki » Commodore 64
C
- rand - MSDN
- rand(3) - Linux manual page
- GNU Scientific Library – Reference Manual: Random Number Generation
C++
- std::rand - cppreference.com
- Boost Random - Reference - 1.64.0
- Pseudo-random number generation - cppreference.com
- mt19937_64 - C++ Reference
- Random number generation using C++ Technical Report 1 by John D. Cook (2008)
C#
- Random Class (System) - MSDN
- C# in Depth: Random numbers
- Simple Random Number Generation - CodeProject by John D. Cook (2008 - 2011)
D
Fortran
Go
Java
Lisp
Pascal
- Free Pascal - Random
- Generating Random Numbers - Free Pascal wiki
- Delphi compatible LCG Random - Free Pascal wiki
- Marsaglia's pseudo random number generators - Free Pascal wiki
Python
- 9.6. random — Generate pseudo-random numbers — Python 2.7.13 documentation
- 9.6. random — Generate pseudo-random numbers — Python 3.6.1 documentation
Tests
- Randomness tests from Wikipedia
- Diehard tests from Wikipedia
- Spectral test from Wikipedia
- TestU01 from Wikipedia
Misc
- Van der Graaf Generator - Theme One (1972), YouTube Video
References
- ↑ Dice players - Roman fresco from the Osteria della Via di Mercurio (VI 10,1.19, room b) in Pompeii, Source: Filippo Coarelli (ed.) (2002). Pompeji. Hirmer Verlag, Munich, ISBN: 3-7774-9530-1, p. 146, Wikimedia Commons, History of randomness from Wikipedia
- ↑ Donald Knuth (1997). The Art of Computer Programming (TAOCP) - Volume 2 - Seminumerical Algorithms. Chapter 3 – Random numbers
- ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. Advances in Computer Chess 7
- ↑ "In the past, some implementations of rand() have had serious shortcomings in the randomness, distribution and period of the sequence produced (in one well-known example, the low-order bit simply alternated between 1 and 0 between calls) rand() is not recommended for serious random-number generation needs, like cryptography. It is recommended to use C++11's random number generation facilities to replace rand()." rand - cppreference.com
- ↑ Re: random book moves/ random generator by Thorsten Greiner, CCC, January 13, 2000
- ↑ Pseudo-random number generation - cppreference.com
- ↑ amy-0.8.7.tar.gz /src/random.c
- ↑ Agner Fog (2001). Chaotic Random Number Generators with Random Cycle Lengths. pdf
- ↑ Re: random book moves/ random generator by Stefan Meyer-Kahlen, CCC, January 13, 2000
- ↑ arasan-chess/movegen.h at master · jdart1/arasan-chess · GitHub
- ↑ mt19937_64 - C++ Reference
- ↑ rand::chacha::ChaChaRng - Rust
- ↑ Salsa20 from Wikipedia
- ↑ Mersenne twister from Wikipedia