Hacker News Reader

Comment by andrewla | Hacker News Reader

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

View on HN

I'm virtually rich

Why use seq rather than Math.random()?

Because it's an exploit (read top comment)

Adapted to use Math.random

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

With Math.random you get ~50% win, with the sequence you get 85% because it's an exploit

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.

That would make a crazy snare rudiment

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()

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.

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".

This might be what you're talking about:

http://samy.pl/opensesame/

the guesser gets 14% right on that sequence, fwiw. And you can just keep repeating it indefinitely.

Only if you map 0=right and 1=left.

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

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()

How to find which sequence is the best?

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?

Reply on news.ycombinator.com