Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
I would love to see "Creepers" TASed. It's a relatively unknown game from the early 90s, one of the last made by Psygnosis before they were bought by Sony. The style is somewhat like "Lemmings", but with caterpillars instead.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
Warp wrote:
Blue Streak wrote:
Given the exponential growth of computing power
I'm not so sure that computing power is growing so "exponentially", but even if it did, it wouldn't really be of so much help to us.
For what it's worth, calculations per second per $1000 has experienced exponential growth over the past century according to one of Ray Kurzweil's graphs: http://www.singularity.com/charts/page70.html.
True brute-forcing is probably going to be infeasible, but we can simplify the problem by considering it as a set of smaller identical problems. Taking, for example, thirty frames, one could compute which combination of button presses starts Mario at rest and moves him the largest number of pixels to the right in that amount of time. In principle one could build a library of such smaller movement optimization problems (a database of position and momentum changes) and chain them together as needed throughout the route, rather than solving the same problem each time Mario is in that situation. Mathematically this would be trading time for space since you'd need to store more data, but that might be an acceptable tradeoff in general since it's cheaper to search a database for the aforementioned sequence than calculate it from scratch each time. Search times often scale logarithmically in size, and polynomically at worst.
Certainly none of this would be easy to do, but TASing has been around long enough that the trial and error methods of human players yield highly diminished returns for many classic games (improvements now often consist of a handful of frames). This is could be an opportunity to enter a new, smarter era of TASing by having individuals or small teams program optimization algorithms for games rather than endlessly rerecord frames. It might also yield a plethora of new glitches since it would be an exhaustive exploration of the game mechanics.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
A fascinating new paper describes the difficulty of Mario, Donkey Kong, Zelda, Metroid, and Pokémon games from the perspective of their computational complexity: http://arxiv.org/abs/1203.1895.
The primary conclusion of the paper is that the intended set of gameplay mechanics in these games places them in the class NP-hard. Without getting into the details of what this means, it is a technical way of saying that, based on very general principles, there is probably no algorithm that can efficiently find the optimal solution to these games (where "probably" refers to the prevailing opinion of computer scientists on important open questions that impact this result, such as P versus NP).
This has important implications for the future of TASes, where ultimately some algorithm must exist that solves these games optimally. In the introduction, the authors even mention tool-assisted speedruns as the motivation for this study.
There are of course various caveats impacting this result in favor of easier solutions, one being that a proof of P = NP would make the efficient solution of these games far more likely. Another is the fact not all NP-hard problems are unrealistic to solve, it's just that the solution time becomes more and more sensitive to the size of the problem. Thus, while the existence of block puzzles in Zelda forces a certain level of complexity upon the algorithms required to solve the game optimally, some block puzzles are far easier to solve than others in terms of the number of possible moves and configurations. It may be that those actually implemented in the games are simple enough that they can still be solved exactly without taking a million years of computer-time.
A third caveat is that there are still open questions about quantum computers. While the computational power of quantum mechanics as currently formulated is known, it may be that a complete theory of quantum gravity requires a modification to quantum mechanics that increases its computational power. Such a possibility also would make the efficient solution of these games more plausible, although it would also require us to have quantum computers in the first place.
A final caveat is that this result doesn't account for the multitude of broken game mechanics that are known to exist (glitches, sequence breaks, etc.). So the problem of determining perfect play within the intended mechanics is almost certainly harder than one that allows various puzzles to be skipped, although finding the set of all possible glitches is another challenge in itself.
Given the exponential growth of computing power, along with various open theoretical questions, and the fact that games can be broken in many ways not intended, there are reasons to believe that there is a path towards the ultimate optimization. It would be a fascinating exercise to analyze even small sections of the existing level design to see if one can prove that a certain combination of moves (and even button presses) is optimal.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
I implicitly meant that "must be entertaining" is an objective, although perhaps that was not how it sounded.
What it means to "break a game" is rather ambiguous to me. I assume you mean things like sequence breaking as not being the main goal of the movies on this site. In that case I can agree, because there are plenty of movies that don't. However, I personally consider a movie like Acmlm's Tetrisphere as "breaking the game" even though it appears to play by all the game's rules.
In any case, I don't think I fundamentally disagree. Personally I think it would be interesting to produce a movie that approximates the optimal intended playthrough of Sonic 3 and Knuckles, but I'm biased towards thinking just about everything regarding this game is worth doing. =P
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
The goal of this site is generally to showcase how a game programmed by sub-optimal programmers can be played by an optimal human with certain objectives.
If I understand what is being requested in this topic, it is simply a run that shows how a game programmed by optimal programmers would be played by an optimal human given certain objectives.
It is generally obvious what this is in the context of S3K. The set of legal moves is well-defined, as are the intended possible routes through the levels, and there are no bugs that inhibit the intended play (except for the Tails level-wrap death bug in Icecap 1). Undoubtedly there'll still be some ambiguity though (for instance, is calling Tails to respawn early an intended action, or a bug?).
In principle, any well-designed game could have such a category on this site. Such videos would be essentially unable to be further improved once made if lowest completion time is still a primary objective. But they also would redefine the purpose of the site to also show "idealized playthroughs" instead of just "speedruns", which may not be desirable.
I really do understand and appreciate the point of this though. On many occasions I have watched playthroughs on Youtube of games that I'm interested in experiencing as intended by the designer, yet I do not want to take the time to buy and play myself. Sometimes it is frustrating that a human is still the one playing the game, whereas this concept removes the ability to fail or waste time.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
wuschelbeutel1 wrote:
This probably sounds dumb (I don't know much about CS & math) but why is it not viable to use a brute force backwards induction method. Doesn't the complexity rise linearly that way?
Let's say we consider Mario Bros.. We start at the last controllable frame of the game, try every possible input combination (or those that make sense), find the fastest one, then use that and go back one frame - rinse and repeat. That way all the games should be solved relatively quickly...or where do I go wrong?
I can see where you think the linear complexity comes in. Let's say that there are 20 blue spheres and that each of these 20 could be the final one, but let's just pick one to be the final for now. There are then 19 different paths from a blue sphere to our final blue sphere. We would determine which of these is quickest and then go to the next step back, which would contain 18 possible ways to get to sphere 19. Of these 18, we'd again find one to be the fastest and go back another step along that path...and so on to the beginning. This is exactly identical to solving the problem in the forward direction by finding the next closest sphere (which I will henceforth call the nearest-neighbor method).
But the problem is not that simple. There are plenty of instances in TASes when seemingly suboptimal choices are made at a given time in order to yield a faster outcome later. In general there could be a path that is larger than the optimal one at some step which actually leads to a series of much smaller steps. The following two images show a sample traveling salesman problem with the starting point at A (we can ignore the need to return to A at the end). The first one always takes the path to the next closest point, yet this is suboptimal when compared to the second version (even ignoring the last step). If this is visually hard to see you can try aligning the arrows in a long row.
So we cannot solve the problem optimally by strictly finding the quickest time from one blue sphere to the next and taking that move as the next step. It is possible that this nearest-neighbor method actually does yield the optimal solution, but in general it will not, and therefore we must test a far larger space of possibilities that makes the complexity scale exponentially and not linearly.
You may wonder if the fact that the problem is restricted to a rectangular grid that wraps simplifies the problem in a way that makes the nearest-neighbor method always optimal. I would conjecture that it does not, although I don't have a proof of that at the moment.
On a related yet important note, even if the optimal solution was found using the nearest neighbor method, there are higher-level rules in the game that would make the solution wrong. One example of this is turning blue spheres into rings.
Let's say Sonic is in the position shown above. The shortest move to a blue sphere is to walk straight forward, so that would be move one. There are then three blue spheres at equal distances that can be used for move two, but because turning takes extra frames we would say that the sphere directly ahead is the next fastest one to reach. However, we know that it's quicker in the long run to go to either the left or right sphere and go around the perimeter turning them all into rings.
If a system had no knowledge of this rule and used the nearest-neighbor method it would find the wrong answer. Thus, we have to input some knowledge of the higher level system mechanics into a special stage solver. This is a real blessing computationally for us because we can be reasonably confident that we know the fastest solution to any enclosing pattern of blue spheres, although it's still a problem to figure out where the optimal entry and exit points occur in the formation since these depend on what happened previously what's left to do in the stage.
So in summary, a sequence of local optimizations does not necessarily give us the global minimum and the presence of higher-level rules requires us to compute optimal solutions for larger substructures of spheres. The first condition makes solving this a pain in the ass, but the second is a real gift because we can use our complete knowledge of the game's rules to simplify the problem somewhat.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
According to Wikipedia, a lot (if not every) restrictive case of the TSP is still NP-hard, including the Euclidean version. I think trying a branch-and-bound approach (as I suggested at the end of my previous post) is reasonable, especially because humans have an interesting way of being able to find close to optimal solutions by eye to give us an upper bound in this problem. The toughest one will be n=144 though; that's probably still unreasonable with a branch-and-bound method.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
Warp wrote:
The traveling salesman problem is NP-hard, but finding the shortest path in a graph is not. http://en.wikipedia.org/wiki/Shortest_path_problem
The difference between TSP and the shortest path problem is that the latter doesn't have to find a route through all nodes, only a route from node A to node B.
What makes finding an optimal solution to a game hard is not the complexity of the algorithm, but the size of the graph. Even though the shortest path searching algorithm might be polynomial-time, the size of the graph is exponential (each node splits into n new nodes, so the number of nodes grows exponentially as you advance), so it doesn't really help.
Let's ignore the effects of the actual spheres for the moment and consider just points. We can phrase the entire problem thus: On a 32x32 grid G (containing 1024 nodes), find the shortest path from node A (the start) that passes through n particular nodes at least once (where n is the number of blue spheres). We can't easily define where the last node is because we don't know on which node the optimal path ends, but unlike the TSP, we are not required to return to node A and so this problem requires one less step than that problem.
For the first step there are n possible nodes on G to approach (because we only care about paths that lead to a blue sphere). We can divide this step into n shortest path problems on G. The shortest path problem itself is quite easy in the ideal version of the problem because we know its solution already. Since G is a rectilinear grid we know that the shortest path to a node having coordinates {x,y} relative to the previous node is x + y units in length. The maximum value of x + y is 32 since G wraps and no node can ever be more than 16 + 16 units away. We define this x-by-y region to be R. If we assume that there is no back-tracking in our motion on R and that all moves are directed toward the desired node there are actually (x+y)!/(x!*y!) shortest paths of identical length (draw a grid and test for yourself if you'd like). However, in the real problem every turn costs us frames so the two paths along the edges of R that turn only once are actually the optimal paths. In any subsequent mention of "shortest path" I mean that which requires the fewest frames.
After completing a given path there are n-1 nodes left to travel to, so we have to repeat the shortest path procedure above. Thus the problem amounts to computing n! shortest paths, meaning that we compute the shortest paths between all possible pairs of the n nodes on G. However, after knowing all these paths we have to find the sum of the n shortest path problems that is the smallest. So we have to compute n! sums and keep the smallest value.
Ultimately that should be our answer in the idealized version of the problem, but we also have to consider lots of other things. Often there won't be two identical shortest paths, but one that is more complex to calculate and the frames spent turning on a blue sphere at the end of a segment to position Sonic for the next segment must also be considered.
Sometimes the shortest path between two spheres will be greater than x + y units because the positioning of bumpers, catapults, and red spheres is such that you can't find a sequence of turns that gets you to the next blue sphere in x + y steps. Or, the number of turns would be so many that the frames lost in turning would be gained in a somewhat longer distance but overall faster route with fewer turns (this would have to be tested). This also includes the use of bumpers to make you go backwards.
Futhermore, the problem gets worse because taking different paths through the blue spheres will mean that the state of G during each shortest-path calculation is different (i.e. some blue spheres will already have been turned to red spheres or rings depending on the prior paths taken). You'd have to compute the shortest path for all possible states of R between Sonic and the next blue sphere. For k blue spheres present initially upon R, there are 2^k possible states that they could be in, and technically more than that since some could be either rings or red spheres after being touched. So when computing the sum of the shortest paths in the final problem we're required know which of the at least 2^k different states that R is in given the previously taken paths and this will affect which path is actually the shortest. In theory we'd then have at least ((x+y)!/(x!y!))*2^k possible paths to test for each step and then know which of 2^k values to use for each step of the n! sums.
This sounds terrible for us, but it's important to remember that paths with fewer turns are greatly preferred and so these are far more likely to be the shortest paths. The problem is that we have no way of knowing a priori that these paths are definitively the shortest ones and so we have to test the others too. However, there is another saving grace: Sonic can't turn on red spheres, so any possible path that requires turning on a point labeled "red sphere" can be disregarded as a possibility.
What are we left with? A real mess, mainly because there's no way of knowing in advance with absolute certainly how two complete sequences though the n blue spheres compare to each other without actually calculating them. However, we may be able to place some restrictions on the calculation of n! sums to make things easier. You can't guarantee that always selecting the next closest blue sphere after completing each step will lead to the optimal answer, but you can be quite confident that always choosing the sphere farthest away will not produce the optimal answer. Thus, we can start by computing what is likely one of the shorter routes by always choosing the next closest blue sphere, and we can now use that solution as an upper limit. Any branch of sums that exceeds that length at some point along its calculation will get cut off, so we eliminate a lot of the possibilities this way. Also, if we are eliminating the longer routes between spheres in this way, then that means that we may not have to do shortest-path calculations for the spheres farther away, which of course would greatly improve the feasibility of the computation.
So the best approach is probably one where we input human knowledge of a "good" solution and then use that as an upper-bound on the problem. Start by calculating a given shortest path, add it to the sum, calculate another shortest path, add it to the sum, etc., and eventually the combination is likely to exceed the length of the known solution, at which point any sequence branching off from that point will truncate and a different sequence can be initiated at a previous step. Sorry for the tl;dr post.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
I'm glad there's a topic about taking an algorithmic approach to TASing. I recently thought about trying to write a bot that finds the frame perfect solution to each of the 14 special stages in Sonic 3 & Knuckles. However, I don't actually know that it's doable because the problem is a more complex version of the rectilinear traveling salesman problem (TSP). The TSP itself is already in the complexity class NP-hard, which means that there's no algorithm for solving it in a reasonable amount of time for all but the smallest values....unless I buy a quantum computer. I don't even know if the approximate solutions are tractable with the computing resources I have access to.
Joined: 5/5/2007
Posts: 12
Location: Mesa, Arizona, USA
Spencer Nilsen wrote the American Sonic CD OST and I think that it is absolutely brilliant (I also love his Ecco stuff). However, the decision to replace the soundtrack in this game is one of the most divisive issues in video game music history. People still argue today about whether the Japanese or American one is better.
So we cannot solve the problem optimally by strictly finding the quickest time from one blue sphere to the next and taking that move as the next step. It is possible that this nearest-neighbor method actually does yield the optimal solution, but in general it will not, and therefore we must test a far larger space of possibilities that makes the complexity scale exponentially and not linearly.
You may wonder if the fact that the problem is restricted to a rectangular grid that wraps simplifies the problem in a way that makes the nearest-neighbor method always optimal. I would conjecture that it does not, although I don't have a proof of that at the moment.
On a related yet important note, even if the optimal solution was found using the nearest neighbor method, there are higher-level rules in the game that would make the solution wrong. One example of this is turning blue spheres into rings.
Let's say Sonic is in the position shown above. The shortest move to a blue sphere is to walk straight forward, so that would be move one. There are then three blue spheres at equal distances that can be used for move two, but because turning takes extra frames we would say that the sphere directly ahead is the next fastest one to reach. However, we know that it's quicker in the long run to go to either the left or right sphere and go around the perimeter turning them all into rings.
If a system had no knowledge of this rule and used the nearest-neighbor method it would find the wrong answer. Thus, we have to input some knowledge of the higher level system mechanics into a special stage solver. This is a real blessing computationally for us because we can be reasonably confident that we know the fastest solution to any enclosing pattern of blue spheres, although it's still a problem to figure out where the optimal entry and exit points occur in the formation since these depend on what happened previously what's left to do in the stage.
So in summary, a sequence of local optimizations does not necessarily give us the global minimum and the presence of higher-level rules requires us to compute optimal solutions for larger substructures of spheres. The first condition makes solving this a pain in the ass, but the second is a real gift because we can use our complete knowledge of the game's rules to simplify the problem somewhat.