Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Better late than never just my 2 cents:
I did not like the TAS either due to the OOB-looking sections.
But what exactly is going "wrong" here for me? After all, there are very many videos where similar clipping occurs: SMB 64, Zelda Screen wrap, Super Mario Cart, just to name a few. And I don't mind the clipping there.
The main difference for me is that I - as a viewer - completely loose orientation. That is what bothers me: I see Samus running around and suddenly - BAM - the graphics glitch, some door-transition occurs and I think: "Oh, there she is". This is not some clever move I can only follow in slow-motion. It's just a total interruption. And that's the point where I think: "That's not a minor glitch anymore".
This might be some criterion to classify glitches as major: If a viewer who knows the game looses orientation (even in slow-motion), it is not a minor glitch anymore.
The technical reasoning for it being a minor glitch is definitely sound. But after all, the mission-statement of the site is to create entertaining videos. Not videos where the viewer needs to read a manual to understand that a major-looking glitch is only a minor one from a technical perspective.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
I am wondering about a detail in the medusa-fight: AFAIK, you shoot as quickly as possible. Shouldn't it help the to shoot the first shot from a longer distance and the last one from the shortest distance possible?
Since the first shot can be released sooner and the last shot takes shorter to reach the target, this should gain some time.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
FYI:
The youtube-video is not available in Germany :-(
Youtube claims that the video contains music from Sony Music Entertainment and has thus been blocked.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
A very nice run that I really enjoyed.
One question though:
Directly after Dungeon 7 (23:17 on Youtube) after walking south: Why didn't you get back up into the menu-area and walk to the left there? Looks like this would have been 1-2 seconds faster?
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Derakon wrote:
I have implemented A* for my own game work, thanks. It's not a very complicated algorithm.
Good to know. That's makes the discussion a lot easier. Where did you try it? And how did it perform? Did you implement it directly in an emulator or did you use some interface?
* At the start of each level, turn around, jump, and then start moving forwards
This should IMO be easily found since AFAIK it pays off after a few seconds only.
* Collect a mushroom and fireflower so the fortress level(s) can be finished faster
IMO this cannot be solved by A*. Here the implementor will have to define different scenarios, let A* evaluate them and choose the best one.
* Going through the wall in 1-2 to get to the warp zone faster
Since this is faster than running on top, A* should find this automatically.
* The flagpole glitch
If it was an unknown glitch, A* would probably not find this. But since it is a known glitch, the target can be defined accordingly by not defining it as reaching the flagpole but reaching the next level.
* The flagpole glitch with jumping off of an enemy
Should be found as well IMO.
* The vine screen-scrolling glitch
This is a tough one, since the situation is hard to evaluate. The goal will have to be set by the programmer, just like with the mushrooms.
* Avoiding fireworks
Define the goal as reaching the next level (and not the flagpole) and rate the states accordingly.
The trick is to win optimally. And that requires far more lateral thinking than A* is going to be able to provide.
That's a good summary: A* is not artificial intelligence that will use some kind of creativity to win a game. Instead it is can be a good tool to find a perfect way along the paths, the programmer has in mind.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Derakon wrote:
As a general rule, this falls under "trying to solve games programmatically" and has similar flaws.
Before diving into the details, I would be interested in knowing who in this thread did actually know A*-search before reading this topic.
Now the details:
I am not sure that this will actually work either (otherwise I would just do it and not post here). BUT: If you do find a good evaluation-function for the state of the game, the algorithm works very efficiently and is NOT a brute-force-approach, but an informed search-algorithm that has to be tailored for each game it should be applied to.
Wikipedia shows a nice picture that shows the efficiency and the issues, this algorithm has:
1.) Before hitting the obstacle, the algorithm pursues a direct path.
2.) Upon hitting it, it has to go "wide" and examine a wide variety of states to find the perfect way around the obstacle.
Thus: As long as the game does not have many of these obstacles that slow down the progress, it should be very efficient to solve.
SMB falls into this category IMO.
Just to be clear: a tube you can jump over is not a relevant obstace, since it does not slow down progress. But a platform you have to wait for for severy seconds would create a severe hit in performance.
Basically, it all comes down to a graph-traversal-issue: What are the paths that are worth evaluating? This graph is really complex for most games. But A* offers two relevant means of reducing the computational complexity significantly:
1.) Detection of duplicate states
Many button-combinations lead to an equal state of the game. Let's take the starting-position of SMB and a simplified controller where you have only the buttons "up" and "right". That is 4 combinations per frame. If you made a pure brute-force-approach, after 60 frames, there would be 4^60 (about 10^36 states). Sounds frustrating! But if you detect the duplicate states, this number is reduced dramatically.
2.) Detection of inefficient states
Here the evaluation-function comes into play: Each state is rated by adding the amount of frames needed to get there and the (estimated) least amount of frames needed to complete the level (e.g. until after the fireworks have ended). Then the state with the smallest sum will be evaluated.
Here, all the moves that are too inefficient will be ignored.
Let me show a very simplyfied example to show how efficient the algorithm can work:
Imagine a game, where you just have to run 10m to the right. You start at position 0 and win when reaching 10. For each second, you have to decide if you want to want to run 1m to the left or the right.
Thus when starting the game, you have to decide if you run 1m to the left or the right.
A* will try both and end up with to states:
a) 1s into the game, standing on position 1 (1m to the right)
b) 1s into the game, standing on position -1 (1m to the left)
Now each state will be rated:
From state (a) you will need at least 9s to finish the game (9m left, 1m/s). State (a) is thus rated with 1s into the game + 9s to finish = 10s
State (b) is accordingly rated with 1s into the game + 11s to finish = 12s.
Now the algorighm chooses the best-valued state, which is (a) and evaluates the possible actions.
After this, there are three active states:
a) 2s into the game, standing on position 2 (twice to the right)
b) 2s into the game, standing on position 0 (once right, once left)
c) 1s into the game, standin on position -1 (the original state (b))
Let me introduce a shorter notation:
a) 2s, 2m, RR
b) 2s, 0m, RL
c) 1s, -1m, L, already known to have a rating of 12s
States (a) and (b) still need to be evaluated:
(a) will be rated with 10s: 2s into the game + 8s minimal completion time
(b) will be rated with 12s: 2s into the game + 10s minimal completion time.
Again, the best state will get further evaluation:
a) 3s, 3m, RRR, rated with 3s+7s=10s
b) 3s, 1m, RRL, rated with 3s + 9s = 12s
c) 2s, 0m, RL, already known to be rated as 12s
d) 1s, -1m, L, already known to be rated as 12s
You probably got the idea by now. And when applying this further, the optimal solution will be found with reaching the goal with the perfect time of 10s and only 20 evaluated states. Compare this to brute-forcing the game: There you would have had to evaluate all 2^10 = 1024 states. That's a very significant reduction that does even grow for longer periods:
If the goals was at 100m instead of 10m:
A* would need only 200 states, while brute-forcing would need 2^100 (about 10^30) states.
But we still don't have anybody around who actually tried that, do we?
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
thelegendarymudkip wrote:
The problem with that is that it doesn't take in account glitches.
That depends on the kind of glitch.
If the glitch takes too long to set up, it will probably not be found, since only "promising" states are examined. The hopping at the beginning of each level will probably be found easily.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Hi,
did anybody ever try to solve a game by using an A*-search?
(http://en.wikipedia.org/wiki/A*_search_algorithm)
This algorithm guarantees (under some assumptions) a perfect and unbeatable result.
IMO this algorithm should work very well for many old jump'n'run-games and deliver perfect solutions in a very reasonable time.
Let me describe the most important part in a few sentences, but be warned: This might be a bit theoretical!
You can read for an hour in the wiki or just believe the following statement:
The core of the algorithm is the evaluation-function of a gamestate: "How long will it at least take from here to the end?".
As long as this function does NEVER report a value that is higher than the value that is actually achievable, the algorithm will definitely find the perfect solution. That's it! Let's leave the algorithm's internals aside and concentrate on this evaluation-function.
You might want to take a shortcut and take the easiest evaluation-function possible: Always estimate the remaining time with "0".
You can do that, since this function fulfills the requirement: NEVER report a value higher than the value that is actually achievable. Thus the algorithm will eventually find a perfect solution.
BUT: With this function, the algorithm will basically brute-force the game, which will take far too long.
You see where this goes: The better the function is at estimating the remaining time (without ever returning a result too high), the faster the algorithm will terminate.
So we should provide a function that comes closer to the actual results.
If you take for instance Super Mario Bros:
Just return the time it would take to run from the current position to the flagpole at top-speed. Since mario does rarely slow down during the run, this simple estimate should be very good. In practice you would need some more fine-tuning to account for shortcuts inside the levels.
So back to the initial question:
Did anybody ever try to do that in an actual game?
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
feos wrote:
Ilari wrote:
AndiHoffi wrote:
Is there a way to get a whole memory-dump in lua? I did not find anything like it in the doc. Without the memory-dump, I can stop the whole thing immediately, since there would be no way to detect equal states (that have been reached on two different ways).
Whole emulated system memory or whole host process memory?
The first isn't the complete state (there are e.g. CPU registers), and the second contains all sorts of irrelevant stuff (that likely differs even if states are identical).
Wouldn't one only need critical addresses values?
First of all: I think, I found the method minutes after posting. That's why I removed the question hoping nobody saw it yet :-)
About the critical addresses:
In order to rate a state, I do only need a few critical addresses. But in order implement an efficient search, I need to detect duplicate states.
E.g. in most jump'n'run-games it does not matter if you keep the jump-button pressed or not, while you are falling down. So I do need the whole machine-state in order to check if the same state was reached in two different ways. This consists at least out of the following things: frame-counts, full memory-dump, registers, buttons pressed. Perhaps the memory-dump can (and should) be filtered some more if the game saves some really unimportant stuff there (like a statistical buttons-pressed-count...). I did not check this yet, since I am still in the middle working on a proper communication with Lua.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Derakon wrote:
I suspect you'd have more luck figuring out how to write the necessary inter-language glue code needed to control Lua from your language of choice.
This sounds like an interesting approach, I did not think about yet.
Using sockets might actually do the trick (but wouldn't be fast).
Perhaps the WinAPI-Library contains something useable as well.
Have you done something like that before?
About the design:
"wrong" is a hard word and I would never say that about FCEUX. I do know how tough it often is to maintain an old codebase. A modern design would probably be to build the emulator-library first and the frontend on top of it. But since I do not know the internals, I don't want to judge anything. I was just hoping that this kind of API does exist somewhere :-)
I do sincerely doubt that LUA is by far the easiest way to do that.
Having the emulator-functions (http://www.fceux.com/web/help/fceux.html?LuaScripting.html) in a dll would be the easiest for me and I would already have written an adapter and be in the "fun-zone" by now :-)
Without this, I am reading and trying around how to solve the issues that stand in my way:
- how to integrate some SQL-module
- how to serialize an object
- finding a way to hash an object for faster comparison
All these are issues that I would not have in my preferred language and more will probably come up very soon.
While trying so solve these issues, I am finding myself tempted to just crawl through the sources of FCEUX and find the necessary hooks myself. But this is not the easiest thing to do either...
All I wanted to do is to try a simple A*-search, which might work very well for a bunch of games. A proof of concept (for the first few seconds of the game) would take only about a day for me in C#. After having read several hours about Lua, I am not even sure, the stuff I want to do is possible at all. Actually doing it, will probably take much more than a week.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
AnS wrote:
can you tell me which link brought you there?
Not exactly. It turned up during googling. The search "fceux external input" still leads there.
AndiHoffi wrote:
My goal is to get a reliable interface to control FCEUX from my own code.
Well, Lua is pretty reliable. Why do you think everyone uses it?
It's definitely reliable, but frankly speaking I don't like having to learn the gazillionth special-purpose-language that has only minimal developing-support. AFAIK, lua ist still mostly written with text-editors. The disadvantages compared to a full-blown IDE (like Eclipse or Visual Studio) are obvious.
As I wrote somewhere else: I was hoping that FCEUX offers the API that lua uses for external usage. This way everyone could use his preferred language to code against this API.
I guess, this does exist somewhere inside FCEUX's internals anyway (how else should lua be able to use it?). So all it would need is someone knowing his way around in FCEUX to export this interface to a windows-dll (in my case :-)).
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
DeHackEd wrote:
What language do you want exactly then?
A language with a nice IDE and Debugger :-)
Like C# or Java. So for Windows, some dll would suffice. I don't need the gui. Just a dll where I can load a rom, set the machine's state, the controller-input and read the RAM to check the input's results.
In another forum, someone is basically controlling the GUI of FCEUX using C#. But IMO this can neither be fast nor reliable.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
adelikat wrote:
So you are asking for someone to re-implement what's already built due to your resistance to a particular language?
I was hoping that something like this does already exist. Especially FCEUX has so many extensions that I thought that there must be some kind internal of API that might also be exposed for external usage.
About the language of choice:
It's always easier to do something in the language you know instead of learning a new one with new ways to get things done:
- Is there a nice IDE for lua?
- What about debugging the scripts?
- How do I get access to a database?
- What about structuring the code into modules?
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Hi,
I just read the part "ExternalInput" in the documentation:
http://www.fceux.com/web/fceux-2.0.2.htm?{19278BFA-FEA2-4A51-867F-26DA4B7430F2}.htm
This sounds like a nice external interface to control the emulator without using lua. Is the any more information available besides this page?
My goal is to get a reliable interface to control FCEUX from my own code.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Hi,
I am currently thinking about solving a specific NES-game not by myself, but by using the A*-algorithm.
But in order to do this, I need an emulator that I can control via some kind of API:
- Bring the NES to a specific memory-state
- Specify the buttons pressed
- Advance a frame
- Get the new memory-state
Does something like this exist?
No, I don't want to use LUA :)
Thank you
Andreas
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Hi,
I am wondering, why there is no 100%-like-run for this game.
Since a real 100%-run is impossible for this game (without dying), we need another goal:
Get as many items as possible without dying during one run.
Everything you collect counts as one item: Coins, Mushrooms, Fireflowers, 1-Ups, Stars do all count as one item.
Would anybody be interested in such a run?
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
AnS wrote:
Unfortunately, this doesn't seem to work well, because with more comfort people only become more lazy. We lower our own limit of patience accordingly with the new (lowered) level of difficulties. That's why I'm not even sure if there's any point in further development.
Basically, you are saying that better tools lead to worse TASes. Or the other way around: Worse tools lead to better TASes.
Interesting point. So I guess, you are making all your TASes directly on a console and achieve the perfect results, since a console is the worst instrument for a TAS?
I only did one TAS yet, and this one with the TASEditor. I cannot even imagine how much more work it would have been without the TASEditor. And without it, I would probably not have done the TAS at all. Making a TAS this way, did actually just "feel right".
IMO, this is a great tool that offers very comfortable ways for both: trying multiple options and optimization.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
goofydylan8 wrote:
But I really wish that when people make small improvements to their own submissions they would write a full submission text instead of just reference the old comments. It is annoying when later on you want to read about how a run was made and you have to jump back through the previous few groups of submission comments to get a grasp. Even if it is just a copy-paste of the old text with the same note you have currently put first it helps.
Good point! So I added some kind of version-history.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
Ace Of Hearts wrote:
So here's what I'm gonna do. I'm gonna vote Yes on this, since I was entertained, and say that I'm fine with this being published, because it is a well-done high-completion run - but I'm also going to put it out there that I suggest a truer 100% run that bothers to get the White Sword, Blue Ring, and Big Shield would obsolete this, even at time cost.
I do support that. The rule "get everything that cannot be lost" is a very clear one, but IMO the result does neither really fulfil "all items" nor "100%". So this IMO very nice run should be published and be eventually obsoleted by a run that collects the items mentioned above. The category should be "all items".
IMO a real 100%-run should actually show all the game's secrets: All the items, all the caves, all dungeons and both bomb-upgrades.
Experienced Forum User, Published Author, Player
(161)
Joined: 1/1/2013
Posts: 43
FractalFusion wrote:
Well, it doesn't have to be an atlas map encode. Even any kind of map display showing which rooms have been visited is good.
What about the following idea:
The movie will be encoded on the right side of a map (thus the video will be about twice as wide as a normal encode).
This map will look very similar to the ingame-map, but will be rotated to have the same orientation as the floors inside the rooms. The room, Shadax is currently in, will be displayed in green and rooms already visible will be yellow.
No idea how to actually do that though :-)
I guess, there are no technical impossibilies in the way, but a handfull of issues that need to be solved...
Thanks. I had a look at it and it's really impressive. There is already some kind of game-map (http://www.vgmaps.com/Atlas/NES/Solstice-Kastlerock.png). But somehow I don't have enough imagination how a nice ingame-map might look like: The rooms just don't fit close enough to each other graphically. Especially the rooms that you can leave at the top or bottom might look a little awkward...
Any ideas?
1.) Before hitting the obstacle, the algorithm pursues a direct path.
2.) Upon hitting it, it has to go "wide" and examine a wide variety of states to find the perfect way around the obstacle.
Thus: As long as the game does not have many of these obstacles that slow down the progress, it should be very efficient to solve.
SMB falls into this category IMO.
Just to be clear: a tube you can jump over is not a relevant obstace, since it does not slow down progress. But a platform you have to wait for for severy seconds would create a severe hit in performance.
Basically, it all comes down to a graph-traversal-issue: What are the paths that are worth evaluating? This graph is really complex for most games. But A* offers two relevant means of reducing the computational complexity significantly:
1.) Detection of duplicate states
Many button-combinations lead to an equal state of the game. Let's take the starting-position of SMB and a simplified controller where you have only the buttons "up" and "right". That is 4 combinations per frame. If you made a pure brute-force-approach, after 60 frames, there would be 4^60 (about 10^36 states). Sounds frustrating! But if you detect the duplicate states, this number is reduced dramatically.
2.) Detection of inefficient states
Here the evaluation-function comes into play: Each state is rated by adding the amount of frames needed to get there and the (estimated) least amount of frames needed to complete the level (e.g. until after the fireworks have ended). Then the state with the smallest sum will be evaluated.
Here, all the moves that are too inefficient will be ignored.
Let me show a very simplyfied example to show how efficient the algorithm can work:
Imagine a game, where you just have to run 10m to the right. You start at position 0 and win when reaching 10. For each second, you have to decide if you want to want to run 1m to the left or the right.
Thus when starting the game, you have to decide if you run 1m to the left or the right.
A* will try both and end up with to states:
a) 1s into the game, standing on position 1 (1m to the right)
b) 1s into the game, standing on position -1 (1m to the left)
Now each state will be rated:
From state (a) you will need at least 9s to finish the game (9m left, 1m/s). State (a) is thus rated with 1s into the game + 9s to finish = 10s
State (b) is accordingly rated with 1s into the game + 11s to finish = 12s.
Now the algorighm chooses the best-valued state, which is (a) and evaluates the possible actions.
After this, there are three active states:
a) 2s into the game, standing on position 2 (twice to the right)
b) 2s into the game, standing on position 0 (once right, once left)
c) 1s into the game, standin on position -1 (the original state (b))
Let me introduce a shorter notation:
a) 2s, 2m, RR
b) 2s, 0m, RL
c) 1s, -1m, L, already known to have a rating of 12s
States (a) and (b) still need to be evaluated:
(a) will be rated with 10s: 2s into the game + 8s minimal completion time
(b) will be rated with 12s: 2s into the game + 10s minimal completion time.
Again, the best state will get further evaluation:
a) 3s, 3m, RRR, rated with 3s+7s=10s
b) 3s, 1m, RRL, rated with 3s + 9s = 12s
c) 2s, 0m, RL, already known to be rated as 12s
d) 1s, -1m, L, already known to be rated as 12s
You probably got the idea by now. And when applying this further, the optimal solution will be found with reaching the goal with the perfect time of 10s and only 20 evaluated states. Compare this to brute-forcing the game: There you would have had to evaluate all 2^10 = 1024 states. That's a very significant reduction that does even grow for longer periods:
If the goals was at 100m instead of 10m:
A* would need only 200 states, while brute-forcing would need 2^100 (about 10^30) states.
But we still don't have anybody around who actually tried that, do we?