What BisqBot did:
1. Find the fastest way to get a weapon refilll (or two or three) when I want them. It was able to get most of my 120 frame results down into about 40 frames. This was entirely luck-against-luck. BisqBot's advantage over me was that he's faster in testing different attempts, and he's tireless.
2. Optimize the battle of Wily3 (bubble machines). The collision checks of the thrown bricks are very vague (the bricks seem to consist 90% of air), and it's hard to make them hit the instant the robot appears. There was about 4-10 frames of room of improvement in each of my hits; as result, BisqBot made the battle about 60 frames faster than it would have been. Again, luck against luck, and again, BisqBot's advantage over me was that he's faster in testing different attempts, and he's tireless.
BisqBot played about 8 seconds of the movie in total, saving about 3 seconds in total. Maybe even 5.
I'd hate there to be two similair projects in existance. No reason to tred water against one another. I have created a pretty flexable frame work intended on reading emulator's memory. It also has coded support to support bots, it's just that the key commands are empty, due to not having a valid way to comunicate. If you want an example, though very immature, look at the Tetris class in GameGeneric.cs.
One of the main things my approach lacks is being able to hook an instruction address. Aside from that, it seemlessly switches between games and emulators, and should have enough features on the programmers and users end of it all.
http://www.red-stars.net/EmuRead/EmuRead-110205.rarhttp://www.red-stars.net/content/EmuRead
i know C++, Java and C, haven't done much with emulation, but I'd be willing to help out with something like this. I'm not that experienced with C++, but I'm using it at work so I'm learning new things all the time. I'm sure you've looked into it, but I'd suggest Python for the scripting language. From what I've heard it's a great language.
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.
The idea is to program some basic knowledge of the game into it. Don't walk against walls. Don't visit rooms you've already visited unless you first accomplish some goal. Don't die. If you attack and miss, reject it. If you attack, don't attack again for a mimimum delay. Tend to move in straight lines for at many frames at a time and never immediately go backwards.
Yes, it's exhaustive, but you should be able to weed out bad decisions pretty fast. Combine with a preplanned target route (by rooms) with time restrictions and you should be able to figure something out.
To be more useful, you'd probably only ever press "go" inside a room full of baddies who need to have their butts kicked while Link still finds himself going out the door in record time.
After thinking about this... we could search the entire game space distributedly if we did it right, and it wouldn't be overly overly hard. I guess the hardest part would be testing it? Maybe not even?
Generating the entire tree for an entire game... you have what... 8 buttons and the possibility of not hitting anything, so 9 moves each frame. (I'm thinking brute force here)
with 9 possibilities, you could encode that to characters ABCDEFGHI... then have a user start with A, and they do it recursively, all at the same time, because the way i see it that seems the easiest to code up... you can do a depth of 10 in about 5 minutes (i've done some stuff similar to this before in Java... so C++ would prolly be faster, but 5 minutes seems fair)
Then you have every possibility for those 10 frames from the starting position they are given. It wouldn't be that hard to send around the data between a group of people. Getting a server might not even be out of the question. Just have to set up some mechanism for pruning. Since the human zelda movie is around 30 minutes, we could probably test at a certain point to see if a piece of the triforce is obtained and anything that doesn't get it would just return false. There might be a better way, I'm just going from the top of my head right now, but seems resonable. We could even make tester and generater nodes. Some nodes just for testing, and some just for generating. seperate programs... Could set up a database on the web to give out info to process, not entirely that hard.
Generating the entire tree for an entire game... you have what... 8 buttons and the possibility of not hitting anything, so 9 moves each frame. (I'm thinking brute force here)
Unless I'm misunderstanding how you mean "moves", there are more than 8 possible in a given frame, there are 2^8 = 256, since you can press more than one button on a given frame.
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
Dehacked.. you posted while I was writing my last post, let me respond... yea that's a good idea. I was thinking more brute force algorithm. If you put the route in, and some basic training, you could just let it play every room. After it gets through each room the fastest, you move onto the next... If it can run on linux, I have a pc i can dedicate to it. It's not overly fast though.
I'm not really up to date on how to manipulate zelda. Do your actions in previous rooms affect what happens in later rooms?
We could make a bunch of savestates as you enter each room to and make it distributed that way... Could record a movie and make some way of finding where the next room needed to be processed is.... that's prolly easier on us...
qbproger,
Please check your math. It may help to read the discussion about Super Mario Bros. located here.
The problem is in the exponent. Distributed or parallel computing will only let us cut out multiples, not exponents. The trick is to prune things early and often, like the above discussion said - that is, NOT brute force.
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.
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.
You're not going to use every button all at once; there are some basic restrictions. If you call up the menu, you do it to do something specific, plus you wait for the menu to come up. You're not going to press Left/Right or Up/Down at the same time (there are no bugs relating to this, are there?). You're kinda stuck for a frame when attacking. There's nothing to do during a screen transition.
So if you want to do this, figure out some heuristics and plan a route. Determine a means of calculating progress and we'll let `em have it. A screenful at a time? A room at a time? Pre-planned route or let the bot roam dungeons freely?
Boco, I wasn't thinking of ways to interface with the rom at the time, what dehacked said makes a lot of sense. The whole multiple buttons at the same time really messes my previous theory up too... so how about no more comments on that. lol.
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.
I think the best play will result in the bot having a strict time limit (per room) and a strict set of goals (will collecting money/bombs be needed? will it have access to bombs/arrows, and how many? etc), doing one room at a time, and knowing enough about the game to not do useless inputs. All menu access should be done manually at strict points, the route and all item drops will be predetermined.
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.
To clarify, i wasnt complaining about the idea, but destroying any hope that this will make speed runs easier. It will certainly make them less tedious. I know that an exhaustive button mashing was never intended.
It's not that I am pessimist but I don't see how Bisqbot can be so much faster except if he uses a different route (or force brute from start to end which will take several years for one pc).
When I see commentaries such as Bisqbot can do 20% faster fights let me laugh out loud. There's probably some improvements possible here and there but not that much.
And using a bot is kinda lame. Even if you would have the source code, the video will be imperfect. It could be beaten by some movies that contains glitches. Because as far as I know, programmers don't intentionally add glitches in games.
Doing LoZ is not as simple as doing room by room. Sometimes, you do an action 3 rooms ago and it affects the randomness in the current room.
You obviously didn't see bisqbot play SMB1 then. Watching it save its ass on 1-3 at the flagpole approach gave me a chuckle. Who knows what an incompetent player with a goal is capable of.
Hell no. It got caught on all kinds of obstacles.
But it does know how to walljump (more specifically, it gets lucky quite often). It's like watching an inhuman baby playing.
Zelda is a different genre. There are easier and more localized goals to aim for. Maybe it won't be so bad.
Xebra: Doing a room as quickly as possible doesn't mean that the randomness will be better.
DeHackEd: In the end, if the final results isn't as good as it should be, don't be surprised.
When I started LoZ, it was more complicated than I thought. This game isn't like it looks to be.
Though, Bisqbot could probably help at some places but not the entire game.
Unless you just wanted a bot doing a movie and doesn't care if it's perfect or not then I misunderstood. Probably because some people think it will beat the current run.
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.
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.
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.
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
I think if the AI is good enough it would be capable of making a better TAS than any human in any game. Just program in all the knowledge that a person has, and when you combined that with it going faster then it's a better TAS maker in every way. The only problem is that programming it well enough would be extremely hard.
