How do I classify my emulator input optimization problem, and with which algorithm should I approach it?

Question

Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) as:

What methods exist to find local optimums on extremely large combinatorial search spaces?

Background

In the tool-assisted superplay community we look to provide specially-crafted (not generated in real-time) input to a video game console or emulator in order to minimize some cost (usually time-to-completion). The way this is currently done is by playing the game frame-by-frame and specifying the input for each frame, often redoing parts of the run many times (for example, the recently published run for The Legend of Zelda: Ocarina of Time has a total of 198,590 retries).

Making these runs obtain their goal usually comes down to two main factors: route-planning and traversal. The former is much more "creative" than the latter.

Route-planning is determining which way the player should navigate overall to complete the game, and is often the most important part of the run. This is analogous to choosing which sorting method to use, for example. The best bubble sort in the world simply isn't going to outperform a quick-sort on 1 million elements.

In the desire for perfection, however, traversal (how the route is carried out) is also a huge factor. Continuing the analogy, this is how the sorting algorithm is implemented. Some routes can't even be performed without very specific frames of input. This is the most tedious process of tool-assisting and is what makes the production of a completed run takes months or even years. It's not a difficult process (to a human) because it comes down to trying different variations of the same idea until one is deemed best, but humans can only try so many variations in their attention-span. The application of machines to this task seems proper here.

My goal now is to try to automate the traversal process in general for the Nintendo 64 system. The search space for this problem is far too large to attack with a brute-force approach. An n-frame segment of an N64 run has 2³⁰ⁿ possible inputs, meaning a mere 30 frames of input (a second at 30FPS) has 2⁹⁰⁰ possible inputs; it would be impossible to test these potential solutions, let alone those for a full two-hour run.

However, I'm not interested in attempting (or rather, am not going to even try to attempt) total global optimization of a full run. Rather, I would like to, given an initial input, approximate the local optimum for a particular segment of a run (or the nearest n local optimums, for a sort of semi-global optimization). That is, given a route and an initial traversal of that route: search the neighbors of that traversal to minimize cost, but don't degenerate into trying all the cases that could solve the problem.

My program should therefore take a starting state, an input stream, an evaluation function, and output the local optimum by minimizing the result of the evaluation.

Current State

Currently I have all the framework taken care of. This includes evaluating an input stream via manipulation of the emulator, setup and teardown, configuration, etc. And as a placeholder of sorts, the optimizer is a very basic genetic algorithm. It simply evaluates a population of input streams, stores/replaces the winner, and generates a new population by mutating the winner stream. This process continues until some arbitrary criteria is met, like time or generation number.

Note that the slowest part of this program will be, by far, the evaluation of an input stream. This is because this involves emulating the game for n frames. (If I had the time I'd write my own emulator that provided hooks into this kind of stuff, but for now I'm left with synthesizing messages and modifying memory for an existing emulator from another process.) On my main computer, which is fairly modern, evaluating 200 frames takes roughly 14 seconds. As such, I'd prefer an algorithm (given the choice) that minimizes the number of function evaluations.

I've created a system in the framework that manages emulators concurrently. As such I can evaluate a number of streams at once with a linear performance scale, but practically speaking the number of running emulators can only be 8 to 32 (and 32 is really pushing it) before system performance deteriorates. This means (given the choice), an algorithm which can do processing while an evaluation is taking place would be highly beneficial, because the optimizer can do some heavy-lifting while it waits on an evaluation.

As a test, my evaluation function (for the game Banjo Kazooie) was to sum, per frame, the distance from the player to a goal point. This meant the optimal solution was to get as close to that point as quickly as possible. Limiting mutation to the analog stick only, it took a day to get an okay solution. (This was before I implemented concurrency.)

After adding concurrency, I enabled mutation of A button presses and did the same evaluation function at an area that required jumping. With 24 emulators running it took roughly 1 hour to reach the goal from an initially blank input stream, but would probably need to run for days to get to anything close to optimal.

Problem

The issue I'm facing is that I don't know enough about the mathematical optimization field to know how to properly model my optimization problem! I can roughly follow the conceptual idea of many algorithms as described on Wikipedia, for example, but I don't know how to categorize my problem or select the state-of-the-art algorithm for that category.

