Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How random can you be? (2019)

expunctis.com

Post reply on HN
Print view View original

51–60 of 60 posts

Re: How random can you be? (2019)

#51

Post by TrinaryWorksToo »

If you want to hack it, give it a binary de Bruijn sequence with alphabet size k=2. Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game.

I used http://combos.org/bruijn and pressed left for zero and right for one.

Using rule Grandmama creates close to a perfectly straight line up and to the right when you start from the first 1 in the sequence.

Try: 1001000101010011010000110010110110001110101110011110111111000000

where 1 is right and 0 is left.

Re: How random can you be? (2019)

#53

Post by float4 »

TrinaryWorksToo wrote: post #51

If you want to hack it, give it a binary de Bruijn sequence with alphabet size k=2. Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game. I used http://combos.org/bruijn and pressed left for zero and right for one. Using rule Grandmama creates close to a perfectly straight line up and to the right when you start from the first 1 in the…

This is cool info, thanks.

> Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game.

I'm pretty sure this isn't true though. A de bruin sequence doesn't guarantee that the order of the n-patterns is random, only that the number of unique n-length patterns is maximized.

Indeed, the algorithm you mention puts n-subsequences with many 0's in the front, and subsequences with many 1's in the back. Sure, every n-length subsequence appears only once, but because the order of the subsequences does follow a predictable pattern, your total sequence is still pretty predictable.

This disparity isn't noticeable when n is small (you chose n=6), so you can comfortably beat the game. But pick a large n and your sequence becomes rather predictable.

Try n=20. In that case, the generated sequence S has length |S|=32,768=2^15. In the first half, there are 9098 0's and 7286 1's. In the second half these numbers are exactly the opposite. Throw this sequence into the game, and you end up with a prediction accuracy of 50%. Not worse than random, but you didn't beat the game either.

Re: How random can you be? (2019)

#54

Post by TrinaryWorksToo »

float4 wrote: post #53
TrinaryWorksToo wrote: post #51

If you want to hack it, give it a binary de Bruijn sequence with alphabet size k=2. Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game. I used http://combos.org/bruijn and pressed left for zero and right for one. Using rule Grandmama creates close to a perfectly straight line up and to the right when you start from the first 1 in the…

This is cool info, thanks. > Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game. I'm pretty sure this isn't true though. A de bruin sequence doesn't guarantee that the order of the n-patterns is random, only that the number of unique n-length patterns is maximized. Indeed, the algorithm you mention puts n-subsequences with many 0's i…

I picked n=6 in particular because the code checks the past 5 numbers so 6 means that it can't do its frequency analysis but also avoids the problem you mention. And yes, it isn't random, rather it enforces a unique sequence. Because the code looks for repetition one number at a time, a de bruijn sequence has to be pretty optimal since it attempts not to.

Also this sequence seems to work better: 0000001001000101010011010000110010110110001110101110011110111111

Re: How random can you be? (2019)

#56

Post by TrinaryWorksToo »

float4 wrote: post #53
TrinaryWorksToo wrote: post #51

If you want to hack it, give it a binary de Bruijn sequence with alphabet size k=2. Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game. I used http://combos.org/bruijn and pressed left for zero and right for one. Using rule Grandmama creates close to a perfectly straight line up and to the right when you start from the first 1 in the…

This is cool info, thanks. > Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game. I'm pretty sure this isn't true though. A de bruin sequence doesn't guarantee that the order of the n-patterns is random, only that the number of unique n-length patterns is maximized. Indeed, the algorithm you mention puts n-subsequences with many 0's i…

Here is the follow up blog post where the post mentions De Bruijn sequences specifically: https://www.expunctis.com/2019/04/01/Not-so-random-followup....

Re: How random can you be? (2019)

#57

Post by float4 »

TrinaryWorksToo wrote: post #54
float4 wrote: post #53

Earlier quoted context omitted.

This is cool info, thanks. > Since it looks to follow whichever pattern already exists, and de bruijn sequences minimize existing patterns, it always beats the game. I'm pretty sure this isn't true though. A de bruin sequence doesn't guarantee that the order of the n-patterns is random, only that the number of unique n-length patterns is maximized. Indeed, the algorithm you mention puts n-subsequences with many 0's i…

I picked n=6 in particular because the code checks the past 5 numbers so 6 means that it can't do its frequency analysis but also avoids the problem you mention. And yes, it isn't random, rather it enforces a unique sequence. Because the code looks for repetition one number at a time, a de bruijn sequence has to be pretty optimal since it attempts not to. Also this sequence seems to work better: 000000100100010101001…

Ah yeah. My monitor cut off the text under the graph so I didn't know they just gave away their predictive algorithm. n=6 obviously works, cool approach!
Post reply on HN