2 ms·
The explanation of how it works says it uses 5-grams to predict the next bit, so if you use any sequence in which all 6-grams occur equally often, this won't be
by schoen 10y ago
The explanation of how it works says it uses 5-grams to predict the next bit, so if you use any sequence in which all 6-grams occur equally often, this won't be able to predict you at all.
Actually, an interesting challenge might be to construct a sequence that gives the Oracle as low a score as possible (is there a nicer simpler way to describe this than simulating the Oracle's code and always choosing what it doesn't expect?).
- ikeboy 10y agoAlways choose the one that makes a new 6-gram, or that makes a 6-gram with the fewest previous appearances?
- schoen 10y agoSure, is there an easy way to generate that algorithmically without maintaining an explicit history? Is there a well-known sequence with that property? Do Gray codes have it, for example?
- ikeboy 10y agoYou'd want a sequence that contains every 6-gram exactly once and ends with the same 5 digits as it starts with: such a sequence would be 2^6=64+5=69 bits long, and then you'd repeat the first 64 over and over. (Or just contains exactly once up to cycles.) Some searching tells me this already has a name, see https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence So yes, just take a De Bruijb sequence B(2,6) (algorithms in the link can generate them) and repeat it.
- schoen 10y agoNice!
- smoyer 10y agoYep ... Grays code was my immediate thought too.
- schoen 10y agoThe Gray code turns out to work if you require the n-grams to be aligned to n-character boundaries. So if you interpreted "00001111" as containing only the two 4-grams "0000" and "1111", you're OK; but if you allow arbitrary alignments, so that "00001111" contains the 5 4-grams "0000", "0001", "0011", "0111", and "1111", the Gray code doesn't work. For example, the 4-bit Gray code (under this interpretation) when concatenated into a single bitstream begins "00000001", which then contains the 4-grams "0000", "0000", "0000", "0000", "0001", so the predictor gains an advantage right at the outset. (I didn't check whether it then loses its advantage over time... that's an interesting question.)