Well, I dread Assembly (Which is what I'll presume this is), so I doubt that this would be a good route for me either. I'll let you all know if / when I have a bot that does anything substantial.
It's not that straightforward because even with brute force searching you can use clever algorithms to somewhat cut down the search tree, or at least prioritize branches which are more likely to give you a result. Also, in average it would take half of that time. The complexity class is correct, though (that is, O(2n).)
I already thought and tried to come up with some clever ideas
What I meant by cutting the search tree was things like: If two different paths lead to the same overall state, you can cut one of those search branches away completely (because they end up being identical to each other and hence would make the same subsearch twice). For example, if in one search branch you first press A and then B, and in another you first press B and then A, and the global state ends up being exactly the same in both cases, it's enough to check just one of those branches, rather than both. This will cut one complete search branch away.
(Of course detecting if the overall state of the program in two search tree nodes are identical is a big problem in itself, and may be too hard to be feasible. Basically you would need to store all the CPU registers and RAM contents on each node so that you can compare them. This may well take way too much memory to be feasible.)
You don't need to keep a state for every node though, you could use a keyframe-like system. Also, the amount of states you remove by comparing is probably gonna be very, very huge.
But. Most games already have a RAM value for keys held, so simple comparing save states doesn't work. There's also the possibility for things like simple holding start having no effect. You could prevent these branches from happening by not just comparing all states on frame n, but also comparing those on n and n-1. Of course, this increases running times, and timers also really mess with this.
Honestly, I think you'd need to write something that analyzes the ROM and interprets all the game's code. It would then need to reverse all that and then work it's way backwards from the wanted final state towards game start.
That sounds to me like solving the hard AI problem, personally. :) Teaching a computer to understand source code at anything above a syntactical level would be a monumental task.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Its unlikely you could make a AI bot that could universally TAS every game. I'd assume there would have to be some programmed goals and assumptions about a particular game. Such as Mario moving right and holding down the B button and being able to observe memory addresses and understand the signifcance of each of them. Yes, its possible that some obsure glitch or time saver might get overlooked, but its possible that a well programmed AI bot could beat certain games with less input than what a human TASer could achieve.
Honestly, I think you'd need to write something that analyzes the ROM and interprets all the game's code. It would then need to reverse all that and then work it's way backwards from the wanted final state towards game start.
Not possible. It is known as the halting problem. You want to know what kind of input to provide, given a program, to produce a certain type of outcome. Even without input, there's no way to know whether a program can produce a certain type of outcome (even if said outcome is the decision in a single particular branch instruction rather than the size of entire RAM), let alone what kind of input is necessary for it to happen.
Also, running a program in reverse is not possible due to the fact that there's no "comefrom" statement (except in INTERCAL, in which NES games were not written). What this means that at any point there's a possibility that the preceding instruction was a jump-instruction somewhere else in the code, and there's no way to know if that was the case (and testing each one of them creates an exponentially branching search tree). It is comparable to seeing a collapsed pile of <something>, and trying to "undo" the collapse step by step to see what the original shape was. There is no algorithm to do that.
Well, this is what I know from theory. I have never tried either one of these myself, so I don't know how far one can get with "good enough" heuristic programming. I don't want to discourage anyone from trying, just to inform anyone that trying to encourage others to try it will not be very successful.
I remember when I was a kid I didn't have the goal to beat games, but just to explore them. Maybe a universal TASing bot would have to start from there too. It'd be a much easier to define goal imo. A bot can certainly figure out how certain ram addresses affect each other because people can too, solely relying on algorithms and trial and error (raising hypotheses and testing them; raise such hypotheses first that have yielded much supporting evidence under similar conditions etc). It'd just be insanely difficult to program. I don't think that type of AI has ever been made.
You don't need to keep a state for every node though, you could use a keyframe-like system.
I don't understand what you mean.
The only way two search branches will be identical is if they start from the exact same state. This means that all CPU registers and the entire RAM are identical in both nodes. The only way to know this is to store the state in each node so that you can compare them.
The NES has 2 kB of RAM, which isn't a lot. However, it starts becoming quite a lot when you need to store it billions of times in that many nodes.
You don't need to keep a state for every node though, you could use a keyframe-like system.
I don't understand what you mean.
As you're also keeping track of the input for each branch, you can store a state every n frames, then "deduct" the state for a given node by applying it's input to the closest node that does have a stored state.
Also, my last post was kinda meant to point out that, unless you use a heuristic that will be incomplete and hence will not produce movies like Chrono Trigger or Pokemon Yellow or anything similarly glitched, the only option is actually brute forcing.
As you're also keeping track of the input for each branch, you can store a state every n frames, then "deduct" the state for a given node by applying it's input to the closest node that does have a stored state.
Well, if you don't mind your search being at least an order of magnitude slower... (After all, every time you create a new node, in other words, in emulator terms, every time you advance one frame in any search branch, you would have to find out if the resulting state is identical to an existing state... anywhere in the tree. Getting this to be even moderately fast would require very clever algorithms, and having to run the emulator on each node to get its state would certainly not help.)
Well, thinking about it, you could actually store just a checksum of the state in each node. This checksum could be used as a quick-rejection test (if the checksum is different, the node is most probably not identical; of course one would have to use a checksum algorithm that minimizes collisions). Only if checksums match then one would have to figure out the actual state of the node.
Also, my last post was kinda meant to point out that, unless you use a heuristic that will be incomplete and hence will not produce movies like Chrono Trigger or Pokemon Yellow or anything similarly glitched, the only option is actually brute forcing.
I think you mean "if you use a heuristic" (rather than "unless"), it would not find glitches?
Joined: 7/30/2011
Posts: 129
Location: Watching a TAS in the basement...
I know this topic is old, but I think it'd be really cool to see one of these in action. Is there anything that could work within a reasonable amount of time (obviously discounting Lunar Pool).
I've been thinking about it myself. In order for standard AI techniques to work well in a platformer, it should a) have an obvious way to measure progress within the level (e.g. a run-right-for-great-justice game, where you can just take the X coordinate+subpixel), and within the game itself; and b) have a relatively small maximum speed for the character (this allows you to come up with a good A* optimiser so that the AI can focus on later levels rather than continuously trying to improve the early levels). SMB1 might be a good game to try out that sort of bot on.
Developing a bot that worked for even one game would be very difficult, though, and to play it optimally rather harder. (There are already bots using this sort of technique that play randomly-generated Mario clones, incidentally; I don't have a link handy, but it shouldn't be too hard to find one.)
Joined: 6/25/2007
Posts: 732
Location: Vancouver, British Columbia, Canada
I wish brsolver was more well-known. It's a program that creates the optimal Worms Armageddon input file for any battle race map (beginning to end with jumping and walking). It's private because it could be used for cheating in online competitions, but it's a perfect example of optimal TASing done by a program.
Reading up on the halting problem in the link Bisqwit posted earlier, it seems that the halting problem is only undeciable on Turing machines with infinite memory. The NES, of course, does not have infinite memory, so the halting problem is actually decidable.
Reading up on the halting problem in the link Bisqwit posted earlier, it seems that the halting problem is only undeciable on Turing machines with infinite memory. The NES, of course, does not have infinite memory, so the halting problem is actually decidable.
No, the halting problem does not become decidable if you limit the amount of RAM. You still can't say "this algorithm will halt" (or not halt).
What happens with a finite amount of RAM is that some algorithms become uncomputable. In other words, you can't get an answer to the problem "will this algorithm halt?" because the limited resources don't permit running the whole algorithm. It may run out of memory in practice and hence either terminate because of that or enter an infinite loop (which is an incorrect implementation of the algorithm), but that's not an answer to the problem.
(Likewise a terminating algorithm doesn't become O(1) if you limit the amount of RAM, regardless of what its computational complexity was originally. The only thing you achieve with this is that some inputs cannot be computed. It doesn't change the complexity.)
The halting problem is indeed decidable for systems with finite memory, on systems with much much much greater memory; imagine running a NES emulator and savestating every step, then checking to see if two of the savestates were the same (if they were, you have an infinite loop). This is different from solving the halting problem for algorithms in general, and no existing computer is powerful enough to do it even for a NES.
Let's put it like this: The so-called halting problem does not make sense on systems with finite memory because the answer is trivial. The so-called halting problem implies that memory is unlimited because otherwise it's not a problem at all.
It's the same as with computational complexity. The question "what is the computational complexity of this algorithm?" only makes sense on unlimited RAM because otherwise the answer is trivial ("either O(1) or the algorithm cannot be computed because of limited RAM").
The answers to these questions are still useful in systems with limited memory because they provide useful information about the behavior of these algorithms and what can be deduced about them.
Has anyone considered using artificial neural networks? It's an interesting method to create A.I.
A neural net needs 1 or more inputs, processes the date and generates 1 or more outputs. The advantage of that would be, one won't have to program the A.I. itself (only the neural net), but rather, it 'learns' what it has to do. The more neurons available, the more it can learn.
However, my attempts at creating such artificial neural nets weren't very successful, and they might not at all be suited for playing or TASing games, but I think they still are worth mentioning.
Has anyone considered using artificial neural networks? It's an interesting method to create A.I.
A neural net needs 1 or more inputs, processes the date and generates 1 or more outputs. The advantage of that would be, one won't have to program the A.I. itself (only the neural net), but rather, it 'learns' what it has to do. The more neurons available, the more it can learn.
However, my attempts at creating such artificial neural nets weren't very successful, and they might not at all be suited for playing or TASing games, but I think they still are worth mentioning.
Neural networks do not make a complete bot, but they can be used to discover the ideal way to tackle an isolated situation with a finite number of variables. For example: http://robowiki.net/wiki/Neural_Targeting