From what I can tell, I have a combinatorial problem with an extremely large neighborhood. On top of that, the evaluation function is extremely discontinuous, has no gradient, and has many plateaus. Also, there aren't many constraints, though I'll gladly add the ability to express them if it helps solve the problem; I would like to allow specifying that the Start button should not be used, for example, but this is not the general case.

Question

So my question is: how do I model this? What kind of optimization problem am I trying to solve? Which algorithm am I suppose to use? I'm not afraid of reading research papers so let me know what I should read!

Intuitively, a genetic algorithm couldn't be the best, because it doesn't really seem to learn. For example, if pressing Start seems to always make the evaluation worse (because it pauses the game), there should be some sort of designer or brain that learns: "pressing Start at any point is useless." But even this goal isn't as trivial as it sounds, because sometimes pressing start is optimal, such as in so-called "pause backward-long-jumps" in Super Mario 64! Here the brain would have to learn a much more complex pattern: "pressing Start is useless except when the player is in this very specific state and will continue with some combination of button presses."

It seems like I should (or the machine could learn to) represent input in some other fashion more suited to modification. Per-frame input seems too granular, because what's really needed are "actions", which may span several frames...yet many discoveries are made on a frame-by-frame basis, so I can't totally rule it out (the aforementioned pause backward-long-jump requires frame-level precision). It also seems like the fact that input is processed serially should be something that can be capitalized on, but I'm not sure how.

Currently I'm reading about (Reactive) Tabu Search, Very Large-scale Neighborhood Search, Teaching-learning-based Optimization, and Ant Colony Optimization.

Is this problem simply too hard to tackle with anything other than random genetic algorithms? Or is it actually a trivial problem that was solved long ago? Thanks for reading and thanks in advance for any responses.

Answer 1

From the information you give in your question, I can not see how to apply standard optimisation methods (that I know of). Your objects are not that complicated (more on that later) but your target function is a nasty one: its values are defined by an external system out of your control, it is unlikely to have any nice properties, and so on. Therefore, I think using genetic algorithms is not an unfeasible and maybe even a good approach here; they often work better than other methods if you have no clue about your problem's structure. There is much to consider about

• object space,
• target function and
• parameters of your genetic algorithm,

so allow me elaborate.

What are your objects?

You have answered that already: your are looking at a sequence of actions, each of which takes up one frame. I think this may be too fine grained; maybe try a sequence of actions, each with a duration (in number of frames). This would allow to have mutations like "walk a bit longer" to have different probabilities than "insert a press of A" in a natural way. Try out what works best; you may have to revisit this item after thinking about the other ingredients.

What is your target function?

This one is really crucial. What to you want to optimize? Time to goal? Number of different actions? The number of collected stars? A combination of several factors? As soon as you get multiple targets, things get hairy -- there (usually) are no longer optima!

You mentioned time to goal. This is likely not a good target function at all. Why? Because most sequences will not even reach the goal so they will bottom-line to some constant, creating a fitness landscape like this (conceptual sketch in one dimension):

^[source]

There are huge areas where the target funtion is $0$. Genetic algorithms are all about signals: small changes in the solution have to indicate an improvement (or decline) in quality if and only if the change is "directed" towards an optimal solution (ideally). If that is not the case (drastically), you have little more than a random search, hitting a good solution with probability near $0$. What does that mean for our target function? It has to be something that improves whenever a solution improves slightly, even if overall quality is still low. So what about

$\qquad \displaystyle \frac{1}{1 + \text{final distance to goal}} + \frac{1}{1 + \text{time to goal}}$

using "infinity" as time to goal if the goal is not reached, that is set the second summand to $0$. As long as the goal is not reached, getting nearer moves fitness up to $1$. All sequences that reach the goal have a baseline of $1$ and improve further the faster they are.

So how do you measure distance? Linear distance may look tempting but has its problems; again, wrong signals may be sent. Consider this simple scenario:

^[source]

Every sequence that starts with a jump to the upper corridor improves until it reaches a spot just above the goal, but it can never actually get to the goal! Even worse, among all sequences that do not reach the goal, those that go up are as good as those that go down, so the GA can not reject sequences that are clearly doomed. In other words, linear distance creates particularly bad local optima which can trap the GA if there are dead ends in the level.

