Difference between revisions of "What is a speedrun?"

Revision as of 21:07, 22 April 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.

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 in the fewest hops, 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 in the example below.

Real problems are rarely so simple, however. Consider that instead of any given hop having the same impact, a weighting is assigned to each link. Given this new information, can you find the shortest path in the new example?

The image below shows the shortest path. Many readers may have selected a different path based on the new weighting information. In that case, they are now solving a different optimization problem; that is, they solved for the minimum weight path. This means that they changed the goal based on the information they were given, however the original goal to reach the end in the fewest hops remained the same. This is a trap that many people can fall into subconsciously because they want to make use of everything they have been provided. I will revisit this concept later on in the article.

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.

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.

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. 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.