How We Trained a Genetic Algorithm to Fly in Paper Mario: TTYD 

✈😔😥

Fortunately, all the parents die too, so they don't have to mourn for very long. =P

malleo pod when

My mom must feel them

OH THE HUMANITY

As a random throw-in who cares comment, mine was actually a report into AI within games, unfortunately I never thought to look into genetic algorithms as it didn't quite fit the purpose of my goal, that being producing a system to easily tailor AI difficulty to player skill level. Wouldn't be surprised if a decent amount of people have used genetic algorithms or even other forms of learning algorithms within games as part of their thesis. Might be conditional to being at not the best uni's like mine though. Sort of get more free reign on your reports when they don't expect anything anyway. In fact, won't deny I'd have loved to see this video back when I did mine, as the concept of using GA's or other learning algorithms to maximise efficiency within specific tasks and having multiple work with each other in a large task sounds incredibly interesting. To be honest, might have to be a personal project of mine in the future to explore battle optimisations within some other games. Generally learning algorithms aren't the best for random elements, but I'd be curious for games like Paper Mario where randomness is fairly minimised if it'd do anything differently.

Could definitely be a capstone project for my data science bootcamp

That's awesome!

Do you mean pathing or flight? Because for the former it’s way more efficient to just precompute MSTs

@@chonchjohnch I mean flight plan optimization. We use a genetic algorithm to identify ways to improve the overall plan for a flight leg based on stuff like wind, convective weather, adsb traffic reports, and the modeled control surfaces of the aircraft being flown. Using that info we can identify ways to save for time, fuel, or best of both and provide those recommendations to the pilot on their electronic flight bag while they're flying. If you'd like to know more look up the NASA TASAR project, it's the basic proof of concept behind our product.

life immitates art

Are you talking about the tom7 (suckerpinch) video? I don’t think that one was built with a genetic algorithm, but it did find some pretty interesting bugs nonetheless and is one of my favorite video game algorithm videos to rewatch every so often

@@snoozbuster nah it was this one by a guy named Chrispresso ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-CI3FRsSAa_U.html

@@bigtodd I thought you were gonna show Sethblings MarI/O, but I'm not sure if that figured out how to wall jump

@@hydra4370 it didn't, but it did find a frame perfect trick if I remember correctly

I was thinking of using some photos to demonstrate, but I really couldn't come up with anything that would be more than extra eye-candy. So we had to go with a bulleted list. The petri dish animation actually only came up in the last days before we made the video.

Interestingly, as the algorithm is working, the pull-up-at-last-moment technique is one of the very first things it figures out. Then it spends the rest of its time working on the middle of the flight.

nah, that technique is a really old one we discovered over 2000 years ago in search of the question of how to avoid producing more people, of course it wouldn't be optimal for paper airplanes.

@@MrRyanroberson1 That joke doesnt work because they said pull up, not pull out...

@@jongyon7192p i mean, i'm sure there's a species of duck out there where it applies perfectly fine

ok i pull up

If I remember my Mario Party TTYD stuff, max flight speed is faster than max running, but inferior to frame-perfect wiggle-walking or wiggle-running, I don't remember which it's called exactly (flicking up and down while moving left or right). It's super hard to do in RTA and only really usable up to the first Crump fight, after that diagonal paths are superior to wiggle-walking in straight left/right lines so it only really gets to shine in TAS.

Thanks for the kind words!

Thank you for the kind words! And if you want to collaborate on something using a GA, send me a note. The library we used, GAUL, is pretty easy to work with once you get the basic structure it uses.

It really depends on the problem, and flight optimization is one where GAs are quite well suited. Since the fitness landscape is relatively smooth with respect to controller inputs, the local minima don't seem to be too deep. The mutation & mixing operators definitely have a big part to play. Though I only glossed over it, the deletion/insertion mutation operators were a big help in longer flights. And the stretching/squooshing operator for crossover also helps the algorithm come up with children that contain good input patterns but in different arrangements. I think if you wanted to apply this to other tasks, or even tune the plane flight optimization, I think switching the controller input vector into a different basis, say, by taking a Fourier transform, would be a promising avenue.

That's a good point. He does attempt to state that there are too many variables to reliably calculate an "optimal" flightpath, but to me personally, that sounds like maybe his implementation for the flightpath isn't exactly 1:1 with the game. Also it wasn't really mentioned, but I'd imagine there are situations where different combination of inputs could lead to the exact same result. Which could just mean that there are multiple "correct" answers to what is the most optimal pathing. GA is a decent, quick and easy method to solve this problem reasonably... but I also know that this problem could be solved (less efficiently, and less elegantly) with straight bruteforce. Which could be a good long term solution for the actual TAS implementation.

