Joined: 11/13/2006
Posts: 2794
Location: Northern California
cwitty wrote:
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.
GoodNES lists about 22,000 ROMs, though I'm going to safely assume that the number of actual different games is about a tenth of that.
TASvideos Admin and acting Senior Judge 💙 | CohostwarmCabin wrote:
You shouldn't need a degree in computer science to get into this hobby.
You can do "better" than brute force. The problem with brute force is that it treats the game as a black box, and just kind of tries inputs until the desired end state is reached.
The more practical approach you'd use for automatic TASing would be symbolic execution with model checking. This allows you to turn your input state explosion into path explosion, which is smaller (multiple inputs go through the same path). The reason I put "better" in quotes is because the complexity is still exponential in the number of frames, but the constant factor is smaller.
I've been working on this on and off for some time, but never quite dedicated enough time to it for it to be useful. Maybe I should get back to it...
Ever since I wrote this script for predicting RNG in this run I wondered if the formula could be reduced. [...] So my question is: is it possible to reduce the formula or function to a simpler one?
Yes. Alyosha already noted how a single step in the inner loop behaved, which is basically a linear feedback shift register. For the code below, I used the standard bit library that comes with Lua 5.2, but any implementation or bit operators would do. I also, like creaothceann already mentioned, considered your RNG to be a single 16-bit value, rather than two bytes, which makes manipulation a lot simpler.
Language: Lua
require 'bit'
local function myRNG(rng)
local b
for i = 0x01, 0x0B do
b = 1 - bit.band(1, bit.bxor(rng, bit.rshift(rng, 1), bit.rshift(rng, 15)))
rng = bit.bor(bit.lshift(rng, 1), b) % 0x10000
end
return rng
end
You can do "better" than brute force. The problem with brute force is that it treats the game as a black box, and just kind of tries inputs until the desired end state is reached.
The more practical approach you'd use for automatic TASing would be symbolic execution with model checking. This allows you to turn your input state explosion into path explosion, which is smaller (multiple inputs go through the same path). The reason I put "better" in quotes is because the complexity is still exponential in the number of frames, but the constant factor is smaller.
I've been working on this on and off for some time, but never quite dedicated enough time to it for it to be useful. Maybe I should get back to it...
Counterpoints:
http://tasvideos.org/2285M.htmlhttp://tasvideos.org/984M.html
Both of these movies wait at the title screen for over a minute. Your proposed pathing model could not begin to exploit classes of bugs like these because it would almost certainly not model the title screen. The title screen is just an example, but the takeaway point is your model almost certainly cannot reliably be simpler than the entire execution context of the game program.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Counterpoints:
http://tasvideos.org/2285M.htmlhttp://tasvideos.org/984M.html
Both of these movies wait at the title screen for over a minute. Your proposed pathing model could not begin to exploit classes of bugs like these because it would almost certainly not model the title screen. The title screen is just an example, but the takeaway point is your model almost certainly cannot reliably be simpler than the entire execution context of the game program.
Sorry, I don't follow. Symbolic execution explores any reachable state, so I'm not sure where your supposed contradiction lies. Symbolic execution degrades to brute force in the worst case, so anything reachable by brute force is reachable by symbolic execution.
You say "model the title screen". I don't know where the idea that we needed to model the game is coming from, maybe I was too terse in my explanation. We model the system (NES, N64, etc.) at a cycle-accurate level and execute arbitrary programs, symbolically. (In practice, everything starts with concrete values and only the inputs are symbolic, and those propagate throughout the system.)
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.
For the Computer Science geeks around, a more formal proof. Not completely rigorous, but good enough, I think.
Definitions:Games: A game G(S,B,E,L,I,M) consists of (1) a set S of game states (think savestates), (2) a set B ⊂ S of starting states, (3) a set E ⊂ S of ending states, (4) a set L ⊂ S of losing states from which an ending state can never be reached (think gameovers, crashes and so on), (5) a set I of inputs, and (6) a map M:S × I → S that takes a state and an input and returns another state.
Game execution: Given a current state s ∈ S and a set of inputs (i1, i2, …, iN), the game execution corresponds to sequentially applying each input to the current state until all inputs have been used.
Game completion: a game execution that starts from a state b ∈ B and reaches an ending state after all inputs.
TAS Decision Problem (TASDP): Given an input game G(S,B,E,L,I,M) and an integer N, is there a game completion with an input of length at most N?
TASDP certificate: A state b ∈ B plus a set of N inputs (i1, i2, …, iN) such that executing the game from state b using these inputs will reach an ending state.
TAS Optimization Problem (TAS-OPT): Given an input game G(S,B,E,L,I,M), find a game completion such that no other possible game completion has an input of smaller length.
Theorem: TASDP is NP-Complete.
Proof: There are two steps:
(1) TASDP is in NP: given a certificate with input length N, the game can be executed using this input to verify that an ending state is reached. This takes N steps of execution; since verification of a solution is a polynomial of N (linear, in fact), then TASDP is in NP.
(2) Every problem in NP is reducible to TASDP in polynomial time: this can be demonstrated by reducing any other NP-Complete problem to TASDP. Here, I will show that the Traveling Salesman Problem (TSP) with positive integer weights can be reduced to TASDP.
An input to TSP is a weighted complete graph K(m, w) with m vertices and an integer k; as mentioned above, we will assume that all weights w are positive integers. We will construct a (rather boring) "game" G(S,B,E,L,I,M) for TASDP as follows:
S: Each state in S consists of (1) the current vertex, (2) the total accumulated cost and (3) a sequence of m bits, with 1 being 'visited' and 0 being 'not visited', one for each vertex in K(m, w).
B: all states in which all visited bits are 0 and the total cost is 0.
E: all states in which all visited bits are 1 where the total cost is at most k.
L: all states in which the total cost is higher than k, plus all states in which the total cost is exactly k but at least one visited bit is 0.
I: an input is the target vertex to visit.
M: starting from vertex i with total cost c and visited bits b, and with input j, then:
if i ≠ j: next state is at vertex j, total cost = c + w(i, j), and sets bit j in b.
if i = j: next state remains at vertex i, total cost = c + k + 1, and sets bit i in b. This makes staying on the current vertex a losing proposition, as an ending state can never be reached.
The integer N is equal to the integer m. This forces at most m inputs, and makes sure the tour visits all vertices and returns to the initial vertex.
Note that, for this particular case, explicit generation of all states in S, E or L is not necessary: only the starting states need to be generated, and everything else can be done lazily. Generating the starting states is O(k), the valid inputs are also generated in O(k), the transition function can be generated in O(1) by a direct adaptation of the description above. Thus the game can be lazily generated in polynomial time in the size of the TSP graph. Moreover, every graph K(m, w) will become a unique game G(S,B,E,L,I,M) by construction. The TASDP constructed this way will return "yes" if and only if the original TSP returned "yes", and so TASDP can be used to solve TSP. Since TSP is NP-Complete (even the positive integer weighted variant), this means that TASDP is NP-Complete. ∎
Theorem: TAS-OPT is NP-Hard.
Proof: TAS-OPT is the optimization version of TASDP. Since TASDP is NP-Complete, then TAS-OPT is NP-Hard. ∎
In other words:
Aqfaq wrote:
Is there a method for proving a TAS to be optimal without brute-forcing all input patterns?
For any given game you might be able to do that; for the general case, no.
Edit: added losing states to definition of games and to the polynomial reduction of TSP.
Ever since I wrote this script for predicting RNG in this run I wondered if the formula could be reduced. [...] So my question is: is it possible to reduce the formula or function to a simpler one?
Yes. Alyosha already noted how a single step in the inner loop behaved, which is basically a linear feedback shift register. For the code below, I used the standard bit library that comes with Lua 5.2, but any implementation or bit operators would do. I also, like creaothceann already mentioned, considered your RNG to be a single 16-bit value, rather than two bytes, which makes manipulation a lot simpler.
Language: Lua
require 'bit'
local function myRNG(rng)
local b
for i = 0x01, 0x0B do
b = 1 - bit.band(1, bit.bxor(rng, bit.rshift(rng, 1), bit.rshift(rng, 15)))
rng = bit.bor(bit.lshift(rng, 1), b) % 0x10000
end
return rng
end
Nice, question answered! I guess this thread accomplished something!
Proofs of complexity class are a bit beyond me, although I do wonder if there will ever be a game that is proved to be beaten as quickly as possible?
One question I have wondered about is if there is another practical way to TAS besides emulation, like hardware direct TASing?
As there is desire to TAS games on newer and newer consoles, it seems unlikely that emulation will be able to keep up at reasonable speeds on home computers, is there a workable alternative?
Any more little game mysteries anyone can think of too?
Note that a problem being in NP doesn't necessarily mean it's hard to solve (ie. exponential-time) in practice. There are NP-problems that can be solved relatively fast in practical cases. Them being in NP simply means that you can give it an artificially-created pathological input that's relatively small, but would take the algorithm more time to solve than the age of the universe.
Example: Given a dictionary of words, and N characters, find out which words can be formed using those characters.
The absolutely pathological situation would be if the dictionary contains all words using all possible combinations of characters, in which case the answer contains N! words, which is exponential.
In practice, however, ie. with actual dictionaries (eg. an dictionary of valid English words), the problem is usually solvable in a fraction of a second, basically regardless of what N is. That's because in practice a dictionary is extremely limited in size and content, and you don't have to try every possible permutation of the N characters to find all the words that can be formed with them.
Of course this doesn't mean this is the case with all NP problems. Some are hard with even rather trivial input.
One question I have wondered about is if there is another practical way to TAS besides emulation, like hardware direct TASing?
High quality Mario Kart Wii TASes have been made on the Wii itself. There are cheatcodes to copy ghost input and slowdown gameplay. TASing on emu is far better if possible, though.
Counterpoints:
http://tasvideos.org/2285M.htmlhttp://tasvideos.org/984M.html
Both of these movies wait at the title screen for over a minute. Your proposed pathing model could not begin to exploit classes of bugs like these because it would almost certainly not model the title screen. The title screen is just an example, but the takeaway point is your model almost certainly cannot reliably be simpler than the entire execution context of the game program.
Sorry, I don't follow. Symbolic execution explores any reachable state, so I'm not sure where your supposed contradiction lies. Symbolic execution degrades to brute force in the worst case, so anything reachable by brute force is reachable by symbolic execution.
You say "model the title screen". I don't know where the idea that we needed to model the game is coming from, maybe I was too terse in my explanation. We model the system (NES, N64, etc.) at a cycle-accurate level and execute arbitrary programs, symbolically. (In practice, everything starts with concrete values and only the inputs are symbolic, and those propagate throughout the system.)
It was probably both the result of my staying up too late and misunderstanding what you meant by "model checking." I did not realize you were referring to model checking in the finite state systems sense, but rather assumed you were talking about creating a simplified model of the game to heuristically prune away game states.
I withdraw my objection.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
One question I have wondered about is if there is another practical way to TAS besides emulation, like hardware direct TASing?
High quality Mario Kart Wii TASes have been made on the Wii itself. There are cheatcodes to copy ghost input and slowdown gameplay. TASing on emu is far better if possible, though.
Oh, that is a cool feature, too bad more games don't have that.
Also for the Rockman ZX rng question, do you know the addresses for the IDs for the drops? I'm pretty sure only 3 bytes are involved in picking the drop, so maybe you can make a save state one frame before killing an enemy, and make a LUA script to simply enumerate through the ~16 million RNG possibilities to get a complete table? It won't help in manipulating those RNGs to come up, but maybe you can see a pattern.
Note that a problem being in NP doesn't necessarily mean it's hard to solve (ie. exponential-time) in practice. There are NP-problems that can be solved relatively fast in practical cases. Them being in NP simply means that you can give it an artificially-created pathological input that's relatively small, but would take the algorithm more time to solve than the age of the universe.
It is one of the reasons I chose to reduce TSP to the TAS problem: TSP has exact solutions for rather large instances (for example, it has been solved for the continental US), and there are rather high quality heuristics that average about 1% above the Held-Karp lower bound for a great many instances.
On the other hand, the "game" corresponding to TSP is positively trivial compared to most actual video games...
On retrospect, I think that the definition of "game" in my previous post should be extended to include "losing states": those states from which an ending state can never be reached. This would cover crashes, for example, as well as getting a game over. For the TSP game, this would mean all states with total cost greater than k.
make a LUA script to simply enumerate through the ~16 million RNG possibilities to get a complete table? It won't help in manipulating those RNGs to come up, but maybe you can see a pattern.
Has been done and we’ve found a pattern that loops every 80 iterations through the items table. The items table is LH->SH->NT->LE->SE->LC->SC(*) then it cycles back to LH, but life ups are a wildcard that can happen anywhere between 2 items, and the amount of each item between cycles varies (until it does 80 cycles, then it loops back to cycle 1 on cycle 81). I also have a list of every RNG number that gives a life up.
I don’t know how to figure anything out from this information, though. I feel stupid. Here’s some of the info: http://pastebin.com/acExBvgT
*Large health -> small health -> nothing -> large energy -> small energy -> large crystal -> small crystal.
oh cool, you found something!
Well now, as you play the game, if you know when the RNG updates, you can kind of predict the future right? For example you will know what the RNG will be 30 frames into the future, and will know how far you are from getting a 1-up or any item you want and how much you need to adjust?
That was my original thought anyway, but maybe the cycle you found can be useful in other ways?
EDIT:
To expand on this a bit. You already know the RNG seed for each level and how the RNG formula works, so if the RNG simply updates once per frame, what you can do is map out the item that will appear at every frame in the level simply by running the RNG code and matching the result to the table you made.
Then you just need to kill an enemy on the right frame, which you now already know.
what you can do is map out the item that will appear at every frame in the level simply by running the RNG code and matching the result to the table you made.
Well, I didn’t actually map out the ENTIRE RNG. That would take years of computing time. Anyway, I did some work, and found out something:
RNG item drop loops every 5699 values. The “first” loop is −1 to 5697. From this you can make up the following formula: RNG modulo 5699 = x, x = whichever item it matches in the first loop. This way, you only need the first loop for a lookup table, rather than the entire RNG.
Now I just need a way to make this information usable… Could probably make a useful Lua out of this, but I suck at programming and I’m not sure what exactly I should program.
I also forgot to mention that there are 2 drop lists in the game, all this talk was about drop list A. Drop list B isn’t that interesting because it doesn’t contain Life Ups; so I don’t think I’ll do any work on it…
Edit: Oh my god I’ve run into a problem… 1683597101 gives a Life Up, but 1683597101 % 5699 isn’t = to a Life Up value from the first loop. Why? ._. Same thing happens with 501745596…
It seems to me like at some point when the RNG gets too big, the modulo stops working. Why, though?
Edit: I’ve attempted RNG % 2^16 % 5699 and RNG % 2^24 % 5699 both, but both are still wrong for at least the first number written up there (1683597101)…
what answer is it giving?
Is it working on lower RNG values and only failing up to that point?
You could also write a little code to just subtract 5699 from the RNG repeatedly until it gets the modulo result to test it.
By the way why are you starting at -1?
Uhm does it matter? Gives something that isn’t a Life Up.
Alyosha wrote:
Is it working on lower RNG values and only failing up to that point?
I’ve mapped out the drop list up to 23663 and % 5699 works on all tested values in it. Those 2 values that don’t work I’ve found manually while randomly playing. I think I’ll try to find the earliest value where % 5699 stops working, eventually.
Alyosha wrote:
You could also write a little code to just subtract 5699 from the RNG repeatedly until it gets the modulo result to test it.
Not sure what you mean.
Alyosha wrote:
By the way why are you starting at -1?
It’s arbitrary. I wanted to start at 0, but −1 is the actual start of that specific cycle that 0 is a part of.
I have an idea what the problem might be I think.
Only the first 3 bytes of the RNG effect the item outcome as far as I tested.
so RNG's larger then 2^24 need to be dealt with by only considering the first 3 bytes of the number.
so RNG's larger then 2^24 need to be dealt with by only considering the first 3 bytes of the number.
In an attempt to make up for that I tried RNG % 2^24 % 5699 (which didn’t work), is that not correct? What should I do? Edit: Gave it another look and as I see it % 2^24 equals “considering the first 3 bytes”. Well, it still doesn’t work with 1683597101…
1683597101 % 2^24 % 5699 =
5531 = big energy
5317 life up
5602 life up
1683597101 % 5699 =
4220 = Nothing
4106 life up
4391 life up
Hmm sorry I wasn't specific enough , by first 3 I mean address wise, not numerically.
So the RNG bytes are AA BB CC DD
AA BB CC determines item drop
So mod24 doesn't work since that is like using BB CC DD
When you calculated the table did you do it this way?
When you calculated the table did you do it this way?
Calculated what now?
What you say sounds pretty weird… If it takes the first 3 bytes address-wise, that should mean that 0–255 should all give the same item drop (since it would be 00 00 00 00–FF address-wise), but as seen from my dumps and just by testing, that’s not the case.
Edit: Attempt:
1683597101 = 0x6459A72D first 3 bytes = 0x6459A7? = 6576551
6576551 % 5699 =
5604 = Big Energy
5602 life up
5673 life up
Yes that is strange . I will do some testing and try to track down what is going wrong.
EDIT:
Ok so all my testing was in the intro stage. I'm guessing this is an area that uses the other drop list you were referring to since I tried your RNG that should give a 1-up and got nothing.
So I'll get to a region that has the proper list and test from there.
EDIT:
Ok so all my testing was in the intro stage. I'm guessing this is an area that uses the other drop list you were referring to since I tried your RNG that should give a 1-up and got nothing.
Intro stage is actually correct. You have to freeze the RNG value to get the drop I’ve listed.
Ohhhh ok I get it now, I had the wrong endianness.
now it makes sense. Well it still has the same behavior I mentioned before. Only the first 3 bytes effect the item. You can test this yourself by simply using 2D A7 59 XX (the first three bytes from 1683597101) they all give 1-ups.
In your example, the first 3 bytes are 0x59A72D = 5875501
5875501 % 5699=5531
But since this definitely gives a 1-up, there must unfortunately be something wrong with your list or formula.
