Speedrun Science: Beating Quake with code

Рет қаралды 20,831

Күн бұрын

A look into applying optimization methods (specifically differential evolution) to improving Quake's tool-assisted speed run record. Credit goes to Jukspa for creating TASQuake and for doing the run on which this project was based. See that run here: • Quake Easy Run TAS in ...
0:00 Introduction
0:22 TASQuake
1:06 Plan
2:36 Implementation
3:15 Optimization
3:53 E1M1 best run
5:14 Full game?
5:38 Outro

Пікірлер: 100

@MattsRamblings 2 жыл бұрын

Big thanks to Jukspa for building TASQuake and for creating the run which I tweak in the vid. Check it out here: kzfaq.info/get/bejne/m9GUlriAvJfLlXU.html

@TA-ob6kz Жыл бұрын

In terms of how to fix the AI’s difficulty in finding very long efficient paths, you should look at what deep mind did to solve the Atari 2600 Pitfall game problem. Since that required looking far ahead. It’s been surpassed since then, but it helped solve some early problems

@LeonMassey 2 жыл бұрын

Oh yeah, this is the kind of hyper specific video I've been looking for. Excellent visualisations, really helps to clarify the elements of the video that might be a little hard to understand through speech alone

@zweekSR 2 жыл бұрын

babe wake up new matt's rambling just dropped

@MikQo117 2 жыл бұрын

ain't no way

@bamtna 2 жыл бұрын

inspirational, i love your videos i make tool assisted runs on counter-strike: source using a tool of my own that has a simulation component and allows the user to edit inputs manually. i have been wanting to move towards using some brute forcing and/or machine learning in short sections of my runs, so it's great to see that you have done so with some success

@beetle179 2 жыл бұрын

+2 imagine the potential here 👀

@ohryanshiels 2 жыл бұрын

Wow, the improvement is sick and the visualizations/explanations and production were even cooler

@sticks_stuff 2 жыл бұрын

matt i love you

@chakra6666 2 жыл бұрын

Very cool video. Minor optimisations in TAS runs are always so interesting. Super impressive that you managed to save 0.25s out of a 5s block!

@Msushi 2 жыл бұрын

this is really cool!

@olly123451 2 жыл бұрын

This is so cool, I’d love to see this applied to more levels or even different runs through require actual combat could be fun to watch being optimised.

@almostmatt1tas 2 жыл бұрын

Quite fascinating! I do a bit of TASing for Doom and would love to see something like this applied to it one day. The current tools we use do have brute force functionality, but in their current state they're great for accomplishing small precise tricks but aren't able to be used to complete a significant section of a run like this. Simply getting around corners effectively is surprisingly difficult to do and it's great to see how you were able to so effectively work out how to further optimize that for this run.

@iisisti 2 жыл бұрын

The visualisation is stunning!

@MattProud Жыл бұрын

Well done. This is excellent material. I'd love a writeup of how you were able to do this, possibly with a Git repository or two that could be browsed. I built a mechanism to do unsupervised JVM tuning years ago, but this is really next level!

@WDC_OSA 2 жыл бұрын

this is remarkable, and thank you for all the interesting visualizations. I love it!

@VEC7ORlt Жыл бұрын

There is playing, there is pro playing, there is speedrunning, there is TAS, and there is you, optimizing the optimized. Very cool stuff, visualization helps a lot too!

@NA-zs2sw 2 жыл бұрын

I love these videos! It would be interesting to hear your thoughts on how to apply this to the entire level/game. I can only think of naive approaches such as forcing checkpoints at different points of the map (i.e. the run _has_ to go through this door, etc.).

@Patashu 2 жыл бұрын

Really cool visualizations and I can't wait to see what comes of it!

@raretapes8057 2 жыл бұрын

Been waiting for a new video from you... awesome

@gumbo64 Жыл бұрын

cool as hell conceptually and the visualisations actually do it justice thank you

@gumbo64 Жыл бұрын

