5 ms·
Given the implementation, an interesting way to cheat is to use de Bruijn sequences [1]. B(2,5) is 00000100011001010011101011011111, so using this sequence mea
by andrewla 8y ago
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 https://en.wikipedia.org/wiki/De_Bruijn_sequence
- empath75 8y agothe guesser gets 14% right on that sequence, fwiw. And you can just keep repeating it indefinitely.
- w-m 8y agoOnly if you map 0=right and 1=left. Mapped the other way, 0=left and 1=right, the guesser gets it right ~43%.
- sebhtml 8y agoBy 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" 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()
- dcbadacd 8y agoHow to find which sequence is the best?
- sebhtml 8y agoI 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()
- btilly 8y agoI 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.
- crdrost 8y agoGiven 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.
- Kuraj 8y agoThat would make a crazy snare rudiment
- brospars 8y agoI'm virtually rich var seq = '0000001000011000101000111001001011001101001111010101110110111111'; var index = 0; setInterval(function(){ captureKeyFunc({code : seq[index%seq.length] === '1' ? 'ArrowLeft':'ArrowRight', preventDefault: function () {}}); index++; }, 10);
- ben174 8y agoWhy use seq rather than Math.random()?
- deleted 8y ago[deleted]
- brospars 8y agoBecause it's an exploit (read top comment)
- turblety 8y agoAdapted to use Math.random setInterval(function(){ captureKeyFunc({code : Math.round(Math.random()) === 1 ? 'ArrowLeft':'ArrowRight', preventDefault: function () {}}); }, 10);
- brospars 8y agoWith Math.random you get ~50% win, with the sequence you get 85% because it's an exploit
- froindt 8y agoThank 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".
- YaxelPerez 8y agoThis might be what you're talking about: http://samy.pl/opensesame/ http://samy.pl/opensesame/
- dwild 8y agoCould 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?