Hello,
I have been a lurker here at TASVideos since "the beginning" and what is most interesting to me are glitchy runs (game glitches and abusing programming "errors") and ways to automate game input (bots/genetic algorithms/etc). I really hope I am not starting a new thread on something that has already been discussed, but I could not find anything on the subject either.
Brute forcing a complete game is out of question measured in today's processing power, however with some smart algorithms (way over my head) and the combined processing power of "TAS volunteers" - wouldn't it be possible to make movies even more perfect? Perhaps also discovering game glitches yet unknown?
I am thinking we/you could start something similar to SETI@home (http://en.wikipedia.org/wiki/SETI@home) where each volunteer would download a batch containing input to process and to maybe discard or rate and upload based on some fitness?
Another option I guess could be to use some cloud service, but that seems rather expensive when we probably have already a lot of unused CPU at our hands.
Please let me know what you think. Is it doable or just plain stupid?
I am excitingly awaiting your feedback =)
/crollo
I wouldn't mind to run a TAS@home program on my computer, as long as it can properly handle multi-core processors. The last time I tried SETI@home and other @home things they had poor support for multi-core processors and ran on only one of my cores.
Brute forcing a complete game is out of question measured in today's processing power
Even measured in the theoretical processing power of the whole universe, it's way too much. The math has been done a couple of times, brute-force-TASing will never ever work.
This means that for every single game, we need to check whether the game is suitable for botting, write a game-specific bot and run it. The specific algorithm that works for the game may or may not be suitable for parallel or distributed computing.
If you end up creating such a bot, and need more CPU power, then I'm sure there will be enough volunteers to help. But a generic framework is likely useless since we'll never have a generic bot. All we can do is handle a few special cases.
It's understandably difficult to grasp how much processing power a brute-force approach would require, and why simply throwing more computers at it will not solve the problem. This is because exponential growth is hard to grasp.
Assume we have a console with one single button to play the game, and the only decision at each frame is whether to push the button or not. This means that at each frame we have only two choices.
I'll just skip all the boring mathematical details, and go right to an example: Assume that we have a million computers, each capable of testing a million combinations per second. How long would it take them to test all the possible combinations for 60 frames (ie. a one second segment)? Answer: Approximately 13 days.
Doesn't sound really bad, does it? Well, how long would it take for them to test by brute force a 2-second segment (ie. 120 frames)? The result might be a surprise: It would take over 40 thousand million million years. Doubling the number of computers would only halve that time.
And this was with a hypothetical console with one single button. Now consider that eg. the NES has at least 6 buttons (more if you count the start and other buttons).
Thanks for your feedback. What I had in mind was actually very specific games that would be near impossible to improve without randomization (or maybe "thinking out of the box"). For example SMB1 (not very random choice) we have pretty clear checkpoints set out for us:
* Enable stage clear flag for level 1-1 (or how the game knows you have completed it) as fast as possible "in any possible way".
* Enter warp zone in 2-1 as fast as possible.
* Etc.
I guess we more or less could disable left button on the D-Pad along with Start/Select and so on in order to minimize number of possible combinations. Now again that kind of disallows for finding weird glitches where you press Left+Right the exact frame you enter a pipe (for example).
As you probably understand I have not completely thought this through, but I was hoping to get you guys thinking in this direction in order to see if it has any potential at all. Maybe you could even utilize the multiprocessing power of today's GPU's as well.
One problem is how to know the current input has produced a wanted glitch, since we do not really know what to look for (since the result would be unknown if the glich is unknown). However, this video has proved that genetic algorithms can in fact produce these kind of findings:
http://youtu.be/c7xJNAJys2s?t=2m56s
Maybe I could attract some Bisqwit mastermind attention with that Megaman vid ;-)
It obviously doens't work for any complex games.
One application would be puzzle games perhaps. Like Kwirk (http://tasvideos.org/1501S.html). Here you could reduce the actual game to a much simpler model. Most of those levels have like below 50 steps. With walking only possible in four ways and often less if you stand besides a wall or something, there are relatively few possibilities to check. Most of those levels have subgoals too, where you have to sink a block somewhere. So steplength to (sub)goal reduce even more.
I found 2 optimisations to Kwirk while trying some levels by hand: http://tasvideos.org/forum/viewtopic.php?t=8667&start=40.
Qblox (http://www.google.de/search?q=qblox&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:de:official&client=firefox-a&source=hp&channel=np) is another game that's quite easy to write a solver for.
However many of those solvers need pretty big RAM and not-computing power, which would make them pretty good distributable over many computer.[/submission]
For example SMB1 (not very random choice) we have pretty clear checkpoints set out for us:
Still, those checkpoints are too far away from each other. Sections longer than a second are impossible to brute force.
crollo wrote:
I guess we more or less could disable left button on the D-Pad along with Start/Select
SMB needs the left button for several tricks, like fast acceleration or glitching through walls.
Not that removing two or three buttons would help much: Warp has already demonstrated that even 2 seconds on a 1-button-gamepad isn't possible.
crollo wrote:
I was hoping to get you guys thinking in this direction in order to see if it has any potential at all.
We already did. Several times. Laws of physics won't comply with the ideas.
Writing a bot for a game is very difficult, it's a lot of work, and it takes a good understanding about programming, complexity, algorithms and data structures. And even then, it's often physically impossible.
Pitching an old idea as new and throwing around buzzwords like distributed computing or GPU offloading does not solve any of these problems.
thommy3 wrote:
[..]Kwirk[..]
You've linked the thread where a bot has been attempted. Apparently it went nowhere. Despite lots and lots of manual optimizations, the amount of CPU/ram required would have been too much on the longer levels.
Why do you think it'd work this time?
Also check out Lunar Pool. This is as simple as it gets for a bot: pick angle and force, fire. Repeat one or two times, end level. Thus you have very short levels, and only a few frames of input that matter during each level. And yet it had to use lots of heuristics to finish in a reasonable timeframe..
Stop dreaming, people. Bots are tools that may be useful in some limited circumstances. They're not the solution to TASing, nor can they replace TASers, nor will a generic bot ever be able to finish a game on its own.
I have seen the Lunar bot and wouldn't that exactly be a valid scenario for this case? Wouldn't the outcome have been better if more processing power was available?
Why is there always so must hostility on these forums? Makes new members not wanting to participate since so many of you seem like self-appointed geniuses (and I bet many of you really are).
Well, I still hope for some open-mindedness...
I don't think that these forums are hostile to new users. We may be a bit hostile to people who try to revive a topic that we've already discussed, without in the process adding anything new to the discussion. But we do that to everyone, old and new alike.
Tub's point is that a generic TAS bot would never work because of the combinatorial explosion of possible inputs. Bots have, thus far, only been used in heavily-constrained situations:
* Lunar Pool, where only two inputs were needed for each shot
* Some Mega Man 1 runs abused a glitch in Wily 2 where Megaman's position was influenced by Cutman's cutter boomerang. A bot was used for dealing with the semi-random motion this caused, though I don't feel like reading the source code to figure out exactly what it did.
* Generally, searching for a specific RNG seed the TASer knows is desirable, by iterating a pre-set selection of techniques for advancing the RNG.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Tub, Derakon
This is nothing but hostility in my book:
"Pitching an old idea as new and throwing around buzzwords like distributed computing or GPU offloading does not solve any of these problems."
If you think I'm after some kind of fortune and fame I guess you have too high of an IQ but lacking EI completely (Asperger syndrome?). Feel free to ban me or whatever measures are needed - I am completely fine being an anonymous lurker.
While you can read hostility into it, I really don't think it's there. There's a difference between bluntness and hostility. If you have ideas for how to solve the very real issues that have been mentioned, then we'd love to hear about them.
Of course, then you go and accuse us of having Asperger's syndrome. That is hostility. I mean, if you want to be banned then I'm sure that the mods can oblige you, but there's no need to resort to that kind of behavior otherwise.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
crollo: I agree that your reception has been a bit harsh. While a massively parallel bot will still not be able to brute force more than a handful of frames, I am sure there are interesting things that could be done with a parallel bot which is too slow on a single core, and I would therefore welcome even a simple demonstration of an MPI parallel lua script if you are interested in making one. Just be aware that this won't make the process of writing a useful bot any simpler - it will just make that bot more powerful.
As others have pointed out, the bot will have to make enough assumptions to get its scaling down from O(exp(n)) to something more manageable for this power to be of use, and those assumptions will make it hard for the bot to discover things we don't already know about. But if you put enough effort into it, I am sure it is possible to make something worthwhile. Our tool-assisted laboratory forum is far too quiet for my tastes, so don't give up!
Well, you can call it whatever you like. It was exactly because of this weird mentality I hesitated to join in the first place. I like the creative work but most of the community need to get over themselves. It's like watching 10 "Napoleon Dynamite guys" argue with eachother and I do not want to be part of that.
When it comes to the practical issues of course I do not have a solution. I'm not a rocket scientist like the rest of you (OK, I admit I pushed it too far already ;-)
I have seen the Lunar bot and wouldn't that exactly be a valid scenario for this case? Wouldn't the outcome have been better if more processing power was available?
Yes, it potentially might have been. But a radical improvement to the movie's length can only be made by fundamentally changing the algorithm. The current algorithm works by a "greedy" principle where the best benefit now is chosen even if it complicates the situation for the next shot. A better algorithm would settle for a less optimal outcome now if it gets a superb result on the next round (but still somehow avoiding the pitfall of ever forgoing the prize in favor of the things to come). But such an improvement would require elevating the runtime cost by an exponential degree. Still, it would have been doable, if I had access to like 20000 computers on which to run the bot for 6 months. But that kind of resources are not found within the TAS community, and I think there are more worthwhile uses for those resources anyway.
_________
Speaking of which, now that I have created my own emulator, I have to see, some day, if I can run the bot faster on that emulator than I did on FCEU. Probably not, because I used a synchronous architecture, but I must test it anyway.
But I feel I need to point one thing out (before I might be a goner); my "plan" was not necessarily to use multithreaded processing on a single computer, but to suggest some infrastructure where the run with the best fitness from a batch would be used as a seed or whatever it is called for the next batch. Many clients would then help produce these results which would hopefully result in the best "evolution" (as with humanity or something). Compared to a single computer this ought to be superior unless the traffic required would make it useless since you need new generations very frequently or something. I admit I have much reading to do when it comes to genetic algorithms, but the dream scenario would be where you could just download pre-defined processing tasks - for example beating Airman - from TASVideos.
My programming skills put food on the table but that's much easier stuff. I don't really have the time nor the skills, but I wouldn't mind sharing some computer resources. That's all I wanted to say. Not that it's new or groundbreaking or even doable.
You only need 19999 more computers since I'm on :-) And I bet most of the community both has the processing power and the will to help out.
What if you have a 30-60 frame segment that needs to be optimized? Getting RAM address X to value Y (altering RND) in as few frames as possible like when you wrote a small bot for some scenario I think it was in Elecman stage. Perhaps those tasks are already fast enough on a single system, but maybe frame count could be increased?
The server could then pre-create input for the clients to test out. The file could contain everything needed like savestate, an array of input (well, multiple arrays) and the result wanted.
So basically these are the two scenarios that came to my mind.
Everyone is so fixated on the term "brute-force" here. If I even remotely understand what crollo is saying, he's not suggesting creating a framework for brute-forcing various games; he's suggesting that we combine our resources to run heuristic algorithms instead of just using our own computers. I personally think this is a good idea, although I'm not sure how high the demand would be for it. How often do people write bots for TASes that take days to process? I honestly wouldn't know. If you want to put time into writing the program, I'm sure it'd find some use, but I doubt many people would be willing to make the same investment unless the demand is much higher than I would assume.
Also keeping in mind that if your expected runtime for a singlethreaded program is only a few days, it might well be easier to leave it singlethreaded than it would be to go to the work of figuring out how to split the job up into sub-jobs to farm out to separate threads, let alone to send to remote machines.
Lunar Pool is a situation in which a server farm could have paid off, since it took months for the job to run on just Bisqwit's computer. But those kinds of situations are currently, I suspect, the exception rather than the rule.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Everyone is so fixated on the term "brute-force" here. If I even remotely understand what crollo is saying, he's not suggesting creating a framework for brute-forcing various games; he's suggesting that we combine our resources to run heuristic algorithms instead of just using our own computers. I personally think this is a good idea, although I'm not sure how high the demand would be for it. How often do people write bots for TASes that take days to process? I honestly wouldn't know. If you want to put time into writing the program, I'm sure it'd find some use, but I doubt many people would be willing to make the same investment unless the demand is much higher than I would assume.
I agree, and I've been biting my tongue because I don't have much to add to it. I've even had similar ideas in the past, but didn't bother bringing it up because it would amount to, "Hey guys! Here's something we can do but no one will!" "Hey Bobo! Yeah, that's a great idea we'll never implement!"
Derakon wrote:
Also keeping in mind that if your expected runtime for a singlethreaded program is only a few days, it might well be easier to leave it singlethreaded than it would be to go to the work of figuring out how to split the job up into sub-jobs to farm out to separate threads, let alone to send to remote machines.
Lunar Pool is a situation in which a server farm could have paid off, since it took months for the job to run on just Bisqwit's computer. But those kinds of situations are currently, I suspect, the exception rather than the rule.
I'll mildly disagree with your first paragraph. Yes, if we want this to be its own stand-alone compiled program that runs on tens of thousands of computers to "solve" a game, it would be too much trouble and will never happen. (Not to mention we'd never find enough people willing to run it. "Download TAS@home! We swear it doesn't have a virus in it!") On the other hand, if you just have a straightforward bot in Lua and just want to increase your processing power tenfold, that should be very easy to do, depending on the game and the bot. A well-programmed bot for certain games should just take an integer as its input, then run through all integers to find the optimal solution (if not, most bots should be adaptable to that method). At that point, it's just a matter of dividing up the parameter space accordingly, then distributing appropriate versions of the bot to the users. The only difficulty would be getting everyone to consistently run the program and report back every day, but I suppose others could pick up the slack for one or two no-shows.
I think Lunar Pool is a great example of how it could work. We'd divvy up the parameter space (shot directions and powers), then have each computer analyze the results only for its shots. Any overlap would be minimal.
Another example would be my Where in Time is Carmen Sandiego bot (*raises eyebrows suggestively*). I was only able to analyze the strategy for each level to a depth of 1, which-- long story short-- meant quite a few levels were beaten in four turns instead of three, two, or one. This is what bisqwit called a "greedy algorithm" for Lunar Pool (I don't know if that's the formal name for it, but I instantly knew what he was talking about when he brought it up). With a network of a few dozen computers, I could probably bump the search depth up to 2 or 3 and shave another twenty minutes off the run. Gosh, do you think it'd be accepted if it were faster???
Everyone is so fixated on the term "brute-force" here. If I even remotely understand what crollo is saying, he's not suggesting creating a framework for brute-forcing various games; he's suggesting that we combine our resources to run heuristic algorithms instead of just using our own computers.
You make it sound like coming up and implementing a good heuristic algorithm for solving a game would be easy. Or that making it distributed is trivial.
I'd say that in the vast majority of cases by the time you have developed, implemented, fine-tuned and run your heuristic to solve the game, you could have made a TAS of the game in the traditional manual way, and probably better than your heuristic ever could. (And this assuming that the heuristic is easily parallelizable, which isn't a given.)
Coming up and implementing a good heuristic is in itself a hard task. Making it distributed can be even harder. In most games the actions you take earlier in the run will affect the outcome of later parts of the run (the most common and obvious case is the RNG, which can be greatly affected by even one single button change in an earlier part of the run). This means that usually you can't simply give level 1 to one computer, level 2 to another, and so on.
Another possible approach is that each computer starts from the beginning, but starts searching for one possible branch (eg. computer 1 starts with running right, computer 2 with a jump to the right and so on). The problem with this is that such search branches can end up in the same states, after which they will perform the same searches as other computers are already doing, thus needlessly doing the same tasks. Communicating between computers (especially over a network) to avoid duplicated search branches can be overwhelmingly slow.
And of course all this must result in a better run than a human could do in a reasonable amount of time (which isn't a given either), or else the whole project will be completely moot.
I like what I'm seeing here - that you actually start finding possible areas of implementation. Still not saying you hadn't thought about this before or that it's my idea.
You are correctly assuming I was never suggesting a brute-force method but rather very specific methods per game or scenario/problem. English is not my native language and I might express myself in a way which might be hard to understand sometimes. When I said brute-forcing was not possible with current processing power I was in fact including distributed processing as well.
I don't suggest to replace you competent TAS:ers with some bot either, but rather trying to come up with some idea where more people could help making the runs as perfect as possible. Only problem is that we can never know that this game is 100% complete without trying every possible combination - right?
Maybe "TAS@home" won't keep people interested due to that fact, but I don't see why people would assume it contains virus or something if the download is hosted on TASVideos.
English is not my native language and I might express myself in a way which might be hard to understand sometimes.
From what I can tell, your English is immaculate and I have had no trouble understanding you. Other people, however...
crollo wrote:
I don't suggest to replace you competent TAS:ers with some bot either, but rather trying to come up with some idea where more people could help making the runs as perfect as possible. Only problem is that we can never know that this game is 100% complete without trying every possible combination - right?
To repeat myself, yes, it would be helpful for certain parts of some games. For example, I could have a distributed computing version of my Carmen Sandiego bot up in a matter of hours. The only problem is that no one would care. Other games and small portions of other games could also be botted in this way.
crollo wrote:
Maybe "TAS@home" won't keep people interested due to that fact, but I don't see why people would assume it contains virus or something if the download is hosted on TASVideos.
I wouldn't want to download any executables from this website. I like the TASes you guys produce, but as for trusting you enough to put a .exe on my hard drive? Nahhhhhhhh...
I'd stick to Lua scripting. Anyway, it's hardly relevant because there is no such program and I doubt there ever will be.
I wouldn't want to download any executables from this website. I like the TASes you guys produce, but as for trusting you enough to put a .exe on my hard drive? Nahhhhhhhh...
What about the emulators? How can you TAS without downloading an emulator in the first place? If you trust the emulator (since most if not all of them come from this website) you can trust the TAS@home program.
Or, did you download the emulator source code, checked it all to see if it's malicious, and compiled it by your own? Very well, ask the TAS@home to be open source (and multi-platform too while that we're at it) and compile it too by your own.
I don't see the problem, you say you don't trust this website, but your logic doesn't work.
