Difference between revisions of "What is a speedrun?"

Revision as of 23:59, 8 May 2014

Introduction

Whether people realize it or not, there is an ongoing debate about what it means to "speedrun" a game. This is most evident through comments on media articles detailing events or significant records, where a chorus of voices are willing to cry foul or otherwise about the runs at hand due to use of glitches or otherwise. Regardless of the state of speedrunning or how many categories exist for a given game, arguments for or against typically go in circles because it is a battle of subjective opionions versus subjective opinions. This article attempts to take an objective and scientifically-focused approach to describing what a speedrun is and to justify why runners play the way they do. A brief summary is included at the end of each section to appease any TL;DR complaints.

Optimization Problems

To borrow from wikipedia a bit:

"In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete variables is known as a combinatorial optimization problem. In a combinatorial optimization problem, we are looking for an object such as an integer, permutation or graph from a finite (or possibly countable infinite) set."

In other words, given a set of available tools, one attempts to construct the best solution. "Best" in this sense depends on the goal at hand. For example, consider a network of connected nodes called a graph. Given a starting and ending location, one can find an arbitrary path between the start and end. If the goal is to get from the start to the end while covering the shortest distance, then you optimize according to the length of the path. Thus this is called the "shortest path problem". See if you can find the shortest path from s to t in the example below.

Graph with weighted distances. Shortest path: s->E->D->C->t, distance 24

Real problems are rarely so simple, however. Consider other types of optimization problems, for example optimizing structural strength of a building, or maximizing the horsepower of an engine. These situations are more about resource management or proper planning, but the end goal is to still try to maximize (or minimize, as the case may be) some effect with respect to available options.

Speedrunning and Optimization

Speedruns are all about optimization. Finding a faster way to accomplish goals, a better route, a more efficient method of movement: all are part of the approach in achieving a good speed run. But how does this play into my earlier description of optimization problems? Games are hardly so simple as to be described as a graph or network, right?

Not exactly. Let's peel back what it means to play a game for a bit. Video games, at their core, are just computer programs. When a human plays a game, they are feeding instructions to the program to act on. We perceive this as a continuous interaction where our inputs from a controller instantly affect game operation. In reality however, the program works in stepped increments and only checks whether you are providing inputs at the beginning of each step. This rate is typically about 60 Hz (or 50 Hz for older PAL systems) so that the program's video output rate can match the refresh rate of the display device. A single step is referred to as a "frame" in both the technical and speedrunning sense.

This means that during a single second of gameplay, you can provide 60 sets of input to the program and influence its processing. This means that whether you're holding every button or no buttons, the game is continuing to process 60 sets of input each second. This is where we can start to draw a connection between playing a game and a graph. Consider a special type of graph called a tree, where an initial node connects to many subsequent nodes that represent changes in state due to differences in input.

Let's set this up in an example. Let's say you're playing a game with only two buttons, A and B. In each frame, you can press nothing, press A, press B, or press A and B. This gives a total of 4 transition possibilities, so you could move into one of four different states in the next frame. From each of those states you can move into 4 other states, and so on. This turns into a very big space very quickly. In just a single second, 4^60 possible paths are created. To put that in perspective, it would take the fastest supercomputer in the world at least 700 billion years to search every path and find the best one. And that's only if it can be completed within a second; what about if it takes several minutes to reach the end? The growth rate is even faster as you add more buttons and directions.

Example tree down to 2 frames. Each following node splits into 4 new nodes each additional frame.

Completing a speedrun is not quite that complex since playing games is not a blind process; we have an idea of where the end is and what we need to do to get there. This trims a huge portion of the search space; we know better than to keep walking into a wall, for example. While the search space has been reduced, it still is quite large, however. Factor in the limits of human reflexes and you have a search space that will probably never be truly conquered without tool assistance. At the core, this is what a speedrun is: an attempt to optimize the path through a game by completing it in the fewest frames possible. I will hold on to this definition and refer back to it a few times in the remaining sections.

SUMMARY: Speedruns are a shortest-path optimization problem trying to minimize the number of frames to complete a game.

Constraints

Something I have avoided bringing up in the prior sections is any mention of additional constraints on the given goal. Constraints always exist, but there is a distinct difference between implicit and explicit constraints. Implicit constraints are limitations imposed by the medium itself. My goal of reaching the top of a skyscraper as quickly as possible is limited by the fact that gravity prevents me from flying and I am hindered by my body's limited supply of stamina to run up stairs. These are examples of implicit constraints: limitations imposed upon your actions by the medium itself.