Therefore, I suggest you overlay a grid over your level and connect neighbour points if the game character can get from one to the other. Then you compute distance-from-goal by the length of the shortest path from the point nearest to where the sequence lands the character to the point nearest to the goal. This is easy to compute and walking into deadends (local optima) is immediately punished¹. Of course you need access to level data, but I assume you have those.

How does your GA work?

Now we can get to the actual genetic algorithm. The key considerations are population, selection, reproduction/mutation and stopping criterion.

Population

How large is your population going to be? If it is too small, it may not provide the diversity necessary to reach a good solution. If it is too large, you are more likely to carry around useless junk, slowing down the process.

How do you initialise your population? Do you pick random action sequences? If so, of which length? Do you have a (small) number of manually generated, reasonable solutions to seed with, maybe such that reach the goal?

Selection

Which individuals are selected for survival/reproduction? The $k$ best? Do you hold tournaments? Do you decide an individual's survival randomly with respect to its fitness? Do you want the best to survive in any case or can they die (may be useful to leave local optima)²?

The core concept here is selection pressure: how hard is it to survive? Make it too small and you don't weed out crap solutions. Make it too high and you make change (in particular moving between local optima) hard.

Reproduction and Mutation

Once you have selected your survivors of one round, you have to create the next generation from them (do the parents survive and are part of the next generation?). There are two major strategies: mutation and recombination.

Mutation is quite clear, although the specifics can differ. For every position in an individual's sequence, mutate it with some probability. You can do this independently for every position, or choose the number of mutations randomly, or you can perform different mutations with different probabilities (such as inserting a new element, removing one, changing one, ...). Mutation is usually about small changes.

Recombination, that is combining aspects of two or more solutions to a new one, is more tricky but can allow big steps, that is leaving one "fitness mountain" and move directly to the slope of another (which may be higher). A classic idea is the crossover; I don't know whether that makes sense here (it seems to me that swapping the prefix of a given sequence for something else will most likely devalue the suffix). Maybe you can use knowledge about the level and positions of the game character at different points in the sequence to guide this, that is create crossover points only where the character is at the same position in both sequences.

Termination

When do you stop? After $N$ generations? When the maximum fitness has not improved since $k$ rounds? Do you stop early if some fitness (with above function, $1$) has not been reached after $n$ rounds in order to eliminate useless initial populations early?

---

As you can see, all these things intertwine to influence the actual performance. If you run multiple populations in parallel, you can even think about implementing genetic drift due to migration and/or catastrophes. There is little theory to guide your way, so you have to try out different setups and look where it gets you. Hopefully, what works for one level will also work for others. Happy tinkering!

Nota bene: Have look at BoxCar 2D in the light of the above. They do some things pretty well (others, not so) and you can get an intuition for how a GA's parameters can influence its performance.

---

1. Actually, constructing a sequence greedily using this fitness, that is choosing the action that minimises distance-to-goal out of all possible next action, may work quite well. Try that before using GA!
2. Of course, you as observer always remember the best solution ever encountered.

Answer 2

For more details on Teaching-learning-based optimization (TLBO) method and its code, refer to the following paper:

An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems by R. Venkata Rao and V. Patel; International Journal of Industrial Engineering Computations 3 (4): 535–560 (2012)

For additional reading:

• Teaching-learning-based optimization algorithm for unconstrained and constrained real parameter optimization problems by R. Venkata Rao, V.J. Savsani and J. Balic; Engineering Optimization (2012)
• Mechanical Design Optimization Using Advanced Optimization Techniques by R. Venkata Rao, J.V. Savsani; Springer-Verlag London (2012); ISBN 978-1-4471-2747-5
• Multi-objective optimization of heat exchangers using a modified teaching-learning-based optimization algorithm by R. Venkata Rao and V. Patel; Applied Mathematical Modeling (2012)
• Multi-objective optimization of two stage thermoelectric coolers using a modified teaching-learning-based optimization algorithm by R. Venkata Rao and V. Patel; Engineering Applications of Artificial Intelligence (2012)