Gah, okay. Imagine you need to collect 7 rupees. Imagine that to collect 1 rupee a room would require the second fastest route for that room. Imagine the difference from the fastest time is 28 frames because you lose 4 frames each room to pick up the rupee. Now imagine, in any of the 7 rooms, 6 rupees can be collected with a 15 second delay. Now there's the 4 frames for the last rupee, and we have 15+4 = 19.
We should go with the longest delay in one room because it leads to a shorter time over all, by 28-19=9 frames.
Now, if we know all of this, we can compute what we should do for each room. However, if our actions in one room influence our actions in another room, then we're screwed. Imagine that 6 rupee pick-up could ONLY happen if we took the second fastest route in room #1.
In short, to calculate what we should do REQUIRES a full game tree which is incalculable.
We could just use my little formula and brute force as we go, which would still be faster than a human run, but technically not perfect. I'm wondering, also, maybe all of this thought is merely mathematical/theoretical, but pointless for Zelda 1. Perhaps the rupee quota will be meet itself just by Link walking over rupees on his shortest room path. If not, we're just going to have to go with our human intuition as to which routes we want to take for a room depending on how important picking up that rupee drop is. For some reason, I believe that the intuition of someone like TSA would be better than any mathematical formula we can come up with, because he's been perfecting the formula in his head for years.
I think Ozmodiar had an interesting idea. Play through the entire game and save the route, then play through that route with small deviations and if the deviations result in a faster run then keep them...
I think this is the most feasable idea. Bag of Magic (i think that's it) pointed that out also. It'd take a lot more AI knowledge to make something that could play through the entire game than I think any of us have. I wouldn't mind researching the AI more if i had the time, because AI interests me in general, but not right now.
We could go through the entire game and deviate from the original path maybe 5 frames at a time and see if it gets us closer to the goal than the previous playthrough.
It is utterly retarded to talk about programming an AI or giving button sequences some sort of fitness score or anything similar. I really wish people would shut up about it. They just sound stupid to people that have any understanding at all of the subject.
I really hope you tone that attitude down. You could have expressed your message with half the words you used for it. Half of your message was basically about you (mildly) insulting people who make you angry. It's not needed here.
But the reason I reply to your post is because I disagree with your message. It is, in fact, possible to score different attempts midway.
For example, if you know the location of the exit in the room, and you know Link's position, you can calculate the minimum number of frames required to reach that exit. It is calculateable. Measures like that might be difficult to come up reliably (so that the bot doesn't make misjudgements based on those simple formulae), but it's definitely possible.
Well, you may have noticed I "toned it down" by simply not responding to people who I deemed were not worthy of a response. I hope that is acceptable to you.
Moving on, how is such a score of any value if you haven't fulfilled the other goals of the room? (Killing all the monsters, moving a block, collecting an item, whatever.) Yes, you can make up arbitrary methods of evaluating a position in the middle of a button sequence, and it is simple to do so, but it doesn't mean such valuations will be useful in the least for finding the best path.
Taking your example, should you have reason to value a path that walks you straight to a blocked exit but does nothing to unblock it? If not, why even attempt to use distance from the exit as a method of evaluating fitness? The true distance from the exit in a room where you have to do something to unblock the exit is both temporal and linear. How much time do you need to unblock the exit from this position, and how far away from the exit will you be when you do it? I find the former part of that question to be so problematic as to make it impossible to evaluate without knowing the entire game tree.
Well, you may have noticed I "toned it down" by simply not responding to people who I deemed were not worthy of a response. I hope that is acceptable to you.
It is what you write, that I judge -- not what you decided not to write.
Taking your example, should you have reason to value a path that walks you straight to a blocked exit but does nothing to unblock it? If not, why even attempt to use distance from the exit as a method of evaluating fitness? The true distance from the exit in a room where you have to do something to unblock the exit is both temporal and linear. How much time do you need to unblock the exit from this position, and how far away from the exit will you be when you do it? I find the former part of that question to be so problematic as to make it impossible to evaluate without knowing the entire game tree.
At the risk of getting flamed, I'll field a response. Your argument makes sense (even though I don't know what all the words mean), but I think it's less complicated than you make it out to be. As far as I can tell, you're saying that it's too difficult/time-consuming/impractical to create a program that's smart enough to decide what the fastest route through a room is when there are multiple tasks to accomplish (like killing every monster, pushing a block, getting a key, etc.). Bear in mind that I'm no programmer (or at least not a very experienced one), but what if you treated each room as a series of tasks, instead of just one? For example, suppose Link enters a room where he has to kill everything, and then push a block to open the door so that he can proceed to the next room. Instead of treating the room as one task, treat it as a series of smaller tasks. For instance, the first task might be to kill everything as quickly as possible. The second task might to be to push the block, and the third task might be to go through the now-opened door. I'm not entirely sure, but I don't think it would be all that complicated to figure out the fastest way to kill everything so that after the last enemy was killed, Link would end up nearest to the block. The way you were describing it, it sounded like Bisqbot would only be trying to accomplish the fastest way to get to the door, which would obviously not entail Link killing anything or accomplishing any other task that would open the door. If you set restrictions like "kill all enemies before pushing block" and "push block before going through door," it might make things easier to deal with. Hopefully that made sense.
..but he also thinks "push the 'B' button repeatedly" and "walk into a wall" are viable strategies for some reason, instead of behaviours to be avoided (and those paths containing them to be purged immediately).
someone is out there who will like you. take off your mask so they can find you faster.
I support the new Nekketsu Kouha Kunio-kun.
Well, it's always a good idea to try actions that don't actively do anything to try to influence luck--and in the case of walking against the wall, that's still visually different from just standing against the wall, even though you're not getting anywhere..
put yourself in my rocketpack if that poochie is one outrageous dude
..but he also thinks "push the 'B' button repeatedly" and "walk into a wall" are viable strategies for some reason, instead of behaviours to be avoided (and those paths containing them to be purged immediately).
They are. Imagine a Patra fight. What if you press A but the sword doesn't hit the Patra. You may think it was a wasted move. But if it causes the Patra to move closer to the door, you may save more time in the end. Then people who are watching the supposedly "perfect" run will wonder why Link missed a swing, and we'll be smiling.
We have to first know what influences randomness before we can decide what to prune. Do you think we can convert it to ASM and study the code? Or is that too impractical? Just saying, if we know that pushing the B button does not affect randomness, we'll be confident when we prune it.
Wow! Even more hardcore diving in games. I like it, but I don't understand it fully. Still.. Woulden't this be a good oportunity to implant debuggers in the emulators?
Sort of the cheat finder in Zsnes?
Perhaps see code in realtime?
"The matrix has you!"
It might be a little off topic, but I made this wip for Zelda a long time ago. It only plays the third world. Since it's that long ago, it's a famtasia movie file. This is why it's probably not too good comparable with Phil's published movie, but I'm pretty sure the movie is a little faster (about 100 frames) than Phil's. I'm posting this wip since it might give some new idea's.
http://rapidshare.de/files/7322739/Baxter_zelda.fmv.html
Oh. Didn't know that. But is it used by you people than?
Or will it be any help?
Yes, it will be an extreme help in demonstrating what can/cannot affect the RNG, as well as in discovering how to let the bot evaluate a path. Learning what happens during room transition, how to see enemy health, etc would be nice. mfried above has already given many useful locations regarding bombs, health, and other stuff, but there's still a lot more work to be done. (though apparently not by xebra because whenever I mention it to him he just calls everyone an idiot and stupid and worthless and etc)
someone is out there who will like you. take off your mask so they can find you faster.
I support the new Nekketsu Kouha Kunio-kun.
Do you think with enough experimentation and data collection we could dervie the rules oh behavior for, say, darknuts? If so, would we be able to mathematically compute with given initial conditions, the fastest method of beating the room without having to resort to brute force?
It's not guaranteed to work, but it's more of a concept.
Let's say you have a board (or a room in Zelda), and your algorithm gives a numerical score of each position in the room. Call this algorithm
A(x,y), where x,y are locations of each pixel, and the return value is a 2D array of pixels, each with a score.
Now lets say your room has 4 enemies.
You make 4 copies of the room, each with 1 enemy in each room.
So you have 4 different Algorithms:
A(x1,y1), A(x2,y2), A(x3,y3), A(x4,y4)
The individual scores of each room can be ADDED together and the score for the new room.
A(x.y) = A(x1,y1) + A(x2,y2) + A(x3,y3) + A(x4,y4)....
And your final value will have a new 2D array of pixels containing scores of the optimum locations.
Think of Minesweeper, and me wanting to add another mine to a pre-determined board.
All I have to do is score the board for that 1 mine (where I want to add it), and add it to my the score of my pre-determined board (which contains some mines already), and I have a new valid minsweeper board containing all the original mines, plus that one extra I wanted to add!
That is the concept of superposition.
I would think that doing an entire room successfully is beyond the scope of Bisqbot as of current.
In a way, it definitely is: Unless I missed some development about this, Bisqbot's current state is that it must be modified to do anything at all besides the part of the game it currently plays.
But, saying that "Bisqbot can handle it" is basically saying that it is possible for us to come up with some ad-hoc formulas for generating input and deciding failure/success that will be able to reach the goal with a reasonably high probability. The question is not whether such a method can work (it is quite general, if not all-encompassingly so), but whether it will be easy enough for us to find the right formulas/algorithms. The algorithms it has used so far have been highly randomized (although still with some intelligent guesses built-in), because it's really easy to implement that way compared to almost anything else, but that doesn't mean these other possibilities being discussed are something different altogether.
One modification that should be made (if it hasn't already) is support for not starting the entire trial over when it makes a mistake. This could be considered part of the current 'framework' if you allow for input generator to remember something of previous states, but it's probably useful for it (partial restarts) to be a separate feature.
Question: Link can only turn to follow a grid with intersections at every 8(?) pixels, so is there ever any benefit to turning when not at a grid intersection? If not, or if usually not, then that information should definitely be taken advantage of to reduce the number of stupid moves considered.
Do you think with enough experimentation and data collection we could dervie the rules oh behavior for, say, darknuts? If so, would we be able to mathematically compute with given initial conditions, the fastest method of beating the room without having to resort to brute force?
If the approximation of randomness is "decent" in this game, that won't be possible. Calculating, say, an SHA1 hash is a well understood and completely deterministic process. That doesn't mean you can pick a "goal hash" and find a string that will produce it. That's kind of the point behind random processes. They are hard to predict and often impossible to reverse.
Then again, maybe the approximation of randomness is piss poor and we can exploit it to our hearts' content. But my guess is we can't.
Joined: 11/27/2004
Posts: 688
Location: WA State, USA
xebra wrote:
Then again, maybe the approximation of randomness is piss poor and we can exploit it to our hearts' content. But my guess is we can't.
I remember being able to consistantly "manipulate luck" in real time so I just walk through a room full of Wizzarobe thingies... so... the randomness generator sucks (and I think my spelling is).
Nach wrote:
I also used to wake up every morning, open my curtains, and see the twin towers. And then one day, wasn't able to anymore, I'll never forget that.
I remember being able to consistantly "manipulate luck" in real time so I just walk through a room full of Wizzarobe thingies... so... the randomness generator sucks (and I think my spelling is).
Isn't that just you getting lucky? Or, possibly it's not all that lucky and in fact quite likely to happen. The random generator doesn't have to suck for either of those to be the case. Unless you were counting steps or timing (or something like that) and using that as a reference to make the Wizzrobes behave a certain way, which I doubt.
edit/note: BTW, I think this whole idea (of this thread's original topic) is possible, but not worth the effort that would be required for the results it would get compared to what people can already do with this game.
I remember being able to consistantly "manipulate luck" in real time so I just walk through a room full of Wizzarobe thingies... so... the randomness generator sucks (and I think my spelling is).
Isn't that just you getting lucky? Or, possibly it's not all that lucky and in fact quite likely to happen. The random generator doesn't have to suck for either of those to be the case. Unless you were counting steps or timing (or something like that) and using that as a reference to make the Wizzrobes behave a certain way, which I doubt.
I think he was just saying that the Wizzrobes seem to act in a predictable way, so their randomness isn't really that "random," which is why he could manipulate them so easily. Or something.
I remember being able to consistantly "manipulate luck" in real time so I just walk through a room full of Wizzarobe thingies... so... the randomness generator sucks (and I think my spelling is).
Isn't that just you getting lucky? Or, possibly it's not all that lucky and in fact quite likely to happen. The random generator doesn't have to suck for either of those to be the case. Unless you were counting steps or timing (or something like that) and using that as a reference to make the Wizzrobes behave a certain way, which I doubt.
Even more likely, I suspect, is he was just dodging them. Even if you don't know when a wizzrobe is going to teleport, or where to, once it actually does they are not difficult to dodge.