also monte carlo tree search is my favourite algorithm i swear its magic u gotta try it when you get the chance

@lahma69 Жыл бұрын

Wow, this is a really clever/intelligent way to go about optimizing any given TAS run. Essentially, as long as any given TAS record is not yet optimized (and it is extremely unlikely it will be if created by a human without the help of a machine learning/optimization algorithm), you can simply take a short chunk of the run (obviously, optimizing a segment at the end of the run simplifies things significantly), which you believe has the most room for improvement, and spend your CPU time optimizing only that short chunk. You could even break down the run into overlapping segments and run the algorithm on multiple machines simultaneously and then, by comparing the different optimized chunks (particularly with the overlapping segments in mind), you could either intuit the best line to further optimize for or even use another optimization algorithm to choose the best segments based on a few given inputs (best starting position for the next segment, character speed going into the next segment, furthest progress into a given bounding box, etc). I think what's most impressive though is how you targeted the lowest hanging fruit and therefore significantly simplifies the problem to solve while still almost guaranteeing an improvement over the current record. I just found your channel and I'm already hooked! On to the next video 🧐

@Twisted_Logic 2 жыл бұрын

Super well done as always, Matt!

@YaLTeRz 2 жыл бұрын

I wonder how it compares to simple bruteforce: mutate the frame numbers and yaw angles a bit randomly, simulate, accept as the new best if it's faster. This simple bruteforce has proven to be surprisingly very effective in Half-Life 1 TASing.

@MattsRamblings 2 жыл бұрын

This is sort of what differential evolution (the algo I'm using) is doing. The difference is that rather than having a single run that it is being changed at each step, a population of runs is maintained, each of which are individually mutated and accepted if they improve on their old value. The key thing is that the proposed mutations are based on other members of the population, rather than being independent, which in theory should make better suggestions.

@deadhorseak Жыл бұрын

Speaking from the perspective of a computer scientist, A hill-climbing approach or genetic algorithm (like the method used here) is almost always more powerful than a brute force solution in an optimization problem (unless the problem is really simple) in terms of finding a good solution more quickly.

@deadhorseak Жыл бұрын

Also, if I understand your method correctly, it's not really a brute force method but rather a sort of hill-climbing algorithm.

@YaLTeRz Жыл бұрын

@@deadhorseak yeah, it's hill climbing (and ensuring the objective you set is "well hill climbable" is very important for good optimizer results in my experience), but new candidates are generated by randomly mutating the best solution rather than using a genetic or other smart algorithm.

@YuriyNasretdinov 2 жыл бұрын

That's so fascinating! The animations and visualisations are also very well made. Not sure why your video got so few views, but I'm pretty sure it must change over time :).

@77ZaRR77 2 жыл бұрын

Combining neural networks with TAS is something innovative.

@piotao Жыл бұрын

THAT is something I was looking for for years!!! There are some games which were made for speedrunning, like xonotic with complete the stage mode (CRS). It will be very interesting to look for an optimal paths - there could be a lot of solutions depending on player average speed, for multi-route maps... But finding the proper paths will be just super-hard problem on it's own!

@frognik79 Жыл бұрын

You sir have earned a subscription. Longer videos with more details would be nice.

@liveteklol 2 жыл бұрын

Subbed ! Want to see more comparison AI vs TAS

@gbkEmilgbk 2 жыл бұрын

Impressive work - well done!

@TheRasteri Жыл бұрын

The visualisations on your whole channel are stunningly beautiful.

@RenderScape Жыл бұрын

This is insanely awesome! Amazing work!

@HoboVibingToMusic 2 жыл бұрын

John Carmack 2. THis is beyond what I thought would be doable

@lacyyy 2 жыл бұрын

Fantastic stuff. I'm making a source movement game for fun and certainly want to include player path optimizations, your videos will certainly be useful for pointing me in the right direction 👏👏👏

@SaperPl1 2 жыл бұрын

