Tweeted twitter.com/#!/StackCompSci/status/200499501247627264
2 deleted 363 characters in body; edited tags
source | link

Before I start: I understandDue to the scopenature of this StackExchange sitethe question, I have to include lots of background information (I think), but do pardon if I'm off-topic. Mybecause my question is an intersection of mathematics, computer science, and software engineering, so picking the right site to ask on has been a bit unclear.: how do I narrow this down?) That said, after asking hereit can be summarized (a pretty much spot-on site, topic-wise) and receiving not muchto the best of a response, I figure I'd try here instead. I won't be offended if you close itmy knowledge) as off topic.:

I've bolded the important points of my question, for those who think the background is irrelevant (though I'm including it for the sake of completeness, apologies for the length.)What methods exist to find local optimums on extremely large combinatorial search spaces?

Before I start: I understand the scope of this StackExchange site (I think), but do pardon if I'm off-topic. My question is an intersection of mathematics, computer science, and software engineering, so picking the right site to ask on has been a bit unclear. That said, after asking here (a pretty much spot-on site, topic-wise) and receiving not much of a response, I figure I'd try here instead. I won't be offended if you close it as off topic.

I've bolded the important points of my question, for those who think the background is irrelevant (though I'm including it for the sake of completeness, apologies for the length.)

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?

    Post Migrated Here from cstheory.stackexchange.com
1
source | link

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

Before I start: I understand the scope of this StackExchange site (I think), but do pardon if I'm off-topic. My question is an intersection of mathematics, computer science, and software engineering, so picking the right site to ask on has been a bit unclear. That said, after asking here (a pretty much spot-on site, topic-wise) and receiving not much of a response, I figure I'd try here instead. I won't be offended if you close it as off topic.

I've bolded the important points of my question, for those who think the background is irrelevant (though I'm including it for the sake of completeness, apologies for the length.)

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 230n possible inputs, meaning a mere 30 frames of input (a second at 30FPS) has 2900 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.