Using Stockfish as a true random number generator, possible?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Using Stockfish as a true random number generator, possible?

Post by Isaac » Mon Mar 30, 2015 3:12 am

Hello people,
I would like to know whether it's possible to use Stockfish as a true random number generator when using at least 2 threads. I've heard that there is randomness involved when using more than 1 thread but at the same time I've been told that it would be impossible to produce truly random numbers based off a chess engine.

What I have done:
1)I ran the command "stockfish bench 32 2 16" 500 times. That is, let Stockfish run the bench command (analyses 37 positions) with 32 Mb of hash tables, 2 threads and up to depth 16.

2)Collected the output "Total nodes" and the "time taken".

3)Using a Python code for fun I ran a correlation test between time taken and total nodes searched. The correlation was about 0.70 with an extremely low p-value (I don't remember exactly but lesser than 10^-12.)
So that there is some linear direct correlation between the time taken to complete such a bench command and the total searched node number, with extremely high probability.

4)Using Maxima software, I checked with the Shapiro-Wilk test if the data has a Gaussian distribution and the result is that it has, with a high probability: the Kendall's W was over 0.99 while the p-value was around 0.27.
At that point I wasn't 100% sure whether true random numbers could have a Gaussian distribution but I thought that probably yes.

5)Using R programming language and its library/package "randtests", I applied the Bartels ratio test to check whether the data "total nodes searched" would pass a true random test, which was my main goal.
Null hypothesis: The data is random.
Alternative hypothesis: The data is not random.
The result is that it did pass it:

Code: Select all

statistic = -0.7462, n = 500, p-value = 0.4555
alternative hypothesis: nonrandomness
The p-value is greater than 0.01 and 0.05 so that the data that I've got is likely if the null hypothesis is true.

As a sidenote, here's a graph of trial number vs nodes searched: https://i.imgur.com/Tt2nVYN.png.


So, did I goof somewhere? Was my test lucky to pass the Bartels ratio test?
More precisely, theoretically, is it really impossible to produce true random numbers from Stockfish or a chess engine in general?
When using more than one thread I think that the total nodes searched for a fixed depth depends on the speed of the processors which depends on the temperature of the processors which has random fluctuations. So I would tend to think that indeed it's possible to produce truly random numbers out of a chess engine.
Thank you.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Using Stockfish as a true random number generator, possi

Post by kbhearn » Mon Mar 30, 2015 5:39 am

a) 1 test for randomness is not enough. random number generators are put through entire batteries of tests looking for an assortment of defects in distribution and order.

b) 500 samples isn't very many, probably not enough for most tests.

c) there is certainly some entropy in the numbers you'll get out, but you will likely need to feed the data through a hash function to get an even distribution

d) the linux kernel already is collecting entropy from events that contribute to the chess engine's randomness (interrupts and other system events) and transforming that into random numbers in what's likely a more efficient and more rigorous manner than what you're going to manage.

Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Re: Using Stockfish as a true random number generator, possi

Post by Isaac » Mon Mar 30, 2015 1:22 pm

Thanks for the reply Kevin.
kbhearn wrote:a) 1 test for randomness is not enough. random number generators are put through entire batteries of tests looking for an assortment of defects in distribution and order.
I've read about diehard tests, there's even a free program that perform these tests but it needs an executable of about 12 Mb of random numbers to work, that's way more than my 500 sample who took me like 1 hour to generate.
b) 500 samples isn't very many, probably not enough for most tests.
True, I'll try to gather more data.
c) there is certainly some entropy in the numbers you'll get out, but you will likely need to feed the data through a hash function to get an even distribution
Interesting, but why would I need an even distribution? Do you mean that this would randomize even more my numbers?
d) the linux kernel already is collecting entropy from events that contribute to the chess engine's randomness (interrupts and other system events) and transforming that into random numbers in what's likely a more efficient and more rigorous manner than what you're going to manage.
Ok good to know. Though I am not interested at all in generating efficiently true random numbers or so. My only goal was to know whether it is possible to generate true random numbers from a multi threaded chess engine like Stockfish. I still don't know the theoretical answer. :)

zullil
Posts: 5680
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Using Stockfish as a true random number generator, possi

Post by zullil » Mon Mar 30, 2015 1:36 pm