Really cool - question about handling whole level though in chunks - why not do it in chunks but starting from the beginning and finding somewhat neutral/optimal points for cut between sections? I know that it will be suboptimal because one section being run at optimal speed may mean negative effect on another, but it is an approach that could let you process whole level.

@MattsRamblings 2 жыл бұрын

Yes, I think that is probably the best way to get an improved full run, and certainly worth trying. Still though, it feels like there should be some way to optimize the whole level at once since it seems like there's an independence between parts of the run that are a long way apart. For example, the first jump out the lift is going to be mostly independent of the jumps near the end, but you need to know how to join changes earlier on to the existing route to stop the effect I show at the end of the vid.

@Essence1123 2 жыл бұрын

Rather than handling them in discrete chunks would it be possible to just have 'waypoints' that MUST be hit. This is sort of like chunks but still optimizes for the whole level rather than one chunk over another

@ElvinDrude 2 жыл бұрын

@@Essence1123 I think you'll still run into issues as those waypoints could just be hit at varying speeds/angles, so the original problem still remains.

@Essence1123 2 жыл бұрын

@@ElvinDrude it still solves the problem of best time on section A ruins the rest of the level as the score given is still for the full level time rather than an individual sectors time. I'm imagining if say there's a button or a door you need to wait on putting a waypoint there would greatly reduce the complexity of the problem set

@Uristqwerty Жыл бұрын

@@MattsRamblings My intuition is that total run time is a poor heuristic to judge early movement by, since you'd need to follow each change with corrections to keep the route on track. For a small segment, the search space is narrow enough to find those corrections naturally, but the whole level's too large as even the smallest differences cascade forwards. It might be more interesting to optimize overlapping segments in sequence, effectively making the heuristic "is fast + will remain fast for the near future", and giving the next segment a strong starting point. For early and late movement to be fully independent, you'd need a frame in between where it matches position and velocity near-perfectly, no? So you'd want to find points like the elevator where either level geometry or a separate sort of search can tweak the end of one segment so that it matches the start of another. Either way, you'd be stitching together segments, whether by hoping that the level geometry is enough, or actually incorporating it into the optimization process as a separate step. Though all it really provides is the ability to go back and further optimize early sections without losing later work, rather than having to manually decide that each early section is good enough and it's time to move on to the next.

@TheFatCheetah 2 жыл бұрын

Would love to see some sections of challenge maps like Mission Impossible 1 & 2 tackled with this algorithm.

@btarg1 2 жыл бұрын

This is amazing! It deserves a lot more attention.

@unfa00 Жыл бұрын

I would love to see a more in-depth video about this, and especially - seeing you optimize the rest of the game!

@mxpph 2 жыл бұрын

Super cool!

@christophercha6704 2 жыл бұрын

Very neat!

@appidydafoo 2 жыл бұрын

Fascinating, thank you

@p3num6ra 2 жыл бұрын

You're videos are awesome!!! I've always had this idea about using evolutionary algorithms to create the perfect QuakeWorld AI. What would they look like? What playstyle would they have? What advantages would they try to get over other bots/players?

@awesomefacts101 Жыл бұрын

all your videos are so cool omg

@voidpunch1324 2 жыл бұрын

As CS student this is very cool stuff, i specially liked how you presented the differences in routing using color lines and the player actually doing the movement, very effective. Any tips to get started using evolutionary algorithms in small projects?

@SBH618 2 жыл бұрын

Great video, keep it up

@deniskfender Жыл бұрын

just amazing!

@notjerrett 2 жыл бұрын

Commenting for engagement :)

@paradoxicalegg6112 Жыл бұрын

you need more subs this is awesome!

@jag0937eb Жыл бұрын

Nice optimisations

@Davesoft Жыл бұрын

"about 200 E1M1's per second" the Real play to play quake :D

@saheilaanarzee5552 Жыл бұрын

this is so cool❤

@nzc9609 2 жыл бұрын

