Of late I have become a bit more interested in some of the more technical aspects of TASing, as opposed to just TSAing games (which has begun to seem a bit repetitive to me.) I guess I was inspired my Lord Tom's River Raid run and the recent work I did with micro500 on Treasure Master, which seemed really fun to me even though it wasn't directly making a TAS. So I got the idea of trying to make a thread similar to wikipedia http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics and see what some people think are significant open problems in TASing.
These can be anything from emulation to game RNG to verification, big issues or small ones, but I want to avoid things like 'I want to see ___ run.'
So does anyone have any thoughts on this?
Is there a certain game which you think is poorly understood that needs a lot of research?
What problem needs to be solved to move TASing forward a step beyond what is currently possible?
Or if you are feeling particularly bold or prophetic, what are the 'Millennium Prize Problems' of TASing?
I appreciate any input. : )
Well if "How many numbers with property X are there?" is a valid question, there's all sorts of TAS equivalents. How many games have ACE potential? How many justifiable categories can we invent for a game? Etc etc.
Will new glitches ever not be found in Zelda games? Seriously, how many different routes have to be invented for OOT...
What is the ideal ratio between Rerecords and movie length? Taken over all movies, does it converge on any interesting number? Imagine if it was the golden ratio.
Will bots be able to TAS with greater or equal efficiency of humans? Currently we cannot brute force stuff, and they're not intelligent enough to understand what the hell they're doing, but when will they be? When will bots be able to hypothesis/test potential glitches for itself?
If a NES game for example is made from finite coding, finite memory, with finite calculations going on, then is there a finite limit on the maximum amount of glitches a game can have? What is it?
Joined: 4/8/2005
Posts: 1573
Location: Gone for a year, just for varietyyyyyyyyy!!
Is there a method for proving a TAS to be optimal without brute-forcing all input patterns?
Are there practical real-life applications for TAS tools and the skill set of the TAS community? For example, could we TAS protein folding? Could we TAS Bisqwit's toy robot?
Is there a method for evaluating a taser's skill?
Who is the best taser of all time? Is this question even meaningful?
What are the psychological effects of tasing?
What is the prevalence of autism among tasers compared to the general public?
Is there a universal mathematical relation between an optimal TAS time and the number of alternative input patterns that achieve the same time?
What is the easiest/hardest system to TAS? Why?
Are SNES games generally harder to TAS than NES games?
What is the hardest game to TAS? Why?
If all games were TASed optimally, what game would produce the longest TAS?
Is it possible to complete 1000 NES games with a single input file without dying at all?
Those are some hard questions. I thought up some too, also some on the easier/ more tractable end of the spectrum.
These are on the more practical end, can anyone think of others like these, that may or may not be possible in a given game?:
Can you complete Bowser in the Fire sea in SM64 in 0 'A' presses?
Can you get by the infinite wall in Windwaker early?
Here are some R&D related ones:
N64 emulation (although this seems to be in progress)
What are the limits of console verification?
Here is a less practical one I came up with:
Is there a repeating input sequence that can be used to beat super mario bros that is substantially shorter than that for a full length run? What is the shortest such sequence?
To be more specific, TAS optimization is reminiscent of the knapsack problem, and given the similarity I'd be inclined to say that TAS optimization in the general case is definitely NP-complete. There would certainly be games where the specific subset is in P, but most would be NP-hard. That said, approximating a solution and optimizing should be possible below O(2n) in general, but it won't be OPTIMAL most of the time.
Incidentally, P vs. NP is one of the millennium prizes mentioned in the first post, so if P = NP, then it might not be as hard as we thought :P
What is the ideal ratio between Rerecords and movie length? Taken over all movies, does it converge on any interesting number? Imagine if it was the golden ratio.
"Rerecords" is the number of times a TASer discards input to try something new. So it only depends on the game and the TASer.
To be more specific, TAS optimization is reminiscent of the knapsack problem, and given the similarity I'd be inclined to say that TAS optimization in the general case is definitely NP-complete.
Be careful with your terminology. An NP problem is, essentially, a yes/no question that's very hard to answer, but the given answer is (relatively) easy to check.
This form of problem for a TAS would typically be "can this game be completed in at most N frames?" The answer may be very hard to find (perhaps requiring brute-forcing all possible combinations), but a given answer is easy to check (just run it, ie. you can check it in linear time).
However "what's the minimum amount of frames that this game can be completed in?" is a different category of problem (because it's not a yes/no question). If the problem is in NP, then it's a so-called NP optimization problem.
The difference is that checking that the answer is correct is not easy.
You pulled out the term NP optimization first :P Although yeah I suppose the problem isn't likely to be in NP, due to the fact that it's impossible to verify in polynomial time if it's optimal. I'd have to look up NP-hard first to even concretely say if it's that, I guess.
I think the best kinds of TASing related problems would be things like 'how do we make producing and optimizing a TAS, for human beings, as easy as possible'. For example, if you consider TASStudio to be superior to no TASStudio, what would be one step better than TASStudio?
Joined: 4/8/2005
Posts: 1573
Location: Gone for a year, just for varietyyyyyyyyy!!
Patashu wrote:
what would be one step better than TASStudio?
The next step is to not produce any input manually. Input is produced automatically and you just choose the result you want to keep. After all, we are not interested in the input pattern itself, but the resulting RAM values.
Maybe not quite like this, but maybe something like this:
Brute force 1 frame and choose (by clicking) the result you want.
Even better: Brute force 2 frames and click the result(s) you want to keep.
Even better: Brute force 3 frames.
The results would be displayed as a list based on relevant RAM addresses ordered from highest to lowest. Let the program tell you the most high/low/anomalous values for the RAM addresses you want to monitor. (That would often be something like the highest player X-position available etc.) Then just choose the best result. Then do the same for the next 3 frames.
3 frames is often enough to find the most basic movement optimization tricks.
Maybe a visual display of the character's "position space" would be useful, too. It would plot all the possible positions of the character for the last 3 frames. Think of a radar in a multiverse.
Even if you couldn't afford brute forcing all possibilities even for just 3 frames, a randomized ghost bot on the background would be better than nothing. The ghost would run continuously, as efficiently as possible (using all CPU power available). It would generate random input. It would always base its attempts on the current player state, so it would always be in a meaningful starting position and the player would be immediately informed when the background bot found a better RAM value for the last ~3 frames. It would often find nothing, but when you TAS 100 hours, it might find a trick.
For brute forcing, use BOINC.
'how do we make producing and optimizing a TAS, for human beings, as easy as possible'. For example, if you consider TASStudio to be superior to no TASStudio
The good thing about movie editors is that they focus on the game, instead of dealing with tools. It also speeds up the progress, because the TASer can even make frame perfect inputs while turboing and with auto-restore the TASer doesn't need to stop at the frame to compare RAM manually. Newbies tend to pick TAStudio, due to more intuitive controls. Of course if the TASer is lazy or doesn't know about the game, a bad result happens.
TAStudio makes things a lot easier, for me atleast. Someone without experience might need to get used to it to use it well. I currently work on Quake 64 and it gets ridicolously easy with that tool, no annoying virtual pad and no input memorization. The down side of it is that you need a decent PC for it, N64 with TAStudio and lua scripts runs at ~25 fps with a 2.7GHz processor and a huge amount of RAM is also recommended, I have only 2GB :(.
Aqfaq: I am currently trying to write some bot for 3D games that brute-force movement, but lua support for TAStudio isn't done yet. It should constantly run in background while the user assigns buttons. The positions and angles where the character should go are probably read from markers.
A better attempt to this would be a 3D enviroment where the TASer draws a path througth the level and moves parts of it around and many to manipulate the movement. The movement will be brute-forced by a bot.
How about some more practical problems that people really want to seem solved?
Figure me out how Mega Man ZX’s RNG works.
What would you like to know about it? I found the work you've done so far and I did a little testing. As far as I can tell the fourth byte has no impact on what is dropped. It also seems that all enemies (at least in the intro level) have the same drop characteristics. I tested with RNG B4B3A413. Hard to tell exactly how it is being used though.
I guess this would be kind of trivial with a trace logger type utility in the emulator, so I would say that is an open problem in R&D.
Ever since I wrote this script for predicting RNG in this run I wondered if the formula could be reduced.
Currently you call the function nRNG (line 44) with two bytes to let the function advance them one step further. As you can see, the bytes run through a bunch of binary operations like XOR and ROL which loops 11 times.
As an example, calling the function nRNG with bytes 0x00 and 0x00 will give you 0x92 and 0x04. With only two bytes there are only a limited number of solutions (0x10000 or simply 65536).
After some testing I found out that when you start at, for example, 0x00 0x00, you will go through every possibility once until you get back to 0x00 0x00... except for the combination 0x55 0x55 and 0xAA 0xAA. These are not occurring which makes sense because calling the nRNG function with 0x55 0x55 will give you 0xAA 0xAA and vice versa.
So my question is: is it possible to reduce the formula or function to a simpler one?
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
ASL: left shift where the new LSB (least significant bit) becomes 0 and the old MSB (most significant bit) goes into carry.
LSR: right shift where the new MSB becomes 0 and the old LSB goes into carry.
ROL: left shift where the new LSB becomes the old carry and the old MSB goes into carry.
ROR: right shift where the new MSB becomes the old carry and the old LSB goes into carry.
I think XOR and AND are pretty basic.
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
What would you like to know about it? I found the work you've done so far and I did a little testing. As far as I can tell the fourth byte has no impact on what is dropped. It also seems that all enemies (at least in the intro level) have the same drop characteristics. I tested with RNG B4B3A413. Hard to tell exactly how it is being used though.
Knowing how to manipulate life up drops would be nice, but I think what I need now is to know how Giga Aspis’s (the snake boss at the start of the game) actions are controlled by the RNG. I’ve kind of figured out that behaviour changes between the 1st health bar and the 2nd one, and also that most of the time the boss has 2 timings at which it attacks, soon or late. I’m still working on figuring out the perfect boss fight, but I think that the manipulation it’d require would be impossible to get unless I can completely understand the RNG and math out all possibilities given a starting RNG value. I believe it is very unlikely that I can manipulate it just in the fight itself, I would need to start manipulating the RNG from the level so that I reach the boss fight with the correct RNG value.
Alyosha wrote:
I guess this would be kind of trivial with a trace logger type utility in the emulator, so I would say that is an open problem in R&D.
is it possible to reduce the formula or function to a simpler one?
I don't think so. You could put the results into look-up tables, but that wouldn't make it simpler. The
rng1, c = ASL(rng1)
rng2, c = ROL(rng2, c)
part could be rewritten to treat [rng2, rng1] as one 16-bit value etc. but in the end that doesn't make the algorithm shorter either and only introduces the possibility of bugs.
@Masterjun:
That is a neat property. Well the function itself can certainly be simplified with more local variables.
If you write RNG1=A7,...,A0 and RNG2=B7,...,B0 then after 1 of the 11 cycles you get
RNG2=B6,...,B0,A7
RNG1=A6,...,A0,NOT(XOR(XOR(A0,B7),A1)) (if I did all my math right)
But simplifying the loop, I think not, since after 11 cycles, RNG2 will look like:
A3,A2,A1,A0,NOT(XOR(XOR(A0,B7),A1),.... and RNG1 will be a mess.
@ALAKTORN:
I just mean that if DeSuMe had a trace logger you could find out all of that stuff pretty easily (compred to trying to deduce what is happening.)
Is there a method for proving a TAS to be optimal without brute-forcing all input patterns?
Are you asking for a general method that works for all TASes for all existing games? Or for all conceivable games? Or just a particular method that might work for at least one particular game?
I suspect that there is no general method that's fast enough to be practical, but I also suspect that some particular TASes could be proved optimal. (The simpler the game, the easier the proof would probably be; so if I wanted to attempt such a proof, I'd start with Desert Bus.)
Aqfaq wrote:
Is there a universal mathematical relation between an optimal TAS time and the number of alternative input patterns that achieve the same time?
Not sure what you mean by this.
Aqfaq wrote:
Is it possible to complete 1000 NES games with a single input file without dying at all?
Are there even 1000 NES games? Wikipedia claims that there are 826, and judging by the titles in the list, some of those wouldn't even have a concept of dying.
--------------------------------
Also, for people talking about TASing being NP-hard: for a problem to actually be NP-hard, it has to have arbitrarily large instances. So any TAS-related problem that involves TASing existing games that run on existing consoles is unlikely to qualify. (For example, Sokoban is evidently PSPACE-complete (and thus NP-hard); but testing whether a Sokoban map that fits in a 1000x1000 grid has a solution can be done in constant time (albeit a very, very large constant).)
If you write RNG1=A7,...,A0 and RNG2=B7,...,B0 then after 1 of the 11 cycles you get
RNG2=B6,...,B0,A7
RNG1=A6,...,A0,NOT(XOR(XOR(A0,B7),A1)) (if I did all my math right)
But simplifying the loop, I think not, since after 11 cycles, RNG2 will look like:
A3,A2,A1,A0,NOT(XOR(XOR(A0,B7),A1),.... and RNG1 will be a mess.
Not bad.
I decided I'd try it on my own and managed to get to this final result. The way you read this is, the next two bytes of rng are in the form abcdefgh ijklmnop and let's say you want to figure out what value n will have. You look at the column for n and see that you have to XOR 1, g, h and i (from the given rng) together to get the value for n. There, it's easy to see why 0x00 0x00 will have 0x92 0x04 as the next value.
I agree that it is unlikely to be able reduce it even further.
Too bad.
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
That's a clever table representation, pretty cool.
I don't really see where the property that the rng goes through every possibility (except the AA-55 cases) comes from, but I guess I'll leave that for people who are better at math.