@@MrCopyrightable With these flights being hundreds of frames long, and there being hundreds of possible inputs per frame, you can't brute force this problem. There are more possibilities than there are particles in the universe.

Maybe the word optimal is being used in the sense of "it's the current fastest-known way", which is pretty common in the speedrunning community.

@@MrCopyrightable @porglezomp is sadly right - the brute force approach here would have to take (number of controller positions) ^ (flight length in frames) passes, which is darn near impossible.

Thank you for the very kind words!

Well, my career goal is to be a college biophysics professor, so your comment gives me a major warm fuzzy. Thanks for the kind words!

Yeah, I focused in on this too.

Thank you for the kind words!

Yeah, it's really simple on paper when you lay it all out like this

Yeah it seems like people used to think the front of the plane panel is most optimal. Reading the code, the entire plane physics seems to be different on the plane panel to prevent things like diving straight into the panel? idk why it's different, just that it is and that it's beneficial.

For your question 2), A) there's no energy being spent here so the analogy with biology isn't perfect. B) a helpful way to think about "overshooting in the same number of frames" is simply "higher average speed" (just by an amount too small to make a difference in the number of frames it takes to reach the platform).

1. Yes, but there's a part of the fitness I glossed over - interference. If you check out the code, src/util_callbacks.c, line 71 starts the fitness function. We have a term in there for if there is a floor before the target that you need to avoid, so the plane minigame automatically optimizes for distance, since it never thinks it made it to the target platform. If we were to try to optimize for score, that would be very hard for the GA since it would create *huge* discontinuities in the fitness whenever you land on one of the score multiplying platforms, and it would almost surely get stuck in a local optimum. 2. @diribigal's response is very much on point. 3. The exit criterion was "I need to use the computer for something else now.", as much as I hate to admit it. Usually, we'd run somewhere between 20k and 100k generations. For the final TAS, we'll probably let it crunch for a while longer. While it's tempting to have an N-generations-without-improvement exit criterion, sometimes we'll go for thousands of generations before a very successful child leads to a burst of improvements over the next few generations.

Yes, we don't prove that we've found a global optimum. And for the long flights, this algorithm quickly beats RTA and previous TAS flights, but the improvements slow down asymptotically. I'd love to find an analytic solution, but I'm not hopeful that one exists.

Happy (belated?) birthday!

We tried that, and it doesn't save more than a couple hundred generations on most flights. On very long flights (like the one to get to Gloomtail's room), the algorithm converges very slowly, and so seeding could be a good idea there... except that we wanted to make sure that the algorithm had a chance to try out things that no sane person (even Malleo) would do, and if we started it in a known-good configuration, there's a chance it could get stuck there and never manage to find an improvement that requires a large change. On this note, we carefully hedge that the algorithm discovered the bug to gain height over the panel "when we directed it to gain as much height as possible" - if you just run the algorithm on an easy flight without that condition, it finds that you gain speed by flying down over the platform and only rarely discovers the bug, even though it might be helpful. This is partly because the bug-triggering inputs have a lot of neutral stick position inputs, and the GA is not likely to randomly stumble upon that particular sequence unless we give it the get-as-high-as-you-can nudge.

@@charlesmcanany6806 Thanks! I had a feeling after I posted this that having a "working" seeded run would probably leave some grey area unexplored where the optimal strategy or any bugs may live. Still glad I asked, and am very thankful for your answer! Really helped sate my curiosity! :)

