3 ms·

This is actually an incredibly deep and difficult question to answer. I would expect no less from cperciva. :-) As I mention in the talk, you get very bad tact

This is actually an incredibly deep and difficult question to answer. I would expect no less from cperciva. :-) As I mention in the talk, you get very bad tactical performance from taking a uniform random distribution and piping it into the emulator. The fuzzer is exponentially unlikely to hold the jump button for many successive frames without a break. In the fully general case, I think instead of maximum entropy, you want something more like Marcus Hutter's AIXI where you spend energy on inputs inversely proportional to their Kolmogorov complexity. Unfortunately, that's uncomputable, but it turns out that just switching to toggling bits with low probability does a lot better than pure randomness. The approach is analogous to swarm testing (https://users.cs.utah.edu/~regehr/papers/swarm12.pdf https://users.cs.utah.edu/~regehr/papers/swarm12.pdf). All of which is to say, the result that we show here is vastly less jumpy than our first tries. The reason it's still more jumpy than a human player is that our platform has no idea where it is in the game, or even that it's playing a game. So if a jump doesn't harm it in the exploration process, there's some chance the first input getting somewhere new will involve a jump, and that will then get locked in. We do have the capability to do optimization on inputs (what conventional PBT calls "shrinking"), and indeed if you apply this to Mario you can get it to jump a lot less and complete levels a lot faster. That capability didn't exist yet when this video was recorded. We should totally do a another post on this topic!

someplaceguy 2y ago
> Unfortunately, that's uncomputable Minor nitpick, but while Kolmogorov complexity as typically defined is uncomputable, I would argue that this result is only a theoretical curiosity and mostly irrelevant. That is, the "uncomputable" Kolmogorov complexity computation presupposes that you have a Turing machine, i.e. a machine with literally infinite memory, which is not possible to construct in our universe. Or alternatively, it presupposes that "computable function" is one that can be computed by a machine with an infinite amount of storage, which amounts to the same thing as having a Turing machine. You could probably define some version of Kolmogorov complexity that is parametrized by the memory size (e.g. of a linear bounded automaton or similar model that better represents a computer with finite resources), which should make it computable. That said, in practice it would probably take an unreasonable amount of time to perform this computation (but that is orthogonal to whether it's computable or not).
- wwilson 2y ago
  Thank you. Comments like this are why I love HN.
- anyfoo 2y ago
  While reading your comment, I kept having the vague feeling that your idea of "theoretically computable" (within the given memory bounds) will still leave some exponential time and/or space complexity, and so effectively will still be "practically not computable". Your last paragraph then seemed to confirm that, i.e. there was no particular shortcut for this specific case that would make it any different from general Kolmogorov complexity. In that sense, isn't your comment itself also "only a theoretical curiosity"? As we went to from "uncomputable", to "theoretically computable under the given constraints", to "practically uncomputable"? While suffering from lack of rigor, I think a lot of times--probably even the majority of times outside purely cs-theoretical treatments--when we colloquially speak of "uncomputable", we are always talking about practical computers without an infinite touring tape, and so actually mean "practically uncomputable". Because, yes, while everyone immediately understands that actual computers don't have infinite memory, at the same time everyone understands that "exponential time" is still "never" in practical terms.
  - someplaceguy 2y ago
    I would somewhat agree with your comment, but I think you're missing some important points: > everyone understands that "exponential time" is still "never" in practical terms. It's important to note that this is not necessarily true: 1. "exponential time" is somewhat ambiguous. An algorithm might be exponential time yet have a very low exponential base (e.g. 1.0001), so in practical terms it might be practically computable for reasonable sizes. 2. Even if the exponential base is high, it still doesn't say anything about whether an algorithm can be used practically or not. The algorithm might still be very efficient for reasonable problem sizes even though it has a high exponential base (important question: exponential in terms of what, exactly?). 3. Exponential time algorithms might only be so in the worst case but might not necessarily be exponential in the average case, or even the vast majority of interesting cases. As an example, it might be easy (or at least doable) to solve the halting problem for normal computer programs. Humans do this all the time with real-world programs when performing formal verification (as these programming languages, logics and tools force you to prove that loops and recursive functions always terminate, even when assuming a model equivalent to a Turing machine), and AFAIK there's no proof that computers can't efficiently do the same for the vast majority of real-world programs (cryptographic algorithms being the usual exception). 4. Whenever someone mentions that the halting problem and Kolmogorov complexity are uncomputable, the discussion ends there. But notice that when I pointed out that it's in fact computable, the discussion turned into one about how efficient the computation might be (which I argue, is how all such discussions should be). 5. As a side note, every single time I argued this point in the past, usually in the context of the halting problem, someone always argued that such an algorithm would necessarily have a time complexity of 2^N, where N=nr. of bits of the machine. This is not true. It would only be true for the simplest and most naive solution to the halting problem, which is inevitably what that person has in mind. In fact, there's already a family of algorithms that solve the halting problem with less complexity for almost all programs: "Floyd's tortoise and hare" and similar ones (see [1]). Note that these algorithms don't even inspect the program, they just run it step by step. This leads me to think that there are undiscovered algorithms that are far more efficient by virtue of exploiting knowledge about the program being analyzed. [1] https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection
