Joined: 11/27/2004
Posts: 688
Location: WA State, USA
IIRC Bisqwit once said that using a quantum computer would only square root the time of brute forcing a TAS compared to a conventional computer or something.
Nach wrote:
I also used to wake up every morning, open my curtains, and see the twin towers. And then one day, wasn't able to anymore, I'll never forget that.
IIRC Bisqwit once said that using a quantum computer would only square root the time of brute forcing a TAS compared to a conventional computer or something.
...
a) You need to specify units, sqrt time doesn't make sense. Chances are, you meant there will be sqrt(original number of tries). Which would have a great effect on complex systems, and a not-so-great effect on simple systems (surprise).
b) sqrt is a relatively significant reduction in amount of work to do. 'Only'? :P
It's not really relevant though, because quantum computing is currently too slow and AFAIK it's not likely to get a big enough boost in speed any time soon for a quantum BisqBot to outspeed a conventional BisqBot. And it certainly won't be cheap enough for anyone here to buy for TASing til several years later.
My money's on conventional computing getting obscenely good at parallel processing before then anyways. Someone's gotta be working on computers with one or two powerful processors and like 20 simpler processors by now - properly programmed that sort of thing could be monstrously fast and still reasonable to build, I think.
Sorry if all that's been said already in other threads too, I don't remember any of them atm.
kwinse wrote:
Kejardon wrote:
Kriole wrote:
Samus is damaged by a Rinka in the opening.
That's a script action; no damage.
... it just dawned on me I know way too much about SM.
My money's on conventional computing getting obscenely good at parallel processing before then anyways. Someone's gotta be working on computers with one or two powerful processors and like 20 simpler processors by now - properly programmed that sort of thing could be monstrously fast and still reasonable to build, I think.
It's actually closer than you think. :)
The contemporary GPU technologies already allow cramming not 20, but hundreds of such "mini-cores" into one GPU, and you can have several GPUs in one PC as well. Considering that bruteforcing is hilariously parallelisable, maybe we can still reap some usefulness from that kind of approach.
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
The reason why sqrt would not be enough of an improvement, is because the number of tries involved is just too high. Something more like a logarithm would be needed. The NES has 8 binary inputs, which are read 60 times per second. If the shortest way through a game is 10 s long, a brute force search would need 8^600 tries, which is about 10^542 tries. The square root of this is the much smaller 10^271, but the number is still far too big. Let's say you had a massively parallel quantum computer with 10000000000 cores, each capable of testing as many possibilities per second. Then, the calculation would take 10^251 seconds, or 10^244 years. And that's with both massive parallelism and a quantum algorithm for NES emulation with a sqrt speedup.
Quantum computers do not help (and probably won't give O(sqrt) for this case anyway), and parallelism helps even less.
That's because a 10s segment is far too large. What can be played by hand will have to be played by hand anyway, and inputs that have no effect on the outcome don't even have to be included in the tests.
So, for instance, a 10 frame long luck manipulation segment where only left, right, down, A, and B make any difference, will take just a couple hours or so. For longer segments involving something other than that, heuristic algorithms that could consider usefulness of certain input will be necessary (however, if one is able to script such a bot, that would surely be enough to test the required action by hand, anyway).
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
The NES has 8 binary inputs, which are read 60 times per second. If the shortest way through a game is 10 s long, a brute force search would need 8^600 tries, which is about 10^542 tries.
Aside from moozoh's great point about the length of the sequence, and the number of useful inputs being far less than you assumed, most video games exhibit optimal substructure over any significant period of time (i.e., an optimal 10 second sequence will also be optimal in the first 5 seconds).
Optimal substructure can be leveraged by using dynamic programming to make the problem polynomial over the length of the input sequence, instead of exponential, as you assumed. If I were to hazard a guess, I think brute forcing a game with dynamic programming is probably close to feasible on current machines.
It's important to remember that "an optimal 10 second sequence will also be optimal in the first 5 seconds" isn't equal to "if you break the task into two segments 5 seconds each, together they will be equal to the optimal 10 second segment". In other words, if the first 5 second segment has a consequence in the second, the result will likely be suboptimal as a whole, which is pretty much the only reason there is little point in large-scale scripting as opposed to doing most of it by hand.
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
It's important to remember that "an optimal 10 second sequence will also be optimal in the first 5 seconds" isn't equal to "if you break the task into two segments 5 seconds each, together they will be equal to the optimal 10 second segment". In other words, if the first 5 second segment has a consequence in the second, the result will likely be suboptimal as a whole, which is pretty much the only reason there is little point in large-scale scripting as opposed to doing most of it by hand.
Right, which is exactly why you should use dynamic programming. If the optimal 10 second version always contains the optimal 5 seconds, then a simple greedy algorithm will work. If it may contain the optimal 5 seconds, then you use dynamic programming.
The whole idea with dynamic programming is that you break the overall problem into subproblems, which are easily solved optimally, and then combine the subproblems (which may be locally suboptimal) into a globally optimal solution.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
It is good to realize that some games will be helped immensely, others not at all.
One game that could be well optimized would be super metroid, if the optimal rout were decided on, each room could be brute forced and optimized individually. (with a few complicating factors).
I thought we were talking about brute forcing the entire game. Sure, if we restrict ourselves to short segments, and make other assumptions about which buttons have any effects (such assumptions will often prevent one from discovering unexpected glitches, by the way), then the problem is manageable.
ntclark: I don't get how this dynamic programming stuff is going to help. How would you use that to solve the first 10 seconds of super mario bros. 1, for example?
Discovering glitches through large-scale input bruteforcing is really infeasible. You would be much better off disassembling the game, understanding its logic and using your brain to abuse the weak parts and "create" glitches. I doubt bruteforcing would be faster no matter how powerful the computer was.
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
Brute forcing a whole game is neat in concept, but even with a quantum computer, it would still take a small eternity to do a whole game.
It would be able to do ever longer segments compared to what bisqbot can do now, but a whole game just has too many iterations.
ntclark: I don't get how this dynamic programming stuff is going to help. How would you use that to solve the first 10 seconds of super mario bros. 1, for example?
A Metroid-style game is a better example. Let's say you have 100 rooms in the game, each room takes ~4 seconds to get through, and the optimal path must go through 200 rooms. You might brute force each room individually using a smart branch-and-bound algorithm (i.e., using alpha-beta pruning, memoization, etc.) testing roughly 100 rooms * (2^8 inputs) ^ (4 s * 60 fps / 16 smartness-factor) = 1.33e38 possibilities. Then the collection of optimal rooms can be combined to find the optimal 200 room path through the game using a shortest path graph algorithm (e.g., floyd-warshall).
Compare to a brute forcing of the entire game: (2^8 inputs)^(4 s * 60 fps * 200 rooms) = 256^384000 possibilities.
Now clearly the dynamic programming approach is still not close to feasible, however, if we start making other assumptions, such as the optimal 4s second path through a room is composed of optimal 1 second paths, and ignore input combinations with start and select, we can reduce that to 100 rooms * 4 segments/room * (2^6 inputs) ^ (1s * 60fps / 16) = 1.4e15. If testing each of those combinations took 1 million cycles, then a quad-core 2 GHz chip would be done in ~3 days.
The assumption we've made here is that an optimal run of the whole game will consist of optimal runs of subsections of the game. The tradeoff is that the subsections have to be chosen small to prevent exponential explosion, but large enough to allow for local minima to be overcome. Techniques like this would never work for an entire RPGs, where local minima take forever to be overcome (e.g., I have to buy a potion 18 minutes before I need it (unless you explicitly define buying a potion as one of the primary goals of the path before it's needed)), but would work great for certain platformers (e.g., contra).
IIRC Bisqwit once said that using a quantum computer would only square root the time of brute forcing a TAS compared to a conventional computer or something.
...
a) You need to specify units, sqrt time doesn't make sense. Chances are, you meant there will be sqrt(original number of tries). Which would have a great effect on complex systems, and a not-so-great effect on simple systems (surprise).
b) sqrt is a relatively significant reduction in amount of work to do. 'Only'? :P
First of all, brute-forcing on a conventional computer is exponential in the number of frames; if you have n buttons, any combination of which can be simultaneously pressed, then there are 2^nt possible runs of t frames, so finding the smallest t for which a run attains the end goal (i.e., TASing) by brute force is also exponential, requiring at least 1+(1-2^nt)/(1-2^n) cases to be checked, which is O(2^nt). Therefore, a quantum computer could brute-force it in O(2^(nt/2)), which is still exponential.
I am happy that such thing can't happen soon.
What would be a movie without its part of humanity?
And what would be the goal of this site and its active community if all movies could be made "perfectly"?
It would be pointless and the site would die.
I am not dreaming of such tools. In fact, I am dreaming it WON'T exist for the sake of future generations of tasers.
