Maybe. But anyway, Wizzrobes, or even Darknuts for that matter, aren't completely random, since the orange Wizzrobes will always end up either in line or perpendicular to Link (if I recall correctly). And the Darknuts (the blue ones more so) turn towards you when you try to hit them, to a certain extent. So there is a method to their madness, and it's not all pure randomness determining their paths.
We would also need to know: the blast radius of a bomb, the enemy dynamics upon being hit, the velocity of Link's sword, and the range of pixels each enemy can be hit upon for them to take damage.
Maybe doing all of this math would be harder then doing a brute force with pruning.
Maybe. But anyway, Wizzrobes, or even Darknuts for that matter, aren't completely random, since the orange Wizzrobes will always end up either in line or perpendicular to Link (if I recall correctly). And the Darknuts (the blue ones more so) turn towards you when you try to hit them, to a certain extent. So there is a method to their madness, and it's not all pure randomness determining their paths.
Well, in fact, their paths aren't random at all. Unfortunately, that doesn't necessarily mean we can predict or influence things in the game to any great extent, which would be the goal of a non-random bot. (For example, lay a bomb, press the magic sequence of buttons that causes all monsters to converge on the bomb.)
yea, I doubt a pruning algorithm could become good enough to be feasable. This has been gone over before, but the number of button combinations at every frame is too great for it to be done using brute force. Even with a pruning algorithm, I doubt any algorithm would be able to recognize a bad path quickly enough to make the brute force workable. I may be wrong (someone is welcome to prove me wrong), but that seems to be the concensus.
Joined: 6/20/2004
Posts: 292
Location: United Kingdom
Does anyone have a link to a website with the memory address of things like "link gets damage", "link dies", "link falls down a hole" etc.? I've got an idea I want to test out.
For all 3 of those examples you could just check if link's health went down (some addresses of things like health/weapons/position were already posted on the first page of this thread... EDIT: and a link to them is also posted by Hoe in the very next message of this thread). To actually detect when they happen and which one of them happened you'd probably need to monitor the PC register and know what code corresponds with those effects, but depending on your idea that might not be necessary.
Does anyone have a link to a website with the memory address of things like "link gets damage", "link dies", "link falls down a hole" etc.? I've got an idea I want to test out.
This is a little off-topic for Zelda, but I've been thinking about a very simple game that might benefit from Bisqbot. Bisqwit had mentioned in the Monopoly thread how difficult it would be to process a 30-second video with the wide range of input options.
How hard would it be, if there were only six different possible inputs? "Up, Up/left, Up/right, Up and A, Up/Left and A, Up/Right and A" for instance.
This is a little off-topic for Zelda, but I've been thinking about a very simple game that might benefit from Bisqbot. Bisqwit had mentioned in the Monopoly thread how difficult it would be to process a 30-second video with the wide range of input options.
How hard would it be, if there were only six different possible inputs? "Up, Up/left, Up/right, Up and A, Up/Left and A, Up/Right and A" for instance.
six raised to the 1800th power (30*60).
It equals,
47016542686193066036546774025438736748006028881169178326657860657238\
87494617879657960610186220482585683660667088914422525960491257996573\
89797439424676647004746709977759829838686292911452094937698092400318\
60574183316115554391365035887912380359718078325007327095508386825892\
67390129755505392089485810383413636683578078308323961605492552333698\
07234526994563639826353686569705364520517332510311310666960180979946\
88535747079541375319681633296229775801854333316284453647504976414603\
18433497609100802832289778218429787181917151490714022806072143945339\
53740985356611109892282192056552249074160623097023676942290488771475\
49281351712038388974919743769396025918404127056058899859454070495113\
94587810726962249892590312318910748416221721733959268105628880383474\
12181005657489221681464741679020002050845667151246745306147908604844\
52713470099606620647689944212004906416527396960952227190727037313186\
69538429355250902438458170026091320317517168027796282721442468974316\
68065081798719636971915687114059218173342084445314334003643863200471\
55884546929428980421306002535474856531247054573779753251193018153910\
49635959647163792792098373253938791979726613816344941449566752887451\
37624002863431746577639926195819109419224107662350300973429868282413\
27477816025838975115873521378090249603279852978215018332004564483371\
60005087517374197229714668210481391353238489100085727876392441360558\
29362969677866144149816972391622037733376
different sequences.
Joined: 4/25/2004
Posts: 615
Location: The Netherlands
Nice head-math there Bis ;)
My two cents (or so). I won't repeat earlier comments about it all so just my approach to it, if I were to tackle it...
Design a path, obviously this by itself is a great challange. But this itself could already be computed! Put the entire zelda map into memory, somehow mark the areas you need to visit and the items you require for these areas. Compute the number of frames you need to move from one frame to another for all general ways (this can pose as a model for most rooms). Compute paths and take the one with the least frames.
The next part requires some manual inputs because I don't think it's really feasible to build a bot that can do something like going to the inventory and switch to an item when you need it to. In other area's, there sometimes is just a straightforward fastest route (walking forward without hitting anything or turning or pausing anywhere to go from left to right is obviously as fast as possible) and no computation is required. I actually think this goes for most of the non-dungeon "mini-instants", as someone called it (I think this is a good term actually).
The computation comes into play with the dungeon instants where you need to clear the room to move on. Here you can let the bot compute away, using the random approach to cover most of the "tree" (you don't really have to brute force things to find a local minimum you know) and perhaps looking a little bit closer at the best local minimum, if desired.
In any case, for luck manipulative purposes, compute a room, remember the best x (5 or 10) results and move on. Compute the next room for each of the x remembered results, and remember the best y results (where x == y). Repeat for as long as you can.
The problem may arise in money. Perhaps the gambling cave can help here (possibly brute forcing that part to manipulate luck since the number of paths are slim, buttons are pressed to influence luck and there's only one "highest" price. When the highest price is gotten you can continue, accepting the loss of frames, to manipulate luck, is acceptable here I think.) Alternatively you can accept the loss of frames to kill and take the loot but this complicates things highly, using the cave may be far more easy...
Anyways, bla. The last real post was almost a year ago. The link Hoe posted is dead (looked interesting...). Was anyone having any progress in this project at all? Did anyone even try? What were the results?
Heh. Okay, Bisqwit. Since you like figuring this stuff out so much:
Obviously it would take so long as to be completely infeasible (your other post in the Monopoly thread said it would take millions of years, and that was conservative, and this looks like it's pretty well impossible as well) but how much space would it take up to have that many 1800 frame videos saved on your harddrive?
Joined: 6/20/2004
Posts: 292
Location: United Kingdom
Couldn't you do something like create a file with all possible combinations (yeah i know, it would be HUGE) and then go through the list in sequential order. If there is an input which causes a premature failure (damage, death etc.), all the possible inputs with that at the beginning could be deleted (crossing off a large amount of possibilities). If a failure after all frames have been input (out of time) then just delete it. If a victory is achieved, it deletes all values that use more frames and the same input (and put it in a victory file or something with a frame count). I know it would be a huge file, but surely it would cut out on a lot of possibilities and trying the same ones again.
This was what I was going to try but I got a bit busy and forgot about it, and i didn't know much of the language at the time (can't remember the name at the moment, lol, was it C++?) especially I/O with files, although it could be done with multi-dimensional arrays. I'm getting good at handling data without I/O (unless you include Microsoft SQL databases and Lotus Notes) in Visual C++ .NET, but I'm almost certain the methods I'm using are .NET only so that wouldn't help too much...
Ok, that probably doesn't make much sense since i'm half asleep but if you're confused by it I'll rewrite it when I'm awake. I know it's a complete redesign of the bisqbot engine but it may work... oh, and if you ever do a TAS@home thing, I'll have my computer on 24/7.
Joined: 4/25/2004
Posts: 615
Location: The Netherlands
That's the whole point of pruning really (without preprocessing). It would be easier to have 1800 save-states and use a recursive tree climbing algorithm, pruning all the brances once a sollution/bad result has been determined. This will prohibit the code from computing a lot of duplicate inputs.