really cool

@skope2055 Жыл бұрын

amazing

@avensCL 2 жыл бұрын

This made me wonder, how do you think engineers find the optimal "routes" (lines with inputs) in Formula 1? Just brute force in a simulated environment? Asking that because teams don't have access to wind tunnels that simulate all conditions, and therefore sometimes they get their calculations completely wrong -as it happened this year in regards to porpoising-, so that means they must be doing something else on top of using theoretical simulations to get the optimal routes. And also, that visualization was fantastic. I can only begin to imagine how it would look like applied to F1 (would be great channel content actually -- or you could even make a career out of it)

@Tymon0000 Жыл бұрын

Nice!

@Shweetz 2 жыл бұрын

The visualizations are amazing. I am currently making a tool for TASing Trackmania 2 but it's only manual script editing right now, and it's hard to visualize/show anything except comparing with world record. I'm currently trying to get some bruteforce automation as a first step, will make a new video if it works. On Trackmania Forever, someone did another tool but it goes about 50 iterations/sec only and it's in c++, so I'm really wondering how you can get 200 iterations/sec in python! The game physics being likely less heavy on calculations would be my bet. Wouldn't c++ give more iterations/sec for Quake? Once again, amazing visualizations and nice explanations :)

@MattsRamblings 2 жыл бұрын

Thank you. To clarify, the bulk of the simulation is still being done in C. I made a library "libtasquake" which is literally just the C TASQuake source but with graphics, etc, removed and a library interface added in. I then made a Python library that calls into this C library. I used Python so that I can take advantage of the wealth of numerical optimization libraries available. Good luck with TM2!

@hughjanes4883 Жыл бұрын

Very late reply but I've always thought about doing a similar thing with the original nes Mario bros, the speed run for that is so short i thought that an algorithm could just brute force (in a similar but tbh a lot less advanced way to the one in this video). Though seeing how much computing power was needed for quake I think a GPU farm would be needed for the longer smb1 run

@Aggnog 2 жыл бұрын

dang yo

@RedlinePostal Жыл бұрын

Optimize from point of barrel explosion, as that’s the part that the algorithm will immediately get lost if it makes even a slight change to position

@TheMuffinMan86 11 ай бұрын

brilliant! i wonder if this could be applied to deathmatch bots for map traversal?

@smokesspeedruncorner8600 Жыл бұрын

Awesome video! What happens if you try this on a level that has a rocket launcher / grenade launcher? Not to mention health, weapons and armor carry forward during each episode from level to level creating another dilemma. I can see why it would be tough to do a single episode in this manner let alone 4. Hopefully there are ways around this because that would be pretty cool to see. Good luck! 😄

@MattsRamblings Жыл бұрын

Yes, all that stuff would have to be managed by hand. For example by disallowing runs that finish with less than a prescribed amount of armour.

@TiagoTiagoT Жыл бұрын

What if you had "genes" that are "key points", points in the path with a given set positions, rotation, speed etc; and alternate optmizing the segments between those "key points" and exploring alternative "key points"; making it so you can "breed" different approaches taking the best parts of each and blending with transitions on close enough "key points"?

@tubbiele2 Жыл бұрын

Wooooow Woooooooooow Edit: you rule ❤

@SnareX Жыл бұрын

We need a new category for speedrubs. I don't think this should be under TAS. Imo tool assisted there's still a human behind the controls, but AI is a tool too. Thoughts?

@ItsRamzi 2 жыл бұрын

This is a shortest path problem. Killing 100% enemies would be much harder, as their locations are chaotic.

@stacksmasherninja7266 2 жыл бұрын

Can we strip down source engine games to simulate them faster as well ? CS1.6/Half Life would be a fun thing to try for me. I have slight experience with plugin development/mod development so if there are any technical resources where I can carry this forward, can you please point me to them ? Secondly, wouldn't policy gradient like algorithms be faster in finding the optimal values ? Maybe using the negative of the time taken to complete the level as the reward ? I am going to try the experiment with policy gradient (assuming there's code available and works on my system) but I wonder if you've got some intuition