infogulch 2y ago
What if you optimized inputs based on the strategy? E.g when you're in the air pressing down has no effect, or more measurably, the code paths between runs where you do or don't press down are very similar or completely converge. Similarly, jumping while running on a flat floor at full speed doesn't affect the game much, so prune it. Maybe call it "strategy-informed tactics"
infogulch 2y ago
To reframe the problem with purely random "Tactics", some frequencies may be an inefficient way to get to desired states of the system. That is, it is useful to consider the correlation between random inputs across time. This reminds me a lot of the problem space involving Perlin Noise. I'd hypothesize that by using a fractal noise pattern you can generate inputs with correlated values yet still remain random enough to get to any state. Have you tried using noise generators for random inputs?

someplaceguy 2y ago

> Unfortunately, that's uncomputable Minor nitpick, but while Kolmogorov complexity as typically defined is uncomputable, I would argue that this result is only a theoretical curiosity and mostly irrelevant. That is, the "uncomputable" Kolmogorov complexity computation presupposes that you have a Turing machine, i.e. a machine with literally infinite memory, which is not possible to construct in our universe. Or alternatively, it presupposes that "computable function" is one that can be computed by a machine with an infinite amount of storage, which amounts to the same thing as having a Turing machine. You could probably define some version of Kolmogorov complexity that is parametrized by the memory size (e.g. of a linear bounded automaton or similar model that better represents a computer with finite resources), which should make it computable. That said, in practice it would probably take an unreasonable amount of time to perform this computation (but that is orthogonal to whether it's computable or not).

wwilson 2y ago
Thank you. Comments like this are why I love HN.
anyfoo 2y ago
While reading your comment, I kept having the vague feeling that your idea of "theoretically computable" (within the given memory bounds) will still leave some exponential time and/or space complexity, and so effectively will still be "practically not computable". Your last paragraph then seemed to confirm that, i.e. there was no particular shortcut for this specific case that would make it any different from general Kolmogorov complexity. In that sense, isn't your comment itself also "only a theoretical curiosity"? As we went to from "uncomputable", to "theoretically computable under the given constraints", to "practically uncomputable"? While suffering from lack of rigor, I think a lot of times--probably even the majority of times outside purely cs-theoretical treatments--when we colloquially speak of "uncomputable", we are always talking about practical computers without an infinite touring tape, and so actually mean "practically uncomputable". Because, yes, while everyone immediately understands that actual computers don't have infinite memory, at the same time everyone understands that "exponential time" is still "never" in practical terms.
- someplaceguy 2y ago
  I would somewhat agree with your comment, but I think you're missing some important points: > everyone understands that "exponential time" is still "never" in practical terms. It's important to note that this is not necessarily true: 1. "exponential time" is somewhat ambiguous. An algorithm might be exponential time yet have a very low exponential base (e.g. 1.0001), so in practical terms it might be practically computable for reasonable sizes. 2. Even if the exponential base is high, it still doesn't say anything about whether an algorithm can be used practically or not. The algorithm might still be very efficient for reasonable problem sizes even though it has a high exponential base (important question: exponential in terms of what, exactly?). 3. Exponential time algorithms might only be so in the worst case but might not necessarily be exponential in the average case, or even the vast majority of interesting cases. As an example, it might be easy (or at least doable) to solve the halting problem for normal computer programs. Humans do this all the time with real-world programs when performing formal verification (as these programming languages, logics and tools force you to prove that loops and recursive functions always terminate, even when assuming a model equivalent to a Turing machine), and AFAIK there's no proof that computers can't efficiently do the same for the vast majority of real-world programs (cryptographic algorithms being the usual exception). 4. Whenever someone mentions that the halting problem and Kolmogorov complexity are uncomputable, the discussion ends there. But notice that when I pointed out that it's in fact computable, the discussion turned into one about how efficient the computation might be (which I argue, is how all such discussions should be). 5. As a side note, every single time I argued this point in the past, usually in the context of the halting problem, someone always argued that such an algorithm would necessarily have a time complexity of 2^N, where N=nr. of bits of the machine. This is not true. It would only be true for the simplest and most naive solution to the halting problem, which is inevitably what that person has in mind. In fact, there's already a family of algorithms that solve the halting problem with less complexity for almost all programs: "Floyd's tortoise and hare" and similar ones (see [1]). Note that these algorithms don't even inspect the program, they just run it step by step. This leads me to think that there are undiscovered algorithms that are far more efficient by virtue of exploiting knowledge about the program being analyzed. [1] https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection

infogulch 2y ago

What if you optimized inputs based on the strategy? E.g when you're in the air pressing down has no effect, or more measurably, the code paths between runs where you do or don't press down are very similar or completely converge. Similarly, jumping while running on a flat floor at full speed doesn't affect the game much, so prune it. Maybe call it "strategy-informed tactics"

infogulch 2y ago

To reframe the problem with purely random "Tactics", some frequencies may be an inefficient way to get to desired states of the system. That is, it is useful to consider the correlation between random inputs across time. This reminds me a lot of the problem space involving Perlin Noise. I'd hypothesize that by using a fractal noise pattern you can generate inputs with correlated values yet still remain random enough to get to any state. Have you tried using noise generators for random inputs?