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

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

Post by Isaac » Tue Mar 31, 2015 12:38 am

Thanks guys again.
To Daniel, the full story that lead me to that question is that I had read that Stockfish bench ceased to be deterministic when using more than 1 thread and that some randomness is introduced. I was wondering whether this randomness in the total nodes searched was truly random or not. I thought that this number would depend on the threads/cores speed which in turn depends on the temperature that isn't deterministic and other random parameters probably. So I came to IRC asking the question in the #programming channel and the guys there told me that I could never generate truly random numbers out of a chess engine. But they didn't give me any explanation, at least that I could understand.
That's why I decided to gather some data and test stuff to see if I could answer the question. I still can't. But at least the true randomness is not discarded.

By the way I've just collected 1500 more numbers, it took over 8 hours to generate. I've ran the Bartels rank test again with null hypothesis : true randomness and alternative hypothesis : non randomness, trend and oscillation. The p-value was well over 0.05 in all cases so that I didn't discard the null hypothesis.

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

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

Post by Isaac » Tue Mar 31, 2015 2:27 am

I've read that good pseudo random number generators can pass all kind of tests and that to answer my question I would have to answer it from first principles. As as I understand it, it means that someone who has the knowledge on how Stockfish SMP (or other chess engines SMP part) code works could answer to my question. I am not qualified enough (not a programmer).

So if Bob Hyatt, Ronald de Man, Lucas Braesch, Marco Costalba, etc. know the answer, I'd appreciate a yes/no answer.

Thanks!

zullil
Posts: 5668
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 » Tue Mar 31, 2015 10:22 am

Isaac wrote: I had read that Stockfish bench ceased to be deterministic when using more than 1 thread and that some randomness is introduced. I was wondering whether this randomness in the total nodes searched was truly random or not.
What do you mean when you say "truly random"? The number of nodes searched using

bench 32 2 20 default depth

is a random variable. I assume it's normally distributed, and you could estimate the mean and variance.

What exactly do you mean when you say "true random number generator"? I'm not sure you understand what you are asking in this thread.

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

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

Post by Isaac » Tue Mar 31, 2015 12:57 pm

zullil wrote:What do you mean when you say "truly random"? The number of nodes searched using

bench 32 2 20 default depth

is a random variable. I assume it's normally distributed, and you could estimate the mean and variance.

What exactly do you mean when you say "true random number generator"? I'm not sure you understand what you are asking in this thread.
It is not normally distributed although it pretty much looks like it is. It isn't because there's a lower bound (0) and I think that this removes the possibility of the data to follow a normal distribution. Though as I wrote in the first post of this thread, I've performed the Shapiro-Wilk test that told me how close to normally distributed the data is. Turns out it was pretty close to it. I had calculated the mean and variance (standard deviation in fact). A funny fact is that the mean is very different from the signature (i.e. nodes searched) when I ran the command "stockfish bench 32 1 16".
By true random number generator I mean whether Stockfish total nodes searched depend on an unpredictable physical process such as temperature of the threads or something like that.

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 » Tue Mar 31, 2015 6:45 pm

Isaac wrote:
zullil wrote:What do you mean when you say "truly random"? The number of nodes searched using

bench 32 2 20 default depth

is a random variable. I assume it's normally distributed, and you could estimate the mean and variance.

What exactly do you mean when you say "true random number generator"? I'm not sure you understand what you are asking in this thread.
It is not normally distributed although it pretty much looks like it is. It isn't because there's a lower bound (0) and I think that this removes the possibility of the data to follow a normal distribution. Though as I wrote in the first post of this thread, I've performed the Shapiro-Wilk test that told me how close to normally distributed the data is. Turns out it was pretty close to it. I had calculated the mean and variance (standard deviation in fact). A funny fact is that the mean is very different from the signature (i.e. nodes searched) when I ran the command "stockfish bench 32 1 16".
By true random number generator I mean whether Stockfish total nodes searched depend on an unpredictable physical process such as temperature of the threads or something like that.
When using multiple threads, it depends on things like OS thread scheduling, the hardware timer used to decide when an OS thread quanta expires, and occasionally the order that different threads try to access the same TT entry and whether they see it in a shared (e.g. L3) cache or in RAM. And maybe also things like hyperthreading, CPU frequency being stepped up and down by power management, etc. So there is very likely some entropy there in the sense that it depends on factors external to the chess engine process, that are unpredictable and for practical purposes could be treated as "random". The amount of entropy it adds may vary a lot depending on your configuration, though. For some machines, it might be rather small, but I guess it would not usually be zero.

But I guess an important q. is, what are you treating as the "output" that you would try to collect this entropy from? If you were to make a cryptographic hash of the entire transposition table after a multi-threaded search, e.g. an SHA1 hash, your chance of getting the same SHA1 hash value from two searches with the same input parameters, should be small. But there might be some searches where it isn't. But hashing a 100MB table down to 16 bytes would probably be OK as source of entropy, as long as multiple threads were used in the search. There are surely easier ways to collect entropy, but I guess you could do that.

But if you were instead to only look at the move chosen by the engine after the search, or at the outcome of the game, then most of the entropy would be lost and you would get very predictable, non-random results.

Some other reading that might be interesting:

A blog post about random number generation in linux
Wikipedia article about hardware RNGs
http://stackoverflow.com/questions/1998 ... -pool-work
2003 Wired article about Lavarand

zullil
Posts: 5668
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 » Tue Mar 31, 2015 7:31 pm

Isaac wrote:
zullil wrote:What do you mean when you say "truly random"? The number of nodes searched using

bench 32 2 20 default depth

is a random variable. I assume it's normally distributed, and you could estimate the mean and variance.

What exactly do you mean when you say "true random number generator"? I'm not sure you understand what you are asking in this thread.
It is not normally distributed although it pretty much looks like it is. It isn't because there's a lower bound (0) and I think that this removes the possibility of the data to follow a normal distribution.
I should have said "modeled using a normal distribution".

Michael Sherwin
Posts: 3041
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

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

Post by Michael Sherwin » Fri Apr 03, 2015 8:12 am

I know that I am nowhere close to being in the loop on this one, but ...
Can a geiger counter be connected to a computer and a program be written for it's input that would produce real random numbers?
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Post Reply