ฝัง
- เผยแพร่เมื่อ 28 ก.ย. 2020
- We need YOUR HELP to shave seconds off the TTYD 100% TAS. To help in the effort to find the fastest Zess T. recipe order, download Recipes@Home here: github.com/SevenChords/CipesA...
Special Thanks to:
Cubik:
- Twitter: / the_co_atheist
SevenChords:
- TH-cam: / @seven_chords
- Instagram: / sevvenchords
Amphitryon (No social media)
Lego:
- Twitch: / lego6245
- Twitter: / lego6245
_____________________________
Twitter: / tasmalleo
Twitch: / tasmalleo
Join my Discord! / discord
Intro/Outro by TheSneakySpy: / thesneakyspy and / thesneakyspy
Check out Mario Kart Wii TASes: mkwtas.com - เกม
This is the most hilarious use of crowdsourced CPU that I've ever heard.
the minecraft seed searching were nice too.
@@minirop wasnt seed searching gpu instead
What about the tallest minecraft cactus?
To possibly save SECONDS off the TAS!
If anyone's curious, that null item is called むこうアイテム, or Invalid Item. The description says, このメッセージが 見れるのは おかしいよ, or "If you can see this message, something's wrong!"
I'd translate the latter sentence as "It's weird that you can see this message".
" I wanted to talk about the traveling salesman problem" just do it anyways.
He can't without opening the can of worms that is quantum computing
@@AmaroqStarwind He very definitely can, especially if done through the lens of classical computer science.
The real question is why he isn't using something like the Held-Karp algorithm.
I was excited when you started to talk about graph theory, and then was disappointed when you stopped talking about graph theory. I like graph theory.
To view the leaderboards for the fastest recipe roadmap, please visit recipesatho.me/
is that still the fastest route?
If you want I can write some quick code to host a webpage with a leaderboard? Just hit me up.
my fastest is still at 4306 (Sep 30, 2020 @ 2:25PM)
@@willytor7899 yes
hundorecipes.blob.core.windows.net/foundpaths/fastestFrames.txt
I've gotten faster, 4143
I absolutely love how your channel, and consequently TTYD, has become a medium for a plethora of both fundamental and application-based computer engineering subjects. Not only that, you are introducing these subjects in an enjoyable and fun way, better than any modern class could.
Keep up the good work my man.
There's nothing quite like real-world applications that aren't ripped from a textbook to show you that skills can be useful. As a probability/statistics person, I like the stuff with finding cheated runs.
I like it when calculus is used to determine the optimal angle for things like the clock punch in SM64.
"We're gonna shave WHOLE SECONDS off this TAS!" This is a hilarious amount and effort for anything outside a speedrun setting, but good job to everyone regardless 👍
Been in the works since March! Will be interesting to see what the PB is come TAS time
Is it possible to port it to OpenCL so it can run on GPUs as well?
screw bitcoin mining. let's route a TAS!
From some quick profiling, it looks like a good chunk of the code's runtime is spent allocating and freeing memory. Allocating and freeing clean structs for each use is good and tidy, but not fast -- if possible, re-using already-allocated space from previous iterations could get you some performance gains. Careful for bugs caused by reading old data, though.
Dude you have no idea how excited I am to watch a 100% tas from you, it’s sure to be a great one, keep up the great work
For reference since I just went and checked myself, 100% requirements are:
All 100 Star Pieces
All 85 unique Badges
All 124 Tattles
All 57 Recipes
All 42 unique Shine Sprites (duplications don't count)
All 7 party members upgraded to Ultra Rank
All 7 Crystal Stars
All 8 Special Moves
Superstar Rank at level 30
All 4 Paper Curses
Ultra Boots and Ultra Hammer
2:50 that beautiful transition with the volume with the incredible SPM music though.
My CPU's toasty enough that I think it might actually be busy cooking something.
Folding at home, Seti at home: I sleep
Cooking at home?: R E A L S H I T
God I just love the application of computer science to absolutely bust this game open. Wish there were other people who would do stuff like this.
Gotta say thanks to the paper Mario community. It got me to play paper Mario and Mario RPG months back and both super fun.
My girlfriend and I watched this video. She understood it completely. Me?
"Hee hee, smart man say words!"
I would love to hear you talk about just the traveling salesman problem for an entire video. Please make that happen once this TAS is completed.
Seen this video before the Docker script and the leaderboard were up. Good job to all those who worked on the project so far!
I'm excited to report that the best known roadmap has gone under 4000 frames recently!! It is now 3988 frames by Amphitryon :D
This outro is beautiful... also I've just begun taking a programming course in university, so this video has absolutely fascinated me!
I'm doing my part! Can't wait for a 100% TAS of this game. Keep up the great work!
For anyone who still cares, I have made a fork that cuts down on a lot of malloc churn and adds a bunch of optimizations.
I can't post links here or else I will risk the wrath of the TH-cam's anti-spam bots, but you can get to my fork by taking the github link the the description and replacing "SevenChords" with "TechSY730".
Check the releases on the right for the newest "blessed" version.
Note however, since I can only build the Windows builds through MinGW-w64, not Visual Studio, and since I don't have a Windows machine I can't actually compare performance, even though I can ensure correctness (as in "does the exe actually work?").
(Malleo or any mods, if you don't want me broadcasting this here, can you give me a reply before deleting the comment OR send me a message on my GitHub however you can (file an issue?)? Just deleting it right away makes it unclear to me if it was TH-cam's bots at it again or something you intended)
Left it running all night while I slept and all day while... I slept (Sick day, lol). My PC's PB is still only 4238. This is like a speedrun for your PC.
what does PB stand for in this case?
@@rickjames5998 Personal Best
I left it running over night and it didn't find anything for 4 hours. Now I understand why this is a community effort.
The intro and outro are so snazzy! Loved the video, thanks for all your work 👍
just spent the past hour or so trying to figure out how this works, i’m so happy i can help you guys out in some way
NFT and Crypto mining pools? Nah man. CPU CROWDSOURCING FOR PAPER MARIO? HELL YEAH.
Adding 30 workers with my ryzen 9 5950x LETS GO ' v'
100% tas??? LET'S GOOOOOOO
It seems like I'm only just now watching this, over 2 months after it premiered, but this is still super interesting! I wonder what progress has been made in this time....
...and a few days ago I was about to ask about this exact thing. Glad I now have a use for all those hella fast cores!
This is really cool! I'll try running it on my pc and see what happens! (I usually only hibernate my PC anyways, so leaving it on all night shouldn't be a problem.)
This made me think, let's say that there's a category for a game that only takes 10 seconds to beat, could we do some bruteforcing strategy so we find the perfectly optimal route/input list
It would be relatively easy to do dragster, it's like 6 seconds long and only like 8 possible inputs. Also, the perfectly optimal route is already known, so it wouldn't be anything new
This reminds me of a TAS that was made by reverse-engineering a game's code, rewriting it in C++, and brute forcing a series of inputs to find the best time: tasvideos.org/6347S.html
@@Malleo This is fascinating!
@@squorsh I’m pretty sure this is what was done
I love TTYD and TASes, so I am now contributing.
Great video! Have you considered using GPU computational tools? It seems like traversing a tree like this is an embarrassingly parallel problem so using thousands of GPU cores would be faster than using CPU threads. The CPU may be called when you need to construct the final set of lists. Additoinally, it may be more efficient to assign jobs and store results from workers to a local database. Cool work!
I don't have a particularly great CPU (intel i5) but I remember lending sometimes weeks of computing time for GIMPS (the Great Internet Mersenne Primes Search). I will gladly do the same for this project.
I can’t wait until someone with a Threadripper 3990X shows up lol
I’m taking advanced computer architecture next term and… I’m very tempted to do my undergraduate research on this project
So, I love speedrunning (admittedly I've only speedrun Metroid games), so I was excited to watch this. Then when I heard "PY", I was like "... so slow.", I mean I'm a former PY dev (now ASM/C/C++), so I have a bit of a soft spot for python, but I'm glad to here it was actually optimized to C.
Next up: Setting up a botnet to get past Magnus von Grapple
last known PBs were a three way tie at 3680 frames btw
my cpus not that good but id be happy to help
Great use of the community! :)
My CPU is heating up now! Hope, that it will help.
Keep up the great work and Ideas!
I have an Idea for the program:
It would be nice to receive a file with all tried combinations of the "best" contributer so far, so that not everybody has to start from scratch. (via update at startup maybe?)
Don't know if that will be doable considering the settings the "best" contributer had set.
Frames now: 4293
Downloaded and running! :)
Im so happy somebody is doing a 100% tas for ttyd i love this game but people don't reay upload a lot of 100% runs
I love it when a community comes together and makes stuff like this. its so wholesome :)
I'm so excited about 100%
Are you using a direct brute-force algorithm, or something that would be more efficient in terms of generating the optimal route (that may not be able to generate a relatively good route unless you generate the aforementioned optimal route)?
I understand not a single word said but ttyd is cool and by extent makes you cool too for doing TAS' of it, TAS' are also cool
Has this already been "finished", or is it still valuable to run this?
Time to murder my CPU finding Paper Mario recipes! Very excited lol
Now this is something. Damn.
Running it now, just found 4409 so i got quite a way to go, but glad i can help!
The theory of this was actually very interesting to watch, despite how technical it is. 10 seconds IS a long time in a TAS. I wanna see the 100% run, so I'm in!
By the way, is it normal for the workers to be on [Searching New Branch XXXX] for 30+ minutes? The first time I ran the program it started displaying the frames for the complete branches right away, but now all 3 workers are just counting up on [Searching New Branch].
Wouldn't running this in Nvidia's CUDA framework be several orders of magnitude faster than CPU calculations?
Not sure if you're aware, but to target CUDA, you have to write the heavy parts of your code a certain way, using special extra statements, and using algorithms that work well with the GPU's differences. It doesn't always get good results for performance and even working out why can be tricky! So unfortunately it's not a simple change.
But, if you want to write the CUDA version, the original code is right there...
I wonder if we could use a GPU acceleration library to allow really absurd numbers of threads.
Finally a real use for my 3990x Threadripper.
ive been wanting a 100% tas
Imagine a world where TASes are written by quantum computers finding the minimum of giant tree graphs of all possible inputs.
If this inventory glitch requires deleting the Strange Sack, does that mean the TAS 100% category doesn't require having it at the end of the run?
Strange Sack does not count towards 100%.
Complete the game and obtain the following:
All 100 Star Pieces
All 85 unique Badges
All 124 Tattles
All 57 Recipes
All 42 unique Shine Sprites (duplications don't count)
All 7 party members upgraded to Ultra Rank
All 7 Crystal Stars
All 8 Special Moves
Superstar Rank at level 30
All 4 Paper Curses
Ultra Boots and Ultra Hammer
@@DannyTheVito I could've sworn Strange Sack was in the definition. Was there a definition change to accommodate this new inventory glitch?
@@discountchocolate4577 Collecting all important items is not required as it's impossible to possess all of them at the same time.
@@DannyTheVito When you put it that way it makes sense. I was thinking of it more as a permanent upgrade than as a key item.
If a mac build ends up happening, will gladly contribute!
I'm actually doing a paper on graph theory right now
In theory, I'm actually doing a graph on paper right now.
TASMalleo’s actually doing a graph theory on paper right now
You went from Python to C? Bless your heart, that sounds rough. Good luck with this project, and I'll see if I can contribute too!
Doesn't this ignore the almost certainly larger time cost of gathering/constructing the initial inventory?
Well that's irrelevant as we are always starting with the same inventory. There is no need to factor in the framecost of constructing the inventory given the fact that it never changes.
Been running Recipes@home for a good 20 hours now and I find it interesting that new results pop up in waves. Is this coincidence or does it create new result files in batches?
I assume this is because of the way Recipes@home works. Since it's going down a tree, a lot of faster roadmaps are going to be clustered.
@@andypage3229 That makes sense.
Bill Gates said think of what people will do with computers 20 years from now.
People 20 years later:
Has the fastest path been found already
Do we have to manually upload our results somewhere?
As long as we're spending a colossal amount of time and effort on this, why not obtain every cook able item in the game, have Zess T cook it and record the outcome. Same applies to each combo of 2 items.
This can help eliminate useless recipes and filter down to possible recipes that will create the things you need.
Most of this info is probably available on a wiki somewhere. In 20 years of existing, surely someone has done a fair amount of the legwork.
Or maybe there is a way to do this by simulating just the recipe section of gamecode (I'm speaking gibberish now) and calculate every combo and have it fart out a spreadsheet of results.
Idk how to do any of that. I'm just a guy with ideas. These ideas may or may not be obscenely dumb.
is it possible to utilize GPU to further help ? i feel like a CPU is rather slow at solving these kind of tasks compared to a GPU
A GPU is good at number crunching, but not other things like lots of branching (e.g. if statements). So I don't necessarily think the GPU would be faster at this. Still, one shouldn't speculate; one should verify. But it's not going to be a silver bullet.
How much RAM does it use, and would allocating more RAM possibly make it run faster? Asking because my PC has 120 GB RAM that it's not using.
can't wait to put my i5-2400 into endless suffering
How do we submit our calculations and how do we know when it's done?
If I understood correctly, your calculations will be automatically submitted to the server if they’re faster than what has been previously discovered.
Also there is no “done” lul that’s why they’re needing so many people helping
*Malleo the Mathematician*
should be written in assembly ;)
Are you still accepting merge requests for this? I've got a whole bunch of optimizations and memory leak fixes going on that I am ready to share soon-ish.
it's running for nearly 24 hours now. 4198 was the best result at 3am. no new (best) result in the last *12 hours x_x
running on an 3700x with workerCount = 12.
When i close the program and start it a bit later again, will it know, what it already checked?
it doesn't know, it just relies on the fact that the chance of you finding the same path is astronomically low.
your odds of finding the same path are the same as your odds of finding the best path
ahh yeah, makes sense. thanks
i feel like the beginning of this video was missing an explanation of why cooking the recipes in a different order would take a different amount of time. if each recipe has a set animation, why does it matter? or is something else going on?
Well the differences in time includes getting items, navigating the inventory, and if 1 or 2 items are needed. The difference between these is a few frames at most, but since there are so many recipes, it can create a huge difference depending on the order. Some orders will be very optimized compared to others
tldr menuing, sorts, and receiving items
Different items create different recipes, a lot use the same items in a different combination to create a recipe, and there is a finite amount of inventory space for the items. Obviously that requires buying items from shops and returning to Zess T to make them, but what combos would be the fastest? Which items should you buy first? Etc.
Has THE cooking route been determined yet?
I don't know much about this topic, but couldn't you use something like simulated annealing to find better roadmaps?
I don't know about simulated annealing, but if it is linked to the travelling salesman problem, then brute-force can be easily beaten.
Yo this kind of thing could be done with 70 and 120 ABC in SM64
I'd bet it already has, since there's only maybe 20 overworld locations to move between, and constraints on order. it's a much smaller graph. The real optimizations come from finding faster ways to get from A to B, and then those faster methods allow for a faster (and maybe different) overall route
Lol this is awesome, you can count on me
I'm having some trouble. Is there a tutorial on how to build the program? I'm struggling to do this on my own. And I hope I'm not too late.
Build? If you're on Windows, there's an executable that's ready to run.
If you can run Linux, then the README instructs you on how to build it on Linux (as well as how to build on Windows)
I think I may have gotten lost in the weds somewhere along the line, but why is 100k iterations the maximum? Wouldn't it just restart if the node you are currently evaluating is a higher total cost than the shortest path found to date? If the path you've taken has cost 4500 at this point there's no point to iterate past that, nonetheless to 100k iterations.
Edit: also is there a reason you didn't just tweak an existing traveling salesperson problem algorithm for crowd use?
this is basically traveling salesman, but it's more complex, since in traveling salesman the history does not impact the travel times.
here since the history alters the items in your menu, it matters.
and yea I'm sure there's lots of optimizations, the restart after 100k is bc the program searches a cluster of nodes near the bottom, so every so often it'll go all the way back up and check a different section of the tree
I'm not smart enough to understand this...this is rlly cool though ^^
Where's that comment with the currently best result
Ah yes good supercomputer
It probably would have been better to keep track of every single route taken and prevent routes from being traversed multiple times. If the routs had an inherent order, then a server could tell each client to do the next one. The server would also keep track of which routes before the one it is currently at don’t have a result, and after some time, sends those routes again. This way, this project would traverse all routes and would have an end point.
Also, why no BOINC?
Traversing all routes is not at all feasible. As Malleo said, there are more possibilities here than there are atoms in the observable universe, though the program in its current state likely noticeably improves this extraordinarily high number. Coordinating a list of already traversed routes to check with would use lots of wasted effort and time as by the time the TAS is made, I doubt any significant portion of routes searched by the time the TAS is released will be non-unique using the current program. Without knowing more details about what makes routes better, something which seems rather impossible, a decent search order cannot be determined, and if it could be, it would likely be done quick enough for this program to not be required. Predetermining a specific order the way you suggested would at least avoid the issue of multiple clients getting the same route and routes being skipped, but significantly damages the efficiency of the search, removing the current depth-first search algorithm's benefit of being able to check many neighboring routes very quickly by simply stepping back and stepping forward again in a different direction. I see no good way to do what you're suggesting without losing lots of time. Thus, searching through random routes is a great option, able to as quickly as possible have many computers searching many routes that are very likely new, and with no part of the algorithm relevant to the actual searching requiring communication with a server.
if there's around 1e60 routes, the chances of say having a duplicate route are less than one in a billion, so it's negligible waste. the time cost of checking against a list of billions of items is surely larger!
Hey can u help me how to tas Mario kart wii I know u made a tutorial 7 years ago but it doesn't work anymore can u help me out?
A bit late, but running. Just incase I do find it, I'm using the username Burley.
What is keeping multiple people running this program from searching down the same paths redundantly? Is it just the sheer size of the search space?
It is extremely unlikely a search space of this massive magnitude will have two identical, even two near-identical paths explored.
my best is at ~4270 frames so far, how bout you guys?
9/29 5:06 PM CST: 4261
9/29 5:16 PM CST: 4241
4225 after around 4 hours
Any way to use a video card GPU?
I right clicked the application and there was an option about running it with GPU, I don't know much about programming, not sure if it's functional
@Kotmaus (*I'm on PC) Click and drag the Recipiesathome.exe to desktop, right click, fifth option "Run with graphics processor". I don't know any of the details on how this works etc., just thought I'd help cause I spotted this
@@bird_man_birdman Your computer has two GFX cards. One on the CPU, and a dedicated one. This is very common on laptops. You're just choosing which adapter you want to use for doing any hardware accelerated actions. You'd want to run games on your dedicated GFX card. In this case, the program is CPU only, so opening with either adapter will have no affect on the performance.
This could probably be explained better, but I just got off work lol.
@@DannyTheVito I'm answering if this .exe is possible to run on a GPU
@@bird_man_birdman The code isn't written to be able to use a GPU for processing: what you're altering with that option is only the Windows setting for which GPU it *would* use for certain tasks if it was.
How long does a single simulation take on average?
each path is very very fast, probably microseconds, but there's literally more paths than atoms in our planet. Likely each path will also vary slightly and will vary based on your hardware as well
@@sage5296makes sense, I just wanted to make sure that they weren't performing simulations as well, which would be much more time and resource intensive.
Hi Malleo
So does this mean you've already optimized the route for collection of the ingredients?
Yeah, that's a lot easier to figure out since there are usually only a few places to get each item without going out of the way, and one of those options often stands out as faster.
the ingredients route is also mostly independent, so the two projects can be worked on at the same time without interfering with eachother
@@sage5296 Since it takes two trips, the ingredients route determines the starting inventory and different starting inventories results in different trees.
Putting 12/16 of my cores onto this, let's see what happens.
p.s. You should totally add the names of everyone who contributed a time to the server, whether or not it ends up being the fastest overall, to your credits. After all, it is a community effort.
p.p.s. you should see if you can make a "leaderboard" that shows us the current fastest time and who did it for funsies
@@moth.monster We now have a functional leaderboard system at recipesatho.me !
Couldn’t we just simply use infinitely a mystery gift and manipulate rng to get the recipe we want each time ?
ran this on my pc overnight, ended up with a roadmap of 4162... it's been 7 hours, not much has happened then
I have made this observation before, but it's interesting that the speedrunning/TAS community happens to have people that are good enough in the specific areas required to actually do this sort of stuff. There's no particular reason I can think of why people capable of understanding this problem (and designing the emulators) would happen to be in the community, and the same goes for the understanding of probability and statistics required to analyze Dream's results.
I'm not implying that they are particularly advanced skills (I know for a fact that analyzing Dream's results is taught at the advanced undergraduate level, and there are a lot of people that meet that level), but it's not something that one would expect from a group of people trying to play video games fast.
I think the most broad reason is math/gaming/speedrunning all sharing the same goal of dedication to solving a problem, and you could go further into things like autism or other disorders being correlated to internet communities in general.