News for hackers. Stuff that matters.
Re:How random can you be? by andrewla on Friday March 08, 2019 @09:33AM (#19337748)
Given the implementation, an interesting way to cheat is to use de Bruijn sequences [1]. B(2,5) is 00000100011001010011101011011111, so using this sequence means that you will cycle through all possible 5-grams, and thus make lots of money.

Ah, should have read more carefully -- it's using 5-grams as the base, not as the model, so really it's 6-grams, so we need B(2,6). We can try 0000001000011000101000111001001011001101001111010101110110111111

[1] https://en.wikipedia.org/wiki/De_Bruijn_sequence

Re:How random can you be? by brospars on Friday March 08, 2019 @11:16AM (#19338873)
I'm virtually rich

var seq = '0000001000011000101000111001001011001101001111010101110110111111'; var index = 0; setInterval(function(){ captureKeyFunc({code : seq[index%seq.length] === '1' ? 'ArrowLeft':'ArrowRight', preventDefault: function () {}}); index++; }, 10);

Re:How random can you be? by turblety on Friday March 08, 2019 @07:11PM (#19343499)
Adapted to use Math.random

setInterval(function(){ captureKeyFunc({code : Math.round(Math.random()) === 1 ? 'ArrowLeft':'ArrowRight', preventDefault: function () {}}); }, 10);

Re:How random can you be? by brospars on Wednesday March 13, 2019 @06:02AM (#19377225)
With Math.random you get ~50% win, with the sequence you get 85% because it's an exploit
Re:How random can you be? by ben174 on Friday March 08, 2019 @04:23PM (#19342321)
Why use seq rather than Math.random()?
Re:How random can you be? by brospars on Wednesday March 13, 2019 @06:03AM (#19377232)
Because it's an exploit (read top comment)
Re:How random can you be? by crdrost on Friday March 08, 2019 @11:14AM (#19338837)
Given the implementation, an interesting way to cheat is to use the following "never loses" sequence:

    RRRRRRLRRRLRLRLLRRRRLLRRLRRLRLLLRRRLLLRLRRLLRLRL
    RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLRLLLRRRLLLRLRRLLRLRL
    RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLLRLLLRRRLLLRLRRLLRLRL
    RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLLRLLLRRRLLLRLRRLLRLRL
    RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLLRLLLRRRLLLRLRRLLRLRL
    ...
You could easily avoid the repetition by saying that on ties you just choose a prediction at random (and likewise for the first 4).

What's at stake here is the same thing that threatens to eventually cause another civil war in the US, but that is a question for another time. :) It is a broad class of theorems which state that if you have a function f: X -> X and you repeat it over and over it naturally finds an input x such that f(x) = x. This repetition has naturally found a set of moves which resets the Markov matrix back to what it was. If you randomized the prediction on ties then I am not sure what I would do exactly... I would have to steer the Markov matrix into a cycle but assuming that it stores the absolute counts for every single prediction, any oscillations I'm using would want to naturally decay to zero... I might be able to exploit it if you were to only look at, say, my last 1000 moves' history to make your predictions, and maybe I can still induce an oscillation that does better than random chance, but I am not sure that I can.

Re:How random can you be? by Kuraj on Friday March 08, 2019 @01:16PM (#19340346)
That would make a crazy snare rudiment
Re:How random can you be? by sebhtml on Friday March 08, 2019 @10:56AM (#19338644)
I modified the "randomize!" button to inject the de Bruijn sequence DB(2,6), and I get a rate of 50%.

Is there an error in my patch ?

  diff --git a/not-so-random.html b/not-so-random.html
  index 48c04da..c650b5b 100644
  --- a/not-so-random.html
  +++ b/not-so-random.html
  @@ -169,8 +169,12 @@
         randomHelpFunc = function(evt) {
            evt.preventDefault();
            //document.onkeydown = null;
  -         for (let i = 0; i<10; i++) {
  -            lastKey = Math.round(Math.random());
  +
  +         // db(2, 6)
  +         var inputString = "0000001000011000101000111001001011001101001111010101110110111111";
  +
  +         for (let i = 0; i< inputString.length; i++) {
  +            lastKey = inputString[i] == "0" ? 0 : 1;
               testPrediction();
               updateAll();
               predictNext()
Re:How random can you be? by btilly on Friday March 08, 2019 @01:50PM (#19340780)
I didn't review the patch, but that is the expected result. That sequence will cause it to think that whatever previous 5 pattern it saw, your next is equally likely to be 1 or 0. So it will guess randomly, and half the time it is right.

However with $1 vs $1.05 returns, you'll steadily make money.

Re:How random can you be? by froindt on Friday March 08, 2019 @11:56AM (#19339335)
Thank you for posting this! I've been trying to figure out what it was called for years!

There was an attack I read about for garage door openers or numeric entry doors where they didn't have an enter button. So entering they entered the De Bruijn sequence and had the answer in a small fraction of the time compared to trying each combo once and hitting "Enter".

Re:How random can you be? by YaxelPerez on Friday March 08, 2019 @12:11PM (#19339515)
This might be what you're talking about:

http://samy.pl/opensesame/

Re:How random can you be? by empath75 on Friday March 08, 2019 @10:00AM (#19338017)
the guesser gets 14% right on that sequence, fwiw. And you can just keep repeating it indefinitely.
Re:How random can you be? by sebhtml on Friday March 08, 2019 @11:05AM (#19338728)
By using "1" for left (lastKey = 0) and "0" for right (lastKey = 1), I get 12%.

A de Bruijn sequence DB(2, k) is spelled by an Eulerian path in the corresponding de Bruijn graph, whose vertices are {0, 1}^k and where any arc (x, y) has the following property: x[2..k] == y[1..k-1].

Obviously, there are as many Eulerian paths as there are de Bruijn sequences.

Each such de Bruijn sequence has a different capability at getting a good score at the game "https://www.expunctis.com/2019/03/07/Not-so-random.html".

  diff --git a/not-so-random.html b/not-so-random.html
  index 48c04da..168a287 100644
  --- a/not-so-random.html
  +++ b/not-so-random.html
  @@ -169,8 +169,12 @@
         randomHelpFunc = function(evt) {
            evt.preventDefault();
            //document.onkeydown = null;
  -         for (let i = 0; i<10; i++) {
  -            lastKey = Math.round(Math.random());
  +
  +         // db(2, 6)
  +         var inputString = "0000001000011000101000111001001011001101001111010101110110111111";
  +
  +         for (let i = 0; i< inputString.length; i++) {
  +            lastKey = inputString[i] == "0" ? 1 : 0;
               testPrediction();
               updateAll();
               predictNext()
Re:How random can you be? by dcbadacd on Friday March 08, 2019 @01:46PM (#19340715)
How to find which sequence is the best?
Re:How random can you be? by w-m on Friday March 08, 2019 @10:20AM (#19338244)
Only if you map 0=right and 1=left.

Mapped the other way, 0=left and 1=right, the guesser gets it right ~43%.

Re:How random can you be? by dwild on Friday March 08, 2019 @01:11PM (#19340302)
Could the algorithm "detect" this and change the grams then? And then you will fight at an higher level where it will be whether you increase it or not?