Explicit constraints are instead limitations imposed by the player to fulfill secondary goals. Secondary goals are exactly that: goals separate from the main goal that have some inherent worth in completing. For example, imagine that you're shopping for a new TV. The primary goal is to get a screen as big as possible. This is simple enough: choose the biggest screen. A secondary goal, however, is to not spend more than you have budgeted. In this situation you may have to pass on the biggest screen and instead settle on a smaller one that is within your budget. This is an explicit constraint because nothing is necessarily stopping you from buying the largest TV available (you can take out a loan if need be), but it makes sense to not spend everything you have to achieve the primary goal.

In the context of speedrunning, implicit constraints are imposed by the game environment. You can't start the game with full power-ups because that's just not how it's programmed. Falling in a pit will kill you. Those are the "rules" of the game, so to speak. Explicit constraints describe optional objectives, which are better translated into "categories" of speedruns. These include 100%, glitchless, low%, and any other applicable category for a game. Categories exist when the case without limitations (referred to in general as "any%") is uninteresting or effectively solved, or where there is significant incentive to achieve the secondary goal. I will go into specifics about categories in a later section.

SUMMARY: Implicit constraints are intrinsic to the medium of an optimization problem, while explicit constraints are applied as external limitations. External constraints change the problem, and thus are regarded differently from the original category.

Glitches and You

One point of controversy that comes up again and again is the utilization of glitches in speedruns. Many viewers have an expectation that speedruns clear the game using only the tools intentionally given by the developers. This is an explicit constraint on the run brought on by an internal perception of the game. This by itself is not inherently wrong or incorrect, but it is based on an attachment to the game. Speedruns in the unconstrained case are separated from this in that the game itself is no longer regarded as a game, but is instead the medium. The "game" then becomes the optimization problem, while the medium is just a set of implicit constraints. In this sense, there is no such thing as a glitch, provided that nothing external to the medium impacts it.

In the case that explicit constraints prevent the use of glitches, there are still a few points to clarify. First of all, it is quite difficult to objectively classify what is and is not a glitch. A glitch or bug in the technical sense is when a program achieves an unexpected state as a result of programming errors. A glitch is fairly apparent when a calculator program fails to calculate 2 + 2 correctly, but is not as clear when mapped to a complex program such as a game. In some cases it may not be apparent what the original intention for a function was. A famous example is the original Street Fighter 2, in which consecutive hits were not meant to connect but in some specific cases could be chained together. This was not the original intention according to the developers, but it formed the basis for the "combo" systems seen in every fighting game since.

I will try to illustrate these points a little better through some examples. In the situations below I have set up a Klotski board. The overall goal of Klotski is to move the Red Block out of the board by moving the other blocks. Any block can move in any direction so long as the spaces are empty. No two blocks can occupy the same tile at the same time. Blocks cannot pass through the perimeter wall, and only two tiles of the wall are open as the puzzle Exit. Can you solve this board? Turn it into an optimization problem: what's the fewest moves you can complete the board in?

Sample Klotski board. Move blocks out of the way so the Red Block can reach the exit.

Solution to the selected Klotski board. Pieces are moved in the order of the numbers.

This problem seems straightforward. There's only a small number of blocks to move in order to complete the puzzle, and it can be done in relatively few turns. However, there is more than meets the eye. Consider that you find a hole beneath the two blocks in the top left. This hole is big enough to fit the Red Block, thus allowing it to exit the board. Using the hole accomplishes the optimization goal of removing the Red Block from the board in fewer turns than possible otherwise.

Alternate solution that utilizes a programming error to leave the board sooner.

In the above case, it's obvious that the programmer made a mistake when setting up the board, never programming a "floor" to this particular section. This "new Exit" is different from the intended exit, but going through it still achieves the end goal of leaving the board. But what differentiates a glitch and an oversight? Consider this new board in which the hole has been patched. Given all of the implicit constraints, there are some parts that are not clearly defined. For example, why can't you move some blocks out of the Exit and then have the Red Block follow?

Another solution that makes other blocks exit before the Red Block to solve the puzzle in one less turn.

In this case, there is nothing fundamentally wrong with the board. All of the implicit constraints are applied, and none are broken or circumvented. However, nothing in the implicit constraints forbids other blocks from moving through the Exit. This would be a case of a programmer oversight, but there is no fault or problem in the code. This can still be labeled as a glitch, but in reality many of these oversights exist throughout normal play of games. Whether the players realize it or not is a different matter. This is what makes it difficult to declare "glitchless" as a blanket category when the distinction between a "glitch" and a "trick" is not immediately clear.