For the sake curiosity again, you guys ever estimate what it would take to explore the entire problem space? If there are finite frames, with finite button inputs at each frame, from a finite amount of starting positions, I wonder if there is an estimated size for just brute-forcing all possible paths. (Estimation only, I'd assume if it was doable you guys would already have explored that and found "the" optimal answer from it) There might not be an answer, but I figured after my first question that any unasked questions will remain unanswered ones :P

@@mme725 We don't have too much say in the starting position; we just take where the TAS first got to the panel. Once we're in flight, we have 147 stick positions to try on each frame, so for an N frame flight, it's 147^N. For a one-second flight, that comes out to 10^130 different combinations.

@@charlesmcanany6806 Oh wow, 147 stick positions! I severely underestimated the degrees of freedom of the stick. @_@ Well thanks for clarifying! Great stuff :D

Malleo can address the value of this better than I can, but the algorithm can definitely be adjusted to try to get closest to a loading zone or door. Might be effective!

if a desync occurs, it will quickly snowball essentially with complete certainty. In a game as complex as TTYD variables are very sensitive to inputs, player position, and frame count. Basically if it desyncs enough to cause a difference in time, its not gonna make it to the end.

Really good questions! I don't have performance metrics of competing techniques, so it's entirely possible that a pure gradient-based approach would do better. I've long been curious about GAs, and this seemed like a fun place to use them. I was particularly interested by the crossover operation, since the flights tend to wind up having repetitive blocks of inputs. There was another comment earlier about using an RL algorithm, which would also have been a fun avenue to pursue. I actually considered adding a gradient step to the optimization, as a post-generation non-Darwinian evolution step. It'd be a bit of a chore to get a gradient-based technique to escape from local minima (and there are tons), but with an enhanced sampling algorithm (I come from simulation-land, so I'm thinking of replica-exchange Monte Carlo sampling or something) it could be quite viable.

As long as local minima aren't too wide, you can escape them by including a noise step in the training process, and/or by randomizing step sizes. You can combine this with a semi-Darwinian approach by evaluating multiple parameter sets in parallel and choosing some fraction of the fittest to move along in addition to some fraction of unfit candidates for the next training step. My intuition tells me that a RNN-based technique would take longer to converge than a GA-based one, but once a solution is found it would generalize to other cases more rapidly instead of having to start over for every flight point. I'm struggling to think of how RL would differ from RNN in this context. It feels like RNN would simply be the mechanism by which the RL would happen. Am I overlooking something? I suppose I can also visualize a non-recursive (maybe even non-NN) gradient descent approach. 100% agree that this would work better as a post-generation optimization step, the more I think about it; it would take FOREVER to try to optimize it from zero-knowledge, and using human inputs as a starting point definitely will have issues with local minima.

@@codahighland I haven't thought through the RL/RNN approach. I use CNNs very heavily for my research, but I'm not too strong on the theory of recurrent nets and fancy loss functions. If you want to play with the code and try adding a gradient-descent step, I'd be happy to walk you through it and give you some pointers.

@@charlesmcanany6806 I don't know when I'm going to have time to take a crack at it, but I'll try to keep it in mind!

Malleo can answer in more detail, but it was pretty much bit-accurate. Ghidra was very careful to cast things to the right size in the generated C code.

It gives us more time to get higher above the platform when we reach the right side.

I was more on the GA side, but I believe it's faster to fly than walk in the general case. I'm curious about the landing, though. We could target our landings further along the floor, but that would mean we can't take a dip below the landing (as Monado's flight shows well at 18:30) and so we'd take a hit from that change. Ultimately, we still need to test out our options.

It gives the same results, bit-for-bit, but I don't think we ever tried re-compiling it for the Gamecube architecture. I doubt it would be the same, since we aren't using Nintendo's development toolchain.

He's decided on the route now

We tried that, but the effect is to only remove the first couple generations. We went with random inputs because we didn't want to start it in a deep well that it would struggle to escape from.

Yup! Any Gamecube or Wii game. You will also need to download the language definition for the consoles' CPU variant, in order to properly reverse-engineer the assembly: github.com/aldelaro5/ghidra-gekko-broadway-lang

I got Ghidra working! Only problem is I don't know how to code anything that isn't a few powerpc asm codes.

I probably should've linked this, given it seems it's hard to find. Here you go:downloads.khinsider.com/game-soundtracks/album/castlevania-best-music-collections-box-disc-17/17.09%2520Bloody%2520Tears%2520~Bloody%2520Tears~%2520%2528From%2520%25E2%2580%259CDracula%2520II-%2520Noroi%2520no%2520Fuin%25E2%2580%259D%2529.mp3

@@Malleo Nice! Thank you 🙏

@@Malleo Was about to ask about the missing music links in the description for this one, tanks!

If you know where the room is and where the most height optimized GA landed in the video, then 100 units is a lot. See'ing as how the algorithm found a bug to build height, one would think, that it would continue using it to get higher or keep the greatest height. The GA did not do that. Now we have an algorithm that found a bug to increase and hold height, but when asked to optimize for height, didn't use it all the time, which leads us to believe that this bug has some sort of limited usage. Without building more height, and see'ing how the plane descends, it's fair to assume that a path to skip 100 units more height, is pretty implausible to hunt down, if not outright impossible. It would be more productive to find some sort of fly glitch or position manipulation, than trying to squeeze 2 more units out of the GA.

@@christophsiebert1213 okay, I see what you're saying - not necessarily ruled out in general, just unlikely that an AI approach is good enough.