4 ms·

This is Will (I gave the talk linked in the post). Happy to answer any questions about this work, or how it generalizes to testing things that aren't Nintendo g

This is Will (I gave the talk linked in the post). Happy to answer any questions about this work, or how it generalizes to testing things that aren't Nintendo games.

thsksbd 2y ago
How does this distinguish between a bug and a "feature"? Edit: i mean this is the spirit of Knuth's quip that when he dies all the bugs in tex will become features
- wwilson 2y ago
  There was a LOT of discussion of this in the Q&A after the talk. Currently we have 4 main approaches: (1) There's some stuff that's pretty much a bug for every program. If it segfaults, exits with a nonzero code, OOMs, triggers a TSAN error, fills the disk with fatal error messages, etc., etc., that's pretty easy to qualify. (2) You can use our SDK to define additional custom test properties. Think like a normal assertions library, but you can also do existential quantification ("this code is reachable/this situation can happen") and soon temporal assertions ("this should never happen without this other thing happening first, possibly on a different node"). (3) We store all the output of your system in every timeline in a giant analytic database and support ad-hoc querying against it. Think "pre-observability", observability but for mirror universes. You can then do all the spelunking and analysis you would do with your production traces, but before your real customers are exposed to any issue. (4) We have some very cool ML approaches in the pipeline that I can't talk about quite yet.
  - ajb 2y ago
    Can you define equivalence classes (mutations that shouldn't change the result) eg timing, order of events, idempotence, etc? So that you can use (3) to define the correct result for all members of the class (Sorry if this is explained in the talk - I'll watch it but it's now too late in the day in my timezone)
cperciva 2y ago
Why is Mario so jumpy?
- wwilson 2y ago
  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).
mustknow2201 2y ago
How close is or isn't this to a genetic algorithm in practice? It seems like as soon as you start scaling out to multiple threads/nodes you'd benefit from crossover, selection techniques and so on?
iamcreasy 2y ago
Very cool presentation. Thanks for doing this. Choosing next input based on present sounds a lot like a Markov chain - is that something you guys use when simulating user interaction with distributed system?

This is Will (I gave the talk linked in the post). Happy to answer any questions about this work, or how it generalizes to testing things that aren't Nintendo games.

thsksbd 2y ago

How does this distinguish between a bug and a "feature"? Edit: i mean this is the spirit of Knuth's quip that when he dies all the bugs in tex will become features

wwilson 2y ago
There was a LOT of discussion of this in the Q&A after the talk. Currently we have 4 main approaches: (1) There's some stuff that's pretty much a bug for every program. If it segfaults, exits with a nonzero code, OOMs, triggers a TSAN error, fills the disk with fatal error messages, etc., etc., that's pretty easy to qualify. (2) You can use our SDK to define additional custom test properties. Think like a normal assertions library, but you can also do existential quantification ("this code is reachable/this situation can happen") and soon temporal assertions ("this should never happen without this other thing happening first, possibly on a different node"). (3) We store all the output of your system in every timeline in a giant analytic database and support ad-hoc querying against it. Think "pre-observability", observability but for mirror universes. You can then do all the spelunking and analysis you would do with your production traces, but before your real customers are exposed to any issue. (4) We have some very cool ML approaches in the pipeline that I can't talk about quite yet.
- ajb 2y ago
  Can you define equivalence classes (mutations that shouldn't change the result) eg timing, order of events, idempotence, etc? So that you can use (3) to define the correct result for all members of the class (Sorry if this is explained in the talk - I'll watch it but it's now too late in the day in my timezone)

cperciva 2y ago

Why is Mario so jumpy?

wwilson 2y ago
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).

mustknow2201 2y ago

How close is or isn't this to a genetic algorithm in practice? It seems like as soon as you start scaling out to multiple threads/nodes you'd benefit from crossover, selection techniques and so on?

iamcreasy 2y ago

Very cool presentation. Thanks for doing this. Choosing next input based on present sounds a lot like a Markov chain - is that something you guys use when simulating user interaction with distributed system?