@wwilson How do you define the X/Y "distance" of a non-Mario application? I.e. any (distributed or not) system that doesn't have a relatively trivial "higher x/y is better" fitness function?
How Antithesis finds bugs
51–56 of 56 posts
Re: How Antithesis finds bugs
#52Re: How Antithesis finds bugs
#53If you just read it it sounds like a scam to some. Going thru all states does not find you bugs magically. You need to know what a bug is first or if it’s an actual intended feature. This article fails to explain it
Re: How Antithesis finds bugs
#54This is fascinating! I thought only Reinforcement Learning was doing things like this but you're saying you can do this via fuzzying? What does this mean exactly? How is it able to learn to advance through all these levels? Is there an underlying learning mechanism at play?
There's no learning exactly, as the post explains the fuzzer is aware of various RAM addresses (as well as having a tactic for how it "presses" buttons in the game). It's just trying to explore the space of Mario's level + his x and y coordinates. (I'm an Antithesis employee.)
This means that, without a learning procedure to direct Mario towards the end of the level, it can only reach the end by itself because the levels (and Mario's in-memory data structures in general) are pretty small, right?
Or rather, if there were tons of irrelevant state, it could always end up trapped somewhere and never actually complete a level even after centuries of fuzzing.
Something similar was tested in the Twitch Plays Pokemon [0] gaming experiment, but there the inputs appeared random but weren't actually random: there were "factions" that either tried to sabotage the run, or that tried to make it progress. Ultimately the majority of the players were cooperating to complete the game and this was a deciding factor to make the run succeed. Maybe fuzzing Pokemon can't complete the game, the way that TPP could (or reinforcement learning could).
Re: How Antithesis finds bugs
#55Earlier quoted context omitted.
Most RL agents are 'jumpy' or jitter a lot, because it makes no difference to the reward, and where it does make a difference, that tends to only matter close to convergence where slight speedups are all that's left. If you want to reduce that, you have to reward-shape it to penalize excess movement. (Which is relevant in robotics, where 'jitter' can be very bad for the machinery in a way not reflected in the simple…
Case in point: Watch an actual Mario speed running world record video, and the human players there are jumping around a lot while running around flat sections with no obstacles. As I understand, the jumping (at least in this case) does nothing to Mario's horizontal speed at all, so they basically just do it for "fun". The difference is that the human players know that they're doing something inconsequential for varie…
Or they might be doing it just to keep their fingers 'warm'. I recall during AlphaStar, there were a lot of questions about why the human pro APMs were so high when it seemed like a lot of them were null ops, and apparently the answer is that they do that just to keep their fingers going and reduce reflex reaction time. (As you can imagine, this would be very bad for imitation learning...)
Re: How Antithesis finds bugs
#56Earlier quoted context omitted.
There's no learning exactly, as the post explains the fuzzer is aware of various RAM addresses (as well as having a tactic for how it "presses" buttons in the game). It's just trying to explore the space of Mario's level + his x and y coordinates. (I'm an Antithesis employee.)
This means that, without a learning procedure to direct Mario towards the end of the level, it can only reach the end by itself because the levels (and Mario's in-memory data structures in general) are pretty small, right? Or rather, if there were tons of irrelevant state, it could always end up trapped somewhere and never actually complete a level even after centuries of fuzzing. Something similar was tested in the…
The space is large, it just turns out if you direct Mario to explore with a bit of bias (so, in general, there's some favoring of exploring from states where Mario's x coordinate is to the right, e.g.) it completes the levels.
I think Pokemon could be beaten with our techniques. Final Fantasy on NES poses similar problems to Pokemon, and that is a game at which some progress has been made in the past, here.