Probably because some people think it will beat the current run.
If it works at all, it will beat the current run - it can easily be programmed to not accept results that are slower. You're right that we can't be sure it's perfect when all the possibilities aren't being checked, but we can at least make sure it'll be closer to perfect than before. (If it just can't find anything fast enough for a segment then that segment won't be played by it, but a lot of rooms are probably short enough for it to succeed.)
Phil wrote:
Doing a room as quickly as possible doesn't mean that the randomness will be better.
Usually if you do the previous room more quickly that means you have more chances for manipulating luck later (there might be some good luck that you couldn't get before because of being even a few frames slower before). Unless the luck is predetermined by how the last room ended - I don't think this game does that, but even if it did, there are ways of working around it.
Michael Fried wrote:
Just program in all the knowledge that a person has, and...
Now there's an optimistic statement, even in this context... (Although there is the disclaimer that it would be extremely hard)
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.
I don't understand why you think eliminating invalid key combinations is a bad idea.
Why allow your input generating algorithm to create invalid key combinations in the first place?
Because the input generator is exhaustively listing all legal, useful inputs. Not some random subset.
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.
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.
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.
Why allow your input generating algorithm to create invalid key combinations in the first place? There should be nothing to prune.
That is exactly how I read Boco's original statement. I don't think "prune" was used literally to mean that the entire tree is generated and pruned; it was in the context of random tries already, so it seemed to simply mean that you shouldn't generate invalid (or unuseful) input, as a means of cutting down on the amount of possibilities. What is useful input in one part of the game may not be useful in another part, though, so that's why a little extra logic added to the input generation would save a lot of computing time... but as far as I can tell you're both taking that into account already.
edit: Just saw the last posts... maybe I misread that after all. I can't tell, but I assumed it was on-topic.
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?
You are in a room. You are fighting. You have 1 bomb. Should we allow sequences that press 'B' more than once?
Same situation. Note that pressing 'A' freezes you in place for some number of frames. Should we allow sequences that press 'A' while pressing any other button, etc?
Many many many of these can be enumerated and used to prune the possible inputs. That is what I meant by "legal and useful".
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.
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?
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.
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.
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.
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.
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.
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.
Your way allows for both holes in the searchspace and repeated computation.
The former is not a disadvantage, because the holes only exist in what you don't have time to compute anyway. Repeated computation is a disadvantage, but not a big one at all because the whole problem is that there are lots of possibilities, and when there are lots of possibilities the chance of repeating one is small. (If it is a problem, it could be reduced by remembering previous attempts in some way, but I suspect that would add more overhead than the time it saves.)
xebra wrote:
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.
I think Bisqbot is already nearly sufficient for doing a concept test of a room or two. It's not so far off. All this talk about making it distributed and scripted and automated to go through the entire game perfectly once it's planned out and set up... I think that is the far-off part of it, and unnecessary at that, although it would surely be neat if it happens. (note: That was probably your point - this response is not directed at you.)
xebra wrote:
Until we know which things do and do not affect randomness.
Isn't this pretty easy to test beforehand? Even without looking at the game's random generator function (which can be done) it's possible to be reasonably sure whether it affects the randomness. However, in this case it's probably not worth it to add the restriction either way, because if pressing B more times doesn't do anything besides possibly affecting randomness, then doing so can't make things worse. (Which agrees with what you proposed before, in this one case.)
Until we know which things do and do not affect randomness.
Isn't this pretty easy to test beforehand? Even without looking at the game's random generator function (which can be done) it's possible to be reasonably sure whether it affects the randomness. However, in this case it's probably not worth it to add the restriction either way, because if pressing B more times doesn't do anything besides possibly affecting randomness, then doing so can't make things worse. (Which agrees with what you proposed before, in this one case.)
It can "make things worse" in the sense that allowing it greatly increases the range of possible input, which means you'll take longer to find a solution because you'll try things that evaluate the same many many times.
(oh, I lost what I was going to say. anyway it was something like 10 frames input is 3 GB with no restriction, and just adding a 0-or-1 B button press restriction makes it only 3 MB instead, etc., 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.
It can "make things worse" in the sense that allowing it greatly increases the range of possible input, which means you'll take longer to find a solution because you'll try things that evaluate the same many many times.
Only in your scheme will it take longer to find a solution.
If the attempts are random (i.e. what Bisqbot does) then it won't take any longer. You could even add 1000 extra buttons that don't do anything and let it press them at random, and it still would barely affect the computation time.
Who cares how many combinations there are? Let's just build a huge computer that's a quintillion times faster than a normal computer and it'll make all these problems insignificant!
Quintillion is only 18 orders of magnitude. If we are talking about ONLY the LAST part of the LAST level in SMB that's like 300 orders of magnitude. You'll need to do a bit better than that.
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.
300? Wtf? *gets out calculator*
Let's see, 4 buttons you have to worry about it, how long is it, 5 seconds or so? Dammit, quintillion is much too small. Ok, let's build a computer that's a google plex times faster than normal, that should do the trick! :)
Edit: Oops, it's only 3 buttons you have to worry about since you're always pressing B. *presses some numbers on a calcultor* Still too much. :(
People taking into account the number of buttons should consider that waiting is an acceptable movement, too. Action buttons can be pushed while in motion, too.
Heuristics are useful, but they take up time and could be useless or worse than that. Even something as simple as "don't death" would remove shortcuts from many games, and would stop the bot from beating Prince of Persia 2 (except in some versions, in which you can glitch the game to the end)
Boco's suggestion of using a pruning method makes sense. Maybe Xebra hasn't understood that you don't generate all valid/possible inputs that way. Instead, you look at the possible start from all sequence inputs (a "small" number), and decide whether they are good starts, or not. Then, you continue exploring just the good ones.
This method has very serious disadvantages, still, but I'll talk more about it in my next post.
Finally, I think the best game for bot-testing purposes should be one like Deja Vu.
The efficiency of Bisqbot is measured in frames. That's it, the fewer frames used for achieving a certain goal, the better. If there's a known input that achieves the goal, and Bisqbot finds a faster one, then it's said that Bisqbot has found a timesaver (I love making up terminology).
I've identified three levels for Timesavers:
1. Those that come as a result of a Strategic decision. By strategy, I mean choosing the goals to accomplish, and the order in which they will be achieved.
2. Those that come as a result of a Tactic decision. By Tactics, I mean choosing the path/method that will be used to achieve each goal.
3. Those that come as a result of Improved Skill. By Skill, I mean how well each path/method is accomplished.
Changes at an higher level have more weight on the result. A change of strategy will usually look unpredictable working from a lower level. A small delay at the start may cause an huge timesaver much much later. (This would rend useless boco's idea)
However, changes at a lower level have a lot less impact. I can figure that a change of gameplay to achieve a simple goal (such as jumping into a platform) will only repercute on, maybe, just the next X frames.
We could use then ramification & pruning, if we looked ahead X frames before "cutting branches".
I only see 2 different timesavers:
- Strategy (pretty much your first and second point, and a part of your third point)
- Luck manipulation (I guess it's a part of your third point)
I think Bisqbot is able to help a great deal on the luck manipulation part.
I only see 2 different timesavers:
- Strategy (pretty much your first and second point, and a part of your third point)
- Luck manipulation (I guess it's a part of your third point)
I think Bisqbot is able to help a great deal on the luck manipulation part.
Your way is not less correct than mine (it could be even more correct, in fact, as it englobes everything), but I think it is less appropiate for coding a bot (unless, of course, your sole purpose is having a bot that manipulates luck).
DrJones: It's a little unclear what you're suggesting and how you think it could actually be implemented. It sounds to me like it would take enormously more programming effort to get anything. Sure, better search algorithms than pure randomness can (and possibly should) be used. But this talk about playing more than small segments and actually affecting the strategy... unless you have some damned amazing AI planned, that is quite impossible for a game like this, especially if you want it to be able to handle other games like this without being completely remade. Maybe a pruning method makes sense, but it has to be incredibly good pruning to reduce the computation time enough. So far nobody has come close to suggesting what that pruning method might be, probably because it's very difficult to figure out.
Bisqbot (after being modified with some much-easier-to-figure-out heuristics) can already handle improving both tactics and skill within a practical timeframe, and the high-level strategy has already been optimized independently of the low-level playing by some humans with actual intelligence. Doing even better than that might be a nice goal, but maybe we should start small and consider something that could be completed within the next 6-12 months of part of the free time of a few individuals.
DrJones wrote:
People taking into account the number of buttons should consider that waiting is an acceptable movement, too. Action buttons can be pushed while in motion, too.
Maybe you haven't read their posts carefully enough, for they are already taking these things into account by considering combinations of buttons.
So... to stay on topic: Michael Fried already posted a nice list of memory addresses. We don't have any relevant program code addresses yet, but maybe they aren't so necessary for this game. What things would Bisqbot need to be able to optimize that are not adequately covered by the addresses he listed? The thing that comes to mind right now is: How can it detect screen transitions? And do we want to try getting it to handle rooms that require pushing blocks? (If so there probably needs to be a way to detect if the secret entrance has been opened, and some support for intermediate goals of X,Y position.)
I think (completely unsupported) that so far, anything where the consequences follow logically from the actions, humans beat computers by silly margins. Conversly the only place where computers beat humans is when the consequences do not follow logically from the actions, such as in luck manipulation. A computer can try thousands of buttons combinations quickly and evaluate the results.
So I think that's where the focus should lie. We can get optimal drops of rupees and bombs and possibly better enemy placement (which would have to be evaluated by the computer trying to run trough the room in predefined paths without getting hurt or some such, or even by a human if all the enemies have to be killed).
I'll eat my words when I see a bot play a room faster than a human would. I don't think it's going to happen any time soon.
For the most part I agree, except I think that a room in Zelda 1 is not quite too long for a bot to optimize, when enough restrictions have been added. It might be long enough that the current algorithm would have to be modified (a genetic algorithm sounds good for this to me), but you can also get pretty far by changing the input generation and failure conditions. (Making it considerably more likely for it to walk in the direction it's trying to go, making it fail if it gets knocked back away from its goal position, making it fail if it's too far away from its goal position to possibly be able to reach it faster than the current run does, etc.) It would take some clever restrictions, but they aren't too hard to come up with.
DrJones: It's a little unclear what you're suggesting and how you think it could actually be implemented. It sounds to me like it would take enormously more programming effort to get anything. Sure, better search algorithms than pure randomness can (and possibly should) be used. But this talk about playing more than small segments and actually affecting the strategy... unless you have some damned amazing AI planned, that is quite impossible for a game like this, especially if you want it to be able to handle other games like this without being completely remade. Maybe a pruning method makes sense, but it has to be incredibly good pruning to reduce the computation time enough. So far nobody has come close to suggesting what that pruning method might be, probably because it's very difficult to figure out.
Bisqbot (after being modified with some much-easier-to-figure-out heuristics) can already handle improving both tactics and skill within a practical timeframe, and the high-level strategy has already been optimized independently of the low-level playing by some humans with actual intelligence. Doing even better than that might be a nice goal, but maybe we should start small and consider something that could be completed within the next 6-12 months of part of the free time of a few individuals.
Of course, I was talking about teorethical ways of implementing a bot able to play games. Splicing up the task between various levels of abstraction seems to me a better method than brute forcing, and helps us having a better understandment of the problems that may arise. For example, how a sub-optimal path lends to a better overall time later in the game could be explained because another tactic/strategy was being used.
Not all layers have to be implemented. Of course, it can have some pathfinding routines and some kind of genetical algorithms for battles (as they usually rely on few combinations that are very effective), but they can also be directed by human players.
Also, it should be noted that most of the strategic layer is predefined by each game (that's why they have to explain their rules and the goal on their manual), which makes more difficult creating a generic playing bot.
All this explanation was just to make clear that most of the work of bisqbot is directed to optimization of paths, which, as the rest of layers needed to "play a game" are given by an human player.
About the pruning:
An actual pruning method would be comparing the actual path with other path obtained by an human player. I have said that I think that, if all paths use the same tactic and strategy, we can consider that a path which creates a small delay that it's not corrected within X frames is just bad and can be pruned.
The main problem I have found, is that it is very hard for bots to "see" what's happening in the game, and detecting if they have reach the goal, and such.
I have an heuristic idea. Collisions are very interesting. I think that having a short memory (2-3 seconds) of positions in which collisions happened, and if they were good (i.e.powerups), or bad (i.e. walls or shoots) would help the bot avoiding the bad ones.
Some collisions can be detected because the input didn't affect the outcome (i.e. walking against a wall), or because it changed the state of the player (i.e. life meter drops). As many collisions are produced by not static elements, the memory shouldn't last too much time.