@MattsRamblings 2 жыл бұрын

Policy gradient (or other RL approaches) sound sensible to me. That is one of the approaches I considered but opted to try black box methods first, since it's easier to get working.

@justice83 Жыл бұрын

Couldn't work out why you would want to wait on the opposite side of the lift while it goes down..

@bamtna 2 жыл бұрын

Could you describe how the initial population was generated? Was it something like using DE within some close bounds to the original script and taking the first 300 to finish?

@MattsRamblings 2 жыл бұрын

Hey, I used DE with a fairly tight initial population around the existing record, and an objective function that is 0 if the exit is hit and 1 otherwise. Since DE accepts a mutation if the candidate is less than *or equal to* the old value, I figure this means the population should naturally spread itself about the feasible space. I stop when a) all the population has value 0 (ie. all exiting), and b) the standard deviation of each parameter stops increasing.

@bamtna 2 жыл бұрын

@@MattsRamblings Wonderful, thank you

@hrnekbezucha 2 жыл бұрын

Do split seconds count? I would imagine the end level tally is what matters, so the TAS run would need to be half a second (?) faster to round to 17.

@MattsRamblings 2 жыл бұрын

Normally for submissions for SDA (speed demos archive) the fractions are dropped. So to beat a run that got 18.xxx seconds you'd have to get one with 17.xxx seconds or below. Still though, I think the existing TAS record time is the sum of exact finish times, and so any time improvement on an individual level would mean an improvement overall without needing to cross a "second boundary". (I still might need to make adjustments to subsequent levels though since I might have changed the RNG).

@hrnekbezucha 2 жыл бұрын

@@MattsRamblings Well, good luck :)

@Jukspa 2 жыл бұрын

@@MattsRamblings Yep I counted the TAS time as sum of exact times rather than the truncated times, this way it also matches the timing of human runs.

@SleepyAdam Жыл бұрын

Did you also program into the algorithm some kinda RNG manipulation to make sure you don't get shot?

@MattsRamblings Жыл бұрын

The script I based this off uses RNG manipulation by shooting the gun which rolls some new random numbers in order to determine the shotgun scatter thus affecting the monster behaviour later on. My modifications don't explicitly account for RNG but if a proposed route means the player is slowed down by a monster attack it won't get chosen simply due to being slower.

@SleepyAdam Жыл бұрын

@@MattsRamblings Awesome. Didn't even notice the shotgun blasts I was too mesmerized by the speed, lol.

@AB-ms7my Жыл бұрын

Can you post your source code please?

@klaasbarends Жыл бұрын

Would be interested in seeing an ai learn quake from scratch. Would it discover strafe jumps, bunny hops, etc?

@MattsRamblings Жыл бұрын

You might be interested in another video I did where I use reinforcement learning to make a bunny hopping bot kzfaq.info/get/bejne/nt5nntmFv7KsiX0.html

@tomyoungblood9175 4 ай бұрын

What is your education?

@julius333333 Жыл бұрын

any reason why you didn't use good old reinforcement learning

@MattsRamblings Жыл бұрын

I think that's a good idea. Generally it's more work getting it set up, choosing hyper parameters etc (in my experience) but maybe something I'll try

@the_kovic 2 жыл бұрын

I take it your changes to TASQuake aren't open source? If they were, someone with too much free time and computational power could start slowly and systematically improving the run

@MattsRamblings 2 жыл бұрын

Hey there, I'm planning on releasing the source code once it is tidied up. Having the community collaborate to improve the run would be a great thing.

@Asdayasman 2 жыл бұрын

So you're basically doing a gradient descent through the problem space which has an exponential explosion in states past the first few opening moves? Sounds like you could go all alpha zero on it and use MCTS to TAS optimise a whole level. Well, not "optimise", but at least find a better solution.