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.
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.
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.
JXQ:
I just hate reading meaningless garbage in a forum I usually enjoy, what can I say. And lots of people are spouting a LOT of meaningless garbage. For example, there is no way to evaluate the fitness of a strategy beyond "did you do something irrevocably bad, oops!" or "did you already spend longer than a human, oops!". Period. It simply cannot be done. How can you say midway into a sequence that getting hit or walking into a wall or walking away from your ultimate target are inherently worse than not doing these things? How can you say midway into a sequence that getting rupies or bombs is inherently better than not getting rupies or bombs? The POINT of BisqBot is to try to get really lucky in situations that are chaotic and unpredictable. Chess is not chaotic and unpredictable. Drops in Rockman, based on pseudorandom factors as they are, are. Behavior of monsters and drops in Zelda, based on pseudo random factors as they are, are. 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.
DrJones:
None of what you are saying makes any sense. I'm so tired of arguing with people that insist on talking about things they simply don't understand. I won't bother to refute your latest post, I tire of it, and Nitsuja already tried to reason with you, and you ingored him completely. But it's painfully clear from all of your babble that you have absolutely no clue what you are talking about.
Expressing your opinion is wonderful, but do you actually have any programming experience or training, like Nitsuja? I program for a living, but it's just higher level BS web applications, so when Nitsuja talks about programming, I listen carefully and respect his opinions more than my own misguided preconceptions. You would do well to do likewise.
Do you actually have any experience or training with algorithms, computational methods, or numerical analysis, like I do? I am not the end all be all in this field, but it was my specialization in college. Even after all my training I still make mistakes, sometimes simple, sometimes complex, so when my peers tell me that what I am saying does not make sense, and ask me to critically examine my ideas, I listen. You would do well to do likewise.
We are talking about two completely different things. You are talking about randomly picking inputs based on some heuristics. I am talking about generating all possible inputs, then pruning them based on some heuristics and randomising the order. Your way allows for both holes in the searchspace and repeated computation. And by not understanding what I'm talking about and assuming I'm talking about your way you are intentionally misinterpreting what I say. Please stop.
But what you now claim is "your way" is impossible, as has been mentioned a few times. There is no way to generate all valid/useful inputs. The number of possible button sequences is too vast for what you are claiming to be talking about to make any sense in the least. So, forgive me for assuming what you say isn't nonsense, when that is, in fact, all it turns out to be.
We can even take "useful" further. By knowing how far Link walks for each frame held of each direction we can calculate from an input sequence where he is (ignoring damage etc). We can then prune things like "leave the room immediately" and "walk into a wall" etc. LOTS of things can and should be pruned BEFORE trying them, and even during trials many sequences should be discarded before the alloted time is done.
Until we know which things do and do not affect randomness, I think it is useless to make these kinds of generalizations. Maybe walking into a wall could affect randomness. Maybe it does not, but maybe the fact that you resumed motion in whichever direction you were originally going 1 frame late could affect randomness. Regardless, obviously "bad" outcomes don't need to be pruned, they will either never be generated, or will be terminated as soon as an obviously bad outcome is reached. In either case, there is no magical preprocessing and pruning of a game tree.
but as far as I can tell you're both taking that into account already.
Well, to be sure, I'm not actually taking anything into account, since I'm just theorycrafting all day, and suspect he is doing the same. Hopefully, on some far removed day in a far removed galaxy, someone with the programming expertise to do something more than talk will do something more than talk. Until that day, let the blustering continue!
Boco wrote:
Should we allow sequences that press 'B' more than once?
Because the input generator is exhaustively listing all legal, useful inputs.
It sure would be nice if this was possible, but, gee, I don't think you'll know if an input sequence is useful until you try it out. Or isn't that the point?
Boco wrote:
But if it were some random subset, the randomness should still be done on a central server sending out chunks for processing to ensure no single combination is checked twice.
You may as well ask your friend what lottery numbers he is playing just in case you guys randomly pick the same six numbers.
I don't understand why you think eliminating invalid key combinations is a bad idea. It only needs to be done once for the game, regardless of how many different rooms you want to optimize, and the amount of processing time it would save I would think offsets the extra coding needed.
Why allow your input generating algorithm to create invalid key combinations in the first place? There should be nothing to prune. Some people seem to be imagining there is a way to enumerate all possible key combinations, then process them for legality, and then cast a magic spell and create a TAS. All of those propositions are equally possible, as in, not at all. All I am proposing is to allow BisqBot to do inhumanly fast random testing for us in short sequences where we would be doing random testing by hand, anyways.
JXQ wrote:
I also don't understand why you seem to have such an attitude toward people on this board who don't agree with your ideas. Everyone should be able to ask questions and give input without worrying about if you are going to jump down their throats.
Because people keep saying retarded things even after having been offered numerous reasonable responses. I say retarded stuff all the time, as well, but I'm pretty sure when I make stupid mistakes I mostly say, "Oops, that was a moronic thing to say!" and shut the Hell up.
The trick is to prune things early and often, like the above discussion said - that is, NOT brute force.
I think the trick is not to prune at all but to just do what BisqBot does ... try lots of random paths for relatively short sequences! You guys need to stop taking this thread off topic, if you want to argue about random bullshit no one really knows about anyways, there is a thread for that.
You need to keep in mind that a pure brute force method is not ever feasible. Each frame has like 2^#of buttons possibilities, and you multiply for each frame. So for 5 buttons used, and a 30 second time cap the possibilities would be (2^5)^(30*60)=~ 1.86*10^2709. This shows that an exaustive search for a whole game is impossible, but for short segments and specific goals, it is possible. The problem is that the bot often must know what is coming up to see the value in a specific set of moves, but this is not possible. I doubt that a bot will ever do a whole run unless there is some way to implement lots of check points. I guess a quantum computer with a few kiloqubits might be able to do it in the futere, I dont know.
Somehow you missed the entire point, and then proceeded to babble on about irrelevant statistics no one cares about. It is possible to "implement lots of check points" as the ENTIRE game can be broken up into more or less disjoint ~3s long action sequences separated by room changes. Given what Bisqwit has already accomplished with Rockman, it is not difficult to see how you could use BisqBot to build a very nearly perfect Zelda movie, one room at a time.
I remember playing this a few times at a friend's house, but it was really long and repetitive. And it was long enough and repetitive enough that I never bothered to beat it. I'm not sure if it would be fun to watch a TAS.
Plus, after watching the Zelda 1 movie, I don't think Bisqbot is going to make enough of an improvement to go through the trouble of organizing a big network of continually-updated random-searching optimizing source code.
I think you're being needlessly pessimistic. BisqBot drastically improved the sequences it played in Rockman. I would be very surprised if it wasn't possible to cut the length of all the fighting sequences in Zelda 1 by 20% at the very least.
The idea behind using a bot for Zelda 1 is not to do anything so mundane as manipulate drops. The point is to optimize the hundreds of short fighting sequences.
This is talking about having a computer make all or most of an entire run, rather than using a computer to find the best sequence to manipulate luck in a single instance.
No sir, I don't like it.
The point is that Zelda is made up almost exclusively of hundreds of "single instances."
I surmise that a true SETI@Home like approach would require you to enumerate, somehow, all to-be-tested sequences of button presses, which I don't think is a feasible task. I did not examine Bisqwit's code for his MM1 branded BisqBot, but I have the sneaking suspicion there was a random component in the generation of button sequences.
As such, a more likely scenario for a group approach is this:
- We all have a copy of the TAS current up to the latest "official progress"
- We all run BisqBot configured to look for the same goal
- After some amount of time, we all report on the shortest sequence we could find, and we use the shortest valid sequence to update the official TAS, and redistribute the TAS
- One of the coders updates BisqBot with a new configuration for the next goal, and BisqBot is redistributed
- Rinse and repeat
This isn't as super fancy as some of you are envisioning, but it has the added advantage of being pretty simple, provided someone can work out appropriate configurations for BisqBot to achieve specific goals in Zelda.
Another interesting thing that could be done with a distributed approach is to try out many different button sequence generating algorithms. Over the course of completing the game, we would amass a large amount of data concerning the efficacy of various algorithms that might help give the coders an intuition about which methods are most effective in which circumstances, and perhaps, why.
No matter what, BisqBotting almost all of Zelda 1 (even if only in small chunks at a time) will be a huge undertaking for the coders, and, if a distributed approach is adopted, will obviously require an unprecedented amount of organization and cooperation amongst all of us. But I feel in my heart it is something that must be done, and I know it is within our grasp. Zelda 1 is not only hugely popular, but seems the perfect game to smash into oblivion with BisqBot. A TAS so constructed has the potential to be the magnum opus of our entire community.
It seems likely that BisqBot in an appropriately modified form is suitable for optimizing almost all of Zelda 1 due to the highly compartmentalized nature of the game. Sure, all of Phil's sequences look great, but so did most of Bisqwit's play in MM1 until Bisqwit showed us the true potential of bot-powered searches.
It will be a whole lot of work, but I request that Bisqwit -- or someone capable of appropriating, modifying, and competently using his code -- do a complete remake of the Zelda 1 run.