Regardless of the classification of a particular technique, the end point is that it is possible within the implicit constraints of the game. Individual techniques can be prohibited through explicit constraints, but there are no inherent issues with using them. Many people have an aversion to glitches because they see it as something that goes against the spirit of the game. The "spirit" of the game is in the end subjective; it doesn't mean the same thing from person to person. "Playing the game as it's meant to be played" also changes the optimization goal to maximize for enjoyment, which has no objective measure and is specific to an individual's experience. Thus, in the context of speedruns as an optimization goal for least frames, there is no distinction between glitches and normal play unless called out in the explicit constraints. A glitch occurs as just another transition of state, regardless of what a player may see on the screen.

SUMMARY: Glitches are in essence part of a game's implicit constraints. Excluding individual glitches can be declared as an explicit constraint, but this changes the optimization problem.

Cheating

Cheating is something that means something different depending on who you ask. At a very high level, we are biased against anything that gives an unfair advantage for the sake of consistency or fun. But what does it mean to have an "unfair advantage?" Unfair describes something as being unequal in a competitive space. Players have an expectation that competitive games are contests of skill, and tools or codes that surpass or suppress skill gets called out as cheating. Cheating is thus disallowed from competitive matches unless explicitly agreed on by the players. But what does it mean in the context of a single-player speedrun, where there is no opponent?

Prior examples speak only to games as a progression of state based on user inputs. If that were completely true, speedruns would often make use of cheat codes to shorten the run in various ways that would not be possible otherwise. Is this fair from a purely technical sense? It sure is. Cheat features were added to the game for a variety of reasons, and if the focus is to reach the ending as quickly as possible with absolutely no restrictions, cheat codes would get used in any way that helps to achieve a faster run. From the point of view of the player though, this can trivialize the run. If the run is not interesting or challenging, there is little satisfaction that can come from completing it.

Another argument can be made to how cheat codes influence the implicit constraints of a game, and thus change the medium of the run to something unequal. This is identical to the situation with cheat devices (Action Replay, Game Genie, etc). The original game may have one-hit deaths, but a cheat applied to the same game may prevent deaths altogether. In this sense it can be regarded as an entirely different game in that the "rules" have changed.

So are cheats inherently bad? Not necessarily; it just changes the medium for the run. Consider cheat codes that instead make games more challenging. One example is Bucky O'Hare on NES, which had a cheat code to enable the hardest difficulty. This mode was intended as an anti-piracy measure and was considered to be impossible to complete. The additional challenge provides a different sort of run than the stock game, and thus the code is used for speedruns. This situation can also apply to other types of cheats such as unlimited resources or extra abilities, but only makes a compelling speedrun when it adds some intrinsic value over the stock runs.

SUMMARY: Using cheat codes or devices changes the implicit constraints, and by extension changes the medium. It is not inherently bad, but it is no longer the same optimization problem.

Entertainment and Challenges

One way or another, we play games to be entertained. What it means to "be entertained" varies from person to person however; some people enjoy the thrill of working with/against a friend, others look for an immersive experience that takes them to another world. No matter what a person enjoys about games, the end point is to surpass challenges. Progressing through games gives us a sense of accomplishment, presented to our brain in the form of adrenaline and endorphins. Simply put, you feel good when you beat a boss or complete a puzzle. This encourages us to do more and continue progress to keep getting this feeling.

I will refer to this generically as the challenge of a game. By surpassing obstacles, we get positive feedback from our brains. The amount of feedback is proportional to the difficulty of the challenge. Thus we tend to go after the hardest challenges that can be reasonably completed. Reasonable in this sense means that it can be completed without excessive frustration; that is, the efforts that go into completing the challenge must be justified by the rewards. This varies by person and challenge; one person may value the reward for a particular challenge much higher than another person.

This concept has a couple impacts on speedrunning. First consider the concept of diminishing returns. If you replay a game you have already completed, do you get the same rush as the first time you completed it? Not exactly. Since you have completed all of the game's various challenges before, you know that you can complete them again and thus the reward is smaller. This changes if you apply changes to the game, for example raising the difficulty or trying some different gameplay options; anything to make it feel "fresh." One such way is to change the goal, for example trying to complete the challenges in an efficient manner.

Second, consider the difference between types of challenges. Playing a competitive game against a friend is continually rewarding because both of you evolve your play as you continue bouts, thus making it a dynamic challenge. Figuring out a difficult puzzle on the other hand is a static challenge; the puzzle can't change, and thus the solution ceases to be rewarding on subsequent solves. Most games can be considered as some variety of static challenge. The events can be experienced in myriad ways, but the number of solutions are often limited. Consider instead an opportunity to turn a game into a dynamic challenge. Speedrunning a game essentially turns it into a dynamic experience since there is no immediate solution, but there are an effectively unlimited number of outcomes. Unlike my competitive example, the goal isn't to best your friend, but instead is to drive your own time lower and lower. Achieving lower times again and again continues to reward since the challenge itself evolves as you get better. This reward may not be large for everybody, but you can bet it is for speedrunners.