Isaac wrote:Thanks for the reply Kevin.
kbhearn wrote:a) 1 test for randomness is not enough. random number generators are put through entire batteries of tests looking for an assortment of defects in distribution and order.
I've read about diehard tests, there's even a free program that perform these tests but it needs an executable of about 12 Mb of random numbers to work, that's way more than my 500 sample who took me like 1 hour to generate.
b) 500 samples isn't very many, probably not enough for most tests.
True, I'll try to gather more data.
c) there is certainly some entropy in the numbers you'll get out, but you will likely need to feed the data through a hash function to get an even distribution
Interesting, but why would I need an even distribution? Do you mean that this would randomize even more my numbers?
d) the linux kernel already is collecting entropy from events that contribute to the chess engine's randomness (interrupts and other system events) and transforming that into random numbers in what's likely a more efficient and more rigorous manner than what you're going to manage.
Ok good to know. Though I am not interested at all in generating efficiently true random numbers or so. My only goal was to know whether it is possible to generate true random numbers from a multi threaded chess engine like Stockfish. I still don't know the theoretical answer. :)
Not sure I understand why one would want to conduct this experiment. :wink: But in any case, why don't you just use the parity of total nodes as your pseudo-random number. Then it's just 0 or 1, and you can do all sorts of tests to see how "random" your number is.

Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Re: Using Stockfish as a true random number generator, possi

Post by Isaac » Mon Mar 30, 2015 2:03 pm

zullil wrote:Not sure I understand why one would want to conduct this experiment. :wink: But in any case, why don't you just use the parity of total nodes as your pseudo-random number. Then it's just 0 or 1, and you can do all sorts of tests to see how "random" your number is.
The reason is just curiosity.
Intersting about the 0 or 1 conversion of the data... but which kinds of tests will I be able to perform exactly? If you give the me names of the tests I'll read about them and decide whether I'll go for it.
I feel somehow that I lose information if I do that conversion to binary data and that the tests to check the randomness would be less reliable but I may be wrong of course.

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Using Stockfish as a true random number generator, possi

Post by Daniel Shawul » Mon Mar 30, 2015 2:04 pm

Why not use a PRNG? Don't say you are just curious, that will not justify this absurdity.
When you only got a hummer, everything begins to look like a nail.

Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Re: Using Stockfish as a true random number generator, possi

Post by Isaac » Mon Mar 30, 2015 2:43 pm

Daniel Shawul wrote:Why not use a PRNG? Don't say you are just curious, that will not justify this absurdity.
When you only got a hummer, everything begins to look like a nail.
The reason is curiosity. If I really needed random numbers I could as you say use a pseudo random number generator or simply go to https://www.random.org/ and download tons of true random numbers generated live.
I am not interested in using random numbers.
I just want to know the answer to the question "Is it possible to create true random numbers out of a multi threaded chess engine like Stockfish?". I don't care about efficiency, etc. only if the answer is yes or no.
I don't see why wanting to know the answer is aburd by the way.

zullil
Posts: 5680
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Using Stockfish as a true random number generator, possi

Post by zullil » Mon Mar 30, 2015 4:33 pm

Isaac wrote:
zullil wrote:Not sure I understand why one would want to conduct this experiment. :wink: But in any case, why don't you just use the parity of total nodes as your pseudo-random number. Then it's just 0 or 1, and you can do all sorts of tests to see how "random" your number is.
The reason is just curiosity.
Intersting about the 0 or 1 conversion of the data... but which kinds of tests will I be able to perform exactly? If you give the me names of the tests I'll read about them and decide whether I'll go for it.
I feel somehow that I lose information if I do that conversion to binary data and that the tests to check the randomness would be less reliable but I may be wrong of course.
http://csrc.nist.gov/groups/ST/toolkit/ ... -paper.pdf

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Using Stockfish as a true random number generator, possi

Post by Daniel Shawul » Mon Mar 30, 2015 7:38 pm

You don't even need a multi-processor engine to see there is randomness in run time of programs. There are hardware RNG that use cpu heat as an input, so clearly any program that runs on a cpu is bound to show random run time. What is the point of measuring that, or knowing if it is truly random? And in particular, why Stockfish :)

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Using Stockfish as a true random number generator, possi

Post by wgarvin » Mon Mar 30, 2015 8:44 pm

"Randomness" is a property of the source of the information, not something that can be tested for by looking at the information itself. However, if you have a pile of data and you are able to compress it in some way, that is an indication of non-randomness. For large N, the vast majority of all N-bit strings will be incompressible by any compression scheme you select. And yet most of the N-bit strings that humans actually use for things, are somewhat or highly compressible (i.e. not random at all). This is consisely described in the DCE, section 1.

If you want to generate large quantities of highly random data for some reason (crypto key server, whatever) I suggest looking into the history of LavaRnd.

See also: https://xkcd.com/221/

Post Reply