The challenges themselves take on many different forms. In many cases it comes down to the execution of the challenge. Simply knowing how to beat a boss or get through a room unscathed has no reward until you actually do it. On the other side, there are plenty of cases where figuring out the solution is difficult but the execution is trivial. Consider a puzzle room where you have to move blocks around in just the right order to escape. I'll refer to this element as planning. The final piece of comes from discovery, where you feel rewarded from finding something new. This feeds back into both execution and planning in that discoveries give another "tool" to supplement your options in either case. Discovery is a bit harder to justify as a challenge in the typical sense, but when it comes to discovering intended (mechanics and properties) or unintended (glitches and tricks) game behavior then it makes a lot more sense.

Different people may weigh the pieces differently, which is why there is so much variability in how people approach speedruns. Execution is a showcase of technical skill, which can be impressive in its own right. Planning is a non-trivial task as the scope widens from single puzzles to entire chunks of a game. Discovery aids in both the ability to execute efficiently as well as make informed decisions about the correct paths to the end. Some people may enjoy one aspect more than others, but it is impossible to split them up entirely. The sum of execution, planning, and discovery form the challenge of a game, and by extension the challenge of speedruns as well.

SUMMARY: Enjoyment comes from overcoming challenges. Speedruns present a continually evolving challenge in multiple aspects.

Categories Galore

While the core goal for a speedrun is to reach the ending in the least number of gameplay frames, a variety of secondary objectives can be attached to runs. These goals can vary in terms of what they affect in a run, but they often satisfy a generic secondary goal of increasing the challenge in the run at the expense of time. Adding on additional secondary objectives or external constraints to a run can be considered transforming it into a category.

There are a few major distinctions between sets of categories. The most common distinction in practice is based on the console or platform that the game is being run on. This is the case for games that are released on multiple platforms with only very minor differences between them. For example, the Xbox 360 version of a game as opposed to the PS3 version, or even between the Japanese and US versions of a game. The differences between these versions may have an impact on the end time of a run, but by and large it is the same game. Despite this, the implicit constraints are slightly different and thus they are often separated from each other by categories. This type of categorization I will refer to as Comparative Categories, because at some level they are compared against each other based on what is or is not affected by the operating platform. In this case, no direct external constraints are applied to the run and it is simply noting the host platform so comparisons can be made using the best known information.

The next major type I will call the Core Categories. In the most general sense, this is the category that is known as "any%" and refers to beating the game as quickly as possible with no explicit constraints. Sometimes the definition of when a game "ends" is not immediately clear however, and instead a different criteria is defined as completion. These categories are in some ways the penultimate categories since the goal has no stated caveats. In this way, you could say that the Core Category for a game is simply the fastest possible way to finish it. Looked at another way, this also means that any other categories based on explicit constraints are derivatives of the Core Category.

That brings us to Limitation Categories. This type of category refers to any application of explicit constraints on the speedrun. These constraints can be applied for a variety of reasons. For example, suppose a game has diverging "Light" and "Dark" paths to the end. While the Dark path may be the fastest purely in terms of the time it takes to finish, the Light path has significantly different content and presents a different challenge compared to the Dark path. The same can be said for what is commonly called "100%" categories that involve collection of game resources. Adding the restriction that everything must be collected changes the challenge to incorporate more and different content than otherwise necessary for the Core Category. Lastly, explicit constraints can be applied in terms of glitches or techniques that can be used within the run itself. These types can be tricky to justify, but are usually intended to maintain a higher degree of difficulty in the run if a particular trick or glitch removes a large portion of content or challenge.

A graph representation of a notional game where each node is represents a unique piece of content. The blue outline represents the shortest path from s to t known as the Core Category. This path skips out on some significant content however, and thus a different path shown in red represents the shortest path for a Limitation Category. Another Limitation Category might instead try to visit as many pieces of content as possible.

When to make a New Category

In the beginning, there was the Core Category, and the people revered it. Then one day lightning struck and the once-mighty category was reduced to a fraction of its former self. People picked up the pieces and set out to rebuild new categories while remaining ever watchful of what remained of the Core, claiming to make something better that could fulfill the Core's former purpose.

This type of situation comes up within the speedrunning community a fair bit, especially for the most popular and competitive games. Somebody will discover a special trick or otherwise that reduces the time on the Core Category a fair bit, but members of the game's community are reluctant to take up the new trick since it changes the challenge they were initially pursuing. Thus they instead try to continue runs excluding the new discovery by separating it as a limitation into its own category.

The question then becomes: what are the limits in deciding what should or should not be a new category? This goes back in some ways to what people enjoy from a speedrun, which I labelled generically as its challenge. Even though the goal of speedrunning is to optimize the path through a game in the least frames, it doesn't mean a whole lot to humans if there's no challenge to it. You could thus say that any explicit constraints applied to the Core Category are intended to increase the challenge and therefore the enjoyment of the run.

With that in mind, I have set up the chart below to discuss the situations in which it makes sense to create a new category. The axes are treated as relative changes in either the time or challenge if a specific constraint is applied to the Core Category. A + on either axis can be interpreted as somewhat more of either time or challenge, whereas ++ means significantly more. The opposite is true for - and --, respectively. Remember that challenge is defined as the sum of the execution, planning, and discovery for a speedrun; if an explicit constraint only affects some of the execution and does not impact planning or discovery, it will only somewhat impact the challenge. A significant difference in challenge in this case means that it is a very different run than the Core Category with vastly different content and routes. A significant difference in terms of time is also not clear, but consider as a rule of thumb that a somewhat different time will be something like 20% shorter/longer, whereas a significantly longer time may be twice as long.

A chart describing cases where external constraints are applied to a Core Category and whether or not the constraint should be made into a new category. Cells marked with "Core Improvement" indicate that this constraint effectively becomes the new Core. None indicates that there is no reason to make a new category. Maybes are left up to the game's community to decide.

More words to finish this section soon.

Miscellany

This section describes some odds-and-ends topics in the context of the prior sections. I will try to keep the conclusions and discussion focused around objective points, but these sections in particular may have elements sourced from subjective reasoning.

Tool-Assisted Speedruns

Tool-assisted speedruns (TAS) present a more literal approach to completing a game in the least number of frames. Whereas typical speedruns (I will refer to them as RTAs in this section) try to minimize the time as much as possible within human limits, a TAS discards any notion of human skill. A TAS instead strives to find the absolute fastest path to the end by having absolute insight into the game and having the ability to move forward and backward in time. This is another case of "solves a different problem," although the goal itself is the same. Put another way, the difference between a TAS and an RTA is that an RTA has an unstated explicit constraint of "must be performed by human hands."

In most cases, an RTA is a one-off attempt to reach a minimal path. This means that the best path available is limited by random elements, reflexes, and full insight into game mechanics. This is not the case for a TAS. Individual events and luck can be extensively manipulated so that the best possible outcome is achieved, to the point that each and every frame is optimal. The ability to time inputs perfectly allows actions that would be impossible for humans under normal circumstances, such as pressing a button 30 times in a single second. This may seem like cheating to some, but keep in mind that a TAS is trying to answer the question of "what is the absolute shortest path for a game." With this perspective, you can interpret a TAS as the limit that any equivalent RTA can achieve. Thus a TAS focuses on finding the optimal path, while an RTA focuses on approaching an optimal solution achievable within human limits.

Racing and Competition

Something that I glossed over in prior sections is the fact that speedruns may not be a purely solo activity. If SpeedRunsLive is any indication, a great many people enjoy directly competing at speedruns through races. This is a different focus than I explained in the Entertainment and Challenges section, but the drive is very similar. It's as simple as treating speedruns as a way to test your own skills against other runners.

When put into this context, the goals themselves do not change, but the considerations may be different. For example, a race can be considered placing an external constraint of having only one chance to complete the run. This means that risk becomes a larger factor, and consequently may lead to a different type of path to ensure the run finishes at all. Finding an optimal path in a non-optimal situation is a different type of challenge in itself. It does however still fall back to the same three aspects of execution, planning, and discovery. Execution is straight-forward, but planning in this case means having contingency plans for when things go wrong. Discovery remains from understanding intrinsic game mechanics to minimize losses in both execution and planning.

Races aside, competition just from trying to achieve the shortest path can also be a driving factor. You can consider this the "World Record Effect," where standing at the top of the field becomes a large motivator. This type of motivation aids in minimizing the path by mixing skillsets and knowledge from different players, and in many cases results in achieving a lower time than if a single individual tried to achieve it by themselves. There's a thrill inherent to achieving better results over other people just as there is to surpassing your own goals and expectations.

Conclusion & Final Words

Hopefully this made sense.